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 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
 267   // There is little point to call large version on small ranges.
 268   // Need to check carefully, keeping potential idx_t underflow in mind.
 269   // The threshold should be at least one word.
 270   STATIC_ASSERT(small_range_words >= 1);
 271   return (beg_full_word + small_range_words >= end_full_word);
 272 }
 273 
 274 void BitMap::set_large_range(idx_t beg, idx_t end) {
 275   verify_range(beg, end);
 276 
 277   idx_t beg_full_word = word_index_round_up(beg);
 278   idx_t end_full_word = word_index(end);
 279 
 280   if (is_small_range_of_words(beg_full_word, end_full_word)) {
 281     set_range(beg, end);
 282     return;
 283   }
 284 
 285   // The range includes at least one full word.
 286   set_range_within_word(beg, bit_index(beg_full_word));
 287   set_large_range_of_words(beg_full_word, end_full_word);
 288   set_range_within_word(bit_index(end_full_word), end);
 289 }
 290 
 291 void BitMap::clear_large_range(idx_t beg, idx_t end) {
 292   verify_range(beg, end);
 293 
 294   idx_t beg_full_word = word_index_round_up(beg);
 295   idx_t end_full_word = word_index(end);
 296 
 297   if (is_small_range_of_words(beg_full_word, end_full_word)) {
 298     clear_range(beg, end);
 299     return;
 300   }
 301 
 302   // The range includes at least one full word.
 303   clear_range_within_word(beg, bit_index(beg_full_word));
 304   clear_large_range_of_words(beg_full_word, end_full_word);
 305   clear_range_within_word(bit_index(end_full_word), end);
 306 }
 307 
 308 void BitMap::at_put(idx_t offset, bool value) {
 309   if (value) {
 310     set_bit(offset);
 311   } else {
 312     clear_bit(offset);
 313   }
 314 }
 315 
 316 // Return true to indicate that this thread changed
 317 // the bit, false to indicate that someone else did.
 318 // In either case, the requested bit is in the
 319 // requested state some time during the period that
 320 // this thread is executing this call. More importantly,
 321 // if no other thread is executing an action to
 322 // change the requested bit to a state other than
 323 // the one that this thread is trying to set it to,
 324 // then the the bit is in the expected state
 325 // at exit from this method. However, rather than
 326 // make such a strong assertion here, based on
 327 // assuming such constrained use (which though true
 328 // today, could change in the future to service some
 329 // funky parallel algorithm), we encourage callers
 330 // to do such verification, as and when appropriate.
 331 bool BitMap::par_at_put(idx_t bit, bool value) {
 332   return value ? par_set_bit(bit) : par_clear_bit(bit);
 333 }
 334 
 335 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
 336   if (value) {
 337     set_range(start_offset, end_offset);
 338   } else {
 339     clear_range(start_offset, end_offset);
 340   }
 341 }
 342 
 343 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
 344   verify_range(beg, end);
 345 
 346   idx_t beg_full_word = word_index_round_up(beg);
 347   idx_t end_full_word = word_index(end);
 348 
 349   if (beg_full_word < end_full_word) {
 350     // The range includes at least one full word.
 351     par_put_range_within_word(beg, bit_index(beg_full_word), value);
 352     if (value) {
 353       set_range_of_words(beg_full_word, end_full_word);
 354     } else {
 355       clear_range_of_words(beg_full_word, end_full_word);
 356     }
 357     par_put_range_within_word(bit_index(end_full_word), end, value);
 358   } else {
 359     // The range spans at most 2 partial words.
 360     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 361     par_put_range_within_word(beg, boundary, value);
 362     par_put_range_within_word(boundary, end, value);
 363   }
 364 
 365 }
 366 
 367 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
 368   if (value) {
 369     set_large_range(beg, end);
 370   } else {
 371     clear_large_range(beg, end);
 372   }
 373 }
 374 
 375 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
 376   verify_range(beg, end);
 377 
 378   idx_t beg_full_word = word_index_round_up(beg);
 379   idx_t end_full_word = word_index(end);
 380 
 381   if (is_small_range_of_words(beg_full_word, end_full_word)) {
 382     par_at_put_range(beg, end, value);
 383     return;
 384   }
 385 
 386   // The range includes at least one full word.
 387   par_put_range_within_word(beg, bit_index(beg_full_word), value);
 388   if (value) {
 389     set_large_range_of_words(beg_full_word, end_full_word);
 390   } else {
 391     clear_large_range_of_words(beg_full_word, end_full_word);
 392   }
 393   par_put_range_within_word(bit_index(end_full_word), end, value);
 394 }
 395 
 396 inline bm_word_t tail_mask(idx_t tail_bits) {
 397   assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
 398   assert(tail_bits < (idx_t)BitsPerWord, "precondition");
 399   return (bm_word_t(1) << tail_bits) - 1;
 400 }
 401 
 402 // Get the low tail_bits of value, which is the last partial word of a map.
 403 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
 404   return value & tail_mask(tail_bits);
 405 }
 406 
 407 // Compute the new last word of a map with a non-aligned length.
 408 // new_value has the new trailing bits of the map in the low tail_bits.
 409 // old_value is the last word of the map, including bits beyond the end.
 410 // Returns old_value with the low tail_bits replaced by the corresponding
 411 // bits in new_value.
 412 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
 413                                    bm_word_t old_value,
 414                                    idx_t tail_bits) {
 415   bm_word_t mask = tail_mask(tail_bits);
 416   return (new_value & mask) | (old_value & ~mask);
 417 }
 418 
 419 bool BitMap::contains(const BitMap& other) const {
 420   assert(size() == other.size(), "must have same size");
 421   const bm_word_t* dest_map = map();
 422   const bm_word_t* other_map = other.map();
 423   idx_t limit = word_index(size());
 424   for (idx_t index = 0; index < limit; ++index) {
 425     // false if other bitmap has bits set which are clear in this bitmap.
 426     if ((~dest_map[index] & other_map[index]) != 0) return false;
 427   }
 428   idx_t rest = bit_in_word(size());
 429   // true unless there is a partial-word tail in which the other
 430   // bitmap has bits set which are clear in this bitmap.
 431   return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0;
 432 }
 433 
 434 bool BitMap::intersects(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 = word_index(size());
 439   for (idx_t index = 0; index < limit; ++index) {
 440     if ((dest_map[index] & other_map[index]) != 0) return true;
 441   }
 442   idx_t rest = bit_in_word(size());
 443   // false unless there is a partial-word tail with non-empty intersection.
 444   return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0;
 445 }
 446 
 447 void BitMap::set_union(const BitMap& other) {
 448   assert(size() == other.size(), "must have same size");
 449   bm_word_t* dest_map = map();
 450   const bm_word_t* other_map = other.map();
 451   idx_t limit = word_index(size());
 452   for (idx_t index = 0; index < limit; ++index) {
 453     dest_map[index] |= other_map[index];
 454   }
 455   idx_t rest = bit_in_word(size());
 456   if (rest > 0) {
 457     bm_word_t orig = dest_map[limit];
 458     dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest);
 459   }
 460 }
 461 
 462 void BitMap::set_difference(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 = word_index(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_intersection(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 = word_index(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 bool BitMap::set_union_with_result(const BitMap& other) {
 493   assert(size() == other.size(), "must have same size");
 494   bool changed = false;
 495   bm_word_t* dest_map = map();
 496   const bm_word_t* other_map = other.map();
 497   idx_t limit = word_index(size());
 498   for (idx_t index = 0; index < limit; ++index) {
 499     bm_word_t orig = dest_map[index];
 500     bm_word_t temp = orig | other_map[index];
 501     changed = changed || (temp != orig);
 502     dest_map[index] = temp;
 503   }
 504   idx_t rest = bit_in_word(size());
 505   if (rest > 0) {
 506     bm_word_t orig = dest_map[limit];
 507     bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest);
 508     changed = changed || (temp != orig);
 509     dest_map[limit] = temp;
 510   }
 511   return changed;
 512 }
 513 
 514 bool BitMap::set_difference_with_result(const BitMap& other) {
 515   assert(size() == other.size(), "must have same size");
 516   bool changed = false;
 517   bm_word_t* dest_map = map();
 518   const bm_word_t* other_map = other.map();
 519   idx_t limit = word_index(size());
 520   for (idx_t index = 0; index < limit; ++index) {
 521     bm_word_t orig = dest_map[index];
 522     bm_word_t temp = orig & ~other_map[index];
 523     changed = changed || (temp != orig);
 524     dest_map[index] = temp;
 525   }
 526   idx_t rest = bit_in_word(size());
 527   if (rest > 0) {
 528     bm_word_t orig = dest_map[limit];
 529     bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
 530     changed = changed || (temp != orig);
 531     dest_map[limit] = temp;
 532   }
 533   return changed;
 534 }
 535 
 536 bool BitMap::set_intersection_with_result(const BitMap& other) {
 537   assert(size() == other.size(), "must have same size");
 538   bool changed = false;
 539   bm_word_t* dest_map = map();
 540   const bm_word_t* other_map = other.map();
 541   idx_t limit = word_index(size());
 542   for (idx_t index = 0; index < limit; ++index) {
 543     bm_word_t orig = dest_map[index];
 544     bm_word_t temp = orig & other_map[index];
 545     changed = changed || (temp != orig);
 546     dest_map[index] = temp;
 547   }
 548   idx_t rest = bit_in_word(size());
 549   if (rest > 0) {
 550     bm_word_t orig = dest_map[limit];
 551     bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest);
 552     changed = changed || (temp != orig);
 553     dest_map[limit] = temp;
 554   }
 555   return changed;
 556 }
 557 
 558 void BitMap::set_from(const BitMap& other) {
 559   assert(size() == other.size(), "must have same size");
 560   bm_word_t* dest_map = map();
 561   const bm_word_t* other_map = other.map();
 562   idx_t copy_words = word_index(size());
 563   Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
 564   idx_t rest = bit_in_word(size());
 565   if (rest > 0) {
 566     dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
 567                                              dest_map[copy_words],
 568                                              rest);
 569   }
 570 }
 571 
 572 bool BitMap::is_same(const BitMap& other) const {
 573   assert(size() == other.size(), "must have same size");
 574   const bm_word_t* dest_map = map();
 575   const bm_word_t* other_map = other.map();
 576   idx_t limit = word_index(size());
 577   for (idx_t index = 0; index < limit; ++index) {
 578     if (dest_map[index] != other_map[index]) return false;
 579   }
 580   idx_t rest = bit_in_word(size());
 581   return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
 582 }
 583 
 584 bool BitMap::is_full() const {
 585   const bm_word_t* words = map();
 586   idx_t limit = word_index(size());
 587   for (idx_t index = 0; index < limit; ++index) {
 588     if (~words[index] != 0) return false;
 589   }
 590   idx_t rest = bit_in_word(size());
 591   return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
 592 }
 593 
 594 bool BitMap::is_empty() const {
 595   const bm_word_t* words = map();
 596   idx_t limit = word_index(size());
 597   for (idx_t index = 0; index < limit; ++index) {
 598     if (words[index] != 0) return false;
 599   }
 600   idx_t rest = bit_in_word(size());
 601   return (rest == 0) || (tail_of_map(words[limit], rest) == 0);
 602 }
 603 
 604 void BitMap::clear_large() {
 605   clear_large_range_of_words(0, size_in_words());
 606 }
 607 
 608 // Note that if the closure itself modifies the bitmap
 609 // then modifications in and to the left of the _bit_ being
 610 // currently sampled will not be seen. Note also that the
 611 // interval [leftOffset, rightOffset) is right open.
 612 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
 613   verify_range(leftOffset, rightOffset);
 614 
 615   idx_t startIndex = word_index(leftOffset);
 616   idx_t endIndex   = MIN2(word_index(rightOffset) + 1, size_in_words());
 617   for (idx_t index = startIndex, offset = leftOffset;
 618        offset < rightOffset && index < endIndex;
 619        offset = (++index) << LogBitsPerWord) {
 620     idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
 621     for (; offset < rightOffset && rest != 0; offset++) {
 622       if (rest & 1) {
 623         if (!blk->do_bit(offset)) return false;
 624         //  resample at each closure application
 625         // (see, for instance, CMS bug 4525989)
 626         rest = map(index) >> (offset & (BitsPerWord -1));
 627       }
 628       rest = rest >> 1;
 629     }
 630   }
 631   return true;
 632 }
 633 
 634 const BitMap::idx_t* BitMap::_pop_count_table = NULL;
 635 
 636 void BitMap::init_pop_count_table() {
 637   if (_pop_count_table == NULL) {
 638     BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal);
 639     for (uint i = 0; i < 256; i++) {
 640       table[i] = num_set_bits(i);
 641     }
 642 
 643     if (!Atomic::replace_if_null(table, &_pop_count_table)) {
 644       guarantee(_pop_count_table != NULL, "invariant");
 645       FREE_C_HEAP_ARRAY(idx_t, table);
 646     }
 647   }
 648 }
 649 
 650 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) {
 651   idx_t bits = 0;
 652 
 653   while (w != 0) {
 654     while ((w & 1) == 0) {
 655       w >>= 1;
 656     }
 657     bits++;
 658     w >>= 1;
 659   }
 660   return bits;
 661 }
 662 
 663 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) {
 664   assert(_pop_count_table != NULL, "precondition");
 665   return _pop_count_table[c];
 666 }
 667 
 668 BitMap::idx_t BitMap::count_one_bits() const {
 669   init_pop_count_table(); // If necessary.
 670   idx_t sum = 0;
 671   typedef unsigned char uchar;
 672   for (idx_t i = 0; i < size_in_words(); i++) {
 673     bm_word_t w = map()[i];
 674     for (size_t j = 0; j < sizeof(bm_word_t); j++) {
 675       sum += num_set_bits_from_table(uchar(w & 255));
 676       w >>= 8;
 677     }
 678   }
 679   return sum;
 680 }
 681 
 682 void BitMap::print_on_error(outputStream* st, const char* prefix) const {
 683   st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")",
 684       prefix, p2i(map()), p2i((char*)map() + (size() >> LogBitsPerByte)));
 685 }
 686 
 687 #ifndef PRODUCT
 688 
 689 void BitMap::print_on(outputStream* st) const {
 690   tty->print("Bitmap(" SIZE_FORMAT "):", size());
 691   for (idx_t index = 0; index < size(); index++) {
 692     tty->print("%c", at(index) ? '1' : '0');
 693   }
 694   tty->cr();
 695 }
 696 
 697 #endif