1 /*
   2  * Copyright (c) 1997, 2012, 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 #include "precompiled.hpp"
  26 #include "libadt/vectset.hpp"
  27 #include "memory/allocation.inline.hpp"
  28 #include "memory/arena.hpp"
  29 
  30 // Vector Sets - An Abstract Data Type
  31 
  32 // BitsInByte is a lookup table which tells the number of bits that
  33 // are in the looked-up number.  It is very useful in VectorSet_Size.
  34 
  35 uint8_t bitsInByte[BITS_IN_BYTE_ARRAY_SIZE] = {
  36   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  37   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  38   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  39   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  40   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  41   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  42   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  43   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  44   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  45   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  46   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  47   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  48   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  49   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  50   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  51   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  52 };
  53 
  54 //------------------------------VectorSet--------------------------------------
  55 // Create a new, empty Set.
  56 VectorSet::VectorSet(Arena *arena) : Set(arena) {
  57   size = 2;                     // Small initial size
  58   data = (uint32_t *)_set_arena->Amalloc(size*sizeof(uint32_t));
  59   data[0] = 0;                  // No elements
  60   data[1] = 0;
  61 }
  62 
  63 //------------------------------Construct--------------------------------------
  64 Set &VectorSet_Construct(Arena *arena)
  65 {
  66   return *(new VectorSet(arena));
  67 }
  68 
  69 //------------------------------operator=--------------------------------------
  70 Set &VectorSet::operator = (const Set &set)
  71 {
  72   if( &set == this ) return *this;
  73   FREE_FAST(data);
  74   // The cast is a virtual function that checks that "set" is a VectorSet.
  75   slamin(*(set.asVectorSet()));
  76   return *this;
  77 }
  78 
  79 //------------------------------slamin-----------------------------------------
  80 // Initialize one set with another.  No regard is made to the existing Set.
  81 void VectorSet::slamin(const VectorSet& s)
  82 {
  83   size = s.size;                // Use new size
  84   data = (uint32_t*)s._set_arena->Amalloc(size*sizeof(uint32_t)); // Make array of required size
  85   memcpy( data, s.data, size*sizeof(uint32_t) ); // Fill the array
  86 }
  87 
  88 //------------------------------grow-------------------------------------------
  89 // Expand the existing set to a bigger size
  90 void VectorSet::grow( uint newsize )
  91 {
  92   newsize = (newsize+31) >> 5;  // Convert to longwords
  93   uint x = size;
  94   while( x < newsize ) x <<= 1;
  95   data = (uint32_t *)_set_arena->Arealloc(data, size*sizeof(uint32_t), x*sizeof(uint32_t));
  96   memset((char *)(data + size), 0, (x - size)*sizeof(uint32_t));
  97   size = x;
  98 }
  99 
 100 //------------------------------operator<<=------------------------------------
 101 // Insert a member into an existing Set.
 102 Set &VectorSet::operator <<= (uint elem)
 103 {
 104   uint word = elem >> 5;            // Get the longword offset
 105   uint32_t mask = 1L << (elem & 31);  // Get bit mask
 106 
 107   if( word >= size )            // Need to grow set?
 108     grow(elem+1);               // Then grow it
 109   data[word] |= mask;           // Set new bit
 110   return *this;
 111 }
 112 
 113 //------------------------------operator>>=------------------------------------
 114 // Delete a member from an existing Set.
 115 Set &VectorSet::operator >>= (uint elem)
 116 {
 117   uint word = elem >> 5;          // Get the longword offset
 118   if( word >= size )              // Beyond the last?
 119     return *this;                 // Then it's clear & return clear
 120   uint32_t mask = 1L << (elem & 31);     // Get bit mask
 121   data[word] &= ~mask;            // Clear bit
 122   return *this;
 123 }
 124 
 125 //------------------------------operator&=-------------------------------------
 126 // Intersect one set into another.
 127 VectorSet &VectorSet::operator &= (const VectorSet &s)
 128 {
 129   // NOTE: The intersection is never any larger than the smallest set.
 130   if( s.size < size ) size = s.size; // Get smaller size
 131   uint32_t *u1 = data;          // Pointer to the destination data
 132   uint32_t *u2 = s.data;        // Pointer to the source data
 133   for( uint i=0; i<size; i++)   // For data in set
 134     *u1++ &= *u2++;             // Copy and AND longwords
 135   return *this;                 // Return set
 136 }
 137 
 138 //------------------------------operator&=-------------------------------------
 139 Set &VectorSet::operator &= (const Set &set)
 140 {
 141   // The cast is a virtual function that checks that "set" is a VectorSet.
 142   return (*this) &= *(set.asVectorSet());
 143 }
 144 
 145 //------------------------------operator|=-------------------------------------
 146 // Union one set into another.
 147 VectorSet &VectorSet::operator |= (const VectorSet &s)
 148 {
 149   // This many words must be unioned
 150   uint cnt = ((size<s.size)?size:s.size);
 151   uint32_t *u1 = data;          // Pointer to the destination data
 152   uint32_t *u2 = s.data;        // Pointer to the source data
 153   for( uint i=0; i<cnt; i++)    // Copy and OR the two sets
 154     *u1++ |= *u2++;
 155   if( size < s.size ) {         // Is set 2 larger than set 1?
 156     // Extend result by larger set
 157     grow(s.size*sizeof(uint32_t)*8);
 158     memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32_t));
 159   }
 160   return *this;                 // Return result set
 161 }
 162 
 163 //------------------------------operator|=-------------------------------------
 164 Set &VectorSet::operator |= (const Set &set)
 165 {
 166   // The cast is a virtual function that checks that "set" is a VectorSet.
 167   return (*this) |= *(set.asVectorSet());
 168 }
 169 
 170 //------------------------------operator-=-------------------------------------
 171 // Difference one set from another.
 172 VectorSet &VectorSet::operator -= (const VectorSet &s)
 173 {
 174   // This many words must be unioned
 175   uint cnt = ((size<s.size)?size:s.size);
 176   uint32_t *u1 = data;          // Pointer to the destination data
 177   uint32_t *u2 = s.data;        // Pointer to the source data
 178   for( uint i=0; i<cnt; i++ )   // For data in set
 179     *u1++ &= ~(*u2++);          // A <-- A & ~B  with longwords
 180   return *this;                 // Return new set
 181 }
 182 
 183 //------------------------------operator-=-------------------------------------
 184 Set &VectorSet::operator -= (const Set &set)
 185 {
 186   // The cast is a virtual function that checks that "set" is a VectorSet.
 187   return (*this) -= *(set.asVectorSet());
 188 }
 189 
 190 //------------------------------compare----------------------------------------
 191 // Compute 2 booleans: bits in A not B, bits in B not A.
 192 // Return X0 --  A is not a subset of B
 193 //        X1 --  A is a subset of B
 194 //        0X --  B is not a subset of A
 195 //        1X --  B is a subset of A
 196 int VectorSet::compare (const VectorSet &s) const
 197 {
 198   uint32_t *u1 = data;          // Pointer to the destination data
 199   uint32_t *u2 = s.data;        // Pointer to the source data
 200   uint32_t AnotB = 0, BnotA = 0;
 201   // This many words must be unioned
 202   uint cnt = ((size<s.size)?size:s.size);
 203 
 204   // Get bits for both sets
 205   uint i;                       // Exit value of loop
 206   for( i=0; i<cnt; i++ ) {      // For data in BOTH sets
 207     uint32_t A = *u1++;         // Data from one guy
 208     uint32_t B = *u2++;         // Data from other guy
 209     AnotB |= (A & ~B);          // Compute bits in A not B
 210     BnotA |= (B & ~A);          // Compute bits in B not A
 211   }
 212 
 213   // Get bits from bigger set
 214   if( size < s.size ) {
 215     for( ; i<s.size; i++ )      // For data in larger set
 216       BnotA |= *u2++;           // These bits are in B not A
 217   } else {
 218     for( ; i<size; i++ )        // For data in larger set
 219       AnotB |= *u1++;           // These bits are in A not B
 220   }
 221 
 222   // Set & return boolean flags
 223   return ((!BnotA)<<1) + (!AnotB);
 224 }
 225 
 226 //------------------------------operator==-------------------------------------
 227 // Test for set equality
 228 int VectorSet::operator == (const VectorSet &s) const
 229 {
 230   return compare(s) == 3;       // TRUE if A and B are mutual subsets
 231 }
 232 
 233 //------------------------------operator==-------------------------------------
 234 int VectorSet::operator == (const Set &set) const
 235 {
 236   // The cast is a virtual function that checks that "set" is a VectorSet.
 237   return (*this) == *(set.asVectorSet());
 238 }
 239 
 240 //------------------------------disjoint---------------------------------------
 241 // Check for sets being disjoint.
 242 int VectorSet::disjoint(const Set &set) const
 243 {
 244   // The cast is a virtual function that checks that "set" is a VectorSet.
 245   const VectorSet &s = *(set.asVectorSet());
 246 
 247   // NOTE: The intersection is never any larger than the smallest set.
 248   uint small_size = ((size<s.size)?size:s.size);
 249   uint32_t *u1 = data;               // Pointer to the destination data
 250   uint32_t *u2 = s.data;             // Pointer to the source data
 251   for( uint i=0; i<small_size; i++)  // For data in set
 252     if( *u1++ & *u2++ )              // If any elements in common
 253       return 0;                      // Then not disjoint
 254   return 1;                          // Else disjoint
 255 }
 256 
 257 //------------------------------operator<--------------------------------------
 258 // Test for strict subset
 259 int VectorSet::operator < (const VectorSet &s) const
 260 {
 261   return compare(s) == 1;       // A subset B, B not subset A
 262 }
 263 
 264 //------------------------------operator<--------------------------------------
 265 int VectorSet::operator < (const Set &set) const
 266 {
 267   // The cast is a virtual function that checks that "set" is a VectorSet.
 268   return (*this) < *(set.asVectorSet());
 269 }
 270 
 271 //------------------------------operator<=-------------------------------------
 272 // Test for subset
 273 int VectorSet::operator <= (const VectorSet &s) const
 274 {
 275   return compare(s) & 1;        // A subset B
 276 }
 277 
 278 //------------------------------operator<=-------------------------------------
 279 int VectorSet::operator <= (const Set &set) const
 280 {
 281   // The cast is a virtual function that checks that "set" is a VectorSet.
 282   return (*this) <= *(set.asVectorSet());
 283 }
 284 
 285 //------------------------------operator[]-------------------------------------
 286 // Test for membership.  A Zero/Non-Zero value is returned!
 287 int VectorSet::operator[](uint elem) const
 288 {
 289   uint word = elem >> 5;              // Get the longword offset
 290   if( word >= size )                  // Beyond the last?
 291     return 0;                         // Then it's clear
 292   uint32_t mask = 1L << (elem & 31);  // Get bit mask
 293   return ((data[word] & mask))!=0;    // Return the sense of the bit
 294 }
 295 
 296 //------------------------------getelem----------------------------------------
 297 // Get any element from the set.
 298 uint VectorSet::getelem(void) const
 299 {
 300   uint i;                       // Exit value of loop
 301   for( i=0; i<size; i++ )
 302     if( data[i] )
 303       break;
 304   uint32_t word = data[i];
 305   int j;                        // Exit value of loop
 306   for( j= -1; word; j++, word>>=1 );
 307   return (i<<5)+j;
 308 }
 309 
 310 //------------------------------Clear------------------------------------------
 311 // Clear a set
 312 void VectorSet::Clear(void)
 313 {
 314   if( size > 100 ) {            // Reclaim storage only if huge
 315     FREE_RESOURCE_ARRAY(uint32_t,data,size);
 316     size = 2;                   // Small initial size
 317     data = NEW_RESOURCE_ARRAY(uint32_t,size);
 318   }
 319   memset( data, 0, size*sizeof(uint32_t) );
 320 }
 321 
 322 //------------------------------Size-------------------------------------------
 323 // Return number of elements in a Set
 324 uint VectorSet::Size(void) const
 325 {
 326   uint sum = 0;                 // Cumulative size so far.
 327   uint8_t* currByte = (uint8_t*) data;
 328   for( uint32_t i = 0; i < (size<<2); i++) // While have bytes to process
 329     sum += bitsInByte[*currByte++];      // Add bits in current byte to size.
 330   return sum;
 331 }
 332 
 333 //------------------------------Sort-------------------------------------------
 334 // Sort the elements for the next forall statement
 335 void VectorSet::Sort(void)
 336 {
 337 }
 338 
 339 //------------------------------hash-------------------------------------------
 340 int VectorSet::hash() const
 341 {
 342   uint32_t _xor = 0;
 343   uint lim = ((size<4)?size:4);
 344   for( uint i = 0; i < lim; i++ )
 345     _xor ^= data[i];
 346   return (int)_xor;
 347 }
 348 
 349 //------------------------------iterate----------------------------------------
 350 // Used by Set::print().
 351 class VSetI_ : public SetI_ {
 352   VectorSetI vsi;
 353 public:
 354   VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; }
 355 
 356   uint next(void) { ++vsi; return vsi.elem; }
 357   int  test(void) { return vsi.test(); }
 358 };
 359 
 360 SetI_ *VectorSet::iterate(uint &elem) const {
 361   return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem);
 362 }
 363 
 364 //=============================================================================
 365 //------------------------------next-------------------------------------------
 366 // Find and return the next element of a vector set, or return garbage and
 367 // make "VectorSetI::test()" fail.
 368 uint VectorSetI::next(void)
 369 {
 370   j++;                          // Next element in word
 371   mask = (mask & max_jint) << 1;// Next bit in word
 372   do {                          // Do While still have words
 373     while( mask ) {             // While have bits in word
 374       if( s->data[i] & mask ) { // If found a bit
 375         return (i<<5)+j;        // Return the bit address
 376       }
 377       j++;                      // Skip to next bit
 378       mask = (mask & max_jint) << 1;
 379     }
 380     j = 0;                      // No more bits in word; setup for next word
 381     mask = 1;
 382     for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word
 383   } while( i<s->size );
 384   return max_juint;             // No element, iterated them all
 385 }