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