Mercurial > hg > graal-compiler
view src/share/vm/libadt/vectset.cpp @ 15108:b6711b514576
Remove LoopBeginNode loopBegin() from Loop.
author | Josef Eisl <josef.eisl@jku.at> |
---|---|
date | Wed, 09 Apr 2014 17:38:16 +0200 |
parents | b9a9ed0f8eeb |
children |
line wrap: on
line source
/* * Copyright (c) 1997, 2012, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #include "precompiled.hpp" #include "libadt/vectset.hpp" #include "memory/allocation.inline.hpp" // Vector Sets - An Abstract Data Type // %%%%% 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 = ((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_size; 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---------------------------------------- // Used by Set::print(). class VSetI_ : public SetI_ { VectorSetI vsi; public: VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; } uint next(void) { ++vsi; return vsi.elem; } int test(void) { return vsi.test(); } }; SetI_ *VectorSet::iterate(uint &elem) const { return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem); } //============================================================================= //------------------------------next------------------------------------------- // Find and return the next element of a vector set, or return garbage and // make "VectorSetI::test()" fail. uint VectorSetI::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 }