1 /*
2 * Copyright (c) 1997, 2018, 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_SET_HPP
26 #define SHARE_VM_LIBADT_SET_HPP
27
28 #include "memory/allocation.hpp"
29
30 // Sets - An Abstract Data Type
31
32 class SparseSet;
33 class VectorSet;
34 class ListSet;
35 class CoSet;
36
37 class ostream;
38 class SetI_;
39
40 // These sets can grow or shrink, based on the initial size and the largest
41 // element currently in them. Basically, they allow a bunch of bits to be
42 // grouped together, tested, set & cleared, intersected, etc. The basic
43 // Set class is an abstract class, and cannot be constructed. Instead,
44 // one of VectorSet, SparseSet, or ListSet is created. Each variation has
45 // different asymptotic running times for different operations, and different
46 // constants of proportionality as well.
47 // {n = number of elements, N = largest element}
48
49 // VectorSet SparseSet ListSet
50 // Create O(N) O(1) O(1)
51 // Clear O(N) O(1) O(1)
52 // Insert O(1) O(1) O(log n)
53 // Delete O(1) O(1) O(log n)
54 // Member O(1) O(1) O(log n)
55 // Size O(N) O(1) O(1)
56 // Copy O(N) O(n) O(n)
57 // Union O(N) O(n) O(n log n)
58 // Intersect O(N) O(n) O(n log n)
59 // Difference O(N) O(n) O(n log n)
60 // Equal O(N) O(n) O(n log n)
61 // ChooseMember O(N) O(1) O(1)
62 // Sort O(1) O(n log n) O(1)
63 // Forall O(N) O(n) O(n)
64 // Complement O(1) O(1) O(1)
65
66 // TIME: N/32 n 8*n Accesses
67 // SPACE: N/8 4*N+4*n 8*n Bytes
68
69 // Create: Make an empty set
70 // Clear: Remove all the elements of a Set
71 // Insert: Insert an element into a Set; duplicates are ignored
72 // Delete: Removes an element from a Set
73 // Member: Tests for membership in a Set
74 // Size: Returns the number of members of a Set
75 // Copy: Copy or assign one Set to another
76 // Union: Union 2 sets together
77 // Intersect: Intersect 2 sets together
78 // Difference: Compute A & !B; remove from set A those elements in set B
79 // Equal: Test for equality between 2 sets
80 // ChooseMember Pick a random member
81 // Sort: If no other operation changes the set membership, a following
82 // Forall will iterate the members in ascending order.
83 // Forall: Iterate over the elements of a Set. Operations that modify
84 // the set membership during iteration work, but the iterator may
85 // skip any member or duplicate any member.
86 // Complement: Only supported in the Co-Set variations. It adds a small
87 // constant-time test to every Set operation.
88 //
89 // PERFORMANCE ISSUES:
90 // If you "cast away" the specific set variation you are using, and then do
91 // operations on the basic "Set" object you will pay a virtual function call
92 // to get back the specific set variation. On the other hand, using the
93 // generic Set means you can change underlying implementations by just
94 // changing the initial declaration. Examples:
95 // void foo(VectorSet vs1, VectorSet vs2) { vs1 |= vs2; }
96 // "foo" must be called with a VectorSet. The vector set union operation
97 // is called directly.
98 // void foo(Set vs1, Set vs2) { vs1 |= vs2; }
99 // "foo" may be called with *any* kind of sets; suppose it is called with
100 // VectorSets. Two virtual function calls are used to figure out the that vs1
101 // and vs2 are VectorSets. In addition, if vs2 is not a VectorSet then a
102 // temporary VectorSet copy of vs2 will be made before the union proceeds.
103 //
104 // VectorSets have a small constant. Time and space are proportional to the
105 // largest element. Fine for dense sets and largest element < 10,000.
106 // SparseSets have a medium constant. Time is proportional to the number of
107 // elements, space is proportional to the largest element.
108 // Fine (but big) with the largest element < 100,000.
109 // ListSets have a big constant. Time *and space* are proportional to the
110 // number of elements. They work well for a few elements of *any* size
111 // (i.e. sets of pointers)!
112
113 //------------------------------Set--------------------------------------------
114 class Set : public ResourceObj {
115 public:
116
117 // Creates a new, empty set.
118 // DO NOT CONSTRUCT A Set. THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY
119 Set(Arena *arena) : _set_arena(arena) {};
120
121 // Creates a new set from an existing set
122 // DO NOT CONSTRUCT A Set. THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY
123 Set(const Set &s) : ResourceObj(s) {};
124
125 // Set assignment; deep-copy guts
126 virtual Set &operator =(const Set &s)=0;
127 virtual Set &clone(void) const=0;
128
129 // Virtual destructor
130 virtual ~Set() {};
131
132 // Add member to set
133 virtual Set &operator <<=(uint elem)=0;
134 // virtual Set operator << (uint elem);
135
136 // Delete member from set
137 virtual Set &operator >>=(uint elem)=0;
138 // virtual Set operator >> (uint elem);
139
140 // Membership test. Result is Zero (absent)/ Non-Zero (present)
141 virtual int operator [](uint elem) const=0;
142
143 // Intersect sets
144 virtual Set &operator &=(const Set &s)=0;
145 // virtual Set operator & (const Set &s) const;
146
147 // Union sets
148 virtual Set &operator |=(const Set &s)=0;
149 // virtual Set operator | (const Set &s) const;
150
151 // Difference sets
152 virtual Set &operator -=(const Set &s)=0;
153 // virtual Set operator - (const Set &s) const;
154
155 // Tests for equality. Result is Zero (false)/ Non-Zero (true)
156 virtual int operator ==(const Set &s) const=0;
157 int operator !=(const Set &s) const { return !(*this == s); }
158 virtual int disjoint(const Set &s) const=0;
159
160 // Tests for strict subset. Result is Zero (false)/ Non-Zero (true)
161 virtual int operator < (const Set &s) const=0;
162 int operator > (const Set &s) const { return s < *this; }
163
164 // Tests for subset. Result is Zero (false)/ Non-Zero (true)
165 virtual int operator <=(const Set &s) const=0;
166 int operator >=(const Set &s) const { return s <= *this; }
167
168 // Return any member of the Set. Undefined if the Set is empty.
169 virtual uint getelem(void) const=0;
170
171 // Clear all the elements in the Set
172 virtual void Clear(void)=0;
173
174 // Return the number of members in the Set
175 virtual uint Size(void) const=0;
176
177 // If an iterator follows a "Sort()" without any Set-modifying operations
178 // inbetween then the iterator will visit the elements in ascending order.
179 virtual void Sort(void)=0;
180
181 // Convert a set to printable string in an allocated buffer.
182 // The caller must deallocate the string.
183 virtual char *setstr(void) const;
184
185 // Print the Set on "stdout". Can be conveniently called in the debugger
186 void print() const;
187
188 // Parse text from the string into the Set. Return length parsed.
189 virtual int parse(const char *s);
190
191 // Convert a generic Set to a specific Set
192 /* Removed for MCC BUG
193 virtual operator const SparseSet* (void) const;
194 virtual operator const VectorSet* (void) const;
195 virtual operator const ListSet * (void) const;
196 virtual operator const CoSet * (void) const; */
197 virtual const SparseSet *asSparseSet(void) const;
198 virtual const VectorSet *asVectorSet(void) const;
199 virtual const ListSet *asListSet (void) const;
200 virtual const CoSet *asCoSet (void) const;
201
202 // Hash the set. Sets of different types but identical elements will NOT
203 // hash the same. Same set type, same elements WILL hash the same.
204 virtual int hash() const = 0;
205
206 protected:
207 friend class SetI;
208 friend class CoSet;
209 virtual class SetI_ *iterate(uint&) const=0;
210
211 // Need storeage for the set
212 Arena *_set_arena;
213 };
214 typedef Set&((*Set_Constructor)(Arena *arena));
215 extern Set &ListSet_Construct(Arena *arena);
216 extern Set &VectorSet_Construct(Arena *arena);
217 extern Set &SparseSet_Construct(Arena *arena);
218
219 //------------------------------Iteration--------------------------------------
220 // Loop thru all elements of the set, setting "elem" to the element numbers
221 // in random order. Inserted or deleted elements during this operation may
222 // or may not be iterated over; untouched elements will be affected once.
223
224 // Usage: for( SetI i(s); i.test(); i++ ) { body = i.elem; } ...OR...
225 // for( i.reset(s); i.test(); i++ ) { body = i.elem; }
226
227 class SetI_ : public ResourceObj {
228 protected:
229 friend class SetI;
230 virtual ~SetI_();
231 virtual uint next(void)=0;
232 virtual int test(void)=0;
233 };
234
235 class SetI {
236 protected:
237 SetI_ *impl;
238 public:
239 uint elem; // The publically accessible element
240
241 SetI( const Set *s ) { impl = s->iterate(elem); }
242 ~SetI() { delete impl; }
243 void reset( const Set *s ) { delete impl; impl = s->iterate(elem); }
244 void operator ++(void) { elem = impl->next(); }
245 int test(void) { return impl->test(); }
246 };
247
248 #endif // SHARE_VM_LIBADT_SET_HPP