1/*
2 * Copyright (c) 1997, 2010, 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
32class SparseSet;
33class VectorSet;
34class ListSet;
35class CoSet;
36
37class ostream;
38class 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--------------------------------------------
114class 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 &) {};
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
206protected:
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};
214typedef Set&((*Set_Constructor)(Arena *arena));
215extern Set &ListSet_Construct(Arena *arena);
216extern Set &VectorSet_Construct(Arena *arena);
217extern 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
227class SetI_ : public ResourceObj {
228protected:
229  friend class SetI;
230  virtual ~SetI_();
231  virtual uint next(void)=0;
232  virtual int test(void)=0;
233};
234
235class SetI {
236protected:
237  SetI_ *impl;
238public:
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
249