--- a/src/hotspot/share/libadt/vectset.hpp Thu Nov 07 10:28:29 2019 +0000
+++ b/src/hotspot/share/libadt/vectset.hpp Thu Nov 07 12:12:39 2019 +0100
@@ -25,161 +25,85 @@
#ifndef SHARE_LIBADT_VECTSET_HPP
#define SHARE_LIBADT_VECTSET_HPP
-#include "libadt/set.hpp"
+#include "memory/allocation.hpp"
-#define BITS_IN_BYTE_ARRAY_SIZE 256
-
-// Vector Sets - An Abstract Data Type
-//INTERFACE
+// Vector Sets
// 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))
-
+// element currently in them.
//------------------------------VectorSet--------------------------------------
-class VectorSet : public Set {
-friend class VectorSetI; // Friendly iterator class
-protected:
+class VectorSet : public ResourceObj {
+private:
uint size; // Size of data IN LONGWORDS (32bits)
uint32_t* data; // The data, bit packed
+ Arena *_set_arena;
- 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
+ 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(Arena *arena);
~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; }
+ void insert(uint elem);
- 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
- 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) );
+ void clear();
+ bool is_empty() const;
+ int hash() const;
+ void reset() {
+ 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; }
// Fast inlined "test and set". Replaces the idiom:
- // if( visited[idx] ) return;
- // visited <<= idx;
+ // if (visited.test(idx)) return;
+ // visited.set(idx);
// With:
- // if( visited.test_set(idx) ) return;
+ // if (visited.test_set(idx)) return;
//
- int test_set( uint elem ) {
+ 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;
+ if (word >= size) {
+ // Then grow; set; return 0;
+ this->insert(elem);
+ 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
+ int test(uint elem) const {
+ uint word = elem >> 5;
+ if (word >= size) {
+ return 0;
+ }
+ uint32_t mask = 1L << (elem & 31);
+ return data[word] & mask;
+ }
+
+ void remove(uint elem) {
+ uint word = elem >> 5;
+ if (word >= size) {
+ return;
+ }
+ uint32_t mask = 1L << (elem & 31);
+ data[word] &= ~mask; // Clear 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
+ void set(uint elem) {
+ uint word = elem >> 5;
+ if (word >= size) {
+ this->insert(elem);
} else {
- uint32_t mask = 1L << (elem & 31); // Get bit mask
- data[word] |= mask; // Set bit
+ uint32_t mask = 1L << (elem & 31);
+ data[word] |= mask;
}
}
-
-
-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_LIBADT_VECTSET_HPP