< prev index next >
src/hotspot/share/utilities/bitMap.cpp
Print this page
rev 57098 : [mq]: max_size
rev 57099 : [mq]: improve
*** 172,189 ****
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_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);
}
#endif // #ifdef ASSERT
void BitMap::pretouch() {
os::pretouch_memory(word_addr(0), word_addr(size()));
--- 172,202 ----
void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
}
#ifdef ASSERT
! 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_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,237 ****
}
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);
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);
--- 239,250 ----
}
void BitMap::set_range(idx_t beg, idx_t end) {
verify_range(beg, 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,256 ****
}
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);
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);
--- 258,269 ----
}
void BitMap::clear_range(idx_t beg, idx_t end) {
verify_range(beg, 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,283 ****
}
}
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.
// The threshold should be at least one word.
STATIC_ASSERT(small_range_words >= 1);
! 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);
if (is_small_range_of_words(beg_full_word, end_full_word)) {
set_range(beg, end);
return;
}
--- 276,298 ----
}
}
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 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;
}
void BitMap::set_large_range(idx_t beg, idx_t end) {
verify_range(beg, 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,300 ****
}
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);
if (is_small_range_of_words(beg_full_word, end_full_word)) {
clear_range(beg, end);
return;
}
--- 304,315 ----
}
void BitMap::clear_large_range(idx_t beg, idx_t end) {
verify_range(beg, 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,352 ****
}
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);
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) {
--- 356,367 ----
}
void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
verify_range(beg, 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,384 ****
}
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);
if (is_small_range_of_words(beg_full_word, end_full_word)) {
par_at_put_range(beg, end, value);
return;
}
--- 388,399 ----
}
void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
verify_range(beg, 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,428 ****
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());
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,443 ----
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 = 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,443 ****
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());
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.
--- 448,458 ----
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 = 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,456 ****
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());
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,471 ----
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 = 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,471 ****
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());
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,486 ----
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 = 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,486 ****
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());
for (idx_t index = 0; index < limit; ++index) {
dest_map[index] &= other_map[index];
}
idx_t rest = bit_in_word(size());
if (rest > 0) {
--- 491,501 ----
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 = 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,502 ****
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());
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;
--- 507,517 ----
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 = 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,524 ****
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());
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;
--- 529,539 ----
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 = 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,546 ****
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());
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;
--- 551,561 ----
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 = 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,567 ****
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());
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],
--- 572,582 ----
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 = 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,601 ****
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());
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());
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());
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);
--- 586,616 ----
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 = 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 = 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 = 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,621 ****
// 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());
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++) {
--- 625,636 ----
// 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 = 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 >