| /* |
| * Copyright (c) 1997, 2011, 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. |
| * |
| */ |
| |
| #ifndef SHARE_VM_LIBADT_VECTSET_HPP |
| #define SHARE_VM_LIBADT_VECTSET_HPP |
| |
| #include "libadt/set.hpp" |
| |
| #define BITS_IN_BYTE_ARRAY_SIZE 256 |
| |
| // 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_t* 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 |
| void Reset(void) { // Reset a set |
| memset( data, 0, size*sizeof(uint32_t) ); |
| } |
| |
| /* 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_t* 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_t mask = 1L << (elem & 31); // Get bit mask |
| uint32_t 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_t 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_t mask = 1L << (elem & 31); // Get bit mask |
| data[word] |= mask; // Set bit |
| } |
| } |
| |
| |
| private: |
| 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 VectorSetI : public StackObj { |
| friend class VectorSet; |
| const VectorSet *s; |
| uint i, j; |
| uint32_t mask; |
| uint next(void); |
| |
| public: |
| uint elem; // The publically accessible element |
| |
| VectorSetI( const VectorSet *vset ) : |
| s(vset), |
| i((uint)-1L), |
| j((uint)-1L), |
| mask((unsigned)(1L<<31)) { |
| elem = next(); |
| } |
| |
| void operator ++(void) { elem = next(); } |
| int test(void) { return i < s->size; } |
| }; |
| |
| #endif // SHARE_VM_LIBADT_VECTSET_HPP |