1 /* 2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #include "precompiled.hpp" 26 #include "libadt/vectset.hpp" 27 #include "memory/allocation.inline.hpp" 28 29 // Vector Sets - An Abstract Data Type 30 31 // BitsInByte is a lookup table which tells the number of bits that 32 // are in the looked-up number. It is very useful in VectorSet_Size. 33 34 uint8_t bitsInByte[256] = { 35 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 36 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 37 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 38 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 39 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 40 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 41 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 42 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 43 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 44 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 45 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 46 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 47 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 48 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 49 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 50 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 51 }; 52 53 //------------------------------VectorSet-------------------------------------- 54 // Create a new, empty Set. 55 VectorSet::VectorSet(Arena *arena) : Set(arena) { 56 size = 2; // Small initial size 57 data = (uint32_t *)_set_arena->Amalloc(size*sizeof(uint32_t)); 58 data[0] = 0; // No elements 59 data[1] = 0; 60 } 61 62 //------------------------------Construct-------------------------------------- 63 Set &VectorSet_Construct(Arena *arena) 64 { 65 return *(new VectorSet(arena)); 66 } 67 68 //------------------------------operator=-------------------------------------- 69 Set &VectorSet::operator = (const Set &set) 70 { 71 if( &set == this ) return *this; 72 FREE_FAST(data); 73 // The cast is a virtual function that checks that "set" is a VectorSet. 74 slamin(*(set.asVectorSet())); 75 return *this; 76 } 77 78 //------------------------------slamin----------------------------------------- 79 // Initialize one set with another. No regard is made to the existing Set. 80 void VectorSet::slamin(const VectorSet& s) 81 { 82 size = s.size; // Use new size 83 data = (uint32_t*)s._set_arena->Amalloc(size*sizeof(uint32_t)); // Make array of required size 84 memcpy( data, s.data, size*sizeof(uint32_t) ); // Fill the array 85 } 86 87 //------------------------------grow------------------------------------------- 88 // Expand the existing set to a bigger size 89 void VectorSet::grow( uint newsize ) 90 { 91 newsize = (newsize+31) >> 5; // Convert to longwords 92 uint x = size; 93 while( x < newsize ) x <<= 1; 94 data = (uint32_t *)_set_arena->Arealloc(data, size*sizeof(uint32_t), x*sizeof(uint32_t)); 95 memset((char *)(data + size), 0, (x - size)*sizeof(uint32_t)); 96 size = x; 97 } 98 99 //------------------------------operator<<=------------------------------------ 100 // Insert a member into an existing Set. 101 Set &VectorSet::operator <<= (uint elem) 102 { 103 register uint word = elem >> 5; // Get the longword offset 104 register uint32_t mask = 1L << (elem & 31); // Get bit mask 105 106 if( word >= size ) // Need to grow set? 107 grow(elem+1); // Then grow it 108 data[word] |= mask; // Set new bit 109 return *this; 110 } 111 112 //------------------------------operator>>=------------------------------------ 113 // Delete a member from an existing Set. 114 Set &VectorSet::operator >>= (uint elem) 115 { 116 register uint word = elem >> 5; // Get the longword offset 117 if( word >= size ) // Beyond the last? 118 return *this; // Then it's clear & return clear 119 register uint32_t mask = 1L << (elem & 31); // Get bit mask 120 data[word] &= ~mask; // Clear bit 121 return *this; 122 } 123 124 //------------------------------operator&=------------------------------------- 125 // Intersect one set into another. 126 VectorSet &VectorSet::operator &= (const VectorSet &s) 127 { 128 // NOTE: The intersection is never any larger than the smallest set. 129 if( s.size < size ) size = s.size; // Get smaller size 130 register uint32_t *u1 = data; // Pointer to the destination data 131 register uint32_t *u2 = s.data; // Pointer to the source data 132 for( uint i=0; i<size; i++) // For data in set 133 *u1++ &= *u2++; // Copy and AND longwords 134 return *this; // Return set 135 } 136 137 //------------------------------operator&=------------------------------------- 138 Set &VectorSet::operator &= (const Set &set) 139 { 140 // The cast is a virtual function that checks that "set" is a VectorSet. 141 return (*this) &= *(set.asVectorSet()); 142 } 143 144 //------------------------------operator|=------------------------------------- 145 // Union one set into another. 146 VectorSet &VectorSet::operator |= (const VectorSet &s) 147 { 148 // This many words must be unioned 149 register uint cnt = ((size<s.size)?size:s.size); 150 register uint32_t *u1 = data; // Pointer to the destination data 151 register uint32_t *u2 = s.data; // Pointer to the source data 152 for( uint i=0; i<cnt; i++) // Copy and OR the two sets 153 *u1++ |= *u2++; 154 if( size < s.size ) { // Is set 2 larger than set 1? 155 // Extend result by larger set 156 grow(s.size*sizeof(uint32_t)*8); 157 memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32_t)); 158 } 159 return *this; // Return result set 160 } 161 162 //------------------------------operator|=------------------------------------- 163 Set &VectorSet::operator |= (const Set &set) 164 { 165 // The cast is a virtual function that checks that "set" is a VectorSet. 166 return (*this) |= *(set.asVectorSet()); 167 } 168 169 //------------------------------operator-=------------------------------------- 170 // Difference one set from another. 171 VectorSet &VectorSet::operator -= (const VectorSet &s) 172 { 173 // This many words must be unioned 174 register uint cnt = ((size<s.size)?size:s.size); 175 register uint32_t *u1 = data; // Pointer to the destination data 176 register uint32_t *u2 = s.data; // Pointer to the source data 177 for( uint i=0; i<cnt; i++ ) // For data in set 178 *u1++ &= ~(*u2++); // A <-- A & ~B with longwords 179 return *this; // Return new set 180 } 181 182 //------------------------------operator-=------------------------------------- 183 Set &VectorSet::operator -= (const Set &set) 184 { 185 // The cast is a virtual function that checks that "set" is a VectorSet. 186 return (*this) -= *(set.asVectorSet()); 187 } 188 189 //------------------------------compare---------------------------------------- 190 // Compute 2 booleans: bits in A not B, bits in B not A. 191 // Return X0 -- A is not a subset of B 192 // X1 -- A is a subset of B 193 // 0X -- B is not a subset of A 194 // 1X -- B is a subset of A 195 int VectorSet::compare (const VectorSet &s) const 196 { 197 register uint32_t *u1 = data; // Pointer to the destination data 198 register uint32_t *u2 = s.data; // Pointer to the source data 199 register uint32_t AnotB = 0, BnotA = 0; 200 // This many words must be unioned 201 register uint cnt = ((size<s.size)?size:s.size); 202 203 // Get bits for both sets 204 uint i; // Exit value of loop 205 for( i=0; i<cnt; i++ ) { // For data in BOTH sets 206 register uint32_t A = *u1++; // Data from one guy 207 register uint32_t B = *u2++; // Data from other guy 208 AnotB |= (A & ~B); // Compute bits in A not B 209 BnotA |= (B & ~A); // Compute bits in B not A 210 } 211 212 // Get bits from bigger set 213 if( size < s.size ) { 214 for( ; i<s.size; i++ ) // For data in larger set 215 BnotA |= *u2++; // These bits are in B not A 216 } else { 217 for( ; i<size; i++ ) // For data in larger set 218 AnotB |= *u1++; // These bits are in A not B 219 } 220 221 // Set & return boolean flags 222 return ((!BnotA)<<1) + (!AnotB); 223 } 224 225 //------------------------------operator==------------------------------------- 226 // Test for set equality 227 int VectorSet::operator == (const VectorSet &s) const 228 { 229 return compare(s) == 3; // TRUE if A and B are mutual subsets 230 } 231 232 //------------------------------operator==------------------------------------- 233 int VectorSet::operator == (const Set &set) const 234 { 235 // The cast is a virtual function that checks that "set" is a VectorSet. 236 return (*this) == *(set.asVectorSet()); 237 } 238 239 //------------------------------disjoint--------------------------------------- 240 // Check for sets being disjoint. 241 int VectorSet::disjoint(const Set &set) const 242 { 243 // The cast is a virtual function that checks that "set" is a VectorSet. 244 const VectorSet &s = *(set.asVectorSet()); 245 246 // NOTE: The intersection is never any larger than the smallest set. 247 register uint small_size = ((size<s.size)?size:s.size); 248 register uint32_t *u1 = data; // Pointer to the destination data 249 register uint32_t *u2 = s.data; // Pointer to the source data 250 for( uint i=0; i<small_size; i++) // For data in set 251 if( *u1++ & *u2++ ) // If any elements in common 252 return 0; // Then not disjoint 253 return 1; // Else disjoint 254 } 255 256 //------------------------------operator<-------------------------------------- 257 // Test for strict subset 258 int VectorSet::operator < (const VectorSet &s) const 259 { 260 return compare(s) == 1; // A subset B, B not subset A 261 } 262 263 //------------------------------operator<-------------------------------------- 264 int VectorSet::operator < (const Set &set) const 265 { 266 // The cast is a virtual function that checks that "set" is a VectorSet. 267 return (*this) < *(set.asVectorSet()); 268 } 269 270 //------------------------------operator<=------------------------------------- 271 // Test for subset 272 int VectorSet::operator <= (const VectorSet &s) const 273 { 274 return compare(s) & 1; // A subset B 275 } 276 277 //------------------------------operator<=------------------------------------- 278 int VectorSet::operator <= (const Set &set) const 279 { 280 // The cast is a virtual function that checks that "set" is a VectorSet. 281 return (*this) <= *(set.asVectorSet()); 282 } 283 284 //------------------------------operator[]------------------------------------- 285 // Test for membership. A Zero/Non-Zero value is returned! 286 int VectorSet::operator[](uint elem) const 287 { 288 register uint word = elem >> 5; // Get the longword offset 289 if( word >= size ) // Beyond the last? 290 return 0; // Then it's clear 291 register uint32_t mask = 1L << (elem & 31); // Get bit mask 292 return ((data[word] & mask))!=0; // Return the sense of the bit 293 } 294 295 //------------------------------getelem---------------------------------------- 296 // Get any element from the set. 297 uint VectorSet::getelem(void) const 298 { 299 uint i; // Exit value of loop 300 for( i=0; i<size; i++ ) 301 if( data[i] ) 302 break; 303 uint32_t word = data[i]; 304 int j; // Exit value of loop 305 for( j= -1; word; j++, word>>=1 ); 306 return (i<<5)+j; 307 } 308 309 //------------------------------Clear------------------------------------------ 310 // Clear a set 311 void VectorSet::Clear(void) 312 { 313 if( size > 100 ) { // Reclaim storage only if huge 314 FREE_RESOURCE_ARRAY(uint32_t,data,size); 315 size = 2; // Small initial size 316 data = NEW_RESOURCE_ARRAY(uint32_t,size); 317 } 318 memset( data, 0, size*sizeof(uint32_t) ); 319 } 320 321 //------------------------------Size------------------------------------------- 322 // Return number of elements in a Set 323 uint VectorSet::Size(void) const 324 { 325 uint sum = 0; // Cumulative size so far. 326 uint8_t* currByte = (uint8_t*) data; 327 for( uint32_t i = 0; i < (size<<2); i++) // While have bytes to process 328 sum += bitsInByte[*currByte++]; // Add bits in current byte to size. 329 return sum; 330 } 331 332 //------------------------------Sort------------------------------------------- 333 // Sort the elements for the next forall statement 334 void VectorSet::Sort(void) 335 { 336 } 337 338 //------------------------------hash------------------------------------------- 339 int VectorSet::hash() const 340 { 341 uint32_t _xor = 0; 342 uint lim = ((size<4)?size:4); 343 for( uint i = 0; i < lim; i++ ) 344 _xor ^= data[i]; 345 return (int)_xor; 346 } 347 348 //------------------------------iterate---------------------------------------- 349 // Used by Set::print(). 350 class VSetI_ : public SetI_ { 351 VectorSetI vsi; 352 public: 353 VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; } 354 355 uint next(void) { ++vsi; return vsi.elem; } 356 int test(void) { return vsi.test(); } 357 }; 358 359 SetI_ *VectorSet::iterate(uint &elem) const { 360 return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem); 361 } 362 363 //============================================================================= 364 //------------------------------next------------------------------------------- 365 // Find and return the next element of a vector set, or return garbage and 366 // make "VectorSetI::test()" fail. 367 uint VectorSetI::next(void) 368 { 369 j++; // Next element in word 370 mask = (mask & max_jint) << 1;// Next bit in word 371 do { // Do While still have words 372 while( mask ) { // While have bits in word 373 if( s->data[i] & mask ) { // If found a bit 374 return (i<<5)+j; // Return the bit address 375 } 376 j++; // Skip to next bit 377 mask = (mask & max_jint) << 1; 378 } 379 j = 0; // No more bits in word; setup for next word 380 mask = 1; 381 for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word 382 } while( i<s->size ); 383 return max_juint; // No element, iterated them all 384 }