1.1 --- a/src/share/vm/utilities/bitMap.inline.hpp Wed Jun 04 13:51:09 2008 -0700
1.2 +++ b/src/share/vm/utilities/bitMap.inline.hpp Thu Jun 05 15:57:56 2008 -0700
1.3 @@ -22,6 +22,17 @@
1.4 *
1.5 */
1.6
1.7 +
1.8 +inline void BitMap::set_bit(idx_t bit) {
1.9 + verify_index(bit);
1.10 + *word_addr(bit) |= bit_mask(bit);
1.11 +}
1.12 +
1.13 +inline void BitMap::clear_bit(idx_t bit) {
1.14 + verify_index(bit);
1.15 + *word_addr(bit) &= ~bit_mask(bit);
1.16 +}
1.17 +
1.18 inline bool BitMap::par_set_bit(idx_t bit) {
1.19 verify_index(bit);
1.20 volatile idx_t* const addr = word_addr(bit);
1.21 @@ -64,42 +75,236 @@
1.22 } while (true);
1.23 }
1.24
1.25 +inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.26 + if (hint == small_range && end - beg == 1) {
1.27 + set_bit(beg);
1.28 + } else {
1.29 + if (hint == large_range) {
1.30 + set_large_range(beg, end);
1.31 + } else {
1.32 + set_range(beg, end);
1.33 + }
1.34 + }
1.35 +}
1.36 +
1.37 +inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.38 + if (hint == small_range && end - beg == 1) {
1.39 + clear_bit(beg);
1.40 + } else {
1.41 + if (hint == large_range) {
1.42 + clear_large_range(beg, end);
1.43 + } else {
1.44 + clear_range(beg, end);
1.45 + }
1.46 + }
1.47 +}
1.48 +
1.49 +inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.50 + if (hint == small_range && end - beg == 1) {
1.51 + par_at_put(beg, true);
1.52 + } else {
1.53 + if (hint == large_range) {
1.54 + par_at_put_large_range(beg, end, true);
1.55 + } else {
1.56 + par_at_put_range(beg, end, true);
1.57 + }
1.58 + }
1.59 +}
1.60 +
1.61 +inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
1.62 + bm_word_t* map = _map;
1.63 + for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0;
1.64 +}
1.65 +
1.66 +
1.67 +inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
1.68 + bm_word_t* map = _map;
1.69 + for (idx_t i = beg; i < end; ++i) map[i] = 0;
1.70 +}
1.71 +
1.72 +
1.73 +inline void BitMap::clear() {
1.74 + clear_range_of_words(0, size_in_words());
1.75 +}
1.76 +
1.77 +
1.78 +inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
1.79 + if (hint == small_range && end - beg == 1) {
1.80 + par_at_put(beg, false);
1.81 + } else {
1.82 + if (hint == large_range) {
1.83 + par_at_put_large_range(beg, end, false);
1.84 + } else {
1.85 + par_at_put_range(beg, end, false);
1.86 + }
1.87 + }
1.88 +}
1.89 +
1.90 inline BitMap::idx_t
1.91 -BitMap::find_next_one_bit(idx_t beg_bit, idx_t end_bit) const
1.92 -{
1.93 - verify_range(beg_bit, end_bit);
1.94 - assert(bit_in_word(end_bit) == 0, "end_bit not word-aligned");
1.95 +BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const {
1.96 + assert(l_offset <= size(), "BitMap index out of bounds");
1.97 + assert(r_offset <= size(), "BitMap index out of bounds");
1.98 + assert(l_offset <= r_offset, "l_offset > r_offset ?");
1.99
1.100 - if (beg_bit == end_bit) {
1.101 - return beg_bit;
1.102 + if (l_offset == r_offset) {
1.103 + return l_offset;
1.104 }
1.105 -
1.106 - idx_t index = word_index(beg_bit);
1.107 - idx_t r_index = word_index(end_bit);
1.108 - idx_t res_bit = beg_bit;
1.109 + idx_t index = word_index(l_offset);
1.110 + idx_t r_index = word_index(r_offset-1) + 1;
1.111 + idx_t res_offset = l_offset;
1.112
1.113 // check bits including and to the _left_ of offset's position
1.114 - idx_t res = map(index) >> bit_in_word(res_bit);
1.115 - if (res != (uintptr_t) NoBits) {
1.116 + idx_t pos = bit_in_word(res_offset);
1.117 + idx_t res = map(index) >> pos;
1.118 + if (res != (uintptr_t)NoBits) {
1.119 // find the position of the 1-bit
1.120 - for (; !(res & 1); res_bit++) {
1.121 + for (; !(res & 1); res_offset++) {
1.122 res = res >> 1;
1.123 }
1.124 - assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
1.125 - return res_bit;
1.126 + assert(res_offset >= l_offset &&
1.127 + res_offset < r_offset, "just checking");
1.128 + return MIN2(res_offset, r_offset);
1.129 }
1.130 // skip over all word length 0-bit runs
1.131 for (index++; index < r_index; index++) {
1.132 res = map(index);
1.133 - if (res != (uintptr_t) NoBits) {
1.134 + if (res != (uintptr_t)NoBits) {
1.135 // found a 1, return the offset
1.136 - for (res_bit = bit_index(index); !(res & 1); res_bit++) {
1.137 + for (res_offset = bit_index(index); !(res & 1); res_offset++) {
1.138 res = res >> 1;
1.139 }
1.140 assert(res & 1, "tautology; see loop condition");
1.141 - assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
1.142 - return res_bit;
1.143 + assert(res_offset >= l_offset, "just checking");
1.144 + return MIN2(res_offset, r_offset);
1.145 }
1.146 }
1.147 - return end_bit;
1.148 + return r_offset;
1.149 }
1.150 +
1.151 +inline BitMap::idx_t
1.152 +BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
1.153 + assert(l_offset <= size(), "BitMap index out of bounds");
1.154 + assert(r_offset <= size(), "BitMap index out of bounds");
1.155 + assert(l_offset <= r_offset, "l_offset > r_offset ?");
1.156 +
1.157 + if (l_offset == r_offset) {
1.158 + return l_offset;
1.159 + }
1.160 + idx_t index = word_index(l_offset);
1.161 + idx_t r_index = word_index(r_offset-1) + 1;
1.162 + idx_t res_offset = l_offset;
1.163 +
1.164 + // check bits including and to the _left_ of offset's position
1.165 + idx_t pos = res_offset & (BitsPerWord - 1);
1.166 + idx_t res = (map(index) >> pos) | left_n_bits((int)pos);
1.167 +
1.168 + if (res != (uintptr_t)AllBits) {
1.169 + // find the position of the 0-bit
1.170 + for (; res & 1; res_offset++) {
1.171 + res = res >> 1;
1.172 + }
1.173 + assert(res_offset >= l_offset, "just checking");
1.174 + return MIN2(res_offset, r_offset);
1.175 + }
1.176 + // skip over all word length 1-bit runs
1.177 + for (index++; index < r_index; index++) {
1.178 + res = map(index);
1.179 + if (res != (uintptr_t)AllBits) {
1.180 + // found a 0, return the offset
1.181 + for (res_offset = index << LogBitsPerWord; res & 1;
1.182 + res_offset++) {
1.183 + res = res >> 1;
1.184 + }
1.185 + assert(!(res & 1), "tautology; see loop condition");
1.186 + assert(res_offset >= l_offset, "just checking");
1.187 + return MIN2(res_offset, r_offset);
1.188 + }
1.189 + }
1.190 + return r_offset;
1.191 +}
1.192 +
1.193 +inline BitMap::idx_t
1.194 +BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset,
1.195 + idx_t r_offset) const
1.196 +{
1.197 + verify_range(l_offset, r_offset);
1.198 + assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned");
1.199 +
1.200 + if (l_offset == r_offset) {
1.201 + return l_offset;
1.202 + }
1.203 + idx_t index = word_index(l_offset);
1.204 + idx_t r_index = word_index(r_offset);
1.205 + idx_t res_offset = l_offset;
1.206 +
1.207 + // check bits including and to the _left_ of offset's position
1.208 + idx_t res = map(index) >> bit_in_word(res_offset);
1.209 + if (res != (uintptr_t)NoBits) {
1.210 + // find the position of the 1-bit
1.211 + for (; !(res & 1); res_offset++) {
1.212 + res = res >> 1;
1.213 + }
1.214 + assert(res_offset >= l_offset &&
1.215 + res_offset < r_offset, "just checking");
1.216 + return res_offset;
1.217 + }
1.218 + // skip over all word length 0-bit runs
1.219 + for (index++; index < r_index; index++) {
1.220 + res = map(index);
1.221 + if (res != (uintptr_t)NoBits) {
1.222 + // found a 1, return the offset
1.223 + for (res_offset = bit_index(index); !(res & 1); res_offset++) {
1.224 + res = res >> 1;
1.225 + }
1.226 + assert(res & 1, "tautology; see loop condition");
1.227 + assert(res_offset >= l_offset && res_offset < r_offset, "just checking");
1.228 + return res_offset;
1.229 + }
1.230 + }
1.231 + return r_offset;
1.232 +}
1.233 +
1.234 +
1.235 +// Returns a bit mask for a range of bits [beg, end) within a single word. Each
1.236 +// bit in the mask is 0 if the bit is in the range, 1 if not in the range. The
1.237 +// returned mask can be used directly to clear the range, or inverted to set the
1.238 +// range. Note: end must not be 0.
1.239 +inline BitMap::bm_word_t
1.240 +BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
1.241 + assert(end != 0, "does not work when end == 0");
1.242 + assert(beg == end || word_index(beg) == word_index(end - 1),
1.243 + "must be a single-word range");
1.244 + bm_word_t mask = bit_mask(beg) - 1; // low (right) bits
1.245 + if (bit_in_word(end) != 0) {
1.246 + mask |= ~(bit_mask(end) - 1); // high (left) bits
1.247 + }
1.248 + return mask;
1.249 +}
1.250 +
1.251 +inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
1.252 + memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t));
1.253 +}
1.254 +
1.255 +inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
1.256 + memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t));
1.257 +}
1.258 +
1.259 +inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
1.260 + idx_t bit_rounded_up = bit + (BitsPerWord - 1);
1.261 + // Check for integer arithmetic overflow.
1.262 + return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
1.263 +}
1.264 +
1.265 +inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset,
1.266 + idx_t r_offset) const {
1.267 + return get_next_one_offset_inline(l_offset, r_offset);
1.268 +}
1.269 +
1.270 +inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset,
1.271 + idx_t r_offset) const {
1.272 + return get_next_zero_offset_inline(l_offset, r_offset);
1.273 +}
1.274 +
1.275 +inline void BitMap2D::clear() {
1.276 + _map.clear();
1.277 +}
