Mercurial > hg > truffle
diff src/share/vm/libadt/vectset.hpp @ 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.hpp Sat Dec 01 00:00:00 2007 +0000 @@ -0,0 +1,176 @@ +/* + * Copyright 1997 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. + * + */ + +#ifndef _VECTOR_SET_ +#define _VECTOR_SET_ +// Vector Sets - An Abstract Data Type +//INTERFACE + +// These sets can grow or shrink, based on the initial size and the largest +// element currently in them. Slow and bulky for sparse sets, these sets +// are super for dense sets. They are fast and compact when dense. + +// TIME: +// O(1) - Insert, Delete, Member, Sort +// O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference, +// Equal, ChooseMember, Forall + +// SPACE: (max_element)/(8*sizeof(int)) + + +//------------------------------VectorSet-------------------------------------- +class VectorSet : public Set { +friend class VectorSetI; // Friendly iterator class +protected: + uint size; // Size of data IN LONGWORDS (32bits) + uint32 *data; // The data, bit packed + + void slamin( const VectorSet& s ); // Initialize one set with another + int compare(const VectorSet &s) const; // Compare set contents + void grow(uint newsize); // Grow vector to required bitsize + +public: + VectorSet(Arena *arena); // Creates a new, empty set. + VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts + Set &operator =(const Set &s); // Set clone; deep-copy guts + VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts + { if( &s != this ) { slamin(s); } return *this; } + ~VectorSet() {} + Set &clone(void) const { return *(new VectorSet(*this)); } + + Set &operator <<=(uint elem); // Add member to set + VectorSet operator << (uint elem) // Add member to new set + { VectorSet foo(*this); foo <<= elem; return foo; } + Set &operator >>=(uint elem); // Delete member from set + VectorSet operator >> (uint elem) // Delete member from new set + { VectorSet foo(*this); foo >>= elem; return foo; } + + VectorSet &operator &=(const VectorSet &s); // Intersect sets into first set + Set &operator &=(const Set &s); // Intersect sets into first set + VectorSet operator & (const VectorSet &s) const + { VectorSet foo(*this); foo &= s; return foo; } + + VectorSet &operator |=(const VectorSet &s); // Intersect sets into first set + Set &operator |=(const Set &s); // Intersect sets into first set + VectorSet operator | (const VectorSet &s) const + { VectorSet foo(*this); foo |= s; return foo; } + + VectorSet &operator -=(const VectorSet &s); // Intersect sets into first set + Set &operator -=(const Set &s); // Intersect sets into first set + VectorSet operator - (const VectorSet &s) const + { VectorSet foo(*this); foo -= s; return foo; } + + int operator ==(const VectorSet &s) const; // True if sets are equal + int operator ==(const Set &s) const; // True if sets are equal + int operator < (const VectorSet &s) const; // True if strict subset + int operator < (const Set &s) const; // True if strict subset + int operator <=(const VectorSet &s) const; // True if subset relation holds. + int operator <=(const Set &s) const; // True if subset relation holds. + int disjoint (const Set &s) const; // True if sets are disjoint + + int operator [](uint elem) const; // Test for membership + uint getelem(void) const; // Return a random element + void Clear(void); // Clear a set + uint Size(void) const; // Number of elements in the Set. + void Sort(void); // Sort before iterating + int hash() const; // Hash function + + /* Removed for MCC BUG + operator const VectorSet* (void) const { return this; } */ + const VectorSet *asVectorSet() const { return this; } + + // Expose internals for speed-critical fast iterators + uint word_size() const { return size; } + uint32 *EXPOSE() const { return data; } + + // Fast inlined "test and set". Replaces the idiom: + // if( visited[idx] ) return; + // visited <<= idx; + // With: + // if( visited.test_set(idx) ) return; + // + int test_set( uint elem ) { + uint word = elem >> 5; // Get the longword offset + if( word >= size ) // Beyond the last? + return test_set_grow(elem); // Then grow; set; return 0; + uint32 mask = 1L << (elem & 31); // Get bit mask + uint32 datum = data[word] & mask;// Get bit + data[word] |= mask; // Set bit + return datum; // Return bit + } + int test_set_grow( uint elem ) { // Insert & return 0; + (*this) <<= elem; // Insert into set + return 0; // Return 0! + } + + // Fast inlined test + int test( uint elem ) const { + uint word = elem >> 5; // Get the longword offset + if( word >= size ) return 0; // Beyond the last? + uint32 mask = 1L << (elem & 31); // Get bit mask + return data[word] & mask; // Get bit + } + + // Fast inlined set + void set( uint elem ) { + uint word = elem >> 5; // Get the longword offset + if( word >= size ) { // Beyond the last? + test_set_grow(elem); // Then grow and set + } else { + uint32 mask = 1L << (elem & 31); // Get bit mask + data[word] |= mask; // Set bit + } + } + + +private: + friend class VSetI_; + SetI_ *iterate(uint&) const; +}; + +//------------------------------Iteration-------------------------------------- +// Loop thru all elements of the set, setting "elem" to the element numbers +// in random order. Inserted or deleted elements during this operation may +// or may not be iterated over; untouched elements will be affected once. +// Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; } + +class VSetI_ : public SetI_ { + friend class VectorSet; + friend class VectorSetI; + const VectorSet *s; + uint i, j; + uint32 mask; + VSetI_(const VectorSet *vset); + uint next(void); + int test(void) { return i < s->size; } +}; + +class VectorSetI : public SetI { +public: + VectorSetI( const VectorSet *s ) : SetI(s) { } + void operator ++(void) { elem = ((VSetI_*)impl)->next(); } + int test(void) { return ((VSetI_*)impl)->test(); } +}; + +#endif // _VECTOR_SET_