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