Mercurial > hg > truffle
annotate src/share/vm/libadt/vectset.cpp @ 14649:f6301b007a16
6498581: ThreadInterruptTest3 produces wrong output on Windows
Summary: There is race condition between os::interrupt and os::is_interrupted on Windows. In JVM_Sleep(Thread.sleep), check if thread gets interrupted, it may see interrupted but not really interrupted so cause spurious waking up (early return from sleep). Fix by checking if interrupt event really gets set thus prevent false return. For intrinsic of _isInterrupted, on Windows, go fastpath only on bit not set.
Reviewed-by: acorn, kvn
Contributed-by: david.holmes@oracle.com, yumin.qi@oracle.com
| author | minqi |
|---|---|
| date | Wed, 26 Feb 2014 15:20:41 -0800 |
| 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 } |