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