1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/libadt/vectset.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,390 @@
1.4 +/*
1.5 + * Copyright 1997-2005 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Vector Sets - An Abstract Data Type
1.29 +
1.30 +#include "incls/_precompiled.incl"
1.31 +#include "incls/_vectset.cpp.incl"
1.32 +
1.33 +// %%%%% includes not needed with AVM framework - Ungar
1.34 +// #include "port.hpp"
1.35 +//IMPLEMENTATION
1.36 +// #include "vectset.hpp"
1.37 +
1.38 +// BitsInByte is a lookup table which tells the number of bits that
1.39 +// are in the looked-up number. It is very useful in VectorSet_Size.
1.40 +
1.41 +uint8 bitsInByte[256] = {
1.42 + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1.43 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.44 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.45 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.46 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.47 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.48 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.49 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.50 + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1.51 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.52 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.53 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.54 + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1.55 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.56 + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1.57 + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
1.58 +};
1.59 +
1.60 +//------------------------------VectorSet--------------------------------------
1.61 +// Create a new, empty Set.
1.62 +VectorSet::VectorSet(Arena *arena) : Set(arena) {
1.63 + size = 2; // Small initial size
1.64 + data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32));
1.65 + data[0] = 0; // No elements
1.66 + data[1] = 0;
1.67 +}
1.68 +
1.69 +//------------------------------Construct--------------------------------------
1.70 +Set &VectorSet_Construct(Arena *arena)
1.71 +{
1.72 + return *(new VectorSet(arena));
1.73 +}
1.74 +
1.75 +//------------------------------operator=--------------------------------------
1.76 +Set &VectorSet::operator = (const Set &set)
1.77 +{
1.78 + if( &set == this ) return *this;
1.79 + FREE_FAST(data);
1.80 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.81 + slamin(*(set.asVectorSet()));
1.82 + return *this;
1.83 +}
1.84 +
1.85 +//------------------------------slamin-----------------------------------------
1.86 +// Initialize one set with another. No regard is made to the existing Set.
1.87 +void VectorSet::slamin(const VectorSet& s)
1.88 +{
1.89 + size = s.size; // Use new size
1.90 + data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size
1.91 + memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array
1.92 +}
1.93 +
1.94 +//------------------------------grow-------------------------------------------
1.95 +// Expand the existing set to a bigger size
1.96 +void VectorSet::grow( uint newsize )
1.97 +{
1.98 + newsize = (newsize+31) >> 5; // Convert to longwords
1.99 + uint x = size;
1.100 + while( x < newsize ) x <<= 1;
1.101 + data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32));
1.102 + memset((char *)(data + size), 0, (x - size)*sizeof(uint32));
1.103 + size = x;
1.104 +}
1.105 +
1.106 +//------------------------------operator<<=------------------------------------
1.107 +// Insert a member into an existing Set.
1.108 +Set &VectorSet::operator <<= (uint elem)
1.109 +{
1.110 + register uint word = elem >> 5; // Get the longword offset
1.111 + register uint32 mask = 1L << (elem & 31); // Get bit mask
1.112 +
1.113 + if( word >= size ) // Need to grow set?
1.114 + grow(elem+1); // Then grow it
1.115 + data[word] |= mask; // Set new bit
1.116 + return *this;
1.117 +}
1.118 +
1.119 +//------------------------------operator>>=------------------------------------
1.120 +// Delete a member from an existing Set.
1.121 +Set &VectorSet::operator >>= (uint elem)
1.122 +{
1.123 + register uint word = elem >> 5; // Get the longword offset
1.124 + if( word >= size ) // Beyond the last?
1.125 + return *this; // Then it's clear & return clear
1.126 + register uint32 mask = 1L << (elem & 31); // Get bit mask
1.127 + data[word] &= ~mask; // Clear bit
1.128 + return *this;
1.129 +}
1.130 +
1.131 +//------------------------------operator&=-------------------------------------
1.132 +// Intersect one set into another.
1.133 +VectorSet &VectorSet::operator &= (const VectorSet &s)
1.134 +{
1.135 + // NOTE: The intersection is never any larger than the smallest set.
1.136 + if( s.size < size ) size = s.size; // Get smaller size
1.137 + register uint32 *u1 = data; // Pointer to the destination data
1.138 + register uint32 *u2 = s.data; // Pointer to the source data
1.139 + for( uint i=0; i<size; i++) // For data in set
1.140 + *u1++ &= *u2++; // Copy and AND longwords
1.141 + return *this; // Return set
1.142 +}
1.143 +
1.144 +//------------------------------operator&=-------------------------------------
1.145 +Set &VectorSet::operator &= (const Set &set)
1.146 +{
1.147 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.148 + return (*this) &= *(set.asVectorSet());
1.149 +}
1.150 +
1.151 +//------------------------------operator|=-------------------------------------
1.152 +// Union one set into another.
1.153 +VectorSet &VectorSet::operator |= (const VectorSet &s)
1.154 +{
1.155 + // This many words must be unioned
1.156 + register uint cnt = ((size<s.size)?size:s.size);
1.157 + register uint32 *u1 = data; // Pointer to the destination data
1.158 + register uint32 *u2 = s.data; // Pointer to the source data
1.159 + for( uint i=0; i<cnt; i++) // Copy and OR the two sets
1.160 + *u1++ |= *u2++;
1.161 + if( size < s.size ) { // Is set 2 larger than set 1?
1.162 + // Extend result by larger set
1.163 + grow(s.size*sizeof(uint32)*8);
1.164 + memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32));
1.165 + }
1.166 + return *this; // Return result set
1.167 +}
1.168 +
1.169 +//------------------------------operator|=-------------------------------------
1.170 +Set &VectorSet::operator |= (const Set &set)
1.171 +{
1.172 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.173 + return (*this) |= *(set.asVectorSet());
1.174 +}
1.175 +
1.176 +//------------------------------operator-=-------------------------------------
1.177 +// Difference one set from another.
1.178 +VectorSet &VectorSet::operator -= (const VectorSet &s)
1.179 +{
1.180 + // This many words must be unioned
1.181 + register uint cnt = ((size<s.size)?size:s.size);
1.182 + register uint32 *u1 = data; // Pointer to the destination data
1.183 + register uint32 *u2 = s.data; // Pointer to the source data
1.184 + for( uint i=0; i<cnt; i++ ) // For data in set
1.185 + *u1++ &= ~(*u2++); // A <-- A & ~B with longwords
1.186 + return *this; // Return new set
1.187 +}
1.188 +
1.189 +//------------------------------operator-=-------------------------------------
1.190 +Set &VectorSet::operator -= (const Set &set)
1.191 +{
1.192 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.193 + return (*this) -= *(set.asVectorSet());
1.194 +}
1.195 +
1.196 +//------------------------------compare----------------------------------------
1.197 +// Compute 2 booleans: bits in A not B, bits in B not A.
1.198 +// Return X0 -- A is not a subset of B
1.199 +// X1 -- A is a subset of B
1.200 +// 0X -- B is not a subset of A
1.201 +// 1X -- B is a subset of A
1.202 +int VectorSet::compare (const VectorSet &s) const
1.203 +{
1.204 + register uint32 *u1 = data; // Pointer to the destination data
1.205 + register uint32 *u2 = s.data; // Pointer to the source data
1.206 + register uint32 AnotB = 0, BnotA = 0;
1.207 + // This many words must be unioned
1.208 + register uint cnt = ((size<s.size)?size:s.size);
1.209 +
1.210 + // Get bits for both sets
1.211 + uint i; // Exit value of loop
1.212 + for( i=0; i<cnt; i++ ) { // For data in BOTH sets
1.213 + register uint32 A = *u1++; // Data from one guy
1.214 + register uint32 B = *u2++; // Data from other guy
1.215 + AnotB |= (A & ~B); // Compute bits in A not B
1.216 + BnotA |= (B & ~A); // Compute bits in B not A
1.217 + }
1.218 +
1.219 + // Get bits from bigger set
1.220 + if( size < s.size ) {
1.221 + for( ; i<s.size; i++ ) // For data in larger set
1.222 + BnotA |= *u2++; // These bits are in B not A
1.223 + } else {
1.224 + for( ; i<size; i++ ) // For data in larger set
1.225 + AnotB |= *u1++; // These bits are in A not B
1.226 + }
1.227 +
1.228 + // Set & return boolean flags
1.229 + return ((!BnotA)<<1) + (!AnotB);
1.230 +}
1.231 +
1.232 +//------------------------------operator==-------------------------------------
1.233 +// Test for set equality
1.234 +int VectorSet::operator == (const VectorSet &s) const
1.235 +{
1.236 + return compare(s) == 3; // TRUE if A and B are mutual subsets
1.237 +}
1.238 +
1.239 +//------------------------------operator==-------------------------------------
1.240 +int VectorSet::operator == (const Set &set) const
1.241 +{
1.242 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.243 + return (*this) == *(set.asVectorSet());
1.244 +}
1.245 +
1.246 +//------------------------------disjoint---------------------------------------
1.247 +// Check for sets being disjoint.
1.248 +int VectorSet::disjoint(const Set &set) const
1.249 +{
1.250 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.251 + const VectorSet &s = *(set.asVectorSet());
1.252 +
1.253 + // NOTE: The intersection is never any larger than the smallest set.
1.254 + register uint small = ((size<s.size)?size:s.size);
1.255 + register uint32 *u1 = data; // Pointer to the destination data
1.256 + register uint32 *u2 = s.data; // Pointer to the source data
1.257 + for( uint i=0; i<small; i++) // For data in set
1.258 + if( *u1++ & *u2++ ) // If any elements in common
1.259 + return 0; // Then not disjoint
1.260 + return 1; // Else disjoint
1.261 +}
1.262 +
1.263 +//------------------------------operator<--------------------------------------
1.264 +// Test for strict subset
1.265 +int VectorSet::operator < (const VectorSet &s) const
1.266 +{
1.267 + return compare(s) == 1; // A subset B, B not subset A
1.268 +}
1.269 +
1.270 +//------------------------------operator<--------------------------------------
1.271 +int VectorSet::operator < (const Set &set) const
1.272 +{
1.273 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.274 + return (*this) < *(set.asVectorSet());
1.275 +}
1.276 +
1.277 +//------------------------------operator<=-------------------------------------
1.278 +// Test for subset
1.279 +int VectorSet::operator <= (const VectorSet &s) const
1.280 +{
1.281 + return compare(s) & 1; // A subset B
1.282 +}
1.283 +
1.284 +//------------------------------operator<=-------------------------------------
1.285 +int VectorSet::operator <= (const Set &set) const
1.286 +{
1.287 + // The cast is a virtual function that checks that "set" is a VectorSet.
1.288 + return (*this) <= *(set.asVectorSet());
1.289 +}
1.290 +
1.291 +//------------------------------operator[]-------------------------------------
1.292 +// Test for membership. A Zero/Non-Zero value is returned!
1.293 +int VectorSet::operator[](uint elem) const
1.294 +{
1.295 + register uint word = elem >> 5; // Get the longword offset
1.296 + if( word >= size ) // Beyond the last?
1.297 + return 0; // Then it's clear
1.298 + register uint32 mask = 1L << (elem & 31); // Get bit mask
1.299 + return ((data[word] & mask))!=0; // Return the sense of the bit
1.300 +}
1.301 +
1.302 +//------------------------------getelem----------------------------------------
1.303 +// Get any element from the set.
1.304 +uint VectorSet::getelem(void) const
1.305 +{
1.306 + uint i; // Exit value of loop
1.307 + for( i=0; i<size; i++ )
1.308 + if( data[i] )
1.309 + break;
1.310 + uint32 word = data[i];
1.311 + int j; // Exit value of loop
1.312 + for( j= -1; word; j++, word>>=1 );
1.313 + return (i<<5)+j;
1.314 +}
1.315 +
1.316 +//------------------------------Clear------------------------------------------
1.317 +// Clear a set
1.318 +void VectorSet::Clear(void)
1.319 +{
1.320 + if( size > 100 ) { // Reclaim storage only if huge
1.321 + FREE_RESOURCE_ARRAY(uint32,data,size);
1.322 + size = 2; // Small initial size
1.323 + data = NEW_RESOURCE_ARRAY(uint32,size);
1.324 + }
1.325 + memset( data, 0, size*sizeof(uint32) );
1.326 +}
1.327 +
1.328 +//------------------------------Size-------------------------------------------
1.329 +// Return number of elements in a Set
1.330 +uint VectorSet::Size(void) const
1.331 +{
1.332 + uint sum = 0; // Cumulative size so far.
1.333 + uint8 *currByte = (uint8*)data;
1.334 + for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process
1.335 + sum += bitsInByte[*currByte++]; // Add bits in current byte to size.
1.336 + return sum;
1.337 +}
1.338 +
1.339 +//------------------------------Sort-------------------------------------------
1.340 +// Sort the elements for the next forall statement
1.341 +void VectorSet::Sort(void)
1.342 +{
1.343 +}
1.344 +
1.345 +//------------------------------hash-------------------------------------------
1.346 +int VectorSet::hash() const
1.347 +{
1.348 + uint32 _xor = 0;
1.349 + uint lim = ((size<4)?size:4);
1.350 + for( uint i = 0; i < lim; i++ )
1.351 + _xor ^= data[i];
1.352 + return (int)_xor;
1.353 +}
1.354 +
1.355 +//------------------------------iterate----------------------------------------
1.356 +SetI_ *VectorSet::iterate(uint &elem) const
1.357 +{
1.358 + VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this));
1.359 + elem = foo->next();
1.360 + return foo;
1.361 +}
1.362 +
1.363 +//=============================================================================
1.364 +//------------------------------VSetI_-----------------------------------------
1.365 +// Initialize the innards of a VectorSet iterator
1.366 +VSetI_::VSetI_( const VectorSet *vset ) : s(vset)
1.367 +{
1.368 + i = (uint)-1L;
1.369 + j = (uint)-1L;
1.370 + mask = (unsigned)(1L<<31);
1.371 +}
1.372 +
1.373 +//------------------------------next-------------------------------------------
1.374 +// Find and return the next element of a vector set, or return garbage and
1.375 +// make "VSetI_::test()" fail.
1.376 +uint VSetI_::next(void)
1.377 +{
1.378 + j++; // Next element in word
1.379 + mask = (mask & max_jint) << 1;// Next bit in word
1.380 + do { // Do While still have words
1.381 + while( mask ) { // While have bits in word
1.382 + if( s->data[i] & mask ) { // If found a bit
1.383 + return (i<<5)+j; // Return the bit address
1.384 + }
1.385 + j++; // Skip to next bit
1.386 + mask = (mask & max_jint) << 1;
1.387 + }
1.388 + j = 0; // No more bits in word; setup for next word
1.389 + mask = 1;
1.390 + for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word
1.391 + } while( i<s->size );
1.392 + return max_juint; // No element, iterated them all
1.393 +}
