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