1 /*
   2  * Copyright (c) 1997, 2018, 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) {
 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, 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) {
 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::write_to(bm_word_t* buffer, size_t buffer_size_in_bytes) const {
 676   assert(buffer_size_in_bytes == size_in_bytes(), "must be");
 677   memcpy(buffer, _map, size_in_bytes());
 678 }
 679 
 680 #ifndef PRODUCT
 681 
 682 void BitMap::print_on(outputStream* st) const {
 683   tty->print("Bitmap(" SIZE_FORMAT "):", size());
 684   for (idx_t index = 0; index < size(); index++) {
 685     tty->print("%c", at(index) ? '1' : '0');
 686   }
 687   tty->cr();
 688 }
 689 
 690 #endif