vectset.cpp revision 1472:c18cbe5936b8
1262685Sdelphij/* 250276Speter * Copyright (c) 1997, 2005, Oracle and/or its affiliates. All rights reserved. 3262685Sdelphij * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 450276Speter * 550276Speter * This code is free software; you can redistribute it and/or modify it 650276Speter * under the terms of the GNU General Public License version 2 only, as 750276Speter * published by the Free Software Foundation. 850276Speter * 950276Speter * This code is distributed in the hope that it will be useful, but WITHOUT 1050276Speter * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1150276Speter * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1250276Speter * version 2 for more details (a copy is included in the LICENSE file that 1350276Speter * accompanied this code). 1450276Speter * 1550276Speter * You should have received a copy of the GNU General Public License version 1650276Speter * 2 along with this work; if not, write to the Free Software Foundation, 1750276Speter * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1850276Speter * 1950276Speter * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2050276Speter * or visit www.oracle.com if you need additional information or have any 2150276Speter * questions. 2250276Speter * 2350276Speter */ 2450276Speter 2550276Speter// Vector Sets - An Abstract Data Type 2650276Speter 2750276Speter#include "incls/_precompiled.incl" 2850276Speter#include "incls/_vectset.cpp.incl" 2950276Speter 30166124Srafan// %%%%% includes not needed with AVM framework - Ungar 3150276Speter// #include "port.hpp" 3250276Speter//IMPLEMENTATION 3350276Speter// #include "vectset.hpp" 34166124Srafan 35166124Srafan// BitsInByte is a lookup table which tells the number of bits that 36166124Srafan// are in the looked-up number. It is very useful in VectorSet_Size. 37262685Sdelphij 38166124Srafanuint8 bitsInByte[256] = { 39166124Srafan 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 40166124Srafan 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 41174993Srafan 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 42262685Sdelphij 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 43166124Srafan 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 4497049Speter 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 45262629Sdelphij 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 46262629Sdelphij 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 47262629Sdelphij 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 48174993Srafan 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 49166124Srafan 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 50166124Srafan 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 51166124Srafan 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 52166124Srafan 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 53166124Srafan 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 54166124Srafan 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 55262629Sdelphij}; 5650276Speter 5750276Speter//------------------------------VectorSet-------------------------------------- 5850276Speter// Create a new, empty Set. 59166124SrafanVectorSet::VectorSet(Arena *arena) : Set(arena) { 6050276Speter size = 2; // Small initial size 6150276Speter data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32)); 62174993Srafan data[0] = 0; // No elements 63174993Srafan data[1] = 0; 64174993Srafan} 65174993Srafan 66262629Sdelphij//------------------------------Construct-------------------------------------- 67174993SrafanSet &VectorSet_Construct(Arena *arena) 68174993Srafan{ 69174993Srafan return *(new VectorSet(arena)); 70174993Srafan} 71174993Srafan 72174993Srafan//------------------------------operator=-------------------------------------- 73174993SrafanSet &VectorSet::operator = (const Set &set) 74262685Sdelphij{ 75174993Srafan if( &set == this ) return *this; 76174993Srafan FREE_FAST(data); 77174993Srafan // The cast is a virtual function that checks that "set" is a VectorSet. 78174993Srafan slamin(*(set.asVectorSet())); 79174993Srafan return *this; 80174993Srafan} 81174993Srafan 82174993Srafan//------------------------------slamin----------------------------------------- 83174993Srafan// Initialize one set with another. No regard is made to the existing Set. 84174993Srafanvoid VectorSet::slamin(const VectorSet& s) 85262685Sdelphij{ 86262685Sdelphij size = s.size; // Use new size 87262685Sdelphij data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size 88262685Sdelphij memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array 89174993Srafan} 90174993Srafan 91174993Srafan//------------------------------grow------------------------------------------- 92174993Srafan// Expand the existing set to a bigger size 93174993Srafanvoid VectorSet::grow( uint newsize ) 94174993Srafan{ 95174993Srafan newsize = (newsize+31) >> 5; // Convert to longwords 96174993Srafan uint x = size; 97174993Srafan while( x < newsize ) x <<= 1; 98174993Srafan data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32)); 99174993Srafan memset((char *)(data + size), 0, (x - size)*sizeof(uint32)); 100262685Sdelphij size = x; 101262685Sdelphij} 102262685Sdelphij 103262685Sdelphij//------------------------------operator<<=------------------------------------ 104174993Srafan// Insert a member into an existing Set. 105174993SrafanSet &VectorSet::operator <<= (uint elem) 106174993Srafan{ 107174993Srafan register uint word = elem >> 5; // Get the longword offset 108174993Srafan register uint32 mask = 1L << (elem & 31); // Get bit mask 109174993Srafan 110174993Srafan if( word >= size ) // Need to grow set? 111174993Srafan grow(elem+1); // Then grow it 112174993Srafan data[word] |= mask; // Set new bit 113174993Srafan return *this; 114174993Srafan} 115174993Srafan 116174993Srafan//------------------------------operator>>=------------------------------------ 117174993Srafan// Delete a member from an existing Set. 118174993SrafanSet &VectorSet::operator >>= (uint elem) 119174993Srafan{ 120262685Sdelphij register uint word = elem >> 5; // Get the longword offset 121174993Srafan if( word >= size ) // Beyond the last? 122174993Srafan return *this; // Then it's clear & return clear 123174993Srafan register uint32 mask = 1L << (elem & 31); // Get bit mask 124174993Srafan data[word] &= ~mask; // Clear bit 125174993Srafan return *this; 126174993Srafan} 127174993Srafan 12850276Speter//------------------------------operator&=------------------------------------- 12950276Speter// Intersect one set into another. 130262629SdelphijVectorSet &VectorSet::operator &= (const VectorSet &s) 131262629Sdelphij{ 132262629Sdelphij // NOTE: The intersection is never any larger than the smallest set. 13366963Speter if( s.size < size ) size = s.size; // Get smaller size 13450276Speter register uint32 *u1 = data; // Pointer to the destination data 13550276Speter register uint32 *u2 = s.data; // Pointer to the source data 13666963Speter for( uint i=0; i<size; i++) // For data in set 137262685Sdelphij *u1++ &= *u2++; // Copy and AND longwords 138262685Sdelphij return *this; // Return set 139262685Sdelphij} 140166124Srafan 14166963Speter//------------------------------operator&=------------------------------------- 142262685SdelphijSet &VectorSet::operator &= (const Set &set) 143262685Sdelphij{ 14466963Speter // The cast is a virtual function that checks that "set" is a VectorSet. 145174993Srafan return (*this) &= *(set.asVectorSet()); 146262685Sdelphij} 147262685Sdelphij 148174993Srafan//------------------------------operator|=------------------------------------- 149262685Sdelphij// Union one set into another. 150174993SrafanVectorSet &VectorSet::operator |= (const VectorSet &s) 15166963Speter{ 152174993Srafan // This many words must be unioned 153262685Sdelphij register uint cnt = ((size<s.size)?size:s.size); 154262685Sdelphij register uint32 *u1 = data; // Pointer to the destination data 155174993Srafan register uint32 *u2 = s.data; // Pointer to the source data 156262685Sdelphij for( uint i=0; i<cnt; i++) // Copy and OR the two sets 157174993Srafan *u1++ |= *u2++; 15850276Speter if( size < s.size ) { // Is set 2 larger than set 1? 159262685Sdelphij // Extend result by larger set 160262685Sdelphij grow(s.size*sizeof(uint32)*8); 161262685Sdelphij memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32)); 162262685Sdelphij } 163262685Sdelphij return *this; // Return result set 164262685Sdelphij} 165262685Sdelphij 166262685Sdelphij//------------------------------operator|=------------------------------------- 167262685SdelphijSet &VectorSet::operator |= (const Set &set) 168262685Sdelphij{ 169262685Sdelphij // The cast is a virtual function that checks that "set" is a VectorSet. 170262685Sdelphij return (*this) |= *(set.asVectorSet()); 17150276Speter} 172166124Srafan 173166124Srafan//------------------------------operator-=------------------------------------- 174166124Srafan// Difference one set from another. 17566963SpeterVectorSet &VectorSet::operator -= (const VectorSet &s) 176262685Sdelphij{ 17766963Speter // This many words must be unioned 17866963Speter register uint cnt = ((size<s.size)?size:s.size); 17966963Speter register uint32 *u1 = data; // Pointer to the destination data 18066963Speter register uint32 *u2 = s.data; // Pointer to the source data 18166963Speter for( uint i=0; i<cnt; i++ ) // For data in set 18266963Speter *u1++ &= ~(*u2++); // A <-- A & ~B with longwords 18366963Speter return *this; // Return new set 18466963Speter} 18566963Speter 18666963Speter//------------------------------operator-=------------------------------------- 18766963SpeterSet &VectorSet::operator -= (const Set &set) 18866963Speter{ 18966963Speter // The cast is a virtual function that checks that "set" is a VectorSet. 19066963Speter return (*this) -= *(set.asVectorSet()); 19166963Speter} 19250276Speter 19366963Speter//------------------------------compare---------------------------------------- 19450276Speter// Compute 2 booleans: bits in A not B, bits in B not A. 19550276Speter// Return X0 -- A is not a subset of B 196174993Srafan// X1 -- A is a subset of B 197174993Srafan// 0X -- B is not a subset of A 198174993Srafan// 1X -- B is a subset of A 199174993Srafanint VectorSet::compare (const VectorSet &s) const 200174993Srafan{ 201174993Srafan register uint32 *u1 = data; // Pointer to the destination data 202174993Srafan register uint32 *u2 = s.data; // Pointer to the source data 203174993Srafan register uint32 AnotB = 0, BnotA = 0; 204174993Srafan // This many words must be unioned 205174993Srafan register uint cnt = ((size<s.size)?size:s.size); 206174993Srafan 207174993Srafan // Get bits for both sets 208174993Srafan uint i; // Exit value of loop 209262685Sdelphij for( i=0; i<cnt; i++ ) { // For data in BOTH sets 210262685Sdelphij register uint32 A = *u1++; // Data from one guy 211262685Sdelphij register uint32 B = *u2++; // Data from other guy 212262685Sdelphij AnotB |= (A & ~B); // Compute bits in A not B 213262685Sdelphij BnotA |= (B & ~A); // Compute bits in B not A 214174993Srafan } 215174993Srafan 216174993Srafan // Get bits from bigger set 217174993Srafan if( size < s.size ) { 218174993Srafan for( ; i<s.size; i++ ) // For data in larger set 219174993Srafan BnotA |= *u2++; // These bits are in B not A 220174993Srafan } else { 221174993Srafan for( ; i<size; i++ ) // For data in larger set 222166124Srafan AnotB |= *u1++; // These bits are in A not B 223174993Srafan } 224166124Srafan 225174993Srafan // Set & return boolean flags 226174993Srafan return ((!BnotA)<<1) + (!AnotB); 227174993Srafan} 228174993Srafan 229166124Srafan//------------------------------operator==------------------------------------- 230174993Srafan// Test for set equality 231166124Srafanint VectorSet::operator == (const VectorSet &s) const 232166124Srafan{ 233166124Srafan return compare(s) == 3; // TRUE if A and B are mutual subsets 234174993Srafan} 235174993Srafan 236174993Srafan//------------------------------operator==------------------------------------- 237174993Srafanint VectorSet::operator == (const Set &set) const 238174993Srafan{ 239174993Srafan // The cast is a virtual function that checks that "set" is a VectorSet. 240174993Srafan return (*this) == *(set.asVectorSet()); 241174993Srafan} 242174993Srafan 243174993Srafan//------------------------------disjoint--------------------------------------- 244166124Srafan// Check for sets being disjoint. 245166124Srafanint VectorSet::disjoint(const Set &set) const 246166124Srafan{ 247166124Srafan // The cast is a virtual function that checks that "set" is a VectorSet. 248166124Srafan const VectorSet &s = *(set.asVectorSet()); 249166124Srafan 250166124Srafan // NOTE: The intersection is never any larger than the smallest set. 251166124Srafan register uint small = ((size<s.size)?size:s.size); 252166124Srafan register uint32 *u1 = data; // Pointer to the destination data 253166124Srafan register uint32 *u2 = s.data; // Pointer to the source data 254166124Srafan for( uint i=0; i<small; i++) // For data in set 25550276Speter if( *u1++ & *u2++ ) // If any elements in common 256262685Sdelphij return 0; // Then not disjoint 257262685Sdelphij return 1; // Else disjoint 258262685Sdelphij} 25950276Speter 26050276Speter//------------------------------operator<-------------------------------------- 26150276Speter// Test for strict subset 26250276Speterint VectorSet::operator < (const VectorSet &s) const 26350276Speter{ 26450276Speter return compare(s) == 1; // A subset B, B not subset A 26550276Speter} 26650276Speter 267262685Sdelphij//------------------------------operator<-------------------------------------- 268262685Sdelphijint VectorSet::operator < (const Set &set) const 269262685Sdelphij{ 270262685Sdelphij // The cast is a virtual function that checks that "set" is a VectorSet. 271262685Sdelphij return (*this) < *(set.asVectorSet()); 272262685Sdelphij} 273262685Sdelphij 274262685Sdelphij//------------------------------operator<=------------------------------------- 275262685Sdelphij// Test for subset 27650276Speterint VectorSet::operator <= (const VectorSet &s) const 277166124Srafan{ 278166124Srafan return compare(s) & 1; // A subset B 279166124Srafan} 280166124Srafan 281262685Sdelphij//------------------------------operator<=------------------------------------- 282166124Srafanint VectorSet::operator <= (const Set &set) const 283166124Srafan{ 284166124Srafan // The cast is a virtual function that checks that "set" is a VectorSet. 285166124Srafan return (*this) <= *(set.asVectorSet()); 286262685Sdelphij} 287166124Srafan 288166124Srafan//------------------------------operator[]------------------------------------- 289262629Sdelphij// Test for membership. A Zero/Non-Zero value is returned! 290174993Srafanint VectorSet::operator[](uint elem) const 291174993Srafan{ 292174993Srafan register uint word = elem >> 5; // Get the longword offset 293166124Srafan if( word >= size ) // Beyond the last? 294166124Srafan return 0; // Then it's clear 295166124Srafan register uint32 mask = 1L << (elem & 31); // Get bit mask 296166124Srafan return ((data[word] & mask))!=0; // Return the sense of the bit 297166124Srafan} 298166124Srafan 29950276Speter//------------------------------getelem---------------------------------------- 30050276Speter// Get any element from the set. 30150276Speteruint VectorSet::getelem(void) const 30250276Speter{ 303174993Srafan uint i; // Exit value of loop 304174993Srafan for( i=0; i<size; i++ ) 305174993Srafan if( data[i] ) 30650276Speter break; 30750276Speter uint32 word = data[i]; 30850276Speter int j; // Exit value of loop 30950276Speter for( j= -1; word; j++, word>>=1 ); 31050276Speter return (i<<5)+j; 31150276Speter} 31262449Speter 31362449Speter//------------------------------Clear------------------------------------------ 31462449Speter// Clear a set 31562449Spetervoid VectorSet::Clear(void) 31662449Speter{ 31762449Speter if( size > 100 ) { // Reclaim storage only if huge 31862449Speter FREE_RESOURCE_ARRAY(uint32,data,size); 31962449Speter size = 2; // Small initial size 32050276Speter data = NEW_RESOURCE_ARRAY(uint32,size); 32197049Speter } 32250276Speter memset( data, 0, size*sizeof(uint32) ); 32350276Speter} 32450276Speter 32550276Speter//------------------------------Size------------------------------------------- 32650276Speter// Return number of elements in a Set 32750276Speteruint VectorSet::Size(void) const 32850276Speter{ 32950276Speter uint sum = 0; // Cumulative size so far. 330262685Sdelphij uint8 *currByte = (uint8*)data; 331262685Sdelphij for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process 332262685Sdelphij sum += bitsInByte[*currByte++]; // Add bits in current byte to size. 333262685Sdelphij return sum; 334262685Sdelphij} 335262685Sdelphij 336262685Sdelphij//------------------------------Sort------------------------------------------- 337262685Sdelphij// Sort the elements for the next forall statement 338262685Sdelphijvoid VectorSet::Sort(void) 339262685Sdelphij{ 340262685Sdelphij} 341262685Sdelphij 342262685Sdelphij//------------------------------hash------------------------------------------- 343262685Sdelphijint VectorSet::hash() const 344262685Sdelphij{ 34550276Speter uint32 _xor = 0; 346262685Sdelphij uint lim = ((size<4)?size:4); 34750276Speter for( uint i = 0; i < lim; i++ ) 34850276Speter _xor ^= data[i]; 34950276Speter return (int)_xor; 35050276Speter} 35150276Speter 35250276Speter//------------------------------iterate---------------------------------------- 35350276SpeterSetI_ *VectorSet::iterate(uint &elem) const 35450276Speter{ 35550276Speter VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this)); 35650276Speter elem = foo->next(); 35750276Speter return foo; 358174993Srafan} 35950276Speter 36050276Speter//============================================================================= 361174993Srafan//------------------------------VSetI_----------------------------------------- 362174993Srafan// Initialize the innards of a VectorSet iterator 363174993SrafanVSetI_::VSetI_( const VectorSet *vset ) : s(vset) 364174993Srafan{ 36597049Speter i = (uint)-1L; 366174993Srafan j = (uint)-1L; 36797049Speter mask = (unsigned)(1L<<31); 36850276Speter} 36950276Speter 37050276Speter//------------------------------next------------------------------------------- 37197049Speter// Find and return the next element of a vector set, or return garbage and 372262685Sdelphij// make "VSetI_::test()" fail. 37397049Speteruint VSetI_::next(void) 374166124Srafan{ 375166124Srafan j++; // Next element in word 376166124Srafan mask = (mask & max_jint) << 1;// Next bit in word 377166124Srafan do { // Do While still have words 37897049Speter while( mask ) { // While have bits in word 37997049Speter if( s->data[i] & mask ) { // If found a bit 38097049Speter return (i<<5)+j; // Return the bit address 381166124Srafan } 382166124Srafan j++; // Skip to next bit 383166124Srafan mask = (mask & max_jint) << 1; 384174993Srafan } 385174993Srafan j = 0; // No more bits in word; setup for next word 386174993Srafan mask = 1; 387174993Srafan for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word 388174993Srafan } while( i<s->size ); 38997049Speter return max_juint; // No element, iterated them all 39097049Speter} 39150276Speter