Mercurial > hg > truffle
comparison src/share/vm/libadt/vectset.hpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | c18cbe5936b8 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a61af66fc99e |
---|---|
1 /* | |
2 * Copyright 1997 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 * | |
23 */ | |
24 | |
25 #ifndef _VECTOR_SET_ | |
26 #define _VECTOR_SET_ | |
27 // Vector Sets - An Abstract Data Type | |
28 //INTERFACE | |
29 | |
30 // These sets can grow or shrink, based on the initial size and the largest | |
31 // element currently in them. Slow and bulky for sparse sets, these sets | |
32 // are super for dense sets. They are fast and compact when dense. | |
33 | |
34 // TIME: | |
35 // O(1) - Insert, Delete, Member, Sort | |
36 // O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference, | |
37 // Equal, ChooseMember, Forall | |
38 | |
39 // SPACE: (max_element)/(8*sizeof(int)) | |
40 | |
41 | |
42 //------------------------------VectorSet-------------------------------------- | |
43 class VectorSet : public Set { | |
44 friend class VectorSetI; // Friendly iterator class | |
45 protected: | |
46 uint size; // Size of data IN LONGWORDS (32bits) | |
47 uint32 *data; // The data, bit packed | |
48 | |
49 void slamin( const VectorSet& s ); // Initialize one set with another | |
50 int compare(const VectorSet &s) const; // Compare set contents | |
51 void grow(uint newsize); // Grow vector to required bitsize | |
52 | |
53 public: | |
54 VectorSet(Arena *arena); // Creates a new, empty set. | |
55 VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts | |
56 Set &operator =(const Set &s); // Set clone; deep-copy guts | |
57 VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts | |
58 { if( &s != this ) { slamin(s); } return *this; } | |
59 ~VectorSet() {} | |
60 Set &clone(void) const { return *(new VectorSet(*this)); } | |
61 | |
62 Set &operator <<=(uint elem); // Add member to set | |
63 VectorSet operator << (uint elem) // Add member to new set | |
64 { VectorSet foo(*this); foo <<= elem; return foo; } | |
65 Set &operator >>=(uint elem); // Delete member from set | |
66 VectorSet operator >> (uint elem) // Delete member from new set | |
67 { VectorSet foo(*this); foo >>= elem; return foo; } | |
68 | |
69 VectorSet &operator &=(const VectorSet &s); // Intersect sets into first set | |
70 Set &operator &=(const Set &s); // Intersect sets into first set | |
71 VectorSet operator & (const VectorSet &s) const | |
72 { VectorSet foo(*this); foo &= s; 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 int operator ==(const VectorSet &s) const; // True if sets are equal | |
85 int operator ==(const Set &s) const; // True if sets are equal | |
86 int operator < (const VectorSet &s) const; // True if strict subset | |
87 int operator < (const Set &s) const; // True if strict subset | |
88 int operator <=(const VectorSet &s) const; // True if subset relation holds. | |
89 int operator <=(const Set &s) const; // True if subset relation holds. | |
90 int disjoint (const Set &s) const; // True if sets are disjoint | |
91 | |
92 int operator [](uint elem) const; // Test for membership | |
93 uint getelem(void) const; // Return a random element | |
94 void Clear(void); // Clear a set | |
95 uint Size(void) const; // Number of elements in the Set. | |
96 void Sort(void); // Sort before iterating | |
97 int hash() const; // Hash function | |
98 | |
99 /* Removed for MCC BUG | |
100 operator const VectorSet* (void) const { return this; } */ | |
101 const VectorSet *asVectorSet() const { return this; } | |
102 | |
103 // Expose internals for speed-critical fast iterators | |
104 uint word_size() const { return size; } | |
105 uint32 *EXPOSE() const { return data; } | |
106 | |
107 // Fast inlined "test and set". Replaces the idiom: | |
108 // if( visited[idx] ) return; | |
109 // visited <<= idx; | |
110 // With: | |
111 // if( visited.test_set(idx) ) return; | |
112 // | |
113 int test_set( uint elem ) { | |
114 uint word = elem >> 5; // Get the longword offset | |
115 if( word >= size ) // Beyond the last? | |
116 return test_set_grow(elem); // Then grow; set; return 0; | |
117 uint32 mask = 1L << (elem & 31); // Get bit mask | |
118 uint32 datum = data[word] & mask;// Get bit | |
119 data[word] |= mask; // Set bit | |
120 return datum; // Return bit | |
121 } | |
122 int test_set_grow( uint elem ) { // Insert & return 0; | |
123 (*this) <<= elem; // Insert into set | |
124 return 0; // Return 0! | |
125 } | |
126 | |
127 // Fast inlined test | |
128 int test( uint elem ) const { | |
129 uint word = elem >> 5; // Get the longword offset | |
130 if( word >= size ) return 0; // Beyond the last? | |
131 uint32 mask = 1L << (elem & 31); // Get bit mask | |
132 return data[word] & mask; // Get bit | |
133 } | |
134 | |
135 // Fast inlined set | |
136 void set( uint elem ) { | |
137 uint word = elem >> 5; // Get the longword offset | |
138 if( word >= size ) { // Beyond the last? | |
139 test_set_grow(elem); // Then grow and set | |
140 } else { | |
141 uint32 mask = 1L << (elem & 31); // Get bit mask | |
142 data[word] |= mask; // Set bit | |
143 } | |
144 } | |
145 | |
146 | |
147 private: | |
148 friend class VSetI_; | |
149 SetI_ *iterate(uint&) const; | |
150 }; | |
151 | |
152 //------------------------------Iteration-------------------------------------- | |
153 // Loop thru all elements of the set, setting "elem" to the element numbers | |
154 // in random order. Inserted or deleted elements during this operation may | |
155 // or may not be iterated over; untouched elements will be affected once. | |
156 // Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; } | |
157 | |
158 class VSetI_ : public SetI_ { | |
159 friend class VectorSet; | |
160 friend class VectorSetI; | |
161 const VectorSet *s; | |
162 uint i, j; | |
163 uint32 mask; | |
164 VSetI_(const VectorSet *vset); | |
165 uint next(void); | |
166 int test(void) { return i < s->size; } | |
167 }; | |
168 | |
169 class VectorSetI : public SetI { | |
170 public: | |
171 VectorSetI( const VectorSet *s ) : SetI(s) { } | |
172 void operator ++(void) { elem = ((VSetI_*)impl)->next(); } | |
173 int test(void) { return ((VSetI_*)impl)->test(); } | |
174 }; | |
175 | |
176 #endif // _VECTOR_SET_ |