bitMap.cpp revision 342:37f87013dfd8
1/* 2 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved. 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 * 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 20 * CA 95054 USA or visit www.sun.com if you need additional information or 21 * have any questions. 22 * 23 */ 24 25# include "incls/_precompiled.incl" 26# include "incls/_bitMap.cpp.incl" 27 28 29BitMap::BitMap(bm_word_t* map, idx_t size_in_bits) : 30 _map(map), _size(size_in_bits) 31{ 32 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); 33 assert(size_in_bits >= 0, "just checking"); 34} 35 36 37BitMap::BitMap(idx_t size_in_bits, bool in_resource_area) : 38 _map(NULL), _size(0) 39{ 40 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); 41 resize(size_in_bits, in_resource_area); 42} 43 44 45void BitMap::verify_index(idx_t index) const { 46 assert(index < _size, "BitMap index out of bounds"); 47} 48 49void BitMap::verify_range(idx_t beg_index, idx_t end_index) const { 50#ifdef ASSERT 51 assert(beg_index <= end_index, "BitMap range error"); 52 // Note that [0,0) and [size,size) are both valid ranges. 53 if (end_index != _size) verify_index(end_index); 54#endif 55} 56 57void BitMap::resize(idx_t size_in_bits, bool in_resource_area) { 58 assert(size_in_bits >= 0, "just checking"); 59 idx_t old_size_in_words = size_in_words(); 60 bm_word_t* old_map = map(); 61 62 _size = size_in_bits; 63 idx_t new_size_in_words = size_in_words(); 64 if (in_resource_area) { 65 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words); 66 } else { 67 if (old_map != NULL) FREE_C_HEAP_ARRAY(bm_word_t, _map); 68 _map = NEW_C_HEAP_ARRAY(bm_word_t, new_size_in_words); 69 } 70 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map, 71 MIN2(old_size_in_words, new_size_in_words)); 72 if (new_size_in_words > old_size_in_words) { 73 clear_range_of_words(old_size_in_words, size_in_words()); 74 } 75} 76 77void BitMap::set_range_within_word(idx_t beg, idx_t end) { 78 // With a valid range (beg <= end), this test ensures that end != 0, as 79 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 80 if (beg != end) { 81 bm_word_t mask = inverted_bit_mask_for_range(beg, end); 82 *word_addr(beg) |= ~mask; 83 } 84} 85 86void BitMap::clear_range_within_word(idx_t beg, idx_t end) { 87 // With a valid range (beg <= end), this test ensures that end != 0, as 88 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 89 if (beg != end) { 90 bm_word_t mask = inverted_bit_mask_for_range(beg, end); 91 *word_addr(beg) &= mask; 92 } 93} 94 95void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { 96 assert(value == 0 || value == 1, "0 for clear, 1 for set"); 97 // With a valid range (beg <= end), this test ensures that end != 0, as 98 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 99 if (beg != end) { 100 intptr_t* pw = (intptr_t*)word_addr(beg); 101 intptr_t w = *pw; 102 intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end); 103 intptr_t nw = value ? (w | ~mr) : (w & mr); 104 while (true) { 105 intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w); 106 if (res == w) break; 107 w = *pw; 108 nw = value ? (w | ~mr) : (w & mr); 109 } 110 } 111} 112 113void BitMap::set_range(idx_t beg, idx_t end) { 114 verify_range(beg, end); 115 116 idx_t beg_full_word = word_index_round_up(beg); 117 idx_t end_full_word = word_index(end); 118 119 if (beg_full_word < end_full_word) { 120 // The range includes at least one full word. 121 set_range_within_word(beg, bit_index(beg_full_word)); 122 set_range_of_words(beg_full_word, end_full_word); 123 set_range_within_word(bit_index(end_full_word), end); 124 } else { 125 // The range spans at most 2 partial words. 126 idx_t boundary = MIN2(bit_index(beg_full_word), end); 127 set_range_within_word(beg, boundary); 128 set_range_within_word(boundary, end); 129 } 130} 131 132void BitMap::clear_range(idx_t beg, idx_t end) { 133 verify_range(beg, end); 134 135 idx_t beg_full_word = word_index_round_up(beg); 136 idx_t end_full_word = word_index(end); 137 138 if (beg_full_word < end_full_word) { 139 // The range includes at least one full word. 140 clear_range_within_word(beg, bit_index(beg_full_word)); 141 clear_range_of_words(beg_full_word, end_full_word); 142 clear_range_within_word(bit_index(end_full_word), end); 143 } else { 144 // The range spans at most 2 partial words. 145 idx_t boundary = MIN2(bit_index(beg_full_word), end); 146 clear_range_within_word(beg, boundary); 147 clear_range_within_word(boundary, end); 148 } 149} 150 151void BitMap::set_large_range(idx_t beg, idx_t end) { 152 verify_range(beg, end); 153 154 idx_t beg_full_word = word_index_round_up(beg); 155 idx_t end_full_word = word_index(end); 156 157 assert(end_full_word - beg_full_word >= 32, 158 "the range must include at least 32 bytes"); 159 160 // The range includes at least one full word. 161 set_range_within_word(beg, bit_index(beg_full_word)); 162 set_large_range_of_words(beg_full_word, end_full_word); 163 set_range_within_word(bit_index(end_full_word), end); 164} 165 166void BitMap::clear_large_range(idx_t beg, idx_t end) { 167 verify_range(beg, end); 168 169 idx_t beg_full_word = word_index_round_up(beg); 170 idx_t end_full_word = word_index(end); 171 172 assert(end_full_word - beg_full_word >= 32, 173 "the range must include at least 32 bytes"); 174 175 // The range includes at least one full word. 176 clear_range_within_word(beg, bit_index(beg_full_word)); 177 clear_large_range_of_words(beg_full_word, end_full_word); 178 clear_range_within_word(bit_index(end_full_word), end); 179} 180 181void BitMap::mostly_disjoint_range_union(BitMap* from_bitmap, 182 idx_t from_start_index, 183 idx_t to_start_index, 184 size_t word_num) { 185 // Ensure that the parameters are correct. 186 // These shouldn't be that expensive to check, hence I left them as 187 // guarantees. 188 guarantee(from_bitmap->bit_in_word(from_start_index) == 0, 189 "it should be aligned on a word boundary"); 190 guarantee(bit_in_word(to_start_index) == 0, 191 "it should be aligned on a word boundary"); 192 guarantee(word_num >= 2, "word_num should be at least 2"); 193 194 intptr_t* from = (intptr_t*) from_bitmap->word_addr(from_start_index); 195 intptr_t* to = (intptr_t*) word_addr(to_start_index); 196 197 if (*from != 0) { 198 // if it's 0, then there's no point in doing the CAS 199 while (true) { 200 intptr_t old_value = *to; 201 intptr_t new_value = old_value | *from; 202 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value); 203 if (res == old_value) break; 204 } 205 } 206 ++from; 207 ++to; 208 209 for (size_t i = 0; i < word_num - 2; ++i) { 210 if (*from != 0) { 211 // if it's 0, then there's no point in doing the CAS 212 assert(*to == 0, "nobody else should be writing here"); 213 intptr_t new_value = *from; 214 *to = new_value; 215 } 216 217 ++from; 218 ++to; 219 } 220 221 if (*from != 0) { 222 // if it's 0, then there's no point in doing the CAS 223 while (true) { 224 intptr_t old_value = *to; 225 intptr_t new_value = old_value | *from; 226 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value); 227 if (res == old_value) break; 228 } 229 } 230 231 // the -1 is because we didn't advance them after the final CAS 232 assert(from == 233 (intptr_t*) from_bitmap->word_addr(from_start_index) + word_num - 1, 234 "invariant"); 235 assert(to == (intptr_t*) word_addr(to_start_index) + word_num - 1, 236 "invariant"); 237} 238 239void BitMap::at_put(idx_t offset, bool value) { 240 if (value) { 241 set_bit(offset); 242 } else { 243 clear_bit(offset); 244 } 245} 246 247// Return true to indicate that this thread changed 248// the bit, false to indicate that someone else did. 249// In either case, the requested bit is in the 250// requested state some time during the period that 251// this thread is executing this call. More importantly, 252// if no other thread is executing an action to 253// change the requested bit to a state other than 254// the one that this thread is trying to set it to, 255// then the the bit is in the expected state 256// at exit from this method. However, rather than 257// make such a strong assertion here, based on 258// assuming such constrained use (which though true 259// today, could change in the future to service some 260// funky parallel algorithm), we encourage callers 261// to do such verification, as and when appropriate. 262bool BitMap::par_at_put(idx_t bit, bool value) { 263 return value ? par_set_bit(bit) : par_clear_bit(bit); 264} 265 266void BitMap::at_put_grow(idx_t offset, bool value) { 267 if (offset >= size()) { 268 resize(2 * MAX2(size(), offset)); 269 } 270 at_put(offset, value); 271} 272 273void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { 274 if (value) { 275 set_range(start_offset, end_offset); 276 } else { 277 clear_range(start_offset, end_offset); 278 } 279} 280 281void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { 282 verify_range(beg, end); 283 284 idx_t beg_full_word = word_index_round_up(beg); 285 idx_t end_full_word = word_index(end); 286 287 if (beg_full_word < end_full_word) { 288 // The range includes at least one full word. 289 par_put_range_within_word(beg, bit_index(beg_full_word), value); 290 if (value) { 291 set_range_of_words(beg_full_word, end_full_word); 292 } else { 293 clear_range_of_words(beg_full_word, end_full_word); 294 } 295 par_put_range_within_word(bit_index(end_full_word), end, value); 296 } else { 297 // The range spans at most 2 partial words. 298 idx_t boundary = MIN2(bit_index(beg_full_word), end); 299 par_put_range_within_word(beg, boundary, value); 300 par_put_range_within_word(boundary, end, value); 301 } 302 303} 304 305void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { 306 if (value) { 307 set_large_range(beg, end); 308 } else { 309 clear_large_range(beg, end); 310 } 311} 312 313void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { 314 verify_range(beg, end); 315 316 idx_t beg_full_word = word_index_round_up(beg); 317 idx_t end_full_word = word_index(end); 318 319 assert(end_full_word - beg_full_word >= 32, 320 "the range must include at least 32 bytes"); 321 322 // The range includes at least one full word. 323 par_put_range_within_word(beg, bit_index(beg_full_word), value); 324 if (value) { 325 set_large_range_of_words(beg_full_word, end_full_word); 326 } else { 327 clear_large_range_of_words(beg_full_word, end_full_word); 328 } 329 par_put_range_within_word(bit_index(end_full_word), end, value); 330} 331 332bool BitMap::contains(const BitMap other) const { 333 assert(size() == other.size(), "must have same size"); 334 bm_word_t* dest_map = map(); 335 bm_word_t* other_map = other.map(); 336 idx_t size = size_in_words(); 337 for (idx_t index = 0; index < size_in_words(); index++) { 338 bm_word_t word_union = dest_map[index] | other_map[index]; 339 // If this has more bits set than dest_map[index], then other is not a 340 // subset. 341 if (word_union != dest_map[index]) return false; 342 } 343 return true; 344} 345 346bool BitMap::intersects(const BitMap other) const { 347 assert(size() == other.size(), "must have same size"); 348 bm_word_t* dest_map = map(); 349 bm_word_t* other_map = other.map(); 350 idx_t size = size_in_words(); 351 for (idx_t index = 0; index < size_in_words(); index++) { 352 if ((dest_map[index] & other_map[index]) != 0) return true; 353 } 354 // Otherwise, no intersection. 355 return false; 356} 357 358void BitMap::set_union(BitMap other) { 359 assert(size() == other.size(), "must have same size"); 360 bm_word_t* dest_map = map(); 361 bm_word_t* other_map = other.map(); 362 idx_t size = size_in_words(); 363 for (idx_t index = 0; index < size_in_words(); index++) { 364 dest_map[index] = dest_map[index] | other_map[index]; 365 } 366} 367 368 369void BitMap::set_difference(BitMap other) { 370 assert(size() == other.size(), "must have same size"); 371 bm_word_t* dest_map = map(); 372 bm_word_t* other_map = other.map(); 373 idx_t size = size_in_words(); 374 for (idx_t index = 0; index < size_in_words(); index++) { 375 dest_map[index] = dest_map[index] & ~(other_map[index]); 376 } 377} 378 379 380void BitMap::set_intersection(BitMap other) { 381 assert(size() == other.size(), "must have same size"); 382 bm_word_t* dest_map = map(); 383 bm_word_t* other_map = other.map(); 384 idx_t size = size_in_words(); 385 for (idx_t index = 0; index < size; index++) { 386 dest_map[index] = dest_map[index] & other_map[index]; 387 } 388} 389 390 391void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) { 392 assert(other.size() >= offset, "offset not in range"); 393 assert(other.size() - offset >= size(), "other not large enough"); 394 // XXX Ideally, we would remove this restriction. 395 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0, 396 "Only handle aligned cases so far."); 397 bm_word_t* dest_map = map(); 398 bm_word_t* other_map = other.map(); 399 idx_t offset_word_ind = word_index(offset); 400 idx_t size = size_in_words(); 401 for (idx_t index = 0; index < size; index++) { 402 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index]; 403 } 404} 405 406bool BitMap::set_union_with_result(BitMap other) { 407 assert(size() == other.size(), "must have same size"); 408 bool changed = false; 409 bm_word_t* dest_map = map(); 410 bm_word_t* other_map = other.map(); 411 idx_t size = size_in_words(); 412 for (idx_t index = 0; index < size; index++) { 413 idx_t temp = map(index) | other_map[index]; 414 changed = changed || (temp != map(index)); 415 map()[index] = temp; 416 } 417 return changed; 418} 419 420 421bool BitMap::set_difference_with_result(BitMap other) { 422 assert(size() == other.size(), "must have same size"); 423 bool changed = false; 424 bm_word_t* dest_map = map(); 425 bm_word_t* other_map = other.map(); 426 idx_t size = size_in_words(); 427 for (idx_t index = 0; index < size; index++) { 428 bm_word_t temp = dest_map[index] & ~(other_map[index]); 429 changed = changed || (temp != dest_map[index]); 430 dest_map[index] = temp; 431 } 432 return changed; 433} 434 435 436bool BitMap::set_intersection_with_result(BitMap other) { 437 assert(size() == other.size(), "must have same size"); 438 bool changed = false; 439 bm_word_t* dest_map = map(); 440 bm_word_t* other_map = other.map(); 441 idx_t size = size_in_words(); 442 for (idx_t index = 0; index < size; index++) { 443 bm_word_t orig = dest_map[index]; 444 bm_word_t temp = orig & other_map[index]; 445 changed = changed || (temp != orig); 446 dest_map[index] = temp; 447 } 448 return changed; 449} 450 451 452void BitMap::set_from(BitMap other) { 453 assert(size() == other.size(), "must have same size"); 454 bm_word_t* dest_map = map(); 455 bm_word_t* other_map = other.map(); 456 idx_t size = size_in_words(); 457 for (idx_t index = 0; index < size; index++) { 458 dest_map[index] = other_map[index]; 459 } 460} 461 462 463bool BitMap::is_same(BitMap other) { 464 assert(size() == other.size(), "must have same size"); 465 bm_word_t* dest_map = map(); 466 bm_word_t* other_map = other.map(); 467 idx_t size = size_in_words(); 468 for (idx_t index = 0; index < size; index++) { 469 if (dest_map[index] != other_map[index]) return false; 470 } 471 return true; 472} 473 474bool BitMap::is_full() const { 475 bm_word_t* word = map(); 476 idx_t rest = size(); 477 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 478 if (*word != (bm_word_t) AllBits) return false; 479 word++; 480 } 481 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits; 482} 483 484 485bool BitMap::is_empty() const { 486 bm_word_t* word = map(); 487 idx_t rest = size(); 488 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 489 if (*word != (bm_word_t) NoBits) return false; 490 word++; 491 } 492 return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits; 493} 494 495void BitMap::clear_large() { 496 clear_large_range_of_words(0, size_in_words()); 497} 498 499// Note that if the closure itself modifies the bitmap 500// then modifications in and to the left of the _bit_ being 501// currently sampled will not be seen. Note also that the 502// interval [leftOffset, rightOffset) is right open. 503bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { 504 verify_range(leftOffset, rightOffset); 505 506 idx_t startIndex = word_index(leftOffset); 507 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); 508 for (idx_t index = startIndex, offset = leftOffset; 509 offset < rightOffset && index < endIndex; 510 offset = (++index) << LogBitsPerWord) { 511 idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); 512 for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) { 513 if (rest & 1) { 514 if (!blk->do_bit(offset)) return false; 515 // resample at each closure application 516 // (see, for instance, CMS bug 4525989) 517 rest = map(index) >> (offset & (BitsPerWord -1)); 518 } 519 rest = rest >> 1; 520 } 521 } 522 return true; 523} 524 525BitMap::idx_t* BitMap::_pop_count_table = NULL; 526 527void BitMap::init_pop_count_table() { 528 if (_pop_count_table == NULL) { 529 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256); 530 for (uint i = 0; i < 256; i++) { 531 table[i] = num_set_bits(i); 532 } 533 534 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table, 535 (intptr_t*) &_pop_count_table, 536 (intptr_t) NULL_WORD); 537 if (res != NULL_WORD) { 538 guarantee( _pop_count_table == (void*) res, "invariant" ); 539 FREE_C_HEAP_ARRAY(bm_word_t, table); 540 } 541 } 542} 543 544BitMap::idx_t BitMap::num_set_bits(bm_word_t w) { 545 idx_t bits = 0; 546 547 while (w != 0) { 548 while ((w & 1) == 0) { 549 w >>= 1; 550 } 551 bits++; 552 w >>= 1; 553 } 554 return bits; 555} 556 557BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { 558 assert(_pop_count_table != NULL, "precondition"); 559 return _pop_count_table[c]; 560} 561 562BitMap::idx_t BitMap::count_one_bits() const { 563 init_pop_count_table(); // If necessary. 564 idx_t sum = 0; 565 typedef unsigned char uchar; 566 for (idx_t i = 0; i < size_in_words(); i++) { 567 bm_word_t w = map()[i]; 568 for (size_t j = 0; j < sizeof(bm_word_t); j++) { 569 sum += num_set_bits_from_table(uchar(w & 255)); 570 w >>= 8; 571 } 572 } 573 return sum; 574} 575 576 577#ifndef PRODUCT 578 579void BitMap::print_on(outputStream* st) const { 580 tty->print("Bitmap(%d):", size()); 581 for (idx_t index = 0; index < size(); index++) { 582 tty->print("%c", at(index) ? '1' : '0'); 583 } 584 tty->cr(); 585} 586 587#endif 588 589 590BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot) 591 : _bits_per_slot(bits_per_slot) 592 , _map(map, size_in_slots * bits_per_slot) 593{ 594} 595 596 597BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) 598 : _bits_per_slot(bits_per_slot) 599 , _map(size_in_slots * bits_per_slot) 600{ 601} 602