< prev index next >

src/hotspot/share/utilities/bitMap.cpp

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

@@ -172,18 +172,31 @@
 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
   BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
 }
 
 #ifdef ASSERT
-void BitMap::verify_index(idx_t index) const {
-  assert(index < _size, "BitMap index out of bounds");
+void BitMap::verify_size(idx_t size_in_bits) {
+  assert(size_in_bits <= max_size_in_bits(),
+         "out of bounds: " SIZE_FORMAT, size_in_bits);
 }
 
-void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
-  assert(beg_index <= end_index, "BitMap range error");
-  // Note that [0,0) and [size,size) are both valid ranges.
-  if (end_index != _size) verify_index(end_index);
+void BitMap::verify_index(idx_t bit) const {
+  assert(bit < _size,
+         "BitMap index out of bounds: " SIZE_FORMAT " >= " SIZE_FORMAT,
+         bit, _size);
+}
+
+void BitMap::verify_limit(idx_t bit) const {
+  assert(bit <= _size,
+         "BitMap limit out of bounds: " SIZE_FORMAT " > " SIZE_FORMAT,
+         bit, _size);
+}
+
+void BitMap::verify_range(idx_t beg, idx_t end) const {
+  assert(beg <= end,
+         "BitMap range error: " SIZE_FORMAT " > " SIZE_FORMAT, beg, end);
+  verify_limit(end);
 }
 #endif // #ifdef ASSERT
 
 void BitMap::pretouch() {
   os::pretouch_memory(word_addr(0), word_addr(size()));

@@ -226,12 +239,12 @@
 }
 
 void BitMap::set_range(idx_t beg, idx_t end) {
   verify_range(beg, end);
 
-  idx_t beg_full_word = word_index_round_up(beg);
-  idx_t end_full_word = word_index(end);
+  idx_t beg_full_word = to_words_align_up(beg);
+  idx_t end_full_word = to_words_align_down(end);
 
   if (beg_full_word < end_full_word) {
     // The range includes at least one full word.
     set_range_within_word(beg, bit_index(beg_full_word));
     set_range_of_words(beg_full_word, end_full_word);

@@ -245,12 +258,12 @@
 }
 
 void BitMap::clear_range(idx_t beg, idx_t end) {
   verify_range(beg, end);
 
-  idx_t beg_full_word = word_index_round_up(beg);
-  idx_t end_full_word = word_index(end);
+  idx_t beg_full_word = to_words_align_up(beg);
+  idx_t end_full_word = to_words_align_down(end);
 
   if (beg_full_word < end_full_word) {
     // The range includes at least one full word.
     clear_range_within_word(beg, bit_index(beg_full_word));
     clear_range_of_words(beg_full_word, end_full_word);

@@ -263,21 +276,23 @@
   }
 }
 
 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
   // There is little point to call large version on small ranges.
-  // Need to check carefully, keeping potential idx_t underflow in mind.
+  // Need to check carefully, keeping potential idx_t over/underflow in mind,
+  // because beg_full_word > end_full_word can occur when beg and end are in
+  // the same word.
   // The threshold should be at least one word.
   STATIC_ASSERT(small_range_words >= 1);
-  return (beg_full_word + small_range_words >= end_full_word);
+  return beg_full_word + small_range_words >= end_full_word;
 }
 
 void BitMap::set_large_range(idx_t beg, idx_t end) {
   verify_range(beg, end);
 
-  idx_t beg_full_word = word_index_round_up(beg);
-  idx_t end_full_word = word_index(end);
+  idx_t beg_full_word = to_words_align_up(beg);
+  idx_t end_full_word = to_words_align_down(end);
 
   if (is_small_range_of_words(beg_full_word, end_full_word)) {
     set_range(beg, end);
     return;
   }

@@ -289,12 +304,12 @@
 }
 
 void BitMap::clear_large_range(idx_t beg, idx_t end) {
   verify_range(beg, end);
 
-  idx_t beg_full_word = word_index_round_up(beg);
-  idx_t end_full_word = word_index(end);
+  idx_t beg_full_word = to_words_align_up(beg);
+  idx_t end_full_word = to_words_align_down(end);
 
   if (is_small_range_of_words(beg_full_word, end_full_word)) {
     clear_range(beg, end);
     return;
   }

@@ -341,12 +356,12 @@
 }
 
 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
   verify_range(beg, end);
 
-  idx_t beg_full_word = word_index_round_up(beg);
-  idx_t end_full_word = word_index(end);
+  idx_t beg_full_word = to_words_align_up(beg);
+  idx_t end_full_word = to_words_align_down(end);
 
   if (beg_full_word < end_full_word) {
     // The range includes at least one full word.
     par_put_range_within_word(beg, bit_index(beg_full_word), value);
     if (value) {

@@ -373,12 +388,12 @@
 }
 
 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
   verify_range(beg, end);
 
-  idx_t beg_full_word = word_index_round_up(beg);
-  idx_t end_full_word = word_index(end);
+  idx_t beg_full_word = to_words_align_up(beg);
+  idx_t end_full_word = to_words_align_down(end);
 
   if (is_small_range_of_words(beg_full_word, end_full_word)) {
     par_at_put_range(beg, end, value);
     return;
   }

@@ -418,11 +433,11 @@
 
 bool BitMap::contains(const BitMap& other) const {
   assert(size() == other.size(), "must have same size");
   const bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     // false if other bitmap has bits set which are clear in this bitmap.
     if ((~dest_map[index] & other_map[index]) != 0) return false;
   }
   idx_t rest = bit_in_word(size());

@@ -433,11 +448,11 @@
 
 bool BitMap::intersects(const BitMap& other) const {
   assert(size() == other.size(), "must have same size");
   const bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     if ((dest_map[index] & other_map[index]) != 0) return true;
   }
   idx_t rest = bit_in_word(size());
   // false unless there is a partial-word tail with non-empty intersection.

@@ -446,11 +461,11 @@
 
 void BitMap::set_union(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     dest_map[index] |= other_map[index];
   }
   idx_t rest = bit_in_word(size());
   if (rest > 0) {

@@ -461,11 +476,11 @@
 
 void BitMap::set_difference(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     dest_map[index] &= ~other_map[index];
   }
   idx_t rest = bit_in_word(size());
   if (rest > 0) {

@@ -476,11 +491,11 @@
 
 void BitMap::set_intersection(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     dest_map[index] &= other_map[index];
   }
   idx_t rest = bit_in_word(size());
   if (rest > 0) {

@@ -492,11 +507,11 @@
 bool BitMap::set_union_with_result(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bool changed = false;
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     bm_word_t orig = dest_map[index];
     bm_word_t temp = orig | other_map[index];
     changed = changed || (temp != orig);
     dest_map[index] = temp;

@@ -514,11 +529,11 @@
 bool BitMap::set_difference_with_result(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bool changed = false;
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     bm_word_t orig = dest_map[index];
     bm_word_t temp = orig & ~other_map[index];
     changed = changed || (temp != orig);
     dest_map[index] = temp;

@@ -536,11 +551,11 @@
 bool BitMap::set_intersection_with_result(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bool changed = false;
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     bm_word_t orig = dest_map[index];
     bm_word_t temp = orig & other_map[index];
     changed = changed || (temp != orig);
     dest_map[index] = temp;

@@ -557,11 +572,11 @@
 
 void BitMap::set_from(const BitMap& other) {
   assert(size() == other.size(), "must have same size");
   bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t copy_words = word_index(size());
+  idx_t copy_words = to_words_align_down(size());
   Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
   idx_t rest = bit_in_word(size());
   if (rest > 0) {
     dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
                                              dest_map[copy_words],

@@ -571,31 +586,31 @@
 
 bool BitMap::is_same(const BitMap& other) const {
   assert(size() == other.size(), "must have same size");
   const bm_word_t* dest_map = map();
   const bm_word_t* other_map = other.map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     if (dest_map[index] != other_map[index]) return false;
   }
   idx_t rest = bit_in_word(size());
   return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
 }
 
 bool BitMap::is_full() const {
   const bm_word_t* words = map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     if (~words[index] != 0) return false;
   }
   idx_t rest = bit_in_word(size());
   return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
 }
 
 bool BitMap::is_empty() const {
   const bm_word_t* words = map();
-  idx_t limit = word_index(size());
+  idx_t limit = to_words_align_down(size());
   for (idx_t index = 0; index < limit; ++index) {
     if (words[index] != 0) return false;
   }
   idx_t rest = bit_in_word(size());
   return (rest == 0) || (tail_of_map(words[limit], rest) == 0);

@@ -610,12 +625,12 @@
 // currently sampled will not be seen. Note also that the
 // interval [leftOffset, rightOffset) is right open.
 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
   verify_range(leftOffset, rightOffset);
 
-  idx_t startIndex = word_index(leftOffset);
-  idx_t endIndex   = MIN2(word_index(rightOffset) + 1, size_in_words());
+  idx_t startIndex = to_words_align_down(leftOffset);
+  idx_t endIndex   = to_words_align_up(rightOffset);
   for (idx_t index = startIndex, offset = leftOffset;
        offset < rightOffset && index < endIndex;
        offset = (++index) << LogBitsPerWord) {
     idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
     for (; offset < rightOffset && rest != 0; offset++) {
< prev index next >