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