1 /* 2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved. 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 * 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 "memory/allocation.inline.hpp" 27 #include "memory/resourceArea.hpp" 28 #include "runtime/atomic.hpp" 29 #include "utilities/bitMap.inline.hpp" 30 #include "utilities/copy.hpp" 31 #include "utilities/debug.hpp" 32 33 STATIC_ASSERT(sizeof(BitMap::bm_word_t) == BytesPerWord); // "Implementation assumption." 34 35 typedef BitMap::bm_word_t bm_word_t; 36 typedef BitMap::idx_t idx_t; 37 38 class ResourceBitMapAllocator : StackObj { 39 public: 40 bm_word_t* allocate(idx_t size_in_words) const { 41 return NEW_RESOURCE_ARRAY(bm_word_t, size_in_words); 42 } 43 void free(bm_word_t* map, idx_t size_in_words) const { 44 // Don't free resource allocated arrays. 45 } 46 }; 47 48 class CHeapBitMapAllocator : StackObj { 49 MEMFLAGS _flags; 50 51 public: 52 CHeapBitMapAllocator(MEMFLAGS flags) : _flags(flags) {} 53 bm_word_t* allocate(size_t size_in_words) const { 54 return ArrayAllocator<bm_word_t>::allocate(size_in_words, _flags); 55 } 56 void free(bm_word_t* map, idx_t size_in_words) const { 57 ArrayAllocator<bm_word_t>::free(map, size_in_words); 58 } 59 }; 60 61 class ArenaBitMapAllocator : StackObj { 62 Arena* _arena; 63 64 public: 65 ArenaBitMapAllocator(Arena* arena) : _arena(arena) {} 66 bm_word_t* allocate(idx_t size_in_words) const { 67 return (bm_word_t*)_arena->Amalloc(size_in_words * BytesPerWord); 68 } 69 void free(bm_word_t* map, idx_t size_in_words) const { 70 // ArenaBitMaps currently don't free memory. 71 } 72 }; 73 74 template <class Allocator> 75 BitMap::bm_word_t* BitMap::reallocate(const Allocator& allocator, bm_word_t* old_map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear) { 76 size_t old_size_in_words = calc_size_in_words(old_size_in_bits); 77 size_t new_size_in_words = calc_size_in_words(new_size_in_bits); 78 79 bm_word_t* map = NULL; 80 81 if (new_size_in_words > 0) { 82 map = allocator.allocate(new_size_in_words); 83 84 if (old_map != NULL) { 85 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) map, 86 MIN2(old_size_in_words, new_size_in_words)); 87 } 88 89 if (clear && new_size_in_words > old_size_in_words) { 90 clear_range_of_words(map, old_size_in_words, new_size_in_words); 91 } 92 } 93 94 if (old_map != NULL) { 95 allocator.free(old_map, old_size_in_words); 96 } 97 98 return map; 99 } 100 101 template <class Allocator> 102 bm_word_t* BitMap::allocate(const Allocator& allocator, idx_t size_in_bits, bool clear) { 103 // Reuse reallocate to ensure that the new memory is cleared. 104 return reallocate(allocator, NULL, 0, size_in_bits, clear); 105 } 106 107 template <class Allocator> 108 void BitMap::free(const Allocator& allocator, bm_word_t* map, idx_t size_in_bits) { 109 bm_word_t* ret = reallocate(allocator, map, size_in_bits, 0); 110 assert(ret == NULL, "Reallocate shouldn't have allocated"); 111 } 112 113 template <class Allocator> 114 void BitMap::resize(const Allocator& allocator, idx_t new_size_in_bits, bool clear) { 115 bm_word_t* new_map = reallocate(allocator, map(), size(), new_size_in_bits, clear); 116 117 update(new_map, new_size_in_bits); 118 } 119 120 template <class Allocator> 121 void BitMap::initialize(const Allocator& allocator, idx_t size_in_bits, bool clear) { 122 assert(map() == NULL, "precondition"); 123 assert(size() == 0, "precondition"); 124 125 resize(allocator, size_in_bits, clear); 126 } 127 128 template <class Allocator> 129 void BitMap::reinitialize(const Allocator& allocator, idx_t new_size_in_bits, bool clear) { 130 // Remove previous bits - no need to clear 131 resize(allocator, 0, false /* clear */); 132 133 initialize(allocator, new_size_in_bits, clear); 134 } 135 136 ResourceBitMap::ResourceBitMap(idx_t size_in_bits, bool clear) 137 : BitMap(allocate(ResourceBitMapAllocator(), size_in_bits, clear), size_in_bits) { 138 } 139 140 void ResourceBitMap::resize(idx_t new_size_in_bits) { 141 BitMap::resize(ResourceBitMapAllocator(), new_size_in_bits, true /* clear */); 142 } 143 144 void ResourceBitMap::initialize(idx_t size_in_bits) { 145 BitMap::initialize(ResourceBitMapAllocator(), size_in_bits, true /* clear */); 146 } 147 148 void ResourceBitMap::reinitialize(idx_t size_in_bits) { 149 BitMap::reinitialize(ResourceBitMapAllocator(), size_in_bits, true /* clear */); 150 } 151 152 ArenaBitMap::ArenaBitMap(Arena* arena, idx_t size_in_bits) 153 : BitMap(allocate(ArenaBitMapAllocator(arena), size_in_bits), size_in_bits) { 154 } 155 156 CHeapBitMap::CHeapBitMap(idx_t size_in_bits, MEMFLAGS flags, bool clear) 157 : BitMap(allocate(CHeapBitMapAllocator(flags), size_in_bits, clear), size_in_bits), _flags(flags) { 158 } 159 160 CHeapBitMap::~CHeapBitMap() { 161 free(CHeapBitMapAllocator(_flags), map(), size()); 162 } 163 164 void CHeapBitMap::resize(idx_t new_size_in_bits, bool clear) { 165 BitMap::resize(CHeapBitMapAllocator(_flags), new_size_in_bits, clear); 166 } 167 168 void CHeapBitMap::initialize(idx_t size_in_bits, bool clear) { 169 BitMap::initialize(CHeapBitMapAllocator(_flags), size_in_bits, clear); 170 } 171 172 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) { 173 BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear); 174 } 175 176 #ifdef ASSERT 177 void BitMap::verify_size(idx_t size_in_bits) { 178 assert(size_in_bits <= max_size_in_bits(), 179 "out of bounds: " SIZE_FORMAT, size_in_bits); 180 } 181 182 void BitMap::verify_index(idx_t bit) const { 183 assert(bit < _size, 184 "BitMap index out of bounds: " SIZE_FORMAT " >= " SIZE_FORMAT, 185 bit, _size); 186 } 187 188 void BitMap::verify_limit(idx_t bit) const { 189 assert(bit <= _size, 190 "BitMap limit out of bounds: " SIZE_FORMAT " > " SIZE_FORMAT, 191 bit, _size); 192 } 193 194 void BitMap::verify_range(idx_t beg, idx_t end) const { 195 assert(beg <= end, 196 "BitMap range error: " SIZE_FORMAT " > " SIZE_FORMAT, beg, end); 197 verify_limit(end); 198 } 199 #endif // #ifdef ASSERT 200 201 void BitMap::pretouch() { 202 os::pretouch_memory(word_addr(0), word_addr(size())); 203 } 204 205 void BitMap::set_range_within_word(idx_t beg, idx_t end) { 206 // With a valid range (beg <= end), this test ensures that end != 0, as 207 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 208 if (beg != end) { 209 bm_word_t mask = inverted_bit_mask_for_range(beg, end); 210 *word_addr(beg) |= ~mask; 211 } 212 } 213 214 void BitMap::clear_range_within_word(idx_t beg, idx_t end) { 215 // With a valid range (beg <= end), this test ensures that end != 0, as 216 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 217 if (beg != end) { 218 bm_word_t mask = inverted_bit_mask_for_range(beg, end); 219 *word_addr(beg) &= mask; 220 } 221 } 222 223 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { 224 assert(value == 0 || value == 1, "0 for clear, 1 for set"); 225 // With a valid range (beg <= end), this test ensures that end != 0, as 226 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 227 if (beg != end) { 228 bm_word_t* pw = word_addr(beg); 229 bm_word_t w = *pw; 230 bm_word_t mr = inverted_bit_mask_for_range(beg, end); 231 bm_word_t nw = value ? (w | ~mr) : (w & mr); 232 while (true) { 233 bm_word_t res = Atomic::cmpxchg(pw, w, nw); 234 if (res == w) break; 235 w = res; 236 nw = value ? (w | ~mr) : (w & mr); 237 } 238 } 239 } 240 241 void BitMap::set_range(idx_t beg, idx_t end) { 242 verify_range(beg, end); 243 244 idx_t beg_full_word = to_words_align_up(beg); 245 idx_t end_full_word = to_words_align_down(end); 246 247 if (beg_full_word < end_full_word) { 248 // The range includes at least one full word. 249 set_range_within_word(beg, bit_index(beg_full_word)); 250 set_range_of_words(beg_full_word, end_full_word); 251 set_range_within_word(bit_index(end_full_word), end); 252 } else { 253 // The range spans at most 2 partial words. 254 idx_t boundary = MIN2(bit_index(beg_full_word), end); 255 set_range_within_word(beg, boundary); 256 set_range_within_word(boundary, end); 257 } 258 } 259 260 void BitMap::clear_range(idx_t beg, idx_t end) { 261 verify_range(beg, end); 262 263 idx_t beg_full_word = to_words_align_up(beg); 264 idx_t end_full_word = to_words_align_down(end); 265 266 if (beg_full_word < end_full_word) { 267 // The range includes at least one full word. 268 clear_range_within_word(beg, bit_index(beg_full_word)); 269 clear_range_of_words(beg_full_word, end_full_word); 270 clear_range_within_word(bit_index(end_full_word), end); 271 } else { 272 // The range spans at most 2 partial words. 273 idx_t boundary = MIN2(bit_index(beg_full_word), end); 274 clear_range_within_word(beg, boundary); 275 clear_range_within_word(boundary, end); 276 } 277 } 278 279 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) { 280 // There is little point to call large version on small ranges. 281 // Need to check carefully, keeping potential idx_t over/underflow in mind, 282 // because beg_full_word > end_full_word can occur when beg and end are in 283 // the same word. 284 // The threshold should be at least one word. 285 STATIC_ASSERT(small_range_words >= 1); 286 return beg_full_word + small_range_words >= end_full_word; 287 } 288 289 void BitMap::set_large_range(idx_t beg, idx_t end) { 290 verify_range(beg, end); 291 292 idx_t beg_full_word = to_words_align_up(beg); 293 idx_t end_full_word = to_words_align_down(end); 294 295 if (is_small_range_of_words(beg_full_word, end_full_word)) { 296 set_range(beg, end); 297 return; 298 } 299 300 // The range includes at least one full word. 301 set_range_within_word(beg, bit_index(beg_full_word)); 302 set_large_range_of_words(beg_full_word, end_full_word); 303 set_range_within_word(bit_index(end_full_word), end); 304 } 305 306 void BitMap::clear_large_range(idx_t beg, idx_t end) { 307 verify_range(beg, end); 308 309 idx_t beg_full_word = to_words_align_up(beg); 310 idx_t end_full_word = to_words_align_down(end); 311 312 if (is_small_range_of_words(beg_full_word, end_full_word)) { 313 clear_range(beg, end); 314 return; 315 } 316 317 // The range includes at least one full word. 318 clear_range_within_word(beg, bit_index(beg_full_word)); 319 clear_large_range_of_words(beg_full_word, end_full_word); 320 clear_range_within_word(bit_index(end_full_word), end); 321 } 322 323 void BitMap::at_put(idx_t offset, bool value) { 324 if (value) { 325 set_bit(offset); 326 } else { 327 clear_bit(offset); 328 } 329 } 330 331 // Return true to indicate that this thread changed 332 // the bit, false to indicate that someone else did. 333 // In either case, the requested bit is in the 334 // requested state some time during the period that 335 // this thread is executing this call. More importantly, 336 // if no other thread is executing an action to 337 // change the requested bit to a state other than 338 // the one that this thread is trying to set it to, 339 // then the the bit is in the expected state 340 // at exit from this method. However, rather than 341 // make such a strong assertion here, based on 342 // assuming such constrained use (which though true 343 // today, could change in the future to service some 344 // funky parallel algorithm), we encourage callers 345 // to do such verification, as and when appropriate. 346 bool BitMap::par_at_put(idx_t bit, bool value) { 347 return value ? par_set_bit(bit) : par_clear_bit(bit); 348 } 349 350 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { 351 if (value) { 352 set_range(start_offset, end_offset); 353 } else { 354 clear_range(start_offset, end_offset); 355 } 356 } 357 358 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { 359 verify_range(beg, end); 360 361 idx_t beg_full_word = to_words_align_up(beg); 362 idx_t end_full_word = to_words_align_down(end); 363 364 if (beg_full_word < end_full_word) { 365 // The range includes at least one full word. 366 par_put_range_within_word(beg, bit_index(beg_full_word), value); 367 if (value) { 368 set_range_of_words(beg_full_word, end_full_word); 369 } else { 370 clear_range_of_words(beg_full_word, end_full_word); 371 } 372 par_put_range_within_word(bit_index(end_full_word), end, value); 373 } else { 374 // The range spans at most 2 partial words. 375 idx_t boundary = MIN2(bit_index(beg_full_word), end); 376 par_put_range_within_word(beg, boundary, value); 377 par_put_range_within_word(boundary, end, value); 378 } 379 380 } 381 382 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { 383 if (value) { 384 set_large_range(beg, end); 385 } else { 386 clear_large_range(beg, end); 387 } 388 } 389 390 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { 391 verify_range(beg, end); 392 393 idx_t beg_full_word = to_words_align_up(beg); 394 idx_t end_full_word = to_words_align_down(end); 395 396 if (is_small_range_of_words(beg_full_word, end_full_word)) { 397 par_at_put_range(beg, end, value); 398 return; 399 } 400 401 // The range includes at least one full word. 402 par_put_range_within_word(beg, bit_index(beg_full_word), value); 403 if (value) { 404 set_large_range_of_words(beg_full_word, end_full_word); 405 } else { 406 clear_large_range_of_words(beg_full_word, end_full_word); 407 } 408 par_put_range_within_word(bit_index(end_full_word), end, value); 409 } 410 411 inline bm_word_t tail_mask(idx_t tail_bits) { 412 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called. 413 assert(tail_bits < (idx_t)BitsPerWord, "precondition"); 414 return (bm_word_t(1) << tail_bits) - 1; 415 } 416 417 // Get the low tail_bits of value, which is the last partial word of a map. 418 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) { 419 return value & tail_mask(tail_bits); 420 } 421 422 // Compute the new last word of a map with a non-aligned length. 423 // new_value has the new trailing bits of the map in the low tail_bits. 424 // old_value is the last word of the map, including bits beyond the end. 425 // Returns old_value with the low tail_bits replaced by the corresponding 426 // bits in new_value. 427 inline bm_word_t merge_tail_of_map(bm_word_t new_value, 428 bm_word_t old_value, 429 idx_t tail_bits) { 430 bm_word_t mask = tail_mask(tail_bits); 431 return (new_value & mask) | (old_value & ~mask); 432 } 433 434 bool BitMap::contains(const BitMap& other) const { 435 assert(size() == other.size(), "must have same size"); 436 const bm_word_t* dest_map = map(); 437 const bm_word_t* other_map = other.map(); 438 idx_t limit = to_words_align_down(size()); 439 for (idx_t index = 0; index < limit; ++index) { 440 // false if other bitmap has bits set which are clear in this bitmap. 441 if ((~dest_map[index] & other_map[index]) != 0) return false; 442 } 443 idx_t rest = bit_in_word(size()); 444 // true unless there is a partial-word tail in which the other 445 // bitmap has bits set which are clear in this bitmap. 446 return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0; 447 } 448 449 bool BitMap::intersects(const BitMap& other) const { 450 assert(size() == other.size(), "must have same size"); 451 const bm_word_t* dest_map = map(); 452 const bm_word_t* other_map = other.map(); 453 idx_t limit = to_words_align_down(size()); 454 for (idx_t index = 0; index < limit; ++index) { 455 if ((dest_map[index] & other_map[index]) != 0) return true; 456 } 457 idx_t rest = bit_in_word(size()); 458 // false unless there is a partial-word tail with non-empty intersection. 459 return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0; 460 } 461 462 void BitMap::set_union(const BitMap& other) { 463 assert(size() == other.size(), "must have same size"); 464 bm_word_t* dest_map = map(); 465 const bm_word_t* other_map = other.map(); 466 idx_t limit = to_words_align_down(size()); 467 for (idx_t index = 0; index < limit; ++index) { 468 dest_map[index] |= other_map[index]; 469 } 470 idx_t rest = bit_in_word(size()); 471 if (rest > 0) { 472 bm_word_t orig = dest_map[limit]; 473 dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest); 474 } 475 } 476 477 void BitMap::set_difference(const BitMap& other) { 478 assert(size() == other.size(), "must have same size"); 479 bm_word_t* dest_map = map(); 480 const bm_word_t* other_map = other.map(); 481 idx_t limit = to_words_align_down(size()); 482 for (idx_t index = 0; index < limit; ++index) { 483 dest_map[index] &= ~other_map[index]; 484 } 485 idx_t rest = bit_in_word(size()); 486 if (rest > 0) { 487 bm_word_t orig = dest_map[limit]; 488 dest_map[limit] = merge_tail_of_map(orig & ~other_map[limit], orig, rest); 489 } 490 } 491 492 void BitMap::set_intersection(const BitMap& other) { 493 assert(size() == other.size(), "must have same size"); 494 bm_word_t* dest_map = map(); 495 const bm_word_t* other_map = other.map(); 496 idx_t limit = to_words_align_down(size()); 497 for (idx_t index = 0; index < limit; ++index) { 498 dest_map[index] &= other_map[index]; 499 } 500 idx_t rest = bit_in_word(size()); 501 if (rest > 0) { 502 bm_word_t orig = dest_map[limit]; 503 dest_map[limit] = merge_tail_of_map(orig & other_map[limit], orig, rest); 504 } 505 } 506 507 bool BitMap::set_union_with_result(const BitMap& other) { 508 assert(size() == other.size(), "must have same size"); 509 bool changed = false; 510 bm_word_t* dest_map = map(); 511 const bm_word_t* other_map = other.map(); 512 idx_t limit = to_words_align_down(size()); 513 for (idx_t index = 0; index < limit; ++index) { 514 bm_word_t orig = dest_map[index]; 515 bm_word_t temp = orig | other_map[index]; 516 changed = changed || (temp != orig); 517 dest_map[index] = temp; 518 } 519 idx_t rest = bit_in_word(size()); 520 if (rest > 0) { 521 bm_word_t orig = dest_map[limit]; 522 bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest); 523 changed = changed || (temp != orig); 524 dest_map[limit] = temp; 525 } 526 return changed; 527 } 528 529 bool BitMap::set_difference_with_result(const BitMap& other) { 530 assert(size() == other.size(), "must have same size"); 531 bool changed = false; 532 bm_word_t* dest_map = map(); 533 const bm_word_t* other_map = other.map(); 534 idx_t limit = to_words_align_down(size()); 535 for (idx_t index = 0; index < limit; ++index) { 536 bm_word_t orig = dest_map[index]; 537 bm_word_t temp = orig & ~other_map[index]; 538 changed = changed || (temp != orig); 539 dest_map[index] = temp; 540 } 541 idx_t rest = bit_in_word(size()); 542 if (rest > 0) { 543 bm_word_t orig = dest_map[limit]; 544 bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest); 545 changed = changed || (temp != orig); 546 dest_map[limit] = temp; 547 } 548 return changed; 549 } 550 551 bool BitMap::set_intersection_with_result(const BitMap& other) { 552 assert(size() == other.size(), "must have same size"); 553 bool changed = false; 554 bm_word_t* dest_map = map(); 555 const bm_word_t* other_map = other.map(); 556 idx_t limit = to_words_align_down(size()); 557 for (idx_t index = 0; index < limit; ++index) { 558 bm_word_t orig = dest_map[index]; 559 bm_word_t temp = orig & other_map[index]; 560 changed = changed || (temp != orig); 561 dest_map[index] = temp; 562 } 563 idx_t rest = bit_in_word(size()); 564 if (rest > 0) { 565 bm_word_t orig = dest_map[limit]; 566 bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest); 567 changed = changed || (temp != orig); 568 dest_map[limit] = temp; 569 } 570 return changed; 571 } 572 573 void BitMap::set_from(const BitMap& other) { 574 assert(size() == other.size(), "must have same size"); 575 bm_word_t* dest_map = map(); 576 const bm_word_t* other_map = other.map(); 577 idx_t copy_words = to_words_align_down(size()); 578 Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words); 579 idx_t rest = bit_in_word(size()); 580 if (rest > 0) { 581 dest_map[copy_words] = merge_tail_of_map(other_map[copy_words], 582 dest_map[copy_words], 583 rest); 584 } 585 } 586 587 bool BitMap::is_same(const BitMap& other) const { 588 assert(size() == other.size(), "must have same size"); 589 const bm_word_t* dest_map = map(); 590 const bm_word_t* other_map = other.map(); 591 idx_t limit = to_words_align_down(size()); 592 for (idx_t index = 0; index < limit; ++index) { 593 if (dest_map[index] != other_map[index]) return false; 594 } 595 idx_t rest = bit_in_word(size()); 596 return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0); 597 } 598 599 bool BitMap::is_full() const { 600 const bm_word_t* words = map(); 601 idx_t limit = to_words_align_down(size()); 602 for (idx_t index = 0; index < limit; ++index) { 603 if (~words[index] != 0) return false; 604 } 605 idx_t rest = bit_in_word(size()); 606 return (rest == 0) || (tail_of_map(~words[limit], rest) == 0); 607 } 608 609 bool BitMap::is_empty() const { 610 const bm_word_t* words = map(); 611 idx_t limit = to_words_align_down(size()); 612 for (idx_t index = 0; index < limit; ++index) { 613 if (words[index] != 0) return false; 614 } 615 idx_t rest = bit_in_word(size()); 616 return (rest == 0) || (tail_of_map(words[limit], rest) == 0); 617 } 618 619 void BitMap::clear_large() { 620 clear_large_range_of_words(0, size_in_words()); 621 } 622 623 // Note that if the closure itself modifies the bitmap 624 // then modifications in and to the left of the _bit_ being 625 // currently sampled will not be seen. Note also that the 626 // interval [leftOffset, rightOffset) is right open. 627 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { 628 verify_range(leftOffset, rightOffset); 629 630 idx_t startIndex = to_words_align_down(leftOffset); 631 idx_t endIndex = to_words_align_up(rightOffset); 632 for (idx_t index = startIndex, offset = leftOffset; 633 offset < rightOffset && index < endIndex; 634 offset = (++index) << LogBitsPerWord) { 635 idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); 636 for (; offset < rightOffset && rest != 0; offset++) { 637 if (rest & 1) { 638 if (!blk->do_bit(offset)) return false; 639 // resample at each closure application 640 // (see, for instance, CMS bug 4525989) 641 rest = map(index) >> (offset & (BitsPerWord -1)); 642 } 643 rest = rest >> 1; 644 } 645 } 646 return true; 647 } 648 649 const BitMap::idx_t* BitMap::_pop_count_table = NULL; 650 651 void BitMap::init_pop_count_table() { 652 if (_pop_count_table == NULL) { 653 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal); 654 for (uint i = 0; i < 256; i++) { 655 table[i] = num_set_bits(i); 656 } 657 658 if (!Atomic::replace_if_null(&_pop_count_table, table)) { 659 guarantee(_pop_count_table != NULL, "invariant"); 660 FREE_C_HEAP_ARRAY(idx_t, table); 661 } 662 } 663 } 664 665 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) { 666 idx_t bits = 0; 667 668 while (w != 0) { 669 while ((w & 1) == 0) { 670 w >>= 1; 671 } 672 bits++; 673 w >>= 1; 674 } 675 return bits; 676 } 677 678 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { 679 assert(_pop_count_table != NULL, "precondition"); 680 return _pop_count_table[c]; 681 } 682 683 BitMap::idx_t BitMap::count_one_bits() const { 684 init_pop_count_table(); // If necessary. 685 idx_t sum = 0; 686 typedef unsigned char uchar; 687 for (idx_t i = 0; i < size_in_words(); i++) { 688 bm_word_t w = map()[i]; 689 for (size_t j = 0; j < sizeof(bm_word_t); j++) { 690 sum += num_set_bits_from_table(uchar(w & 255)); 691 w >>= 8; 692 } 693 } 694 return sum; 695 } 696 697 void BitMap::print_on_error(outputStream* st, const char* prefix) const { 698 st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")", 699 prefix, p2i(map()), p2i((char*)map() + (size() >> LogBitsPerByte))); 700 } 701 702 void BitMap::write_to(bm_word_t* buffer, size_t buffer_size_in_bytes) const { 703 assert(buffer_size_in_bytes == size_in_bytes(), "must be"); 704 memcpy(buffer, _map, size_in_bytes()); 705 } 706 707 #ifndef PRODUCT 708 709 void BitMap::print_on(outputStream* st) const { 710 tty->print("Bitmap(" SIZE_FORMAT "):", size()); 711 for (idx_t index = 0; index < size(); index++) { 712 tty->print("%c", at(index) ? '1' : '0'); 713 } 714 tty->cr(); 715 } 716 717 #endif