Mercurial > hg > graal-compiler
diff src/share/vm/libadt/vectset.cpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | c18cbe5936b8 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/libadt/vectset.cpp Sat Dec 01 00:00:00 2007 +0000 @@ -0,0 +1,390 @@ +/* + * Copyright 1997-2005 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + * + */ + +// Vector Sets - An Abstract Data Type + +#include "incls/_precompiled.incl" +#include "incls/_vectset.cpp.incl" + +// %%%%% includes not needed with AVM framework - Ungar +// #include "port.hpp" +//IMPLEMENTATION +// #include "vectset.hpp" + +// BitsInByte is a lookup table which tells the number of bits that +// are in the looked-up number. It is very useful in VectorSet_Size. + +uint8 bitsInByte[256] = { + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 +}; + +//------------------------------VectorSet-------------------------------------- +// Create a new, empty Set. +VectorSet::VectorSet(Arena *arena) : Set(arena) { + size = 2; // Small initial size + data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32)); + data[0] = 0; // No elements + data[1] = 0; +} + +//------------------------------Construct-------------------------------------- +Set &VectorSet_Construct(Arena *arena) +{ + return *(new VectorSet(arena)); +} + +//------------------------------operator=-------------------------------------- +Set &VectorSet::operator = (const Set &set) +{ + if( &set == this ) return *this; + FREE_FAST(data); + // The cast is a virtual function that checks that "set" is a VectorSet. + slamin(*(set.asVectorSet())); + return *this; +} + +//------------------------------slamin----------------------------------------- +// Initialize one set with another. No regard is made to the existing Set. +void VectorSet::slamin(const VectorSet& s) +{ + size = s.size; // Use new size + data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size + memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array +} + +//------------------------------grow------------------------------------------- +// Expand the existing set to a bigger size +void VectorSet::grow( uint newsize ) +{ + newsize = (newsize+31) >> 5; // Convert to longwords + uint x = size; + while( x < newsize ) x <<= 1; + data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32)); + memset((char *)(data + size), 0, (x - size)*sizeof(uint32)); + size = x; +} + +//------------------------------operator<<=------------------------------------ +// Insert a member into an existing Set. +Set &VectorSet::operator <<= (uint elem) +{ + register uint word = elem >> 5; // Get the longword offset + register uint32 mask = 1L << (elem & 31); // Get bit mask + + if( word >= size ) // Need to grow set? + grow(elem+1); // Then grow it + data[word] |= mask; // Set new bit + return *this; +} + +//------------------------------operator>>=------------------------------------ +// Delete a member from an existing Set. +Set &VectorSet::operator >>= (uint elem) +{ + register uint word = elem >> 5; // Get the longword offset + if( word >= size ) // Beyond the last? + return *this; // Then it's clear & return clear + register uint32 mask = 1L << (elem & 31); // Get bit mask + data[word] &= ~mask; // Clear bit + return *this; +} + +//------------------------------operator&=------------------------------------- +// Intersect one set into another. +VectorSet &VectorSet::operator &= (const VectorSet &s) +{ + // NOTE: The intersection is never any larger than the smallest set. + if( s.size < size ) size = s.size; // Get smaller size + register uint32 *u1 = data; // Pointer to the destination data + register uint32 *u2 = s.data; // Pointer to the source data + for( uint i=0; i<size; i++) // For data in set + *u1++ &= *u2++; // Copy and AND longwords + return *this; // Return set +} + +//------------------------------operator&=------------------------------------- +Set &VectorSet::operator &= (const Set &set) +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + return (*this) &= *(set.asVectorSet()); +} + +//------------------------------operator|=------------------------------------- +// Union one set into another. +VectorSet &VectorSet::operator |= (const VectorSet &s) +{ + // This many words must be unioned + register uint cnt = ((size<s.size)?size:s.size); + register uint32 *u1 = data; // Pointer to the destination data + register uint32 *u2 = s.data; // Pointer to the source data + for( uint i=0; i<cnt; i++) // Copy and OR the two sets + *u1++ |= *u2++; + if( size < s.size ) { // Is set 2 larger than set 1? + // Extend result by larger set + grow(s.size*sizeof(uint32)*8); + memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32)); + } + return *this; // Return result set +} + +//------------------------------operator|=------------------------------------- +Set &VectorSet::operator |= (const Set &set) +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + return (*this) |= *(set.asVectorSet()); +} + +//------------------------------operator-=------------------------------------- +// Difference one set from another. +VectorSet &VectorSet::operator -= (const VectorSet &s) +{ + // This many words must be unioned + register uint cnt = ((size<s.size)?size:s.size); + register uint32 *u1 = data; // Pointer to the destination data + register uint32 *u2 = s.data; // Pointer to the source data + for( uint i=0; i<cnt; i++ ) // For data in set + *u1++ &= ~(*u2++); // A <-- A & ~B with longwords + return *this; // Return new set +} + +//------------------------------operator-=------------------------------------- +Set &VectorSet::operator -= (const Set &set) +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + return (*this) -= *(set.asVectorSet()); +} + +//------------------------------compare---------------------------------------- +// Compute 2 booleans: bits in A not B, bits in B not A. +// Return X0 -- A is not a subset of B +// X1 -- A is a subset of B +// 0X -- B is not a subset of A +// 1X -- B is a subset of A +int VectorSet::compare (const VectorSet &s) const +{ + register uint32 *u1 = data; // Pointer to the destination data + register uint32 *u2 = s.data; // Pointer to the source data + register uint32 AnotB = 0, BnotA = 0; + // This many words must be unioned + register uint cnt = ((size<s.size)?size:s.size); + + // Get bits for both sets + uint i; // Exit value of loop + for( i=0; i<cnt; i++ ) { // For data in BOTH sets + register uint32 A = *u1++; // Data from one guy + register uint32 B = *u2++; // Data from other guy + AnotB |= (A & ~B); // Compute bits in A not B + BnotA |= (B & ~A); // Compute bits in B not A + } + + // Get bits from bigger set + if( size < s.size ) { + for( ; i<s.size; i++ ) // For data in larger set + BnotA |= *u2++; // These bits are in B not A + } else { + for( ; i<size; i++ ) // For data in larger set + AnotB |= *u1++; // These bits are in A not B + } + + // Set & return boolean flags + return ((!BnotA)<<1) + (!AnotB); +} + +//------------------------------operator==------------------------------------- +// Test for set equality +int VectorSet::operator == (const VectorSet &s) const +{ + return compare(s) == 3; // TRUE if A and B are mutual subsets +} + +//------------------------------operator==------------------------------------- +int VectorSet::operator == (const Set &set) const +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + return (*this) == *(set.asVectorSet()); +} + +//------------------------------disjoint--------------------------------------- +// Check for sets being disjoint. +int VectorSet::disjoint(const Set &set) const +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + const VectorSet &s = *(set.asVectorSet()); + + // NOTE: The intersection is never any larger than the smallest set. + register uint small = ((size<s.size)?size:s.size); + register uint32 *u1 = data; // Pointer to the destination data + register uint32 *u2 = s.data; // Pointer to the source data + for( uint i=0; i<small; i++) // For data in set + if( *u1++ & *u2++ ) // If any elements in common + return 0; // Then not disjoint + return 1; // Else disjoint +} + +//------------------------------operator<-------------------------------------- +// Test for strict subset +int VectorSet::operator < (const VectorSet &s) const +{ + return compare(s) == 1; // A subset B, B not subset A +} + +//------------------------------operator<-------------------------------------- +int VectorSet::operator < (const Set &set) const +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + return (*this) < *(set.asVectorSet()); +} + +//------------------------------operator<=------------------------------------- +// Test for subset +int VectorSet::operator <= (const VectorSet &s) const +{ + return compare(s) & 1; // A subset B +} + +//------------------------------operator<=------------------------------------- +int VectorSet::operator <= (const Set &set) const +{ + // The cast is a virtual function that checks that "set" is a VectorSet. + return (*this) <= *(set.asVectorSet()); +} + +//------------------------------operator[]------------------------------------- +// Test for membership. A Zero/Non-Zero value is returned! +int VectorSet::operator[](uint elem) const +{ + register uint word = elem >> 5; // Get the longword offset + if( word >= size ) // Beyond the last? + return 0; // Then it's clear + register uint32 mask = 1L << (elem & 31); // Get bit mask + return ((data[word] & mask))!=0; // Return the sense of the bit +} + +//------------------------------getelem---------------------------------------- +// Get any element from the set. +uint VectorSet::getelem(void) const +{ + uint i; // Exit value of loop + for( i=0; i<size; i++ ) + if( data[i] ) + break; + uint32 word = data[i]; + int j; // Exit value of loop + for( j= -1; word; j++, word>>=1 ); + return (i<<5)+j; +} + +//------------------------------Clear------------------------------------------ +// Clear a set +void VectorSet::Clear(void) +{ + if( size > 100 ) { // Reclaim storage only if huge + FREE_RESOURCE_ARRAY(uint32,data,size); + size = 2; // Small initial size + data = NEW_RESOURCE_ARRAY(uint32,size); + } + memset( data, 0, size*sizeof(uint32) ); +} + +//------------------------------Size------------------------------------------- +// Return number of elements in a Set +uint VectorSet::Size(void) const +{ + uint sum = 0; // Cumulative size so far. + uint8 *currByte = (uint8*)data; + for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process + sum += bitsInByte[*currByte++]; // Add bits in current byte to size. + return sum; +} + +//------------------------------Sort------------------------------------------- +// Sort the elements for the next forall statement +void VectorSet::Sort(void) +{ +} + +//------------------------------hash------------------------------------------- +int VectorSet::hash() const +{ + uint32 _xor = 0; + uint lim = ((size<4)?size:4); + for( uint i = 0; i < lim; i++ ) + _xor ^= data[i]; + return (int)_xor; +} + +//------------------------------iterate---------------------------------------- +SetI_ *VectorSet::iterate(uint &elem) const +{ + VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this)); + elem = foo->next(); + return foo; +} + +//============================================================================= +//------------------------------VSetI_----------------------------------------- +// Initialize the innards of a VectorSet iterator +VSetI_::VSetI_( const VectorSet *vset ) : s(vset) +{ + i = (uint)-1L; + j = (uint)-1L; + mask = (unsigned)(1L<<31); +} + +//------------------------------next------------------------------------------- +// Find and return the next element of a vector set, or return garbage and +// make "VSetI_::test()" fail. +uint VSetI_::next(void) +{ + j++; // Next element in word + mask = (mask & max_jint) << 1;// Next bit in word + do { // Do While still have words + while( mask ) { // While have bits in word + if( s->data[i] & mask ) { // If found a bit + return (i<<5)+j; // Return the bit address + } + j++; // Skip to next bit + mask = (mask & max_jint) << 1; + } + j = 0; // No more bits in word; setup for next word + mask = 1; + for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word + } while( i<s->size ); + return max_juint; // No element, iterated them all +}