|
0
|
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 }
|
