1 /*
2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_LIBADT_VECTSET_HPP
26 #define SHARE_VM_LIBADT_VECTSET_HPP
27
28 #include "libadt/set.hpp"
29
30 #define BITS_IN_BYTE_ARRAY_SIZE 256
31
32 // Vector Sets - An Abstract Data Type
33 //INTERFACE
34
35 // These sets can grow or shrink, based on the initial size and the largest
36 // element currently in them. Slow and bulky for sparse sets, these sets
37 // are super for dense sets. They are fast and compact when dense.
38
39 // TIME:
40 // O(1) - Insert, Delete, Member, Sort
41 // O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference,
42 // Equal, ChooseMember, Forall
43
44 // SPACE: (max_element)/(8*sizeof(int))
45
46
47 //------------------------------VectorSet--------------------------------------
48 class VectorSet : public Set {
49 friend class VectorSetI; // Friendly iterator class
50 protected:
51 uint size; // Size of data IN LONGWORDS (32bits)
52 uint32_t* data; // The data, bit packed
53
54 void slamin( const VectorSet& s ); // Initialize one set with another
55 int compare(const VectorSet &s) const; // Compare set contents
56 void grow(uint newsize); // Grow vector to required bitsize
57
58 public:
59 VectorSet(Arena *arena); // Creates a new, empty set.
60 VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts
61 Set &operator =(const Set &s); // Set clone; deep-copy guts
62 VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts
63 { if( &s != this ) { slamin(s); } return *this; }
64 ~VectorSet() {}
65 Set &clone(void) const { return *(new VectorSet(*this)); }
66
67 Set &operator <<=(uint elem); // Add member to set
68 VectorSet operator << (uint elem) // Add member to new set
69 { VectorSet foo(*this); foo <<= elem; return foo; }
70 Set &operator >>=(uint elem); // Delete member from set
71 VectorSet operator >> (uint elem) // Delete member from new set
72 { VectorSet foo(*this); foo >>= elem; return foo; }
73
74 VectorSet &operator &=(const VectorSet &s); // Intersect sets into first set
75 Set &operator &=(const Set &s); // Intersect sets into first set
76 VectorSet operator & (const VectorSet &s) const
77 { VectorSet foo(*this); foo &= s; return foo; }
78
79 VectorSet &operator |=(const VectorSet &s); // Intersect sets into first set
80 Set &operator |=(const Set &s); // Intersect sets into first set
81 VectorSet operator | (const VectorSet &s) const
82 { VectorSet foo(*this); foo |= s; return foo; }
83
84 VectorSet &operator -=(const VectorSet &s); // Intersect sets into first set
85 Set &operator -=(const Set &s); // Intersect sets into first set
86 VectorSet operator - (const VectorSet &s) const
87 { VectorSet foo(*this); foo -= s; return foo; }
88
89 int operator ==(const VectorSet &s) const; // True if sets are equal
90 int operator ==(const Set &s) const; // True if sets are equal
91 int operator < (const VectorSet &s) const; // True if strict subset
92 int operator < (const Set &s) const; // True if strict subset
93 int operator <=(const VectorSet &s) const; // True if subset relation holds.
94 int operator <=(const Set &s) const; // True if subset relation holds.
95 int disjoint (const Set &s) const; // True if sets are disjoint
96
97 int operator [](uint elem) const; // Test for membership
98 uint getelem(void) const; // Return a random element
99 void Clear(void); // Clear a set
100 uint Size(void) const; // Number of elements in the Set.
101 void Sort(void); // Sort before iterating
102 int hash() const; // Hash function
103 void Reset(void) { // Reset a set
104 memset( data, 0, size*sizeof(uint32_t) );
105 }
106
107 /* Removed for MCC BUG
108 operator const VectorSet* (void) const { return this; } */
109 const VectorSet *asVectorSet() const { return this; }
110
111 // Expose internals for speed-critical fast iterators
112 uint word_size() const { return size; }
113 uint32_t* EXPOSE() const { return data; }
114
115 // Fast inlined "test and set". Replaces the idiom:
116 // if( visited[idx] ) return;
117 // visited <<= idx;
118 // With:
119 // if( visited.test_set(idx) ) return;
120 //
121 int test_set( uint elem ) {
122 uint word = elem >> 5; // Get the longword offset
123 if( word >= size ) // Beyond the last?
124 return test_set_grow(elem); // Then grow; set; return 0;
125 uint32_t mask = 1L << (elem & 31); // Get bit mask
126 uint32_t datum = data[word] & mask;// Get bit
127 data[word] |= mask; // Set bit
128 return datum; // Return bit
129 }
130 int test_set_grow( uint elem ) { // Insert & return 0;
131 (*this) <<= elem; // Insert into set
132 return 0; // Return 0!
133 }
134
135 // Fast inlined test
136 int test( uint elem ) const {
137 uint word = elem >> 5; // Get the longword offset
138 if( word >= size ) return 0; // Beyond the last?
139 uint32_t mask = 1L << (elem & 31); // Get bit mask
140 return data[word] & mask; // Get bit
141 }
142
143 // Fast inlined set
144 void set( uint elem ) {
145 uint word = elem >> 5; // Get the longword offset
146 if( word >= size ) { // Beyond the last?
147 test_set_grow(elem); // Then grow and set
148 } else {
149 uint32_t mask = 1L << (elem & 31); // Get bit mask
150 data[word] |= mask; // Set bit
151 }
152 }
153
154
155 private:
156 SetI_ *iterate(uint&) const;
157 };
158
159 //------------------------------Iteration--------------------------------------
160 // Loop thru all elements of the set, setting "elem" to the element numbers
161 // in random order. Inserted or deleted elements during this operation may
162 // or may not be iterated over; untouched elements will be affected once.
163 // Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; }
164
165 class VectorSetI : public StackObj {
166 friend class VectorSet;
167 const VectorSet *s;
168 uint i, j;
169 uint32_t mask;
170 uint next(void);
171
172 public:
173 uint elem; // The publically accessible element
174
175 VectorSetI( const VectorSet *vset ) :
176 s(vset),
177 i((uint)-1L),
178 j((uint)-1L),
179 mask((unsigned)(1L<<31)) {
180 elem = next();
181 }
182
183 void operator ++(void) { elem = next(); }
184 int test(void) { return i < s->size; }
185 };
186
187 #endif // SHARE_VM_LIBADT_VECTSET_HPP