|
1 /* |
|
2 * Copyright (c) 1997, 2012, 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 #include "precompiled.hpp" |
|
26 #include "libadt/vectset.hpp" |
|
27 #include "memory/allocation.inline.hpp" |
|
28 |
|
29 // Vector Sets - An Abstract Data Type |
|
30 |
|
31 // %%%%% includes not needed with AVM framework - Ungar |
|
32 // #include "port.hpp" |
|
33 //IMPLEMENTATION |
|
34 // #include "vectset.hpp" |
|
35 |
|
36 // BitsInByte is a lookup table which tells the number of bits that |
|
37 // are in the looked-up number. It is very useful in VectorSet_Size. |
|
38 |
|
39 uint8 bitsInByte[256] = { |
|
40 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, |
|
41 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
|
42 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
|
43 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
|
44 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
|
45 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
|
46 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
|
47 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
|
48 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
|
49 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
|
50 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
|
51 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
|
52 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
|
53 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
|
54 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
|
55 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 |
|
56 }; |
|
57 |
|
58 //------------------------------VectorSet-------------------------------------- |
|
59 // Create a new, empty Set. |
|
60 VectorSet::VectorSet(Arena *arena) : Set(arena) { |
|
61 size = 2; // Small initial size |
|
62 data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32)); |
|
63 data[0] = 0; // No elements |
|
64 data[1] = 0; |
|
65 } |
|
66 |
|
67 //------------------------------Construct-------------------------------------- |
|
68 Set &VectorSet_Construct(Arena *arena) |
|
69 { |
|
70 return *(new VectorSet(arena)); |
|
71 } |
|
72 |
|
73 //------------------------------operator=-------------------------------------- |
|
74 Set &VectorSet::operator = (const Set &set) |
|
75 { |
|
76 if( &set == this ) return *this; |
|
77 FREE_FAST(data); |
|
78 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
79 slamin(*(set.asVectorSet())); |
|
80 return *this; |
|
81 } |
|
82 |
|
83 //------------------------------slamin----------------------------------------- |
|
84 // Initialize one set with another. No regard is made to the existing Set. |
|
85 void VectorSet::slamin(const VectorSet& s) |
|
86 { |
|
87 size = s.size; // Use new size |
|
88 data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size |
|
89 memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array |
|
90 } |
|
91 |
|
92 //------------------------------grow------------------------------------------- |
|
93 // Expand the existing set to a bigger size |
|
94 void VectorSet::grow( uint newsize ) |
|
95 { |
|
96 newsize = (newsize+31) >> 5; // Convert to longwords |
|
97 uint x = size; |
|
98 while( x < newsize ) x <<= 1; |
|
99 data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32)); |
|
100 memset((char *)(data + size), 0, (x - size)*sizeof(uint32)); |
|
101 size = x; |
|
102 } |
|
103 |
|
104 //------------------------------operator<<=------------------------------------ |
|
105 // Insert a member into an existing Set. |
|
106 Set &VectorSet::operator <<= (uint elem) |
|
107 { |
|
108 register uint word = elem >> 5; // Get the longword offset |
|
109 register uint32 mask = 1L << (elem & 31); // Get bit mask |
|
110 |
|
111 if( word >= size ) // Need to grow set? |
|
112 grow(elem+1); // Then grow it |
|
113 data[word] |= mask; // Set new bit |
|
114 return *this; |
|
115 } |
|
116 |
|
117 //------------------------------operator>>=------------------------------------ |
|
118 // Delete a member from an existing Set. |
|
119 Set &VectorSet::operator >>= (uint elem) |
|
120 { |
|
121 register uint word = elem >> 5; // Get the longword offset |
|
122 if( word >= size ) // Beyond the last? |
|
123 return *this; // Then it's clear & return clear |
|
124 register uint32 mask = 1L << (elem & 31); // Get bit mask |
|
125 data[word] &= ~mask; // Clear bit |
|
126 return *this; |
|
127 } |
|
128 |
|
129 //------------------------------operator&=------------------------------------- |
|
130 // Intersect one set into another. |
|
131 VectorSet &VectorSet::operator &= (const VectorSet &s) |
|
132 { |
|
133 // NOTE: The intersection is never any larger than the smallest set. |
|
134 if( s.size < size ) size = s.size; // Get smaller size |
|
135 register uint32 *u1 = data; // Pointer to the destination data |
|
136 register uint32 *u2 = s.data; // Pointer to the source data |
|
137 for( uint i=0; i<size; i++) // For data in set |
|
138 *u1++ &= *u2++; // Copy and AND longwords |
|
139 return *this; // Return set |
|
140 } |
|
141 |
|
142 //------------------------------operator&=------------------------------------- |
|
143 Set &VectorSet::operator &= (const Set &set) |
|
144 { |
|
145 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
146 return (*this) &= *(set.asVectorSet()); |
|
147 } |
|
148 |
|
149 //------------------------------operator|=------------------------------------- |
|
150 // Union one set into another. |
|
151 VectorSet &VectorSet::operator |= (const VectorSet &s) |
|
152 { |
|
153 // This many words must be unioned |
|
154 register uint cnt = ((size<s.size)?size:s.size); |
|
155 register uint32 *u1 = data; // Pointer to the destination data |
|
156 register uint32 *u2 = s.data; // Pointer to the source data |
|
157 for( uint i=0; i<cnt; i++) // Copy and OR the two sets |
|
158 *u1++ |= *u2++; |
|
159 if( size < s.size ) { // Is set 2 larger than set 1? |
|
160 // Extend result by larger set |
|
161 grow(s.size*sizeof(uint32)*8); |
|
162 memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32)); |
|
163 } |
|
164 return *this; // Return result set |
|
165 } |
|
166 |
|
167 //------------------------------operator|=------------------------------------- |
|
168 Set &VectorSet::operator |= (const Set &set) |
|
169 { |
|
170 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
171 return (*this) |= *(set.asVectorSet()); |
|
172 } |
|
173 |
|
174 //------------------------------operator-=------------------------------------- |
|
175 // Difference one set from another. |
|
176 VectorSet &VectorSet::operator -= (const VectorSet &s) |
|
177 { |
|
178 // This many words must be unioned |
|
179 register uint cnt = ((size<s.size)?size:s.size); |
|
180 register uint32 *u1 = data; // Pointer to the destination data |
|
181 register uint32 *u2 = s.data; // Pointer to the source data |
|
182 for( uint i=0; i<cnt; i++ ) // For data in set |
|
183 *u1++ &= ~(*u2++); // A <-- A & ~B with longwords |
|
184 return *this; // Return new set |
|
185 } |
|
186 |
|
187 //------------------------------operator-=------------------------------------- |
|
188 Set &VectorSet::operator -= (const Set &set) |
|
189 { |
|
190 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
191 return (*this) -= *(set.asVectorSet()); |
|
192 } |
|
193 |
|
194 //------------------------------compare---------------------------------------- |
|
195 // Compute 2 booleans: bits in A not B, bits in B not A. |
|
196 // Return X0 -- A is not a subset of B |
|
197 // X1 -- A is a subset of B |
|
198 // 0X -- B is not a subset of A |
|
199 // 1X -- B is a subset of A |
|
200 int VectorSet::compare (const VectorSet &s) const |
|
201 { |
|
202 register uint32 *u1 = data; // Pointer to the destination data |
|
203 register uint32 *u2 = s.data; // Pointer to the source data |
|
204 register uint32 AnotB = 0, BnotA = 0; |
|
205 // This many words must be unioned |
|
206 register uint cnt = ((size<s.size)?size:s.size); |
|
207 |
|
208 // Get bits for both sets |
|
209 uint i; // Exit value of loop |
|
210 for( i=0; i<cnt; i++ ) { // For data in BOTH sets |
|
211 register uint32 A = *u1++; // Data from one guy |
|
212 register uint32 B = *u2++; // Data from other guy |
|
213 AnotB |= (A & ~B); // Compute bits in A not B |
|
214 BnotA |= (B & ~A); // Compute bits in B not A |
|
215 } |
|
216 |
|
217 // Get bits from bigger set |
|
218 if( size < s.size ) { |
|
219 for( ; i<s.size; i++ ) // For data in larger set |
|
220 BnotA |= *u2++; // These bits are in B not A |
|
221 } else { |
|
222 for( ; i<size; i++ ) // For data in larger set |
|
223 AnotB |= *u1++; // These bits are in A not B |
|
224 } |
|
225 |
|
226 // Set & return boolean flags |
|
227 return ((!BnotA)<<1) + (!AnotB); |
|
228 } |
|
229 |
|
230 //------------------------------operator==------------------------------------- |
|
231 // Test for set equality |
|
232 int VectorSet::operator == (const VectorSet &s) const |
|
233 { |
|
234 return compare(s) == 3; // TRUE if A and B are mutual subsets |
|
235 } |
|
236 |
|
237 //------------------------------operator==------------------------------------- |
|
238 int VectorSet::operator == (const Set &set) const |
|
239 { |
|
240 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
241 return (*this) == *(set.asVectorSet()); |
|
242 } |
|
243 |
|
244 //------------------------------disjoint--------------------------------------- |
|
245 // Check for sets being disjoint. |
|
246 int VectorSet::disjoint(const Set &set) const |
|
247 { |
|
248 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
249 const VectorSet &s = *(set.asVectorSet()); |
|
250 |
|
251 // NOTE: The intersection is never any larger than the smallest set. |
|
252 register uint small_size = ((size<s.size)?size:s.size); |
|
253 register uint32 *u1 = data; // Pointer to the destination data |
|
254 register uint32 *u2 = s.data; // Pointer to the source data |
|
255 for( uint i=0; i<small_size; i++) // For data in set |
|
256 if( *u1++ & *u2++ ) // If any elements in common |
|
257 return 0; // Then not disjoint |
|
258 return 1; // Else disjoint |
|
259 } |
|
260 |
|
261 //------------------------------operator<-------------------------------------- |
|
262 // Test for strict subset |
|
263 int VectorSet::operator < (const VectorSet &s) const |
|
264 { |
|
265 return compare(s) == 1; // A subset B, B not subset A |
|
266 } |
|
267 |
|
268 //------------------------------operator<-------------------------------------- |
|
269 int VectorSet::operator < (const Set &set) const |
|
270 { |
|
271 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
272 return (*this) < *(set.asVectorSet()); |
|
273 } |
|
274 |
|
275 //------------------------------operator<=------------------------------------- |
|
276 // Test for subset |
|
277 int VectorSet::operator <= (const VectorSet &s) const |
|
278 { |
|
279 return compare(s) & 1; // A subset B |
|
280 } |
|
281 |
|
282 //------------------------------operator<=------------------------------------- |
|
283 int VectorSet::operator <= (const Set &set) const |
|
284 { |
|
285 // The cast is a virtual function that checks that "set" is a VectorSet. |
|
286 return (*this) <= *(set.asVectorSet()); |
|
287 } |
|
288 |
|
289 //------------------------------operator[]------------------------------------- |
|
290 // Test for membership. A Zero/Non-Zero value is returned! |
|
291 int VectorSet::operator[](uint elem) const |
|
292 { |
|
293 register uint word = elem >> 5; // Get the longword offset |
|
294 if( word >= size ) // Beyond the last? |
|
295 return 0; // Then it's clear |
|
296 register uint32 mask = 1L << (elem & 31); // Get bit mask |
|
297 return ((data[word] & mask))!=0; // Return the sense of the bit |
|
298 } |
|
299 |
|
300 //------------------------------getelem---------------------------------------- |
|
301 // Get any element from the set. |
|
302 uint VectorSet::getelem(void) const |
|
303 { |
|
304 uint i; // Exit value of loop |
|
305 for( i=0; i<size; i++ ) |
|
306 if( data[i] ) |
|
307 break; |
|
308 uint32 word = data[i]; |
|
309 int j; // Exit value of loop |
|
310 for( j= -1; word; j++, word>>=1 ); |
|
311 return (i<<5)+j; |
|
312 } |
|
313 |
|
314 //------------------------------Clear------------------------------------------ |
|
315 // Clear a set |
|
316 void VectorSet::Clear(void) |
|
317 { |
|
318 if( size > 100 ) { // Reclaim storage only if huge |
|
319 FREE_RESOURCE_ARRAY(uint32,data,size); |
|
320 size = 2; // Small initial size |
|
321 data = NEW_RESOURCE_ARRAY(uint32,size); |
|
322 } |
|
323 memset( data, 0, size*sizeof(uint32) ); |
|
324 } |
|
325 |
|
326 //------------------------------Size------------------------------------------- |
|
327 // Return number of elements in a Set |
|
328 uint VectorSet::Size(void) const |
|
329 { |
|
330 uint sum = 0; // Cumulative size so far. |
|
331 uint8 *currByte = (uint8*)data; |
|
332 for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process |
|
333 sum += bitsInByte[*currByte++]; // Add bits in current byte to size. |
|
334 return sum; |
|
335 } |
|
336 |
|
337 //------------------------------Sort------------------------------------------- |
|
338 // Sort the elements for the next forall statement |
|
339 void VectorSet::Sort(void) |
|
340 { |
|
341 } |
|
342 |
|
343 //------------------------------hash------------------------------------------- |
|
344 int VectorSet::hash() const |
|
345 { |
|
346 uint32 _xor = 0; |
|
347 uint lim = ((size<4)?size:4); |
|
348 for( uint i = 0; i < lim; i++ ) |
|
349 _xor ^= data[i]; |
|
350 return (int)_xor; |
|
351 } |
|
352 |
|
353 //------------------------------iterate---------------------------------------- |
|
354 // Used by Set::print(). |
|
355 class VSetI_ : public SetI_ { |
|
356 VectorSetI vsi; |
|
357 public: |
|
358 VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; } |
|
359 |
|
360 uint next(void) { ++vsi; return vsi.elem; } |
|
361 int test(void) { return vsi.test(); } |
|
362 }; |
|
363 |
|
364 SetI_ *VectorSet::iterate(uint &elem) const { |
|
365 return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem); |
|
366 } |
|
367 |
|
368 //============================================================================= |
|
369 //------------------------------next------------------------------------------- |
|
370 // Find and return the next element of a vector set, or return garbage and |
|
371 // make "VectorSetI::test()" fail. |
|
372 uint VectorSetI::next(void) |
|
373 { |
|
374 j++; // Next element in word |
|
375 mask = (mask & max_jint) << 1;// Next bit in word |
|
376 do { // Do While still have words |
|
377 while( mask ) { // While have bits in word |
|
378 if( s->data[i] & mask ) { // If found a bit |
|
379 return (i<<5)+j; // Return the bit address |
|
380 } |
|
381 j++; // Skip to next bit |
|
382 mask = (mask & max_jint) << 1; |
|
383 } |
|
384 j = 0; // No more bits in word; setup for next word |
|
385 mask = 1; |
|
386 for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word |
|
387 } while( i<s->size ); |
|
388 return max_juint; // No element, iterated them all |
|
389 } |