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