30 // Vector Sets - An Abstract Data Type
31 //INTERFACE
32
33 // These sets can grow or shrink, based on the initial size and the largest
34 // element currently in them. Slow and bulky for sparse sets, these sets
35 // are super for dense sets. They are fast and compact when dense.
36
37 // TIME:
38 // O(1) - Insert, Delete, Member, Sort
39 // O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference,
40 // Equal, ChooseMember, Forall
41
42 // SPACE: (max_element)/(8*sizeof(int))
43
44
45 //------------------------------VectorSet--------------------------------------
46 class VectorSet : public Set {
47 friend class VectorSetI; // Friendly iterator class
48 protected:
49 uint size; // Size of data IN LONGWORDS (32bits)
50 uint32 *data; // The data, bit packed
51
52 void slamin( const VectorSet& s ); // Initialize one set with another
53 int compare(const VectorSet &s) const; // Compare set contents
54 void grow(uint newsize); // Grow vector to required bitsize
55
56 public:
57 VectorSet(Arena *arena); // Creates a new, empty set.
58 VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts
59 Set &operator =(const Set &s); // Set clone; deep-copy guts
60 VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts
61 { if( &s != this ) { slamin(s); } return *this; }
62 ~VectorSet() {}
63 Set &clone(void) const { return *(new VectorSet(*this)); }
64
65 Set &operator <<=(uint elem); // Add member to set
66 VectorSet operator << (uint elem) // Add member to new set
67 { VectorSet foo(*this); foo <<= elem; return foo; }
68 Set &operator >>=(uint elem); // Delete member from set
69 VectorSet operator >> (uint elem) // Delete member from new set
70 { VectorSet foo(*this); foo >>= elem; return foo; }
82 VectorSet &operator -=(const VectorSet &s); // Intersect sets into first set
83 Set &operator -=(const Set &s); // Intersect sets into first set
84 VectorSet operator - (const VectorSet &s) const
85 { VectorSet foo(*this); foo -= s; return foo; }
86
87 int operator ==(const VectorSet &s) const; // True if sets are equal
88 int operator ==(const Set &s) const; // True if sets are equal
89 int operator < (const VectorSet &s) const; // True if strict subset
90 int operator < (const Set &s) const; // True if strict subset
91 int operator <=(const VectorSet &s) const; // True if subset relation holds.
92 int operator <=(const Set &s) const; // True if subset relation holds.
93 int disjoint (const Set &s) const; // True if sets are disjoint
94
95 int operator [](uint elem) const; // Test for membership
96 uint getelem(void) const; // Return a random element
97 void Clear(void); // Clear a set
98 uint Size(void) const; // Number of elements in the Set.
99 void Sort(void); // Sort before iterating
100 int hash() const; // Hash function
101 void Reset(void) { // Reset a set
102 memset( data, 0, size*sizeof(uint32) );
103 }
104
105 /* Removed for MCC BUG
106 operator const VectorSet* (void) const { return this; } */
107 const VectorSet *asVectorSet() const { return this; }
108
109 // Expose internals for speed-critical fast iterators
110 uint word_size() const { return size; }
111 uint32 *EXPOSE() const { return data; }
112
113 // Fast inlined "test and set". Replaces the idiom:
114 // if( visited[idx] ) return;
115 // visited <<= idx;
116 // With:
117 // if( visited.test_set(idx) ) return;
118 //
119 int test_set( uint elem ) {
120 uint word = elem >> 5; // Get the longword offset
121 if( word >= size ) // Beyond the last?
122 return test_set_grow(elem); // Then grow; set; return 0;
123 uint32 mask = 1L << (elem & 31); // Get bit mask
124 uint32 datum = data[word] & mask;// Get bit
125 data[word] |= mask; // Set bit
126 return datum; // Return bit
127 }
128 int test_set_grow( uint elem ) { // Insert & return 0;
129 (*this) <<= elem; // Insert into set
130 return 0; // Return 0!
131 }
132
133 // Fast inlined test
134 int test( uint elem ) const {
135 uint word = elem >> 5; // Get the longword offset
136 if( word >= size ) return 0; // Beyond the last?
137 uint32 mask = 1L << (elem & 31); // Get bit mask
138 return data[word] & mask; // Get bit
139 }
140
141 // Fast inlined set
142 void set( uint elem ) {
143 uint word = elem >> 5; // Get the longword offset
144 if( word >= size ) { // Beyond the last?
145 test_set_grow(elem); // Then grow and set
146 } else {
147 uint32 mask = 1L << (elem & 31); // Get bit mask
148 data[word] |= mask; // Set bit
149 }
150 }
151
152
153 private:
154 SetI_ *iterate(uint&) const;
155 };
156
157 //------------------------------Iteration--------------------------------------
158 // Loop thru all elements of the set, setting "elem" to the element numbers
159 // in random order. Inserted or deleted elements during this operation may
160 // or may not be iterated over; untouched elements will be affected once.
161 // Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; }
162
163 class VectorSetI : public StackObj {
164 friend class VectorSet;
165 const VectorSet *s;
166 uint i, j;
167 uint32 mask;
168 uint next(void);
169
170 public:
171 uint elem; // The publically accessible element
172
173 VectorSetI( const VectorSet *vset ) :
174 s(vset),
175 i((uint)-1L),
176 j((uint)-1L),
177 mask((unsigned)(1L<<31)) {
178 elem = next();
179 }
180
181 void operator ++(void) { elem = next(); }
182 int test(void) { return i < s->size; }
183 };
184
185 #endif // SHARE_VM_LIBADT_VECTSET_HPP
|
30 // Vector Sets - An Abstract Data Type
31 //INTERFACE
32
33 // These sets can grow or shrink, based on the initial size and the largest
34 // element currently in them. Slow and bulky for sparse sets, these sets
35 // are super for dense sets. They are fast and compact when dense.
36
37 // TIME:
38 // O(1) - Insert, Delete, Member, Sort
39 // O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference,
40 // Equal, ChooseMember, Forall
41
42 // SPACE: (max_element)/(8*sizeof(int))
43
44
45 //------------------------------VectorSet--------------------------------------
46 class VectorSet : public Set {
47 friend class VectorSetI; // Friendly iterator class
48 protected:
49 uint size; // Size of data IN LONGWORDS (32bits)
50 uint32_t* data; // The data, bit packed
51
52 void slamin( const VectorSet& s ); // Initialize one set with another
53 int compare(const VectorSet &s) const; // Compare set contents
54 void grow(uint newsize); // Grow vector to required bitsize
55
56 public:
57 VectorSet(Arena *arena); // Creates a new, empty set.
58 VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts
59 Set &operator =(const Set &s); // Set clone; deep-copy guts
60 VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts
61 { if( &s != this ) { slamin(s); } return *this; }
62 ~VectorSet() {}
63 Set &clone(void) const { return *(new VectorSet(*this)); }
64
65 Set &operator <<=(uint elem); // Add member to set
66 VectorSet operator << (uint elem) // Add member to new set
67 { VectorSet foo(*this); foo <<= elem; return foo; }
68 Set &operator >>=(uint elem); // Delete member from set
69 VectorSet operator >> (uint elem) // Delete member from new set
70 { VectorSet foo(*this); foo >>= elem; return foo; }
82 VectorSet &operator -=(const VectorSet &s); // Intersect sets into first set
83 Set &operator -=(const Set &s); // Intersect sets into first set
84 VectorSet operator - (const VectorSet &s) const
85 { VectorSet foo(*this); foo -= s; return foo; }
86
87 int operator ==(const VectorSet &s) const; // True if sets are equal
88 int operator ==(const Set &s) const; // True if sets are equal
89 int operator < (const VectorSet &s) const; // True if strict subset
90 int operator < (const Set &s) const; // True if strict subset
91 int operator <=(const VectorSet &s) const; // True if subset relation holds.
92 int operator <=(const Set &s) const; // True if subset relation holds.
93 int disjoint (const Set &s) const; // True if sets are disjoint
94
95 int operator [](uint elem) const; // Test for membership
96 uint getelem(void) const; // Return a random element
97 void Clear(void); // Clear a set
98 uint Size(void) const; // Number of elements in the Set.
99 void Sort(void); // Sort before iterating
100 int hash() const; // Hash function
101 void Reset(void) { // Reset a set
102 memset( data, 0, size*sizeof(uint32_t) );
103 }
104
105 /* Removed for MCC BUG
106 operator const VectorSet* (void) const { return this; } */
107 const VectorSet *asVectorSet() const { return this; }
108
109 // Expose internals for speed-critical fast iterators
110 uint word_size() const { return size; }
111 uint32_t* EXPOSE() const { return data; }
112
113 // Fast inlined "test and set". Replaces the idiom:
114 // if( visited[idx] ) return;
115 // visited <<= idx;
116 // With:
117 // if( visited.test_set(idx) ) return;
118 //
119 int test_set( uint elem ) {
120 uint word = elem >> 5; // Get the longword offset
121 if( word >= size ) // Beyond the last?
122 return test_set_grow(elem); // Then grow; set; return 0;
123 uint32_t mask = 1L << (elem & 31); // Get bit mask
124 uint32_t datum = data[word] & mask;// Get bit
125 data[word] |= mask; // Set bit
126 return datum; // Return bit
127 }
128 int test_set_grow( uint elem ) { // Insert & return 0;
129 (*this) <<= elem; // Insert into set
130 return 0; // Return 0!
131 }
132
133 // Fast inlined test
134 int test( uint elem ) const {
135 uint word = elem >> 5; // Get the longword offset
136 if( word >= size ) return 0; // Beyond the last?
137 uint32_t mask = 1L << (elem & 31); // Get bit mask
138 return data[word] & mask; // Get bit
139 }
140
141 // Fast inlined set
142 void set( uint elem ) {
143 uint word = elem >> 5; // Get the longword offset
144 if( word >= size ) { // Beyond the last?
145 test_set_grow(elem); // Then grow and set
146 } else {
147 uint32_t mask = 1L << (elem & 31); // Get bit mask
148 data[word] |= mask; // Set bit
149 }
150 }
151
152
153 private:
154 SetI_ *iterate(uint&) const;
155 };
156
157 //------------------------------Iteration--------------------------------------
158 // Loop thru all elements of the set, setting "elem" to the element numbers
159 // in random order. Inserted or deleted elements during this operation may
160 // or may not be iterated over; untouched elements will be affected once.
161 // Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; }
162
163 class VectorSetI : public StackObj {
164 friend class VectorSet;
165 const VectorSet *s;
166 uint i, j;
167 uint32_t mask;
168 uint next(void);
169
170 public:
171 uint elem; // The publically accessible element
172
173 VectorSetI( const VectorSet *vset ) :
174 s(vset),
175 i((uint)-1L),
176 j((uint)-1L),
177 mask((unsigned)(1L<<31)) {
178 elem = next();
179 }
180
181 void operator ++(void) { elem = next(); }
182 int test(void) { return i < s->size; }
183 };
184
185 #endif // SHARE_VM_LIBADT_VECTSET_HPP
|