1 /*

     2  * Copyright 1997-2005 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any 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 }