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