< prev index next >

src/hotspot/share/libadt/vectset.cpp

Print this page
rev 50962 : [mq]: 8207011


  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   register uint word = elem >> 5;            // Get the longword offset
 105   register 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   register 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   register 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   register uint32_t *u1 = data;   // Pointer to the destination data
 132   register 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   register uint cnt = ((size<s.size)?size:s.size);
 151   register uint32_t *u1 = data;   // Pointer to the destination data
 152   register 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   register uint cnt = ((size<s.size)?size:s.size);
 176   register uint32_t *u1 = data;   // Pointer to the destination data
 177   register 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   register uint32_t *u1 = data;   // Pointer to the destination data
 199   register uint32_t *u2 = s.data; // Pointer to the source data
 200   register uint32_t AnotB = 0, BnotA = 0;
 201   // This many words must be unioned
 202   register 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     register uint32_t A = *u1++;  // Data from one guy
 208     register 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   register uint small_size = ((size<s.size)?size:s.size);
 249   register uint32_t *u1 = data;        // Pointer to the destination data
 250   register 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   register uint word = elem >> 5; // Get the longword offset
 290   if( word >= size )              // Beyond the last?
 291     return 0;                     // Then it's clear
 292   register 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)




  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)


< prev index next >