< 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 >