Mercurial > hg > truffle
annotate src/share/vm/libadt/vectset.cpp @ 5073:2db1ad9dd385
rename PiNode.value to PiNode.object and UnsafeCastNode.x to UnsafeCastNode.object
author | Lukas Stadler <lukas.stadler@jku.at> |
---|---|
date | Wed, 14 Mar 2012 16:57:18 +0100 |
parents | f350490a45fd |
children | d2a62e0f25eb |
rev | line source |
---|---|
0 | 1 /* |
2249 | 2 * Copyright (c) 1997, 2011, 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 | |
1972 | 25 #include "precompiled.hpp" |
26 #include "libadt/vectset.hpp" | |
27 #include "memory/allocation.inline.hpp" | |
0 | 28 |
1972 | 29 // Vector Sets - An Abstract Data Type |
0 | 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. | |
1983
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
252 register uint small_size = ((size<s.size)?size:s.size); |
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
253 register uint32 *u1 = data; // Pointer to the destination data |
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
254 register uint32 *u2 = s.data; // Pointer to the source data |
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
255 for( uint i=0; i<small_size; i++) // For data in set |
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
256 if( *u1++ & *u2++ ) // If any elements in common |
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
257 return 0; // Then not disjoint |
c760f78e0a53
7003125: precompiled.hpp is included when precompiled headers are not used
stefank
parents:
1972
diff
changeset
|
258 return 1; // Else disjoint |
0 | 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 | |
4051 | 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) VSetI_(this, elem); | |
366 } | |
367 | |
0 | 368 //============================================================================= |
369 //------------------------------next------------------------------------------- | |
370 // Find and return the next element of a vector set, or return garbage and | |
2249 | 371 // make "VectorSetI::test()" fail. |
372 uint VectorSetI::next(void) | |
0 | 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 } |