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