Mercurial > hg > truffle
annotate src/share/vm/utilities/bitMap.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 | 8a9bb7821e28 |
| children | 4ca6dc0799b6 78bbf4d43a14 |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
14223
de6a9e811145
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
mikael
parents:
10992
diff
changeset
|
2 * Copyright (c) 1997, 2013, 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:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
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:
844
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
| 26 #include "memory/allocation.inline.hpp" | |
| 27 #include "utilities/bitMap.inline.hpp" | |
| 28 #include "utilities/copy.hpp" | |
| 29 #ifdef TARGET_OS_FAMILY_linux | |
| 30 # include "os_linux.inline.hpp" | |
| 31 #endif | |
| 32 #ifdef TARGET_OS_FAMILY_solaris | |
| 33 # include "os_solaris.inline.hpp" | |
| 34 #endif | |
| 35 #ifdef TARGET_OS_FAMILY_windows | |
| 36 # include "os_windows.inline.hpp" | |
| 37 #endif | |
| 14411 | 38 #ifdef TARGET_OS_FAMILY_aix |
| 39 # include "os_aix.inline.hpp" | |
| 40 #endif | |
| 3960 | 41 #ifdef TARGET_OS_FAMILY_bsd |
| 42 # include "os_bsd.inline.hpp" | |
| 43 #endif | |
| 0 | 44 |
| 45 | |
| 342 | 46 BitMap::BitMap(bm_word_t* map, idx_t size_in_bits) : |
| 10992 | 47 _map(map), _size(size_in_bits), _map_allocator(false) |
| 342 | 48 { |
| 49 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); | |
| 0 | 50 assert(size_in_bits >= 0, "just checking"); |
| 51 } | |
| 52 | |
| 53 | |
| 342 | 54 BitMap::BitMap(idx_t size_in_bits, bool in_resource_area) : |
| 10992 | 55 _map(NULL), _size(0), _map_allocator(false) |
| 342 | 56 { |
| 57 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); | |
| 58 resize(size_in_bits, in_resource_area); | |
| 0 | 59 } |
| 60 | |
| 342 | 61 void BitMap::resize(idx_t size_in_bits, bool in_resource_area) { |
| 0 | 62 assert(size_in_bits >= 0, "just checking"); |
| 342 | 63 idx_t old_size_in_words = size_in_words(); |
| 64 bm_word_t* old_map = map(); | |
| 65 | |
| 0 | 66 _size = size_in_bits; |
| 342 | 67 idx_t new_size_in_words = size_in_words(); |
| 68 if (in_resource_area) { | |
| 69 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words); | |
| 70 } else { | |
| 10992 | 71 if (old_map != NULL) { |
| 72 _map_allocator.free(); | |
| 73 } | |
| 74 _map = _map_allocator.allocate(new_size_in_words); | |
| 342 | 75 } |
| 76 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map, | |
| 77 MIN2(old_size_in_words, new_size_in_words)); | |
| 0 | 78 if (new_size_in_words > old_size_in_words) { |
| 79 clear_range_of_words(old_size_in_words, size_in_words()); | |
| 80 } | |
| 81 } | |
| 82 | |
| 83 void BitMap::set_range_within_word(idx_t beg, idx_t end) { | |
| 84 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 85 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 86 if (beg != end) { | |
| 342 | 87 bm_word_t mask = inverted_bit_mask_for_range(beg, end); |
| 0 | 88 *word_addr(beg) |= ~mask; |
| 89 } | |
| 90 } | |
| 91 | |
| 92 void BitMap::clear_range_within_word(idx_t beg, idx_t end) { | |
| 93 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 94 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 95 if (beg != end) { | |
| 342 | 96 bm_word_t mask = inverted_bit_mask_for_range(beg, end); |
| 0 | 97 *word_addr(beg) &= mask; |
| 98 } | |
| 99 } | |
| 100 | |
| 101 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { | |
| 102 assert(value == 0 || value == 1, "0 for clear, 1 for set"); | |
| 103 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 104 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 105 if (beg != end) { | |
| 106 intptr_t* pw = (intptr_t*)word_addr(beg); | |
| 107 intptr_t w = *pw; | |
| 108 intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end); | |
| 109 intptr_t nw = value ? (w | ~mr) : (w & mr); | |
| 110 while (true) { | |
| 111 intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w); | |
| 112 if (res == w) break; | |
|
14352
3dc1055f4e87
8033545: Missing volatile specifier in Bitmap::par_put_range_within_word
tschatzl
parents:
14223
diff
changeset
|
113 w = res; |
| 0 | 114 nw = value ? (w | ~mr) : (w & mr); |
| 115 } | |
| 116 } | |
| 117 } | |
| 118 | |
| 119 void BitMap::set_range(idx_t beg, idx_t end) { | |
| 120 verify_range(beg, end); | |
| 121 | |
| 122 idx_t beg_full_word = word_index_round_up(beg); | |
| 123 idx_t end_full_word = word_index(end); | |
| 124 | |
| 125 if (beg_full_word < end_full_word) { | |
| 126 // The range includes at least one full word. | |
| 127 set_range_within_word(beg, bit_index(beg_full_word)); | |
| 128 set_range_of_words(beg_full_word, end_full_word); | |
| 129 set_range_within_word(bit_index(end_full_word), end); | |
| 130 } else { | |
| 131 // The range spans at most 2 partial words. | |
| 132 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 133 set_range_within_word(beg, boundary); | |
| 134 set_range_within_word(boundary, end); | |
| 135 } | |
| 136 } | |
| 137 | |
| 138 void BitMap::clear_range(idx_t beg, idx_t end) { | |
| 139 verify_range(beg, end); | |
| 140 | |
| 141 idx_t beg_full_word = word_index_round_up(beg); | |
| 142 idx_t end_full_word = word_index(end); | |
| 143 | |
| 144 if (beg_full_word < end_full_word) { | |
| 145 // The range includes at least one full word. | |
| 146 clear_range_within_word(beg, bit_index(beg_full_word)); | |
| 147 clear_range_of_words(beg_full_word, end_full_word); | |
| 148 clear_range_within_word(bit_index(end_full_word), end); | |
| 149 } else { | |
| 150 // The range spans at most 2 partial words. | |
| 151 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 152 clear_range_within_word(beg, boundary); | |
| 153 clear_range_within_word(boundary, end); | |
| 154 } | |
| 155 } | |
| 156 | |
| 157 void BitMap::set_large_range(idx_t beg, idx_t end) { | |
| 158 verify_range(beg, end); | |
| 159 | |
| 160 idx_t beg_full_word = word_index_round_up(beg); | |
| 161 idx_t end_full_word = word_index(end); | |
| 162 | |
| 163 assert(end_full_word - beg_full_word >= 32, | |
| 164 "the range must include at least 32 bytes"); | |
| 165 | |
| 166 // The range includes at least one full word. | |
| 167 set_range_within_word(beg, bit_index(beg_full_word)); | |
| 168 set_large_range_of_words(beg_full_word, end_full_word); | |
| 169 set_range_within_word(bit_index(end_full_word), end); | |
| 170 } | |
| 171 | |
| 172 void BitMap::clear_large_range(idx_t beg, idx_t end) { | |
| 173 verify_range(beg, end); | |
| 174 | |
| 175 idx_t beg_full_word = word_index_round_up(beg); | |
| 176 idx_t end_full_word = word_index(end); | |
| 177 | |
| 178 assert(end_full_word - beg_full_word >= 32, | |
| 179 "the range must include at least 32 bytes"); | |
| 180 | |
| 181 // The range includes at least one full word. | |
| 182 clear_range_within_word(beg, bit_index(beg_full_word)); | |
| 183 clear_large_range_of_words(beg_full_word, end_full_word); | |
| 184 clear_range_within_word(bit_index(end_full_word), end); | |
| 185 } | |
| 186 | |
| 187 void BitMap::at_put(idx_t offset, bool value) { | |
| 188 if (value) { | |
| 189 set_bit(offset); | |
| 190 } else { | |
| 191 clear_bit(offset); | |
| 192 } | |
| 193 } | |
| 194 | |
| 195 // Return true to indicate that this thread changed | |
| 196 // the bit, false to indicate that someone else did. | |
| 197 // In either case, the requested bit is in the | |
| 198 // requested state some time during the period that | |
| 199 // this thread is executing this call. More importantly, | |
| 200 // if no other thread is executing an action to | |
| 201 // change the requested bit to a state other than | |
| 202 // the one that this thread is trying to set it to, | |
| 203 // then the the bit is in the expected state | |
| 204 // at exit from this method. However, rather than | |
| 205 // make such a strong assertion here, based on | |
| 206 // assuming such constrained use (which though true | |
| 207 // today, could change in the future to service some | |
| 208 // funky parallel algorithm), we encourage callers | |
| 209 // to do such verification, as and when appropriate. | |
| 210 bool BitMap::par_at_put(idx_t bit, bool value) { | |
| 211 return value ? par_set_bit(bit) : par_clear_bit(bit); | |
| 212 } | |
| 213 | |
| 214 void BitMap::at_put_grow(idx_t offset, bool value) { | |
| 215 if (offset >= size()) { | |
| 216 resize(2 * MAX2(size(), offset)); | |
| 217 } | |
| 218 at_put(offset, value); | |
| 219 } | |
| 220 | |
| 221 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { | |
| 222 if (value) { | |
| 223 set_range(start_offset, end_offset); | |
| 224 } else { | |
| 225 clear_range(start_offset, end_offset); | |
| 226 } | |
| 227 } | |
| 228 | |
| 229 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { | |
| 230 verify_range(beg, end); | |
| 231 | |
| 232 idx_t beg_full_word = word_index_round_up(beg); | |
| 233 idx_t end_full_word = word_index(end); | |
| 234 | |
| 235 if (beg_full_word < end_full_word) { | |
| 236 // The range includes at least one full word. | |
| 237 par_put_range_within_word(beg, bit_index(beg_full_word), value); | |
| 238 if (value) { | |
| 239 set_range_of_words(beg_full_word, end_full_word); | |
| 240 } else { | |
| 241 clear_range_of_words(beg_full_word, end_full_word); | |
| 242 } | |
| 243 par_put_range_within_word(bit_index(end_full_word), end, value); | |
| 244 } else { | |
| 245 // The range spans at most 2 partial words. | |
| 246 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 247 par_put_range_within_word(beg, boundary, value); | |
| 248 par_put_range_within_word(boundary, end, value); | |
| 249 } | |
| 250 | |
| 251 } | |
| 252 | |
| 253 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { | |
| 254 if (value) { | |
| 255 set_large_range(beg, end); | |
| 256 } else { | |
| 257 clear_large_range(beg, end); | |
| 258 } | |
| 259 } | |
| 260 | |
| 261 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { | |
| 262 verify_range(beg, end); | |
| 263 | |
| 264 idx_t beg_full_word = word_index_round_up(beg); | |
| 265 idx_t end_full_word = word_index(end); | |
| 266 | |
| 267 assert(end_full_word - beg_full_word >= 32, | |
| 268 "the range must include at least 32 bytes"); | |
| 269 | |
| 270 // The range includes at least one full word. | |
| 271 par_put_range_within_word(beg, bit_index(beg_full_word), value); | |
| 272 if (value) { | |
| 273 set_large_range_of_words(beg_full_word, end_full_word); | |
| 274 } else { | |
| 275 clear_large_range_of_words(beg_full_word, end_full_word); | |
| 276 } | |
| 277 par_put_range_within_word(bit_index(end_full_word), end, value); | |
| 278 } | |
| 279 | |
| 280 bool BitMap::contains(const BitMap other) const { | |
| 281 assert(size() == other.size(), "must have same size"); | |
| 342 | 282 bm_word_t* dest_map = map(); |
| 283 bm_word_t* other_map = other.map(); | |
| 0 | 284 idx_t size = size_in_words(); |
| 285 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 342 | 286 bm_word_t word_union = dest_map[index] | other_map[index]; |
| 0 | 287 // If this has more bits set than dest_map[index], then other is not a |
| 288 // subset. | |
| 289 if (word_union != dest_map[index]) return false; | |
| 290 } | |
| 291 return true; | |
| 292 } | |
| 293 | |
| 294 bool BitMap::intersects(const BitMap other) const { | |
| 295 assert(size() == other.size(), "must have same size"); | |
| 342 | 296 bm_word_t* dest_map = map(); |
| 297 bm_word_t* other_map = other.map(); | |
| 0 | 298 idx_t size = size_in_words(); |
| 299 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 300 if ((dest_map[index] & other_map[index]) != 0) return true; | |
| 301 } | |
| 302 // Otherwise, no intersection. | |
| 303 return false; | |
| 304 } | |
| 305 | |
| 306 void BitMap::set_union(BitMap other) { | |
| 307 assert(size() == other.size(), "must have same size"); | |
| 342 | 308 bm_word_t* dest_map = map(); |
| 309 bm_word_t* other_map = other.map(); | |
| 0 | 310 idx_t size = size_in_words(); |
| 311 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 312 dest_map[index] = dest_map[index] | other_map[index]; | |
| 313 } | |
| 314 } | |
| 315 | |
| 316 | |
| 317 void BitMap::set_difference(BitMap other) { | |
| 318 assert(size() == other.size(), "must have same size"); | |
| 342 | 319 bm_word_t* dest_map = map(); |
| 320 bm_word_t* other_map = other.map(); | |
| 0 | 321 idx_t size = size_in_words(); |
| 322 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 323 dest_map[index] = dest_map[index] & ~(other_map[index]); | |
| 324 } | |
| 325 } | |
| 326 | |
| 327 | |
| 328 void BitMap::set_intersection(BitMap other) { | |
| 329 assert(size() == other.size(), "must have same size"); | |
| 342 | 330 bm_word_t* dest_map = map(); |
| 331 bm_word_t* other_map = other.map(); | |
| 0 | 332 idx_t size = size_in_words(); |
| 333 for (idx_t index = 0; index < size; index++) { | |
| 334 dest_map[index] = dest_map[index] & other_map[index]; | |
| 335 } | |
| 336 } | |
| 337 | |
| 338 | |
| 342 | 339 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) { |
| 340 assert(other.size() >= offset, "offset not in range"); | |
| 341 assert(other.size() - offset >= size(), "other not large enough"); | |
| 342 // XXX Ideally, we would remove this restriction. | |
| 343 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0, | |
| 344 "Only handle aligned cases so far."); | |
| 345 bm_word_t* dest_map = map(); | |
| 346 bm_word_t* other_map = other.map(); | |
| 347 idx_t offset_word_ind = word_index(offset); | |
| 348 idx_t size = size_in_words(); | |
| 349 for (idx_t index = 0; index < size; index++) { | |
| 350 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index]; | |
| 351 } | |
| 352 } | |
| 353 | |
| 0 | 354 bool BitMap::set_union_with_result(BitMap other) { |
| 355 assert(size() == other.size(), "must have same size"); | |
| 356 bool changed = false; | |
| 342 | 357 bm_word_t* dest_map = map(); |
| 358 bm_word_t* other_map = other.map(); | |
| 0 | 359 idx_t size = size_in_words(); |
| 360 for (idx_t index = 0; index < size; index++) { | |
| 361 idx_t temp = map(index) | other_map[index]; | |
| 362 changed = changed || (temp != map(index)); | |
| 363 map()[index] = temp; | |
| 364 } | |
| 365 return changed; | |
| 366 } | |
| 367 | |
| 368 | |
| 369 bool BitMap::set_difference_with_result(BitMap other) { | |
| 370 assert(size() == other.size(), "must have same size"); | |
| 371 bool changed = false; | |
| 342 | 372 bm_word_t* dest_map = map(); |
| 373 bm_word_t* other_map = other.map(); | |
| 0 | 374 idx_t size = size_in_words(); |
| 375 for (idx_t index = 0; index < size; index++) { | |
| 342 | 376 bm_word_t temp = dest_map[index] & ~(other_map[index]); |
| 0 | 377 changed = changed || (temp != dest_map[index]); |
| 378 dest_map[index] = temp; | |
| 379 } | |
| 380 return changed; | |
| 381 } | |
| 382 | |
| 383 | |
| 384 bool BitMap::set_intersection_with_result(BitMap other) { | |
| 385 assert(size() == other.size(), "must have same size"); | |
| 386 bool changed = false; | |
| 342 | 387 bm_word_t* dest_map = map(); |
| 388 bm_word_t* other_map = other.map(); | |
| 0 | 389 idx_t size = size_in_words(); |
| 390 for (idx_t index = 0; index < size; index++) { | |
| 342 | 391 bm_word_t orig = dest_map[index]; |
| 392 bm_word_t temp = orig & other_map[index]; | |
| 0 | 393 changed = changed || (temp != orig); |
| 394 dest_map[index] = temp; | |
| 395 } | |
| 396 return changed; | |
| 397 } | |
| 398 | |
| 399 | |
| 400 void BitMap::set_from(BitMap other) { | |
| 401 assert(size() == other.size(), "must have same size"); | |
| 342 | 402 bm_word_t* dest_map = map(); |
| 403 bm_word_t* other_map = other.map(); | |
| 0 | 404 idx_t size = size_in_words(); |
| 405 for (idx_t index = 0; index < size; index++) { | |
| 406 dest_map[index] = other_map[index]; | |
| 407 } | |
| 408 } | |
| 409 | |
| 410 | |
| 411 bool BitMap::is_same(BitMap other) { | |
| 412 assert(size() == other.size(), "must have same size"); | |
| 342 | 413 bm_word_t* dest_map = map(); |
| 414 bm_word_t* other_map = other.map(); | |
| 0 | 415 idx_t size = size_in_words(); |
| 416 for (idx_t index = 0; index < size; index++) { | |
| 417 if (dest_map[index] != other_map[index]) return false; | |
| 418 } | |
| 419 return true; | |
| 420 } | |
| 421 | |
| 422 bool BitMap::is_full() const { | |
| 342 | 423 bm_word_t* word = map(); |
| 0 | 424 idx_t rest = size(); |
| 425 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { | |
| 342 | 426 if (*word != (bm_word_t) AllBits) return false; |
| 0 | 427 word++; |
| 428 } | |
| 342 | 429 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits; |
| 0 | 430 } |
| 431 | |
| 432 | |
| 433 bool BitMap::is_empty() const { | |
| 342 | 434 bm_word_t* word = map(); |
| 0 | 435 idx_t rest = size(); |
| 436 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { | |
| 342 | 437 if (*word != (bm_word_t) NoBits) return false; |
| 0 | 438 word++; |
| 439 } | |
| 342 | 440 return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits; |
| 0 | 441 } |
| 442 | |
| 443 void BitMap::clear_large() { | |
| 444 clear_large_range_of_words(0, size_in_words()); | |
| 445 } | |
| 446 | |
| 447 // Note that if the closure itself modifies the bitmap | |
| 448 // then modifications in and to the left of the _bit_ being | |
| 449 // currently sampled will not be seen. Note also that the | |
| 450 // interval [leftOffset, rightOffset) is right open. | |
| 342 | 451 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { |
| 0 | 452 verify_range(leftOffset, rightOffset); |
| 453 | |
| 454 idx_t startIndex = word_index(leftOffset); | |
| 455 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); | |
| 456 for (idx_t index = startIndex, offset = leftOffset; | |
| 457 offset < rightOffset && index < endIndex; | |
| 458 offset = (++index) << LogBitsPerWord) { | |
| 459 idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); | |
| 342 | 460 for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) { |
| 0 | 461 if (rest & 1) { |
| 342 | 462 if (!blk->do_bit(offset)) return false; |
| 0 | 463 // resample at each closure application |
| 464 // (see, for instance, CMS bug 4525989) | |
| 465 rest = map(index) >> (offset & (BitsPerWord -1)); | |
| 466 } | |
| 467 rest = rest >> 1; | |
| 468 } | |
| 469 } | |
| 342 | 470 return true; |
| 471 } | |
| 472 | |
| 473 BitMap::idx_t* BitMap::_pop_count_table = NULL; | |
| 474 | |
| 475 void BitMap::init_pop_count_table() { | |
| 476 if (_pop_count_table == NULL) { | |
| 6197 | 477 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal); |
| 342 | 478 for (uint i = 0; i < 256; i++) { |
| 479 table[i] = num_set_bits(i); | |
| 480 } | |
| 481 | |
| 482 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table, | |
| 483 (intptr_t*) &_pop_count_table, | |
| 484 (intptr_t) NULL_WORD); | |
| 485 if (res != NULL_WORD) { | |
| 486 guarantee( _pop_count_table == (void*) res, "invariant" ); | |
| 6197 | 487 FREE_C_HEAP_ARRAY(bm_word_t, table, mtInternal); |
| 342 | 488 } |
| 489 } | |
| 0 | 490 } |
| 491 | |
| 342 | 492 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) { |
| 493 idx_t bits = 0; | |
| 0 | 494 |
| 342 | 495 while (w != 0) { |
| 496 while ((w & 1) == 0) { | |
| 497 w >>= 1; | |
| 0 | 498 } |
| 342 | 499 bits++; |
| 500 w >>= 1; | |
| 0 | 501 } |
| 342 | 502 return bits; |
| 0 | 503 } |
| 504 | |
| 342 | 505 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { |
| 506 assert(_pop_count_table != NULL, "precondition"); | |
| 507 return _pop_count_table[c]; | |
| 508 } | |
| 0 | 509 |
| 342 | 510 BitMap::idx_t BitMap::count_one_bits() const { |
| 511 init_pop_count_table(); // If necessary. | |
| 512 idx_t sum = 0; | |
| 513 typedef unsigned char uchar; | |
| 514 for (idx_t i = 0; i < size_in_words(); i++) { | |
| 515 bm_word_t w = map()[i]; | |
| 516 for (size_t j = 0; j < sizeof(bm_word_t); j++) { | |
| 517 sum += num_set_bits_from_table(uchar(w & 255)); | |
| 518 w >>= 8; | |
| 0 | 519 } |
| 520 } | |
| 342 | 521 return sum; |
| 0 | 522 } |
| 523 | |
|
9076
7b835924c31c
8011872: Include Bit Map addresses in the hs_err files
stefank
parents:
6197
diff
changeset
|
524 void BitMap::print_on_error(outputStream* st, const char* prefix) const { |
|
7b835924c31c
8011872: Include Bit Map addresses in the hs_err files
stefank
parents:
6197
diff
changeset
|
525 st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")", |
|
7b835924c31c
8011872: Include Bit Map addresses in the hs_err files
stefank
parents:
6197
diff
changeset
|
526 prefix, map(), (char*)map() + (size() >> LogBitsPerByte)); |
|
7b835924c31c
8011872: Include Bit Map addresses in the hs_err files
stefank
parents:
6197
diff
changeset
|
527 } |
| 342 | 528 |
| 0 | 529 #ifndef PRODUCT |
| 530 | |
| 531 void BitMap::print_on(outputStream* st) const { | |
| 532 tty->print("Bitmap(%d):", size()); | |
| 533 for (idx_t index = 0; index < size(); index++) { | |
| 534 tty->print("%c", at(index) ? '1' : '0'); | |
| 535 } | |
| 536 tty->cr(); | |
| 537 } | |
| 538 | |
| 539 #endif | |
| 540 | |
| 541 | |
| 342 | 542 BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot) |
| 0 | 543 : _bits_per_slot(bits_per_slot) |
| 544 , _map(map, size_in_slots * bits_per_slot) | |
| 545 { | |
| 546 } | |
| 547 | |
| 548 | |
| 549 BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) | |
| 550 : _bits_per_slot(bits_per_slot) | |
| 551 , _map(size_in_slots * bits_per_slot) | |
| 552 { | |
| 553 } |