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