Mercurial > hg > truffle
annotate src/share/vm/utilities/bitMap.cpp @ 6862:8a5ea0a9ccc4
7127708: G1: change task num types from int to uint in concurrent mark
Summary: Change the type of various task num fields, parameters etc to unsigned and rename them to be more consistent with the other collectors. Code changes were also reviewed by Vitaly Davidovich.
Reviewed-by: johnc
Contributed-by: Kaushik Srenevasan <kaushik@twitter.com>
| author | johnc |
|---|---|
| date | Sat, 06 Oct 2012 01:17:44 -0700 |
| parents | d2a62e0f25eb |
| children | 7b835924c31c |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
5988
2a0172480595
7127697: G1: remove dead code after recent concurrent mark changes
tonyp
parents:
3960
diff
changeset
|
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
| 26 #include "memory/allocation.inline.hpp" | |
| 27 #include "utilities/bitMap.inline.hpp" | |
| 28 #include "utilities/copy.hpp" | |
| 29 #ifdef TARGET_OS_FAMILY_linux | |
| 30 # include "os_linux.inline.hpp" | |
| 31 #endif | |
| 32 #ifdef TARGET_OS_FAMILY_solaris | |
| 33 # include "os_solaris.inline.hpp" | |
| 34 #endif | |
| 35 #ifdef TARGET_OS_FAMILY_windows | |
| 36 # include "os_windows.inline.hpp" | |
| 37 #endif | |
| 3960 | 38 #ifdef TARGET_OS_FAMILY_bsd |
| 39 # include "os_bsd.inline.hpp" | |
| 40 #endif | |
| 0 | 41 |
| 42 | |
| 342 | 43 BitMap::BitMap(bm_word_t* map, idx_t size_in_bits) : |
| 44 _map(map), _size(size_in_bits) | |
| 45 { | |
| 46 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); | |
| 0 | 47 assert(size_in_bits >= 0, "just checking"); |
| 48 } | |
| 49 | |
| 50 | |
| 342 | 51 BitMap::BitMap(idx_t size_in_bits, bool in_resource_area) : |
| 52 _map(NULL), _size(0) | |
| 53 { | |
| 54 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); | |
| 55 resize(size_in_bits, in_resource_area); | |
| 0 | 56 } |
| 57 | |
| 342 | 58 void BitMap::resize(idx_t size_in_bits, bool in_resource_area) { |
| 0 | 59 assert(size_in_bits >= 0, "just checking"); |
| 342 | 60 idx_t old_size_in_words = size_in_words(); |
| 61 bm_word_t* old_map = map(); | |
| 62 | |
| 0 | 63 _size = size_in_bits; |
| 342 | 64 idx_t new_size_in_words = size_in_words(); |
| 65 if (in_resource_area) { | |
| 66 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words); | |
| 67 } else { | |
| 6197 | 68 if (old_map != NULL) FREE_C_HEAP_ARRAY(bm_word_t, _map, mtInternal); |
| 69 _map = NEW_C_HEAP_ARRAY(bm_word_t, new_size_in_words, mtInternal); | |
| 342 | 70 } |
| 71 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map, | |
| 72 MIN2(old_size_in_words, new_size_in_words)); | |
| 0 | 73 if (new_size_in_words > old_size_in_words) { |
| 74 clear_range_of_words(old_size_in_words, size_in_words()); | |
| 75 } | |
| 76 } | |
| 77 | |
| 78 void BitMap::set_range_within_word(idx_t beg, idx_t end) { | |
| 79 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 80 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 81 if (beg != end) { | |
| 342 | 82 bm_word_t mask = inverted_bit_mask_for_range(beg, end); |
| 0 | 83 *word_addr(beg) |= ~mask; |
| 84 } | |
| 85 } | |
| 86 | |
| 87 void BitMap::clear_range_within_word(idx_t beg, idx_t end) { | |
| 88 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 89 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 90 if (beg != end) { | |
| 342 | 91 bm_word_t mask = inverted_bit_mask_for_range(beg, end); |
| 0 | 92 *word_addr(beg) &= mask; |
| 93 } | |
| 94 } | |
| 95 | |
| 96 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { | |
| 97 assert(value == 0 || value == 1, "0 for clear, 1 for set"); | |
| 98 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 99 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 100 if (beg != end) { | |
| 101 intptr_t* pw = (intptr_t*)word_addr(beg); | |
| 102 intptr_t w = *pw; | |
| 103 intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end); | |
| 104 intptr_t nw = value ? (w | ~mr) : (w & mr); | |
| 105 while (true) { | |
| 106 intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w); | |
| 107 if (res == w) break; | |
| 108 w = *pw; | |
| 109 nw = value ? (w | ~mr) : (w & mr); | |
| 110 } | |
| 111 } | |
| 112 } | |
| 113 | |
| 114 void BitMap::set_range(idx_t beg, idx_t end) { | |
| 115 verify_range(beg, end); | |
| 116 | |
| 117 idx_t beg_full_word = word_index_round_up(beg); | |
| 118 idx_t end_full_word = word_index(end); | |
| 119 | |
| 120 if (beg_full_word < end_full_word) { | |
| 121 // The range includes at least one full word. | |
| 122 set_range_within_word(beg, bit_index(beg_full_word)); | |
| 123 set_range_of_words(beg_full_word, end_full_word); | |
| 124 set_range_within_word(bit_index(end_full_word), end); | |
| 125 } else { | |
| 126 // The range spans at most 2 partial words. | |
| 127 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 128 set_range_within_word(beg, boundary); | |
| 129 set_range_within_word(boundary, end); | |
| 130 } | |
| 131 } | |
| 132 | |
| 133 void BitMap::clear_range(idx_t beg, idx_t end) { | |
| 134 verify_range(beg, end); | |
| 135 | |
| 136 idx_t beg_full_word = word_index_round_up(beg); | |
| 137 idx_t end_full_word = word_index(end); | |
| 138 | |
| 139 if (beg_full_word < end_full_word) { | |
| 140 // The range includes at least one full word. | |
| 141 clear_range_within_word(beg, bit_index(beg_full_word)); | |
| 142 clear_range_of_words(beg_full_word, end_full_word); | |
| 143 clear_range_within_word(bit_index(end_full_word), end); | |
| 144 } else { | |
| 145 // The range spans at most 2 partial words. | |
| 146 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 147 clear_range_within_word(beg, boundary); | |
| 148 clear_range_within_word(boundary, end); | |
| 149 } | |
| 150 } | |
| 151 | |
| 152 void BitMap::set_large_range(idx_t beg, idx_t end) { | |
| 153 verify_range(beg, end); | |
| 154 | |
| 155 idx_t beg_full_word = word_index_round_up(beg); | |
| 156 idx_t end_full_word = word_index(end); | |
| 157 | |
| 158 assert(end_full_word - beg_full_word >= 32, | |
| 159 "the range must include at least 32 bytes"); | |
| 160 | |
| 161 // The range includes at least one full word. | |
| 162 set_range_within_word(beg, bit_index(beg_full_word)); | |
| 163 set_large_range_of_words(beg_full_word, end_full_word); | |
| 164 set_range_within_word(bit_index(end_full_word), end); | |
| 165 } | |
| 166 | |
| 167 void BitMap::clear_large_range(idx_t beg, idx_t end) { | |
| 168 verify_range(beg, end); | |
| 169 | |
| 170 idx_t beg_full_word = word_index_round_up(beg); | |
| 171 idx_t end_full_word = word_index(end); | |
| 172 | |
| 173 assert(end_full_word - beg_full_word >= 32, | |
| 174 "the range must include at least 32 bytes"); | |
| 175 | |
| 176 // The range includes at least one full word. | |
| 177 clear_range_within_word(beg, bit_index(beg_full_word)); | |
| 178 clear_large_range_of_words(beg_full_word, end_full_word); | |
| 179 clear_range_within_word(bit_index(end_full_word), end); | |
| 180 } | |
| 181 | |
| 182 void BitMap::at_put(idx_t offset, bool value) { | |
| 183 if (value) { | |
| 184 set_bit(offset); | |
| 185 } else { | |
| 186 clear_bit(offset); | |
| 187 } | |
| 188 } | |
| 189 | |
| 190 // Return true to indicate that this thread changed | |
| 191 // the bit, false to indicate that someone else did. | |
| 192 // In either case, the requested bit is in the | |
| 193 // requested state some time during the period that | |
| 194 // this thread is executing this call. More importantly, | |
| 195 // if no other thread is executing an action to | |
| 196 // change the requested bit to a state other than | |
| 197 // the one that this thread is trying to set it to, | |
| 198 // then the the bit is in the expected state | |
| 199 // at exit from this method. However, rather than | |
| 200 // make such a strong assertion here, based on | |
| 201 // assuming such constrained use (which though true | |
| 202 // today, could change in the future to service some | |
| 203 // funky parallel algorithm), we encourage callers | |
| 204 // to do such verification, as and when appropriate. | |
| 205 bool BitMap::par_at_put(idx_t bit, bool value) { | |
| 206 return value ? par_set_bit(bit) : par_clear_bit(bit); | |
| 207 } | |
| 208 | |
| 209 void BitMap::at_put_grow(idx_t offset, bool value) { | |
| 210 if (offset >= size()) { | |
| 211 resize(2 * MAX2(size(), offset)); | |
| 212 } | |
| 213 at_put(offset, value); | |
| 214 } | |
| 215 | |
| 216 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { | |
| 217 if (value) { | |
| 218 set_range(start_offset, end_offset); | |
| 219 } else { | |
| 220 clear_range(start_offset, end_offset); | |
| 221 } | |
| 222 } | |
| 223 | |
| 224 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { | |
| 225 verify_range(beg, end); | |
| 226 | |
| 227 idx_t beg_full_word = word_index_round_up(beg); | |
| 228 idx_t end_full_word = word_index(end); | |
| 229 | |
| 230 if (beg_full_word < end_full_word) { | |
| 231 // The range includes at least one full word. | |
| 232 par_put_range_within_word(beg, bit_index(beg_full_word), value); | |
| 233 if (value) { | |
| 234 set_range_of_words(beg_full_word, end_full_word); | |
| 235 } else { | |
| 236 clear_range_of_words(beg_full_word, end_full_word); | |
| 237 } | |
| 238 par_put_range_within_word(bit_index(end_full_word), end, value); | |
| 239 } else { | |
| 240 // The range spans at most 2 partial words. | |
| 241 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 242 par_put_range_within_word(beg, boundary, value); | |
| 243 par_put_range_within_word(boundary, end, value); | |
| 244 } | |
| 245 | |
| 246 } | |
| 247 | |
| 248 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { | |
| 249 if (value) { | |
| 250 set_large_range(beg, end); | |
| 251 } else { | |
| 252 clear_large_range(beg, end); | |
| 253 } | |
| 254 } | |
| 255 | |
| 256 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { | |
| 257 verify_range(beg, end); | |
| 258 | |
| 259 idx_t beg_full_word = word_index_round_up(beg); | |
| 260 idx_t end_full_word = word_index(end); | |
| 261 | |
| 262 assert(end_full_word - beg_full_word >= 32, | |
| 263 "the range must include at least 32 bytes"); | |
| 264 | |
| 265 // The range includes at least one full word. | |
| 266 par_put_range_within_word(beg, bit_index(beg_full_word), value); | |
| 267 if (value) { | |
| 268 set_large_range_of_words(beg_full_word, end_full_word); | |
| 269 } else { | |
| 270 clear_large_range_of_words(beg_full_word, end_full_word); | |
| 271 } | |
| 272 par_put_range_within_word(bit_index(end_full_word), end, value); | |
| 273 } | |
| 274 | |
| 275 bool BitMap::contains(const BitMap other) const { | |
| 276 assert(size() == other.size(), "must have same size"); | |
| 342 | 277 bm_word_t* dest_map = map(); |
| 278 bm_word_t* other_map = other.map(); | |
| 0 | 279 idx_t size = size_in_words(); |
| 280 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 342 | 281 bm_word_t word_union = dest_map[index] | other_map[index]; |
| 0 | 282 // If this has more bits set than dest_map[index], then other is not a |
| 283 // subset. | |
| 284 if (word_union != dest_map[index]) return false; | |
| 285 } | |
| 286 return true; | |
| 287 } | |
| 288 | |
| 289 bool BitMap::intersects(const BitMap other) const { | |
| 290 assert(size() == other.size(), "must have same size"); | |
| 342 | 291 bm_word_t* dest_map = map(); |
| 292 bm_word_t* other_map = other.map(); | |
| 0 | 293 idx_t size = size_in_words(); |
| 294 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 295 if ((dest_map[index] & other_map[index]) != 0) return true; | |
| 296 } | |
| 297 // Otherwise, no intersection. | |
| 298 return false; | |
| 299 } | |
| 300 | |
| 301 void BitMap::set_union(BitMap other) { | |
| 302 assert(size() == other.size(), "must have same size"); | |
| 342 | 303 bm_word_t* dest_map = map(); |
| 304 bm_word_t* other_map = other.map(); | |
| 0 | 305 idx_t size = size_in_words(); |
| 306 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 307 dest_map[index] = dest_map[index] | other_map[index]; | |
| 308 } | |
| 309 } | |
| 310 | |
| 311 | |
| 312 void BitMap::set_difference(BitMap other) { | |
| 313 assert(size() == other.size(), "must have same size"); | |
| 342 | 314 bm_word_t* dest_map = map(); |
| 315 bm_word_t* other_map = other.map(); | |
| 0 | 316 idx_t size = size_in_words(); |
| 317 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 318 dest_map[index] = dest_map[index] & ~(other_map[index]); | |
| 319 } | |
| 320 } | |
| 321 | |
| 322 | |
| 323 void BitMap::set_intersection(BitMap other) { | |
| 324 assert(size() == other.size(), "must have same size"); | |
| 342 | 325 bm_word_t* dest_map = map(); |
| 326 bm_word_t* other_map = other.map(); | |
| 0 | 327 idx_t size = size_in_words(); |
| 328 for (idx_t index = 0; index < size; index++) { | |
| 329 dest_map[index] = dest_map[index] & other_map[index]; | |
| 330 } | |
| 331 } | |
| 332 | |
| 333 | |
| 342 | 334 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) { |
| 335 assert(other.size() >= offset, "offset not in range"); | |
| 336 assert(other.size() - offset >= size(), "other not large enough"); | |
| 337 // XXX Ideally, we would remove this restriction. | |
| 338 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0, | |
| 339 "Only handle aligned cases so far."); | |
| 340 bm_word_t* dest_map = map(); | |
| 341 bm_word_t* other_map = other.map(); | |
| 342 idx_t offset_word_ind = word_index(offset); | |
| 343 idx_t size = size_in_words(); | |
| 344 for (idx_t index = 0; index < size; index++) { | |
| 345 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index]; | |
| 346 } | |
| 347 } | |
| 348 | |
| 0 | 349 bool BitMap::set_union_with_result(BitMap other) { |
| 350 assert(size() == other.size(), "must have same size"); | |
| 351 bool changed = false; | |
| 342 | 352 bm_word_t* dest_map = map(); |
| 353 bm_word_t* other_map = other.map(); | |
| 0 | 354 idx_t size = size_in_words(); |
| 355 for (idx_t index = 0; index < size; index++) { | |
| 356 idx_t temp = map(index) | other_map[index]; | |
| 357 changed = changed || (temp != map(index)); | |
| 358 map()[index] = temp; | |
| 359 } | |
| 360 return changed; | |
| 361 } | |
| 362 | |
| 363 | |
| 364 bool BitMap::set_difference_with_result(BitMap other) { | |
| 365 assert(size() == other.size(), "must have same size"); | |
| 366 bool changed = false; | |
| 342 | 367 bm_word_t* dest_map = map(); |
| 368 bm_word_t* other_map = other.map(); | |
| 0 | 369 idx_t size = size_in_words(); |
| 370 for (idx_t index = 0; index < size; index++) { | |
| 342 | 371 bm_word_t temp = dest_map[index] & ~(other_map[index]); |
| 0 | 372 changed = changed || (temp != dest_map[index]); |
| 373 dest_map[index] = temp; | |
| 374 } | |
| 375 return changed; | |
| 376 } | |
| 377 | |
| 378 | |
| 379 bool BitMap::set_intersection_with_result(BitMap other) { | |
| 380 assert(size() == other.size(), "must have same size"); | |
| 381 bool changed = false; | |
| 342 | 382 bm_word_t* dest_map = map(); |
| 383 bm_word_t* other_map = other.map(); | |
| 0 | 384 idx_t size = size_in_words(); |
| 385 for (idx_t index = 0; index < size; index++) { | |
| 342 | 386 bm_word_t orig = dest_map[index]; |
| 387 bm_word_t temp = orig & other_map[index]; | |
| 0 | 388 changed = changed || (temp != orig); |
| 389 dest_map[index] = temp; | |
| 390 } | |
| 391 return changed; | |
| 392 } | |
| 393 | |
| 394 | |
| 395 void BitMap::set_from(BitMap other) { | |
| 396 assert(size() == other.size(), "must have same size"); | |
| 342 | 397 bm_word_t* dest_map = map(); |
| 398 bm_word_t* other_map = other.map(); | |
| 0 | 399 idx_t size = size_in_words(); |
| 400 for (idx_t index = 0; index < size; index++) { | |
| 401 dest_map[index] = other_map[index]; | |
| 402 } | |
| 403 } | |
| 404 | |
| 405 | |
| 406 bool BitMap::is_same(BitMap other) { | |
| 407 assert(size() == other.size(), "must have same size"); | |
| 342 | 408 bm_word_t* dest_map = map(); |
| 409 bm_word_t* other_map = other.map(); | |
| 0 | 410 idx_t size = size_in_words(); |
| 411 for (idx_t index = 0; index < size; index++) { | |
| 412 if (dest_map[index] != other_map[index]) return false; | |
| 413 } | |
| 414 return true; | |
| 415 } | |
| 416 | |
| 417 bool BitMap::is_full() const { | |
| 342 | 418 bm_word_t* word = map(); |
| 0 | 419 idx_t rest = size(); |
| 420 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { | |
| 342 | 421 if (*word != (bm_word_t) AllBits) return false; |
| 0 | 422 word++; |
| 423 } | |
| 342 | 424 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits; |
| 0 | 425 } |
| 426 | |
| 427 | |
| 428 bool BitMap::is_empty() const { | |
| 342 | 429 bm_word_t* word = map(); |
| 0 | 430 idx_t rest = size(); |
| 431 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { | |
| 342 | 432 if (*word != (bm_word_t) NoBits) return false; |
| 0 | 433 word++; |
| 434 } | |
| 342 | 435 return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits; |
| 0 | 436 } |
| 437 | |
| 438 void BitMap::clear_large() { | |
| 439 clear_large_range_of_words(0, size_in_words()); | |
| 440 } | |
| 441 | |
| 442 // Note that if the closure itself modifies the bitmap | |
| 443 // then modifications in and to the left of the _bit_ being | |
| 444 // currently sampled will not be seen. Note also that the | |
| 445 // interval [leftOffset, rightOffset) is right open. | |
| 342 | 446 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { |
| 0 | 447 verify_range(leftOffset, rightOffset); |
| 448 | |
| 449 idx_t startIndex = word_index(leftOffset); | |
| 450 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); | |
| 451 for (idx_t index = startIndex, offset = leftOffset; | |
| 452 offset < rightOffset && index < endIndex; | |
| 453 offset = (++index) << LogBitsPerWord) { | |
| 454 idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); | |
| 342 | 455 for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) { |
| 0 | 456 if (rest & 1) { |
| 342 | 457 if (!blk->do_bit(offset)) return false; |
| 0 | 458 // resample at each closure application |
| 459 // (see, for instance, CMS bug 4525989) | |
| 460 rest = map(index) >> (offset & (BitsPerWord -1)); | |
| 461 } | |
| 462 rest = rest >> 1; | |
| 463 } | |
| 464 } | |
| 342 | 465 return true; |
| 466 } | |
| 467 | |
| 468 BitMap::idx_t* BitMap::_pop_count_table = NULL; | |
| 469 | |
| 470 void BitMap::init_pop_count_table() { | |
| 471 if (_pop_count_table == NULL) { | |
| 6197 | 472 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal); |
| 342 | 473 for (uint i = 0; i < 256; i++) { |
| 474 table[i] = num_set_bits(i); | |
| 475 } | |
| 476 | |
| 477 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table, | |
| 478 (intptr_t*) &_pop_count_table, | |
| 479 (intptr_t) NULL_WORD); | |
| 480 if (res != NULL_WORD) { | |
| 481 guarantee( _pop_count_table == (void*) res, "invariant" ); | |
| 6197 | 482 FREE_C_HEAP_ARRAY(bm_word_t, table, mtInternal); |
| 342 | 483 } |
| 484 } | |
| 0 | 485 } |
| 486 | |
| 342 | 487 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) { |
| 488 idx_t bits = 0; | |
| 0 | 489 |
| 342 | 490 while (w != 0) { |
| 491 while ((w & 1) == 0) { | |
| 492 w >>= 1; | |
| 0 | 493 } |
| 342 | 494 bits++; |
| 495 w >>= 1; | |
| 0 | 496 } |
| 342 | 497 return bits; |
| 0 | 498 } |
| 499 | |
| 342 | 500 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { |
| 501 assert(_pop_count_table != NULL, "precondition"); | |
| 502 return _pop_count_table[c]; | |
| 503 } | |
| 0 | 504 |
| 342 | 505 BitMap::idx_t BitMap::count_one_bits() const { |
| 506 init_pop_count_table(); // If necessary. | |
| 507 idx_t sum = 0; | |
| 508 typedef unsigned char uchar; | |
| 509 for (idx_t i = 0; i < size_in_words(); i++) { | |
| 510 bm_word_t w = map()[i]; | |
| 511 for (size_t j = 0; j < sizeof(bm_word_t); j++) { | |
| 512 sum += num_set_bits_from_table(uchar(w & 255)); | |
| 513 w >>= 8; | |
| 0 | 514 } |
| 515 } | |
| 342 | 516 return sum; |
| 0 | 517 } |
| 518 | |
| 342 | 519 |
| 0 | 520 #ifndef PRODUCT |
| 521 | |
| 522 void BitMap::print_on(outputStream* st) const { | |
| 523 tty->print("Bitmap(%d):", size()); | |
| 524 for (idx_t index = 0; index < size(); index++) { | |
| 525 tty->print("%c", at(index) ? '1' : '0'); | |
| 526 } | |
| 527 tty->cr(); | |
| 528 } | |
| 529 | |
| 530 #endif | |
| 531 | |
| 532 | |
| 342 | 533 BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot) |
| 0 | 534 : _bits_per_slot(bits_per_slot) |
| 535 , _map(map, size_in_slots * bits_per_slot) | |
| 536 { | |
| 537 } | |
| 538 | |
| 539 | |
| 540 BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) | |
| 541 : _bits_per_slot(bits_per_slot) | |
| 542 , _map(size_in_slots * bits_per_slot) | |
| 543 { | |
| 544 } |