--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/share/vm/libadt/vectset.cpp Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,390 @@
+/*
+ * Copyright 1997-2005 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+// Vector Sets - An Abstract Data Type
+
+#include "incls/_precompiled.incl"
+#include "incls/_vectset.cpp.incl"
+
+// %%%%% includes not needed with AVM framework - Ungar
+// #include "port.hpp"
+//IMPLEMENTATION
+// #include "vectset.hpp"
+
+// BitsInByte is a lookup table which tells the number of bits that
+// are in the looked-up number. It is very useful in VectorSet_Size.
+
+uint8 bitsInByte[256] = {
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+};
+
+//------------------------------VectorSet--------------------------------------
+// Create a new, empty Set.
+VectorSet::VectorSet(Arena *arena) : Set(arena) {
+ size = 2; // Small initial size
+ data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32));
+ data[0] = 0; // No elements
+ data[1] = 0;
+}
+
+//------------------------------Construct--------------------------------------
+Set &VectorSet_Construct(Arena *arena)
+{
+ return *(new VectorSet(arena));
+}
+
+//------------------------------operator=--------------------------------------
+Set &VectorSet::operator = (const Set &set)
+{
+ if( &set == this ) return *this;
+ FREE_FAST(data);
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ slamin(*(set.asVectorSet()));
+ return *this;
+}
+
+//------------------------------slamin-----------------------------------------
+// Initialize one set with another. No regard is made to the existing Set.
+void VectorSet::slamin(const VectorSet& s)
+{
+ size = s.size; // Use new size
+ data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size
+ memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array
+}
+
+//------------------------------grow-------------------------------------------
+// Expand the existing set to a bigger size
+void VectorSet::grow( uint newsize )
+{
+ newsize = (newsize+31) >> 5; // Convert to longwords
+ uint x = size;
+ while( x < newsize ) x <<= 1;
+ data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32));
+ memset((char *)(data + size), 0, (x - size)*sizeof(uint32));
+ size = x;
+}
+
+//------------------------------operator<<=------------------------------------
+// Insert a member into an existing Set.
+Set &VectorSet::operator <<= (uint elem)
+{
+ register uint word = elem >> 5; // Get the longword offset
+ register uint32 mask = 1L << (elem & 31); // Get bit mask
+
+ if( word >= size ) // Need to grow set?
+ grow(elem+1); // Then grow it
+ data[word] |= mask; // Set new bit
+ return *this;
+}
+
+//------------------------------operator>>=------------------------------------
+// Delete a member from an existing Set.
+Set &VectorSet::operator >>= (uint elem)
+{
+ register uint word = elem >> 5; // Get the longword offset
+ if( word >= size ) // Beyond the last?
+ return *this; // Then it's clear & return clear
+ register uint32 mask = 1L << (elem & 31); // Get bit mask
+ data[word] &= ~mask; // Clear bit
+ return *this;
+}
+
+//------------------------------operator&=-------------------------------------
+// Intersect one set into another.
+VectorSet &VectorSet::operator &= (const VectorSet &s)
+{
+ // NOTE: The intersection is never any larger than the smallest set.
+ if( s.size < size ) size = s.size; // Get smaller size
+ register uint32 *u1 = data; // Pointer to the destination data
+ register uint32 *u2 = s.data; // Pointer to the source data
+ for( uint i=0; i<size; i++) // For data in set
+ *u1++ &= *u2++; // Copy and AND longwords
+ return *this; // Return set
+}
+
+//------------------------------operator&=-------------------------------------
+Set &VectorSet::operator &= (const Set &set)
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ return (*this) &= *(set.asVectorSet());
+}
+
+//------------------------------operator|=-------------------------------------
+// Union one set into another.
+VectorSet &VectorSet::operator |= (const VectorSet &s)
+{
+ // This many words must be unioned
+ register uint cnt = ((size<s.size)?size:s.size);
+ register uint32 *u1 = data; // Pointer to the destination data
+ register uint32 *u2 = s.data; // Pointer to the source data
+ for( uint i=0; i<cnt; i++) // Copy and OR the two sets
+ *u1++ |= *u2++;
+ if( size < s.size ) { // Is set 2 larger than set 1?
+ // Extend result by larger set
+ grow(s.size*sizeof(uint32)*8);
+ memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32));
+ }
+ return *this; // Return result set
+}
+
+//------------------------------operator|=-------------------------------------
+Set &VectorSet::operator |= (const Set &set)
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ return (*this) |= *(set.asVectorSet());
+}
+
+//------------------------------operator-=-------------------------------------
+// Difference one set from another.
+VectorSet &VectorSet::operator -= (const VectorSet &s)
+{
+ // This many words must be unioned
+ register uint cnt = ((size<s.size)?size:s.size);
+ register uint32 *u1 = data; // Pointer to the destination data
+ register uint32 *u2 = s.data; // Pointer to the source data
+ for( uint i=0; i<cnt; i++ ) // For data in set
+ *u1++ &= ~(*u2++); // A <-- A & ~B with longwords
+ return *this; // Return new set
+}
+
+//------------------------------operator-=-------------------------------------
+Set &VectorSet::operator -= (const Set &set)
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ return (*this) -= *(set.asVectorSet());
+}
+
+//------------------------------compare----------------------------------------
+// Compute 2 booleans: bits in A not B, bits in B not A.
+// Return X0 -- A is not a subset of B
+// X1 -- A is a subset of B
+// 0X -- B is not a subset of A
+// 1X -- B is a subset of A
+int VectorSet::compare (const VectorSet &s) const
+{
+ register uint32 *u1 = data; // Pointer to the destination data
+ register uint32 *u2 = s.data; // Pointer to the source data
+ register uint32 AnotB = 0, BnotA = 0;
+ // This many words must be unioned
+ register uint cnt = ((size<s.size)?size:s.size);
+
+ // Get bits for both sets
+ uint i; // Exit value of loop
+ for( i=0; i<cnt; i++ ) { // For data in BOTH sets
+ register uint32 A = *u1++; // Data from one guy
+ register uint32 B = *u2++; // Data from other guy
+ AnotB |= (A & ~B); // Compute bits in A not B
+ BnotA |= (B & ~A); // Compute bits in B not A
+ }
+
+ // Get bits from bigger set
+ if( size < s.size ) {
+ for( ; i<s.size; i++ ) // For data in larger set
+ BnotA |= *u2++; // These bits are in B not A
+ } else {
+ for( ; i<size; i++ ) // For data in larger set
+ AnotB |= *u1++; // These bits are in A not B
+ }
+
+ // Set & return boolean flags
+ return ((!BnotA)<<1) + (!AnotB);
+}
+
+//------------------------------operator==-------------------------------------
+// Test for set equality
+int VectorSet::operator == (const VectorSet &s) const
+{
+ return compare(s) == 3; // TRUE if A and B are mutual subsets
+}
+
+//------------------------------operator==-------------------------------------
+int VectorSet::operator == (const Set &set) const
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ return (*this) == *(set.asVectorSet());
+}
+
+//------------------------------disjoint---------------------------------------
+// Check for sets being disjoint.
+int VectorSet::disjoint(const Set &set) const
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ const VectorSet &s = *(set.asVectorSet());
+
+ // NOTE: The intersection is never any larger than the smallest set.
+ register uint small = ((size<s.size)?size:s.size);
+ register uint32 *u1 = data; // Pointer to the destination data
+ register uint32 *u2 = s.data; // Pointer to the source data
+ for( uint i=0; i<small; i++) // For data in set
+ if( *u1++ & *u2++ ) // If any elements in common
+ return 0; // Then not disjoint
+ return 1; // Else disjoint
+}
+
+//------------------------------operator<--------------------------------------
+// Test for strict subset
+int VectorSet::operator < (const VectorSet &s) const
+{
+ return compare(s) == 1; // A subset B, B not subset A
+}
+
+//------------------------------operator<--------------------------------------
+int VectorSet::operator < (const Set &set) const
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ return (*this) < *(set.asVectorSet());
+}
+
+//------------------------------operator<=-------------------------------------
+// Test for subset
+int VectorSet::operator <= (const VectorSet &s) const
+{
+ return compare(s) & 1; // A subset B
+}
+
+//------------------------------operator<=-------------------------------------
+int VectorSet::operator <= (const Set &set) const
+{
+ // The cast is a virtual function that checks that "set" is a VectorSet.
+ return (*this) <= *(set.asVectorSet());
+}
+
+//------------------------------operator[]-------------------------------------
+// Test for membership. A Zero/Non-Zero value is returned!
+int VectorSet::operator[](uint elem) const
+{
+ register uint word = elem >> 5; // Get the longword offset
+ if( word >= size ) // Beyond the last?
+ return 0; // Then it's clear
+ register uint32 mask = 1L << (elem & 31); // Get bit mask
+ return ((data[word] & mask))!=0; // Return the sense of the bit
+}
+
+//------------------------------getelem----------------------------------------
+// Get any element from the set.
+uint VectorSet::getelem(void) const
+{
+ uint i; // Exit value of loop
+ for( i=0; i<size; i++ )
+ if( data[i] )
+ break;
+ uint32 word = data[i];
+ int j; // Exit value of loop
+ for( j= -1; word; j++, word>>=1 );
+ return (i<<5)+j;
+}
+
+//------------------------------Clear------------------------------------------
+// Clear a set
+void VectorSet::Clear(void)
+{
+ if( size > 100 ) { // Reclaim storage only if huge
+ FREE_RESOURCE_ARRAY(uint32,data,size);
+ size = 2; // Small initial size
+ data = NEW_RESOURCE_ARRAY(uint32,size);
+ }
+ memset( data, 0, size*sizeof(uint32) );
+}
+
+//------------------------------Size-------------------------------------------
+// Return number of elements in a Set
+uint VectorSet::Size(void) const
+{
+ uint sum = 0; // Cumulative size so far.
+ uint8 *currByte = (uint8*)data;
+ for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process
+ sum += bitsInByte[*currByte++]; // Add bits in current byte to size.
+ return sum;
+}
+
+//------------------------------Sort-------------------------------------------
+// Sort the elements for the next forall statement
+void VectorSet::Sort(void)
+{
+}
+
+//------------------------------hash-------------------------------------------
+int VectorSet::hash() const
+{
+ uint32 _xor = 0;
+ uint lim = ((size<4)?size:4);
+ for( uint i = 0; i < lim; i++ )
+ _xor ^= data[i];
+ return (int)_xor;
+}
+
+//------------------------------iterate----------------------------------------
+SetI_ *VectorSet::iterate(uint &elem) const
+{
+ VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this));
+ elem = foo->next();
+ return foo;
+}
+
+//=============================================================================
+//------------------------------VSetI_-----------------------------------------
+// Initialize the innards of a VectorSet iterator
+VSetI_::VSetI_( const VectorSet *vset ) : s(vset)
+{
+ i = (uint)-1L;
+ j = (uint)-1L;
+ mask = (unsigned)(1L<<31);
+}
+
+//------------------------------next-------------------------------------------
+// Find and return the next element of a vector set, or return garbage and
+// make "VSetI_::test()" fail.
+uint VSetI_::next(void)
+{
+ j++; // Next element in word
+ mask = (mask & max_jint) << 1;// Next bit in word
+ do { // Do While still have words
+ while( mask ) { // While have bits in word
+ if( s->data[i] & mask ) { // If found a bit
+ return (i<<5)+j; // Return the bit address
+ }
+ j++; // Skip to next bit
+ mask = (mask & max_jint) << 1;
+ }
+ j = 0; // No more bits in word; setup for next word
+ mask = 1;
+ for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word
+ } while( i<s->size );
+ return max_juint; // No element, iterated them all
+}