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