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