Mercurial > hg > graal-compiler
annotate src/share/vm/libadt/vectset.cpp @ 18096:ca6d25be853b jdk8u25-b13
8044269: Analysis of archive files.
Summary: Add checksum verification.
Reviewed-by: iklam, dholmes, mschoene
| author | jiangli |
|---|---|
| date | Tue, 12 Aug 2014 17:46:16 -0400 |
| parents | b9a9ed0f8eeb |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
6842
b9a9ed0f8eeb
7197424: update copyright year to match last edit in jdk8 hotspot repository
mikael
parents:
6197
diff
changeset
|
2 * Copyright (c) 1997, 2012, 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 { | |
| 6197 | 365 return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem); |
| 4051 | 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 } |