1 /*
   2  * Copyright (c) 1997, 2005, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * 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 }