Mercurial > hg > graal-compiler

comparison src/share/vm/libadt/vectset.cpp @ 0:a61af66fc99e jdk7-b24

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children c18cbe5936b8
comparison
equal deleted inserted replaced
-1:000000000000 0:a61af66fc99e
1 /*
2 * Copyright 1997-2005 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
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 }