src/share/vm/utilities/bitMap.inline.hpp

Tue, 05 Apr 2011 14:12:31 -0700

author
trims
date
Tue, 05 Apr 2011 14:12:31 -0700
changeset 2708
1d1603768966
parent 2314
f95d63e2154a
child 3454
2e966d967c5c
permissions
-rw-r--r--

7010070: Update all 2010 Oracle-changed OpenJDK files to have the proper copyright dates - second pass
Summary: Update the copyright to be 2010 on all changed files in OpenJDK
Reviewed-by: ohair

duke@435 1 /*
stefank@2314 2 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
duke@435 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435 4 *
duke@435 5 * This code is free software; you can redistribute it and/or modify it
duke@435 6 * under the terms of the GNU General Public License version 2 only, as
duke@435 7 * published by the Free Software Foundation.
duke@435 8 *
duke@435 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@435 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@435 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@435 13 * accompanied this code).
duke@435 14 *
duke@435 15 * You should have received a copy of the GNU General Public License version
duke@435 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@435 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435 18 *
trims@1907 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@1907 20 * or visit www.oracle.com if you need additional information or have any
trims@1907 21 * questions.
duke@435 22 *
duke@435 23 */
duke@435 24
stefank@2314 25 #ifndef SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
stefank@2314 26 #define SHARE_VM_UTILITIES_BITMAP_INLINE_HPP
stefank@2314 27
stefank@2314 28 #include "runtime/atomic.hpp"
stefank@2314 29 #include "utilities/bitMap.hpp"
stefank@2314 30
jcoomes@1244 31 #ifdef ASSERT
jcoomes@1244 32 inline void BitMap::verify_index(idx_t index) const {
jcoomes@1244 33 assert(index < _size, "BitMap index out of bounds");
jcoomes@1244 34 }
jcoomes@1244 35
jcoomes@1244 36 inline void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
jcoomes@1244 37 assert(beg_index <= end_index, "BitMap range error");
jcoomes@1244 38 // Note that [0,0) and [size,size) are both valid ranges.
jcoomes@1244 39 if (end_index != _size) verify_index(end_index);
jcoomes@1244 40 }
jcoomes@1244 41 #endif // #ifdef ASSERT
ysr@777 42
ysr@777 43 inline void BitMap::set_bit(idx_t bit) {
ysr@777 44 verify_index(bit);
ysr@777 45 *word_addr(bit) |= bit_mask(bit);
ysr@777 46 }
ysr@777 47
ysr@777 48 inline void BitMap::clear_bit(idx_t bit) {
ysr@777 49 verify_index(bit);
ysr@777 50 *word_addr(bit) &= ~bit_mask(bit);
ysr@777 51 }
ysr@777 52
duke@435 53 inline bool BitMap::par_set_bit(idx_t bit) {
duke@435 54 verify_index(bit);
duke@435 55 volatile idx_t* const addr = word_addr(bit);
duke@435 56 const idx_t mask = bit_mask(bit);
duke@435 57 idx_t old_val = *addr;
duke@435 58
duke@435 59 do {
duke@435 60 const idx_t new_val = old_val | mask;
duke@435 61 if (new_val == old_val) {
duke@435 62 return false; // Someone else beat us to it.
duke@435 63 }
duke@435 64 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
duke@435 65 (volatile void*) addr,
duke@435 66 (void*) old_val);
duke@435 67 if (cur_val == old_val) {
duke@435 68 return true; // Success.
duke@435 69 }
duke@435 70 old_val = cur_val; // The value changed, try again.
duke@435 71 } while (true);
duke@435 72 }
duke@435 73
duke@435 74 inline bool BitMap::par_clear_bit(idx_t bit) {
duke@435 75 verify_index(bit);
duke@435 76 volatile idx_t* const addr = word_addr(bit);
duke@435 77 const idx_t mask = ~bit_mask(bit);
duke@435 78 idx_t old_val = *addr;
duke@435 79
duke@435 80 do {
duke@435 81 const idx_t new_val = old_val & mask;
duke@435 82 if (new_val == old_val) {
duke@435 83 return false; // Someone else beat us to it.
duke@435 84 }
duke@435 85 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
duke@435 86 (volatile void*) addr,
duke@435 87 (void*) old_val);
duke@435 88 if (cur_val == old_val) {
duke@435 89 return true; // Success.
duke@435 90 }
duke@435 91 old_val = cur_val; // The value changed, try again.
duke@435 92 } while (true);
duke@435 93 }
duke@435 94
ysr@777 95 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
ysr@777 96 if (hint == small_range && end - beg == 1) {
ysr@777 97 set_bit(beg);
ysr@777 98 } else {
ysr@777 99 if (hint == large_range) {
ysr@777 100 set_large_range(beg, end);
ysr@777 101 } else {
ysr@777 102 set_range(beg, end);
ysr@777 103 }
ysr@777 104 }
ysr@777 105 }
ysr@777 106
ysr@777 107 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
ysr@777 108 if (hint == small_range && end - beg == 1) {
ysr@777 109 clear_bit(beg);
ysr@777 110 } else {
ysr@777 111 if (hint == large_range) {
ysr@777 112 clear_large_range(beg, end);
ysr@777 113 } else {
ysr@777 114 clear_range(beg, end);
ysr@777 115 }
ysr@777 116 }
ysr@777 117 }
ysr@777 118
ysr@777 119 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
ysr@777 120 if (hint == small_range && end - beg == 1) {
ysr@777 121 par_at_put(beg, true);
ysr@777 122 } else {
ysr@777 123 if (hint == large_range) {
ysr@777 124 par_at_put_large_range(beg, end, true);
ysr@777 125 } else {
ysr@777 126 par_at_put_range(beg, end, true);
ysr@777 127 }
ysr@777 128 }
ysr@777 129 }
ysr@777 130
ysr@777 131 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
ysr@777 132 bm_word_t* map = _map;
ysr@777 133 for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0;
ysr@777 134 }
ysr@777 135
ysr@777 136
ysr@777 137 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
ysr@777 138 bm_word_t* map = _map;
ysr@777 139 for (idx_t i = beg; i < end; ++i) map[i] = 0;
ysr@777 140 }
ysr@777 141
ysr@777 142
ysr@777 143 inline void BitMap::clear() {
ysr@777 144 clear_range_of_words(0, size_in_words());
ysr@777 145 }
ysr@777 146
ysr@777 147
ysr@777 148 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
ysr@777 149 if (hint == small_range && end - beg == 1) {
ysr@777 150 par_at_put(beg, false);
ysr@777 151 } else {
ysr@777 152 if (hint == large_range) {
ysr@777 153 par_at_put_large_range(beg, end, false);
ysr@777 154 } else {
ysr@777 155 par_at_put_range(beg, end, false);
ysr@777 156 }
ysr@777 157 }
ysr@777 158 }
ysr@777 159
duke@435 160 inline BitMap::idx_t
ysr@777 161 BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const {
ysr@777 162 assert(l_offset <= size(), "BitMap index out of bounds");
ysr@777 163 assert(r_offset <= size(), "BitMap index out of bounds");
ysr@777 164 assert(l_offset <= r_offset, "l_offset > r_offset ?");
duke@435 165
ysr@777 166 if (l_offset == r_offset) {
ysr@777 167 return l_offset;
duke@435 168 }
ysr@777 169 idx_t index = word_index(l_offset);
ysr@777 170 idx_t r_index = word_index(r_offset-1) + 1;
ysr@777 171 idx_t res_offset = l_offset;
duke@435 172
duke@435 173 // check bits including and to the _left_ of offset's position
ysr@777 174 idx_t pos = bit_in_word(res_offset);
ysr@777 175 idx_t res = map(index) >> pos;
ysr@777 176 if (res != (uintptr_t)NoBits) {
duke@435 177 // find the position of the 1-bit
ysr@777 178 for (; !(res & 1); res_offset++) {
duke@435 179 res = res >> 1;
duke@435 180 }
ysr@777 181 assert(res_offset >= l_offset &&
ysr@777 182 res_offset < r_offset, "just checking");
ysr@777 183 return MIN2(res_offset, r_offset);
duke@435 184 }
duke@435 185 // skip over all word length 0-bit runs
duke@435 186 for (index++; index < r_index; index++) {
duke@435 187 res = map(index);
ysr@777 188 if (res != (uintptr_t)NoBits) {
duke@435 189 // found a 1, return the offset
ysr@777 190 for (res_offset = bit_index(index); !(res & 1); res_offset++) {
duke@435 191 res = res >> 1;
duke@435 192 }
duke@435 193 assert(res & 1, "tautology; see loop condition");
ysr@777 194 assert(res_offset >= l_offset, "just checking");
ysr@777 195 return MIN2(res_offset, r_offset);
duke@435 196 }
duke@435 197 }
ysr@777 198 return r_offset;
duke@435 199 }
ysr@777 200
ysr@777 201 inline BitMap::idx_t
ysr@777 202 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
ysr@777 203 assert(l_offset <= size(), "BitMap index out of bounds");
ysr@777 204 assert(r_offset <= size(), "BitMap index out of bounds");
ysr@777 205 assert(l_offset <= r_offset, "l_offset > r_offset ?");
ysr@777 206
ysr@777 207 if (l_offset == r_offset) {
ysr@777 208 return l_offset;
ysr@777 209 }
ysr@777 210 idx_t index = word_index(l_offset);
ysr@777 211 idx_t r_index = word_index(r_offset-1) + 1;
ysr@777 212 idx_t res_offset = l_offset;
ysr@777 213
ysr@777 214 // check bits including and to the _left_ of offset's position
ysr@777 215 idx_t pos = res_offset & (BitsPerWord - 1);
ysr@777 216 idx_t res = (map(index) >> pos) | left_n_bits((int)pos);
ysr@777 217
ysr@777 218 if (res != (uintptr_t)AllBits) {
ysr@777 219 // find the position of the 0-bit
ysr@777 220 for (; res & 1; res_offset++) {
ysr@777 221 res = res >> 1;
ysr@777 222 }
ysr@777 223 assert(res_offset >= l_offset, "just checking");
ysr@777 224 return MIN2(res_offset, r_offset);
ysr@777 225 }
ysr@777 226 // skip over all word length 1-bit runs
ysr@777 227 for (index++; index < r_index; index++) {
ysr@777 228 res = map(index);
ysr@777 229 if (res != (uintptr_t)AllBits) {
ysr@777 230 // found a 0, return the offset
ysr@777 231 for (res_offset = index << LogBitsPerWord; res & 1;
ysr@777 232 res_offset++) {
ysr@777 233 res = res >> 1;
ysr@777 234 }
ysr@777 235 assert(!(res & 1), "tautology; see loop condition");
ysr@777 236 assert(res_offset >= l_offset, "just checking");
ysr@777 237 return MIN2(res_offset, r_offset);
ysr@777 238 }
ysr@777 239 }
ysr@777 240 return r_offset;
ysr@777 241 }
ysr@777 242
ysr@777 243 inline BitMap::idx_t
ysr@777 244 BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset,
ysr@777 245 idx_t r_offset) const
ysr@777 246 {
ysr@777 247 verify_range(l_offset, r_offset);
ysr@777 248 assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned");
ysr@777 249
ysr@777 250 if (l_offset == r_offset) {
ysr@777 251 return l_offset;
ysr@777 252 }
ysr@777 253 idx_t index = word_index(l_offset);
ysr@777 254 idx_t r_index = word_index(r_offset);
ysr@777 255 idx_t res_offset = l_offset;
ysr@777 256
ysr@777 257 // check bits including and to the _left_ of offset's position
ysr@777 258 idx_t res = map(index) >> bit_in_word(res_offset);
ysr@777 259 if (res != (uintptr_t)NoBits) {
ysr@777 260 // find the position of the 1-bit
ysr@777 261 for (; !(res & 1); res_offset++) {
ysr@777 262 res = res >> 1;
ysr@777 263 }
ysr@777 264 assert(res_offset >= l_offset &&
ysr@777 265 res_offset < r_offset, "just checking");
ysr@777 266 return res_offset;
ysr@777 267 }
ysr@777 268 // skip over all word length 0-bit runs
ysr@777 269 for (index++; index < r_index; index++) {
ysr@777 270 res = map(index);
ysr@777 271 if (res != (uintptr_t)NoBits) {
ysr@777 272 // found a 1, return the offset
ysr@777 273 for (res_offset = bit_index(index); !(res & 1); res_offset++) {
ysr@777 274 res = res >> 1;
ysr@777 275 }
ysr@777 276 assert(res & 1, "tautology; see loop condition");
ysr@777 277 assert(res_offset >= l_offset && res_offset < r_offset, "just checking");
ysr@777 278 return res_offset;
ysr@777 279 }
ysr@777 280 }
ysr@777 281 return r_offset;
ysr@777 282 }
ysr@777 283
ysr@777 284
ysr@777 285 // Returns a bit mask for a range of bits [beg, end) within a single word. Each
ysr@777 286 // bit in the mask is 0 if the bit is in the range, 1 if not in the range. The
ysr@777 287 // returned mask can be used directly to clear the range, or inverted to set the
ysr@777 288 // range. Note: end must not be 0.
ysr@777 289 inline BitMap::bm_word_t
ysr@777 290 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
ysr@777 291 assert(end != 0, "does not work when end == 0");
ysr@777 292 assert(beg == end || word_index(beg) == word_index(end - 1),
ysr@777 293 "must be a single-word range");
ysr@777 294 bm_word_t mask = bit_mask(beg) - 1; // low (right) bits
ysr@777 295 if (bit_in_word(end) != 0) {
ysr@777 296 mask |= ~(bit_mask(end) - 1); // high (left) bits
ysr@777 297 }
ysr@777 298 return mask;
ysr@777 299 }
ysr@777 300
ysr@777 301 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
ysr@777 302 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t));
ysr@777 303 }
ysr@777 304
ysr@777 305 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
ysr@777 306 memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t));
ysr@777 307 }
ysr@777 308
ysr@777 309 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
ysr@777 310 idx_t bit_rounded_up = bit + (BitsPerWord - 1);
ysr@777 311 // Check for integer arithmetic overflow.
ysr@777 312 return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
ysr@777 313 }
ysr@777 314
ysr@777 315 inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset,
ysr@777 316 idx_t r_offset) const {
ysr@777 317 return get_next_one_offset_inline(l_offset, r_offset);
ysr@777 318 }
ysr@777 319
ysr@777 320 inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset,
ysr@777 321 idx_t r_offset) const {
ysr@777 322 return get_next_zero_offset_inline(l_offset, r_offset);
ysr@777 323 }
ysr@777 324
ysr@777 325 inline void BitMap2D::clear() {
ysr@777 326 _map.clear();
ysr@777 327 }
stefank@2314 328
stefank@2314 329 #endif // SHARE_VM_UTILITIES_BITMAP_INLINE_HPP

mercurial