< prev index next >

src/hotspot/share/utilities/bitMap.cpp

Print this page
rev 57098 : [mq]: max_size
rev 57099 : [mq]: improve


 157     : BitMap(allocate(CHeapBitMapAllocator(flags), size_in_bits, clear), size_in_bits), _flags(flags) {
 158 }
 159 
 160 CHeapBitMap::~CHeapBitMap() {
 161   free(CHeapBitMapAllocator(_flags), map(), size());
 162 }
 163 
 164 void CHeapBitMap::resize(idx_t new_size_in_bits, bool clear) {
 165   BitMap::resize(CHeapBitMapAllocator(_flags), new_size_in_bits, clear);
 166 }
 167 
 168 void CHeapBitMap::initialize(idx_t size_in_bits, bool clear) {
 169   BitMap::initialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
 170 }
 171 
 172 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
 173   BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
 174 }
 175 
 176 #ifdef ASSERT
 177 void BitMap::verify_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) {


 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(pw, w, nw);
 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 


 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;


 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() {




 157     : BitMap(allocate(CHeapBitMapAllocator(flags), size_in_bits, clear), size_in_bits), _flags(flags) {
 158 }
 159 
 160 CHeapBitMap::~CHeapBitMap() {
 161   free(CHeapBitMapAllocator(_flags), map(), size());
 162 }
 163 
 164 void CHeapBitMap::resize(idx_t new_size_in_bits, bool clear) {
 165   BitMap::resize(CHeapBitMapAllocator(_flags), new_size_in_bits, clear);
 166 }
 167 
 168 void CHeapBitMap::initialize(idx_t size_in_bits, bool clear) {
 169   BitMap::initialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
 170 }
 171 
 172 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
 173   BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
 174 }
 175 
 176 #ifdef ASSERT
 177 void BitMap::verify_size(idx_t size_in_bits) {
 178   assert(size_in_bits <= max_size_in_bits(),
 179          "out of bounds: " SIZE_FORMAT, size_in_bits);
 180 }
 181 
 182 void BitMap::verify_index(idx_t bit) const {
 183   assert(bit < _size,
 184          "BitMap index out of bounds: " SIZE_FORMAT " >= " SIZE_FORMAT,
 185          bit, _size);
 186 }
 187 
 188 void BitMap::verify_limit(idx_t bit) const {
 189   assert(bit <= _size,
 190          "BitMap limit out of bounds: " SIZE_FORMAT " > " SIZE_FORMAT,
 191          bit, _size);
 192 }
 193 
 194 void BitMap::verify_range(idx_t beg, idx_t end) const {
 195   assert(beg <= end,
 196          "BitMap range error: " SIZE_FORMAT " > " SIZE_FORMAT, beg, end);
 197   verify_limit(end);
 198 }
 199 #endif // #ifdef ASSERT
 200 
 201 void BitMap::pretouch() {
 202   os::pretouch_memory(word_addr(0), word_addr(size()));
 203 }
 204 
 205 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
 206   // With a valid range (beg <= end), this test ensures that end != 0, as
 207   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
 208   if (beg != end) {
 209     bm_word_t mask = inverted_bit_mask_for_range(beg, end);
 210     *word_addr(beg) |= ~mask;
 211   }
 212 }
 213 
 214 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
 215   // With a valid range (beg <= end), this test ensures that end != 0, as
 216   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
 217   if (beg != end) {


 224   assert(value == 0 || value == 1, "0 for clear, 1 for set");
 225   // With a valid range (beg <= end), this test ensures that end != 0, as
 226   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
 227   if (beg != end) {
 228     bm_word_t* pw = word_addr(beg);
 229     bm_word_t  w  = *pw;
 230     bm_word_t  mr = inverted_bit_mask_for_range(beg, end);
 231     bm_word_t  nw = value ? (w | ~mr) : (w & mr);
 232     while (true) {
 233       bm_word_t res = Atomic::cmpxchg(pw, w, nw);
 234       if (res == w) break;
 235       w  = res;
 236       nw = value ? (w | ~mr) : (w & mr);
 237     }
 238   }
 239 }
 240 
 241 void BitMap::set_range(idx_t beg, idx_t end) {
 242   verify_range(beg, end);
 243 
 244   idx_t beg_full_word = to_words_align_up(beg);
 245   idx_t end_full_word = to_words_align_down(end);
 246 
 247   if (beg_full_word < end_full_word) {
 248     // The range includes at least one full word.
 249     set_range_within_word(beg, bit_index(beg_full_word));
 250     set_range_of_words(beg_full_word, end_full_word);
 251     set_range_within_word(bit_index(end_full_word), end);
 252   } else {
 253     // The range spans at most 2 partial words.
 254     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 255     set_range_within_word(beg, boundary);
 256     set_range_within_word(boundary, end);
 257   }
 258 }
 259 
 260 void BitMap::clear_range(idx_t beg, idx_t end) {
 261   verify_range(beg, end);
 262 
 263   idx_t beg_full_word = to_words_align_up(beg);
 264   idx_t end_full_word = to_words_align_down(end);
 265 
 266   if (beg_full_word < end_full_word) {
 267     // The range includes at least one full word.
 268     clear_range_within_word(beg, bit_index(beg_full_word));
 269     clear_range_of_words(beg_full_word, end_full_word);
 270     clear_range_within_word(bit_index(end_full_word), end);
 271   } else {
 272     // The range spans at most 2 partial words.
 273     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 274     clear_range_within_word(beg, boundary);
 275     clear_range_within_word(boundary, end);
 276   }
 277 }
 278 
 279 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
 280   // There is little point to call large version on small ranges.
 281   // Need to check carefully, keeping potential idx_t over/underflow in mind,
 282   // because beg_full_word > end_full_word can occur when beg and end are in
 283   // the same word.
 284   // The threshold should be at least one word.
 285   STATIC_ASSERT(small_range_words >= 1);
 286   return beg_full_word + small_range_words >= end_full_word;
 287 }
 288 
 289 void BitMap::set_large_range(idx_t beg, idx_t end) {
 290   verify_range(beg, end);
 291 
 292   idx_t beg_full_word = to_words_align_up(beg);
 293   idx_t end_full_word = to_words_align_down(end);
 294 
 295   if (is_small_range_of_words(beg_full_word, end_full_word)) {
 296     set_range(beg, end);
 297     return;
 298   }
 299 
 300   // The range includes at least one full word.
 301   set_range_within_word(beg, bit_index(beg_full_word));
 302   set_large_range_of_words(beg_full_word, end_full_word);
 303   set_range_within_word(bit_index(end_full_word), end);
 304 }
 305 
 306 void BitMap::clear_large_range(idx_t beg, idx_t end) {
 307   verify_range(beg, end);
 308 
 309   idx_t beg_full_word = to_words_align_up(beg);
 310   idx_t end_full_word = to_words_align_down(end);
 311 
 312   if (is_small_range_of_words(beg_full_word, end_full_word)) {
 313     clear_range(beg, end);
 314     return;
 315   }
 316 
 317   // The range includes at least one full word.
 318   clear_range_within_word(beg, bit_index(beg_full_word));
 319   clear_large_range_of_words(beg_full_word, end_full_word);
 320   clear_range_within_word(bit_index(end_full_word), end);
 321 }
 322 
 323 void BitMap::at_put(idx_t offset, bool value) {
 324   if (value) {
 325     set_bit(offset);
 326   } else {
 327     clear_bit(offset);
 328   }
 329 }
 330 


 341 // make such a strong assertion here, based on
 342 // assuming such constrained use (which though true
 343 // today, could change in the future to service some
 344 // funky parallel algorithm), we encourage callers
 345 // to do such verification, as and when appropriate.
 346 bool BitMap::par_at_put(idx_t bit, bool value) {
 347   return value ? par_set_bit(bit) : par_clear_bit(bit);
 348 }
 349 
 350 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
 351   if (value) {
 352     set_range(start_offset, end_offset);
 353   } else {
 354     clear_range(start_offset, end_offset);
 355   }
 356 }
 357 
 358 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
 359   verify_range(beg, end);
 360 
 361   idx_t beg_full_word = to_words_align_up(beg);
 362   idx_t end_full_word = to_words_align_down(end);
 363 
 364   if (beg_full_word < end_full_word) {
 365     // The range includes at least one full word.
 366     par_put_range_within_word(beg, bit_index(beg_full_word), value);
 367     if (value) {
 368       set_range_of_words(beg_full_word, end_full_word);
 369     } else {
 370       clear_range_of_words(beg_full_word, end_full_word);
 371     }
 372     par_put_range_within_word(bit_index(end_full_word), end, value);
 373   } else {
 374     // The range spans at most 2 partial words.
 375     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 376     par_put_range_within_word(beg, boundary, value);
 377     par_put_range_within_word(boundary, end, value);
 378   }
 379 
 380 }
 381 
 382 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
 383   if (value) {
 384     set_large_range(beg, end);
 385   } else {
 386     clear_large_range(beg, end);
 387   }
 388 }
 389 
 390 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
 391   verify_range(beg, end);
 392 
 393   idx_t beg_full_word = to_words_align_up(beg);
 394   idx_t end_full_word = to_words_align_down(end);
 395 
 396   if (is_small_range_of_words(beg_full_word, end_full_word)) {
 397     par_at_put_range(beg, end, value);
 398     return;
 399   }
 400 
 401   // The range includes at least one full word.
 402   par_put_range_within_word(beg, bit_index(beg_full_word), value);
 403   if (value) {
 404     set_large_range_of_words(beg_full_word, end_full_word);
 405   } else {
 406     clear_large_range_of_words(beg_full_word, end_full_word);
 407   }
 408   par_put_range_within_word(bit_index(end_full_word), end, value);
 409 }
 410 
 411 inline bm_word_t tail_mask(idx_t tail_bits) {
 412   assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
 413   assert(tail_bits < (idx_t)BitsPerWord, "precondition");
 414   return (bm_word_t(1) << tail_bits) - 1;


 418 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
 419   return value & tail_mask(tail_bits);
 420 }
 421 
 422 // Compute the new last word of a map with a non-aligned length.
 423 // new_value has the new trailing bits of the map in the low tail_bits.
 424 // old_value is the last word of the map, including bits beyond the end.
 425 // Returns old_value with the low tail_bits replaced by the corresponding
 426 // bits in new_value.
 427 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
 428                                    bm_word_t old_value,
 429                                    idx_t tail_bits) {
 430   bm_word_t mask = tail_mask(tail_bits);
 431   return (new_value & mask) | (old_value & ~mask);
 432 }
 433 
 434 bool BitMap::contains(const BitMap& other) const {
 435   assert(size() == other.size(), "must have same size");
 436   const bm_word_t* dest_map = map();
 437   const bm_word_t* other_map = other.map();
 438   idx_t limit = to_words_align_down(size());
 439   for (idx_t index = 0; index < limit; ++index) {
 440     // false if other bitmap has bits set which are clear in this bitmap.
 441     if ((~dest_map[index] & other_map[index]) != 0) return false;
 442   }
 443   idx_t rest = bit_in_word(size());
 444   // true unless there is a partial-word tail in which the other
 445   // bitmap has bits set which are clear in this bitmap.
 446   return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0;
 447 }
 448 
 449 bool BitMap::intersects(const BitMap& other) const {
 450   assert(size() == other.size(), "must have same size");
 451   const bm_word_t* dest_map = map();
 452   const bm_word_t* other_map = other.map();
 453   idx_t limit = to_words_align_down(size());
 454   for (idx_t index = 0; index < limit; ++index) {
 455     if ((dest_map[index] & other_map[index]) != 0) return true;
 456   }
 457   idx_t rest = bit_in_word(size());
 458   // false unless there is a partial-word tail with non-empty intersection.
 459   return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0;
 460 }
 461 
 462 void BitMap::set_union(const BitMap& other) {
 463   assert(size() == other.size(), "must have same size");
 464   bm_word_t* dest_map = map();
 465   const bm_word_t* other_map = other.map();
 466   idx_t limit = to_words_align_down(size());
 467   for (idx_t index = 0; index < limit; ++index) {
 468     dest_map[index] |= other_map[index];
 469   }
 470   idx_t rest = bit_in_word(size());
 471   if (rest > 0) {
 472     bm_word_t orig = dest_map[limit];
 473     dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest);
 474   }
 475 }
 476 
 477 void BitMap::set_difference(const BitMap& other) {
 478   assert(size() == other.size(), "must have same size");
 479   bm_word_t* dest_map = map();
 480   const bm_word_t* other_map = other.map();
 481   idx_t limit = to_words_align_down(size());
 482   for (idx_t index = 0; index < limit; ++index) {
 483     dest_map[index] &= ~other_map[index];
 484   }
 485   idx_t rest = bit_in_word(size());
 486   if (rest > 0) {
 487     bm_word_t orig = dest_map[limit];
 488     dest_map[limit] = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
 489   }
 490 }
 491 
 492 void BitMap::set_intersection(const BitMap& other) {
 493   assert(size() == other.size(), "must have same size");
 494   bm_word_t* dest_map = map();
 495   const bm_word_t* other_map = other.map();
 496   idx_t limit = to_words_align_down(size());
 497   for (idx_t index = 0; index < limit; ++index) {
 498     dest_map[index] &= other_map[index];
 499   }
 500   idx_t rest = bit_in_word(size());
 501   if (rest > 0) {
 502     bm_word_t orig = dest_map[limit];
 503     dest_map[limit] = merge_tail_of_map(orig & other_map[limit], orig, rest);
 504   }
 505 }
 506 
 507 bool BitMap::set_union_with_result(const BitMap& other) {
 508   assert(size() == other.size(), "must have same size");
 509   bool changed = false;
 510   bm_word_t* dest_map = map();
 511   const bm_word_t* other_map = other.map();
 512   idx_t limit = to_words_align_down(size());
 513   for (idx_t index = 0; index < limit; ++index) {
 514     bm_word_t orig = dest_map[index];
 515     bm_word_t temp = orig | other_map[index];
 516     changed = changed || (temp != orig);
 517     dest_map[index] = temp;
 518   }
 519   idx_t rest = bit_in_word(size());
 520   if (rest > 0) {
 521     bm_word_t orig = dest_map[limit];
 522     bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest);
 523     changed = changed || (temp != orig);
 524     dest_map[limit] = temp;
 525   }
 526   return changed;
 527 }
 528 
 529 bool BitMap::set_difference_with_result(const BitMap& other) {
 530   assert(size() == other.size(), "must have same size");
 531   bool changed = false;
 532   bm_word_t* dest_map = map();
 533   const bm_word_t* other_map = other.map();
 534   idx_t limit = to_words_align_down(size());
 535   for (idx_t index = 0; index < limit; ++index) {
 536     bm_word_t orig = dest_map[index];
 537     bm_word_t temp = orig & ~other_map[index];
 538     changed = changed || (temp != orig);
 539     dest_map[index] = temp;
 540   }
 541   idx_t rest = bit_in_word(size());
 542   if (rest > 0) {
 543     bm_word_t orig = dest_map[limit];
 544     bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
 545     changed = changed || (temp != orig);
 546     dest_map[limit] = temp;
 547   }
 548   return changed;
 549 }
 550 
 551 bool BitMap::set_intersection_with_result(const BitMap& other) {
 552   assert(size() == other.size(), "must have same size");
 553   bool changed = false;
 554   bm_word_t* dest_map = map();
 555   const bm_word_t* other_map = other.map();
 556   idx_t limit = to_words_align_down(size());
 557   for (idx_t index = 0; index < limit; ++index) {
 558     bm_word_t orig = dest_map[index];
 559     bm_word_t temp = orig & other_map[index];
 560     changed = changed || (temp != orig);
 561     dest_map[index] = temp;
 562   }
 563   idx_t rest = bit_in_word(size());
 564   if (rest > 0) {
 565     bm_word_t orig = dest_map[limit];
 566     bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest);
 567     changed = changed || (temp != orig);
 568     dest_map[limit] = temp;
 569   }
 570   return changed;
 571 }
 572 
 573 void BitMap::set_from(const BitMap& other) {
 574   assert(size() == other.size(), "must have same size");
 575   bm_word_t* dest_map = map();
 576   const bm_word_t* other_map = other.map();
 577   idx_t copy_words = to_words_align_down(size());
 578   Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
 579   idx_t rest = bit_in_word(size());
 580   if (rest > 0) {
 581     dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
 582                                              dest_map[copy_words],
 583                                              rest);
 584   }
 585 }
 586 
 587 bool BitMap::is_same(const BitMap& other) const {
 588   assert(size() == other.size(), "must have same size");
 589   const bm_word_t* dest_map = map();
 590   const bm_word_t* other_map = other.map();
 591   idx_t limit = to_words_align_down(size());
 592   for (idx_t index = 0; index < limit; ++index) {
 593     if (dest_map[index] != other_map[index]) return false;
 594   }
 595   idx_t rest = bit_in_word(size());
 596   return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
 597 }
 598 
 599 bool BitMap::is_full() const {
 600   const bm_word_t* words = map();
 601   idx_t limit = to_words_align_down(size());
 602   for (idx_t index = 0; index < limit; ++index) {
 603     if (~words[index] != 0) return false;
 604   }
 605   idx_t rest = bit_in_word(size());
 606   return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
 607 }
 608 
 609 bool BitMap::is_empty() const {
 610   const bm_word_t* words = map();
 611   idx_t limit = to_words_align_down(size());
 612   for (idx_t index = 0; index < limit; ++index) {
 613     if (words[index] != 0) return false;
 614   }
 615   idx_t rest = bit_in_word(size());
 616   return (rest == 0) || (tail_of_map(words[limit], rest) == 0);
 617 }
 618 
 619 void BitMap::clear_large() {
 620   clear_large_range_of_words(0, size_in_words());
 621 }
 622 
 623 // Note that if the closure itself modifies the bitmap
 624 // then modifications in and to the left of the _bit_ being
 625 // currently sampled will not be seen. Note also that the
 626 // interval [leftOffset, rightOffset) is right open.
 627 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
 628   verify_range(leftOffset, rightOffset);
 629 
 630   idx_t startIndex = to_words_align_down(leftOffset);
 631   idx_t endIndex   = to_words_align_up(rightOffset);
 632   for (idx_t index = startIndex, offset = leftOffset;
 633        offset < rightOffset && index < endIndex;
 634        offset = (++index) << LogBitsPerWord) {
 635     idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
 636     for (; offset < rightOffset && rest != 0; offset++) {
 637       if (rest & 1) {
 638         if (!blk->do_bit(offset)) return false;
 639         //  resample at each closure application
 640         // (see, for instance, CMS bug 4525989)
 641         rest = map(index) >> (offset & (BitsPerWord -1));
 642       }
 643       rest = rest >> 1;
 644     }
 645   }
 646   return true;
 647 }
 648 
 649 const BitMap::idx_t* BitMap::_pop_count_table = NULL;
 650 
 651 void BitMap::init_pop_count_table() {


< prev index next >