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