bitMap.cpp revision 2721:f08d439fab8c
1141104Sharti/* 21590Srgrimes * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. 31590Srgrimes * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 41590Srgrimes * 51590Srgrimes * This code is free software; you can redistribute it and/or modify it 61590Srgrimes * under the terms of the GNU General Public License version 2 only, as 71590Srgrimes * published by the Free Software Foundation. 81590Srgrimes * 91590Srgrimes * This code is distributed in the hope that it will be useful, but WITHOUT 101590Srgrimes * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 111590Srgrimes * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 121590Srgrimes * version 2 for more details (a copy is included in the LICENSE file that 131590Srgrimes * accompanied this code). 141590Srgrimes * 151590Srgrimes * You should have received a copy of the GNU General Public License version 161590Srgrimes * 2 along with this work; if not, write to the Free Software Foundation, 171590Srgrimes * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 181590Srgrimes * 191590Srgrimes * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 201590Srgrimes * or visit www.oracle.com if you need additional information or have any 211590Srgrimes * questions. 221590Srgrimes * 231590Srgrimes */ 241590Srgrimes 251590Srgrimes#include "precompiled.hpp" 261590Srgrimes#include "memory/allocation.inline.hpp" 271590Srgrimes#include "utilities/bitMap.inline.hpp" 281590Srgrimes#include "utilities/copy.hpp" 291590Srgrimes#ifdef TARGET_OS_FAMILY_linux 301590Srgrimes# include "os_linux.inline.hpp" 311590Srgrimes#endif 321590Srgrimes#ifdef TARGET_OS_FAMILY_solaris 331590Srgrimes# include "os_solaris.inline.hpp" 341590Srgrimes#endif 351590Srgrimes#ifdef TARGET_OS_FAMILY_windows 361590Srgrimes# include "os_windows.inline.hpp" 3762833Swsanchez#endif 3862833Swsanchez#ifdef TARGET_OS_FAMILY_bsd 391590Srgrimes# include "os_bsd.inline.hpp" 401590Srgrimes#endif 4162833Swsanchez 4294587Sobrien 431590SrgrimesBitMap::BitMap(bm_word_t* map, idx_t size_in_bits) : 441590Srgrimes _map(map), _size(size_in_bits) 451590Srgrimes{ 461590Srgrimes assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); 471590Srgrimes assert(size_in_bits >= 0, "just checking"); 481590Srgrimes} 491590Srgrimes 501590Srgrimes 511590SrgrimesBitMap::BitMap(idx_t size_in_bits, bool in_resource_area) : 521590Srgrimes _map(NULL), _size(0) 531590Srgrimes{ 541590Srgrimes assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); 55144026Sharti resize(size_in_bits, in_resource_area); 56144026Sharti} 57144026Sharti 58144026Shartivoid BitMap::resize(idx_t size_in_bits, bool in_resource_area) { 591590Srgrimes assert(size_in_bits >= 0, "just checking"); 60144026Sharti idx_t old_size_in_words = size_in_words(); 61144026Sharti bm_word_t* old_map = map(); 62144026Sharti 63144026Sharti _size = size_in_bits; 64144026Sharti idx_t new_size_in_words = size_in_words(); 651590Srgrimes if (in_resource_area) { 66144026Sharti _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words); 67144026Sharti } else { 68144026Sharti if (old_map != NULL) FREE_C_HEAP_ARRAY(bm_word_t, _map); 69144026Sharti _map = NEW_C_HEAP_ARRAY(bm_word_t, new_size_in_words); 70144026Sharti } 711590Srgrimes Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map, 721590Srgrimes MIN2(old_size_in_words, new_size_in_words)); 73144341Sharti if (new_size_in_words > old_size_in_words) { 74141104Sharti clear_range_of_words(old_size_in_words, size_in_words()); 751590Srgrimes } 76141104Sharti} 77141104Sharti 7827644Scharniervoid BitMap::set_range_within_word(idx_t beg, idx_t end) { 79141104Sharti // With a valid range (beg <= end), this test ensures that end != 0, as 80141104Sharti // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 81141104Sharti if (beg != end) { 82141104Sharti bm_word_t mask = inverted_bit_mask_for_range(beg, end); 83141104Sharti *word_addr(beg) |= ~mask; 841590Srgrimes } 85141104Sharti} 86141104Sharti 87141104Shartivoid BitMap::clear_range_within_word(idx_t beg, idx_t end) { 88145683Sharti // With a valid range (beg <= end), this test ensures that end != 0, as 891590Srgrimes // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 90141104Sharti if (beg != end) { 91141104Sharti bm_word_t mask = inverted_bit_mask_for_range(beg, end); 921590Srgrimes *word_addr(beg) &= mask; 93146572Sharti } 94141104Sharti} 95141104Sharti 96141104Shartivoid BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { 97141104Sharti assert(value == 0 || value == 1, "0 for clear, 1 for set"); 98141104Sharti // With a valid range (beg <= end), this test ensures that end != 0, as 991590Srgrimes // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 1001590Srgrimes if (beg != end) { 101144341Sharti intptr_t* pw = (intptr_t*)word_addr(beg); 1021590Srgrimes intptr_t w = *pw; 1031590Srgrimes intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end); 1041590Srgrimes intptr_t nw = value ? (w | ~mr) : (w & mr); 1051590Srgrimes while (true) { 1061590Srgrimes intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w); 107138916Sharti if (res == w) break; 108138916Sharti w = *pw; 109138916Sharti nw = value ? (w | ~mr) : (w & mr); 110138916Sharti } 111144026Sharti } 112144026Sharti} 1131590Srgrimes 114144026Shartivoid BitMap::set_range(idx_t beg, idx_t end) { 1151590Srgrimes verify_range(beg, end); 116144026Sharti 117144026Sharti idx_t beg_full_word = word_index_round_up(beg); 118144026Sharti idx_t end_full_word = word_index(end); 119144026Sharti 120144026Sharti if (beg_full_word < end_full_word) { 121126824Sru // The range includes at least one full word. 122144341Sharti set_range_within_word(beg, bit_index(beg_full_word)); 123144341Sharti set_range_of_words(beg_full_word, end_full_word); 124144341Sharti set_range_within_word(bit_index(end_full_word), end); 125144341Sharti } else { 126144341Sharti // The range spans at most 2 partial words. 127144341Sharti idx_t boundary = MIN2(bit_index(beg_full_word), end); 128144341Sharti set_range_within_word(beg, boundary); 129144341Sharti set_range_within_word(boundary, end); 130144341Sharti } 131144341Sharti} 132144341Sharti 133144026Shartivoid BitMap::clear_range(idx_t beg, idx_t end) { 134138916Sharti verify_range(beg, end); 135144341Sharti 1361590Srgrimes idx_t beg_full_word = word_index_round_up(beg); 137144341Sharti idx_t end_full_word = word_index(end); 138144341Sharti 139144341Sharti if (beg_full_word < end_full_word) { 140138916Sharti // The range includes at least one full word. 141144020Sharti clear_range_within_word(beg, bit_index(beg_full_word)); 142138916Sharti clear_range_of_words(beg_full_word, end_full_word); 143138916Sharti clear_range_within_word(bit_index(end_full_word), end); 144144020Sharti } else { 145138916Sharti // The range spans at most 2 partial words. 146144026Sharti idx_t boundary = MIN2(bit_index(beg_full_word), end); 1471590Srgrimes clear_range_within_word(beg, boundary); 1481590Srgrimes clear_range_within_word(boundary, end); 1491590Srgrimes } 1501590Srgrimes} 1511590Srgrimes 1521590Srgrimesvoid BitMap::set_large_range(idx_t beg, idx_t end) { 153144026Sharti verify_range(beg, end); 154144026Sharti 155144026Sharti idx_t beg_full_word = word_index_round_up(beg); 156145971Sharti idx_t end_full_word = word_index(end); 157144026Sharti 158144026Sharti assert(end_full_word - beg_full_word >= 32, 159144026Sharti "the range must include at least 32 bytes"); 160144026Sharti 161144026Sharti // The range includes at least one full word. 162144026Sharti set_range_within_word(beg, bit_index(beg_full_word)); 163144026Sharti set_large_range_of_words(beg_full_word, end_full_word); 164144026Sharti set_range_within_word(bit_index(end_full_word), end); 165144026Sharti} 166144026Sharti 167144026Shartivoid BitMap::clear_large_range(idx_t beg, idx_t end) { 168144026Sharti verify_range(beg, end); 169144026Sharti 170144026Sharti idx_t beg_full_word = word_index_round_up(beg); 171177101Sobrien idx_t end_full_word = word_index(end); 172144026Sharti 173144026Sharti assert(end_full_word - beg_full_word >= 32, 174144026Sharti "the range must include at least 32 bytes"); 175144026Sharti 176144026Sharti // The range includes at least one full word. 177144026Sharti clear_range_within_word(beg, bit_index(beg_full_word)); 178145679Sharti clear_large_range_of_words(beg_full_word, end_full_word); 179144026Sharti clear_range_within_word(bit_index(end_full_word), end); 1801590Srgrimes} 1811590Srgrimes 1821590Srgrimesvoid BitMap::mostly_disjoint_range_union(BitMap* from_bitmap, 18318730Ssteve idx_t from_start_index, 1841590Srgrimes idx_t to_start_index, 1851590Srgrimes size_t word_num) { 18669527Swill // Ensure that the parameters are correct. 1871590Srgrimes // These shouldn't be that expensive to check, hence I left them as 1881590Srgrimes // guarantees. 189144026Sharti guarantee(from_bitmap->bit_in_word(from_start_index) == 0, 1901590Srgrimes "it should be aligned on a word boundary"); 1911590Srgrimes guarantee(bit_in_word(to_start_index) == 0, 1921590Srgrimes "it should be aligned on a word boundary"); 1931590Srgrimes guarantee(word_num >= 2, "word_num should be at least 2"); 1941590Srgrimes 1951590Srgrimes intptr_t* from = (intptr_t*) from_bitmap->word_addr(from_start_index); 1961590Srgrimes intptr_t* to = (intptr_t*) word_addr(to_start_index); 1971590Srgrimes 198145616Sharti if (*from != 0) { 199144026Sharti // if it's 0, then there's no point in doing the CAS 200144026Sharti while (true) { 201144026Sharti intptr_t old_value = *to; 2021590Srgrimes intptr_t new_value = old_value | *from; 203145616Sharti intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value); 204144026Sharti if (res == old_value) break; 205144026Sharti } 206144026Sharti } 207144026Sharti ++from; 208145971Sharti ++to; 209144026Sharti 210144026Sharti for (size_t i = 0; i < word_num - 2; ++i) { 211144026Sharti if (*from != 0) { 212144026Sharti // if it's 0, then there's no point in doing the CAS 213144026Sharti assert(*to == 0, "nobody else should be writing here"); 214144026Sharti intptr_t new_value = *from; 215144026Sharti *to = new_value; 216144026Sharti } 217177101Sobrien 218144026Sharti ++from; 219144026Sharti ++to; 220144026Sharti } 221144026Sharti 222144026Sharti if (*from != 0) { 223144026Sharti // if it's 0, then there's no point in doing the CAS 224144026Sharti while (true) { 225144026Sharti intptr_t old_value = *to; 226144026Sharti intptr_t new_value = old_value | *from; 227144026Sharti intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value); 228144026Sharti if (res == old_value) break; 229144026Sharti } 230144026Sharti } 231144026Sharti 232144026Sharti // the -1 is because we didn't advance them after the final CAS 233144026Sharti assert(from == 234144026Sharti (intptr_t*) from_bitmap->word_addr(from_start_index) + word_num - 1, 235144026Sharti "invariant"); 236144026Sharti assert(to == (intptr_t*) word_addr(to_start_index) + word_num - 1, 237144026Sharti "invariant"); 238145679Sharti} 239145616Sharti 2401590Srgrimesvoid BitMap::at_put(idx_t offset, bool value) { 241145616Sharti if (value) { 2421590Srgrimes set_bit(offset); 243144894Sharti } else { 244150595Sphk clear_bit(offset); 245144894Sharti } 246144894Sharti} 247144894Sharti 248144894Sharti// Return true to indicate that this thread changed 249144894Sharti// the bit, false to indicate that someone else did. 250144894Sharti// In either case, the requested bit is in the 251144894Sharti// requested state some time during the period that 252144894Sharti// this thread is executing this call. More importantly, 253144894Sharti// if no other thread is executing an action to 254144894Sharti// change the requested bit to a state other than 255144894Sharti// the one that this thread is trying to set it to, 256145612Sharti// then the the bit is in the expected state 257144894Sharti// at exit from this method. However, rather than 258144894Sharti// make such a strong assertion here, based on 259144894Sharti// assuming such constrained use (which though true 260144894Sharti// today, could change in the future to service some 261144894Sharti// funky parallel algorithm), we encourage callers 262144894Sharti// to do such verification, as and when appropriate. 263144894Shartibool BitMap::par_at_put(idx_t bit, bool value) { 264144894Sharti return value ? par_set_bit(bit) : par_clear_bit(bit); 265144894Sharti} 266144894Sharti 267144894Shartivoid BitMap::at_put_grow(idx_t offset, bool value) { 268144894Sharti if (offset >= size()) { 269144894Sharti resize(2 * MAX2(size(), offset)); 270144894Sharti } 271144894Sharti at_put(offset, value); 272144894Sharti} 273150595Sphk 274144894Shartivoid BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { 275144894Sharti if (value) { 276145612Sharti set_range(start_offset, end_offset); 277144894Sharti } else { 278144894Sharti clear_range(start_offset, end_offset); 279144894Sharti } 2801590Srgrimes} 281145616Sharti 2821590Srgrimesvoid BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { 2831590Srgrimes verify_range(beg, end); 2841590Srgrimes 285145616Sharti idx_t beg_full_word = word_index_round_up(beg); 2861590Srgrimes idx_t end_full_word = word_index(end); 287145616Sharti 288145616Sharti if (beg_full_word < end_full_word) { 2891590Srgrimes // The range includes at least one full word. 290145616Sharti par_put_range_within_word(beg, bit_index(beg_full_word), value); 2918874Srgrimes if (value) { 292145616Sharti set_range_of_words(beg_full_word, end_full_word); 293145616Sharti } else { 294145616Sharti clear_range_of_words(beg_full_word, end_full_word); 295145616Sharti } 296145616Sharti par_put_range_within_word(bit_index(end_full_word), end, value); 2971590Srgrimes } else { 2981590Srgrimes // The range spans at most 2 partial words. 2991590Srgrimes idx_t boundary = MIN2(bit_index(beg_full_word), end); 3001590Srgrimes par_put_range_within_word(beg, boundary, value); 3011590Srgrimes par_put_range_within_word(boundary, end, value); 3021590Srgrimes } 3031590Srgrimes 3041590Srgrimes} 3051590Srgrimes 3061590Srgrimesvoid BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { 3071590Srgrimes if (value) { 3081590Srgrimes set_large_range(beg, end); 3091590Srgrimes } else { 3101590Srgrimes clear_large_range(beg, end); 3111590Srgrimes } 3121590Srgrimes} 31398136Sjmallett 3141590Srgrimesvoid BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { 3151590Srgrimes verify_range(beg, end); 31693056Simp 3171590Srgrimes idx_t beg_full_word = word_index_round_up(beg); 318144745Sharti idx_t end_full_word = word_index(end); 319144745Sharti 320144745Sharti assert(end_full_word - beg_full_word >= 32, 3211590Srgrimes "the range must include at least 32 bytes"); 322138232Sharti 323138232Sharti // The range includes at least one full word. 3241590Srgrimes par_put_range_within_word(beg, bit_index(beg_full_word), value); 325138232Sharti if (value) { 326138232Sharti set_large_range_of_words(beg_full_word, end_full_word); 3271590Srgrimes } else { 3281590Srgrimes clear_large_range_of_words(beg_full_word, end_full_word); 3291590Srgrimes } 3301590Srgrimes par_put_range_within_word(bit_index(end_full_word), end, value); 331144341Sharti} 332144341Sharti 333144341Shartibool BitMap::contains(const BitMap other) const { 334144341Sharti assert(size() == other.size(), "must have same size"); 335144341Sharti bm_word_t* dest_map = map(); 336144341Sharti bm_word_t* other_map = other.map(); 337144341Sharti idx_t size = size_in_words(); 338144341Sharti for (idx_t index = 0; index < size_in_words(); index++) { 339144341Sharti bm_word_t word_union = dest_map[index] | other_map[index]; 340144341Sharti // If this has more bits set than dest_map[index], then other is not a 341144341Sharti // subset. 342144341Sharti if (word_union != dest_map[index]) return false; 343144341Sharti } 344144341Sharti return true; 345144341Sharti} 346144341Sharti 347144341Shartibool BitMap::intersects(const BitMap other) const { 348144341Sharti assert(size() == other.size(), "must have same size"); 349144341Sharti bm_word_t* dest_map = map(); 350144341Sharti bm_word_t* other_map = other.map(); 351144341Sharti idx_t size = size_in_words(); 352144341Sharti for (idx_t index = 0; index < size_in_words(); index++) { 353144341Sharti if ((dest_map[index] & other_map[index]) != 0) return true; 354144341Sharti } 355144341Sharti // Otherwise, no intersection. 356144341Sharti return false; 357144341Sharti} 358144341Sharti 359144341Shartivoid BitMap::set_union(BitMap other) { 360144341Sharti assert(size() == other.size(), "must have same size"); 361144341Sharti bm_word_t* dest_map = map(); 362144341Sharti bm_word_t* other_map = other.map(); 363144341Sharti idx_t size = size_in_words(); 364144341Sharti for (idx_t index = 0; index < size_in_words(); index++) { 365144341Sharti dest_map[index] = dest_map[index] | other_map[index]; 366144341Sharti } 367144341Sharti} 368144341Sharti 369144341Sharti 370144341Shartivoid BitMap::set_difference(BitMap other) { 371144341Sharti assert(size() == other.size(), "must have same size"); 372144341Sharti bm_word_t* dest_map = map(); 373144341Sharti bm_word_t* other_map = other.map(); 374144341Sharti idx_t size = size_in_words(); 375144341Sharti for (idx_t index = 0; index < size_in_words(); index++) { 376144341Sharti dest_map[index] = dest_map[index] & ~(other_map[index]); 377144341Sharti } 378144341Sharti} 379144341Sharti 380144341Sharti 381144341Shartivoid BitMap::set_intersection(BitMap other) { 382144341Sharti assert(size() == other.size(), "must have same size"); 383144341Sharti bm_word_t* dest_map = map(); 384144341Sharti bm_word_t* other_map = other.map(); 385144341Sharti idx_t size = size_in_words(); 386144341Sharti for (idx_t index = 0; index < size; index++) { 387144341Sharti dest_map[index] = dest_map[index] & other_map[index]; 388144341Sharti } 389144341Sharti} 390144341Sharti 391144341Sharti 392144341Shartivoid BitMap::set_intersection_at_offset(BitMap other, idx_t offset) { 393144341Sharti assert(other.size() >= offset, "offset not in range"); 394144341Sharti assert(other.size() - offset >= size(), "other not large enough"); 395144341Sharti // XXX Ideally, we would remove this restriction. 396144341Sharti guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0, 397144341Sharti "Only handle aligned cases so far."); 398144341Sharti bm_word_t* dest_map = map(); 399144341Sharti bm_word_t* other_map = other.map(); 400144341Sharti idx_t offset_word_ind = word_index(offset); 401144341Sharti idx_t size = size_in_words(); 402144341Sharti for (idx_t index = 0; index < size; index++) { 403144341Sharti dest_map[index] = dest_map[index] & other_map[offset_word_ind + index]; 404144341Sharti } 405144341Sharti} 406145679Sharti 407145679Shartibool BitMap::set_union_with_result(BitMap other) { 408145679Sharti assert(size() == other.size(), "must have same size"); 409145679Sharti bool changed = false; 410145679Sharti bm_word_t* dest_map = map(); 411145679Sharti bm_word_t* other_map = other.map(); 412145679Sharti idx_t size = size_in_words(); 413146345Sharti for (idx_t index = 0; index < size; index++) { 414146345Sharti idx_t temp = map(index) | other_map[index]; 415145679Sharti changed = changed || (temp != map(index)); 416146345Sharti map()[index] = temp; 417145679Sharti } 418146345Sharti return changed; 419146345Sharti} 420145679Sharti 421145679Sharti 4221590Srgrimesbool BitMap::set_difference_with_result(BitMap other) { 4231590Srgrimes assert(size() == other.size(), "must have same size"); 4241590Srgrimes bool changed = false; 425143100Sharti bm_word_t* dest_map = map(); 4261590Srgrimes bm_word_t* other_map = other.map(); 4271590Srgrimes idx_t size = size_in_words(); 4281590Srgrimes for (idx_t index = 0; index < size; index++) { 4291590Srgrimes bm_word_t temp = dest_map[index] & ~(other_map[index]); 430143100Sharti changed = changed || (temp != dest_map[index]); 4311590Srgrimes dest_map[index] = temp; 4321590Srgrimes } 4331590Srgrimes return changed; 4341590Srgrimes} 435143027Sharti 436143027Sharti 4371590Srgrimesbool BitMap::set_intersection_with_result(BitMap other) { 438143027Sharti assert(size() == other.size(), "must have same size"); 439143027Sharti bool changed = false; 440138232Sharti bm_word_t* dest_map = map(); 441143027Sharti bm_word_t* other_map = other.map(); 442143027Sharti idx_t size = size_in_words(); 443143027Sharti for (idx_t index = 0; index < size; index++) { 444143027Sharti bm_word_t orig = dest_map[index]; 445143027Sharti bm_word_t temp = orig & other_map[index]; 446143027Sharti changed = changed || (temp != orig); 447143027Sharti dest_map[index] = temp; 448143027Sharti } 449143027Sharti return changed; 4501590Srgrimes} 4511590Srgrimes 4521590Srgrimes 4531590Srgrimesvoid BitMap::set_from(BitMap other) { 4541590Srgrimes assert(size() == other.size(), "must have same size"); 4551590Srgrimes bm_word_t* dest_map = map(); 456143684Sharti bm_word_t* other_map = other.map(); 457143684Sharti idx_t size = size_in_words(); 458143684Sharti for (idx_t index = 0; index < size; index++) { 459143684Sharti dest_map[index] = other_map[index]; 4601590Srgrimes } 4611590Srgrimes} 4621590Srgrimes 4631590Srgrimes 4641590Srgrimesbool BitMap::is_same(BitMap other) { 4651590Srgrimes assert(size() == other.size(), "must have same size"); 466143684Sharti bm_word_t* dest_map = map(); 467143684Sharti bm_word_t* other_map = other.map(); 4681590Srgrimes idx_t size = size_in_words(); 469143684Sharti for (idx_t index = 0; index < size; index++) { 470143684Sharti if (dest_map[index] != other_map[index]) return false; 471143684Sharti } 472138232Sharti return true; 473143684Sharti} 474143684Sharti 4751590Srgrimesbool BitMap::is_full() const { 476143684Sharti bm_word_t* word = map(); 477143684Sharti idx_t rest = size(); 478143684Sharti for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 479143684Sharti if (*word != (bm_word_t) AllBits) return false; 480143684Sharti word++; 481143684Sharti } 482143684Sharti return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits; 483143684Sharti} 484143684Sharti 485143684Sharti 486143684Shartibool BitMap::is_empty() const { 487143684Sharti bm_word_t* word = map(); 4888874Srgrimes idx_t rest = size(); 489143684Sharti for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 490143684Sharti if (*word != (bm_word_t) NoBits) return false; 491143684Sharti word++; 492143684Sharti } 493143684Sharti return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits; 494143684Sharti} 495143684Sharti 496143684Shartivoid BitMap::clear_large() { 497143684Sharti clear_large_range_of_words(0, size_in_words()); 498143684Sharti} 499143684Sharti 500143684Sharti// Note that if the closure itself modifies the bitmap 5011590Srgrimes// then modifications in and to the left of the _bit_ being 502143684Sharti// currently sampled will not be seen. Note also that the 503143684Sharti// interval [leftOffset, rightOffset) is right open. 504143684Shartibool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { 505143684Sharti verify_range(leftOffset, rightOffset); 506143684Sharti 507143684Sharti idx_t startIndex = word_index(leftOffset); 508143684Sharti idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); 509143684Sharti for (idx_t index = startIndex, offset = leftOffset; 510143684Sharti offset < rightOffset && index < endIndex; 511143684Sharti offset = (++index) << LogBitsPerWord) { 512143684Sharti idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); 513143684Sharti for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) { 5141590Srgrimes if (rest & 1) { 515143684Sharti if (!blk->do_bit(offset)) return false; 516143684Sharti // resample at each closure application 517143684Sharti // (see, for instance, CMS bug 4525989) 518143684Sharti rest = map(index) >> (offset & (BitsPerWord -1)); 519143684Sharti } 520143684Sharti rest = rest >> 1; 521143684Sharti } 522143684Sharti } 523143684Sharti return true; 524143684Sharti} 525143684Sharti 526143684ShartiBitMap::idx_t* BitMap::_pop_count_table = NULL; 527143684Sharti 5281590Srgrimesvoid BitMap::init_pop_count_table() { 5291590Srgrimes if (_pop_count_table == NULL) { 5301590Srgrimes BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256); 5311590Srgrimes for (uint i = 0; i < 256; i++) { 5321590Srgrimes table[i] = num_set_bits(i); 5331590Srgrimes } 5341590Srgrimes 5351590Srgrimes intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table, 5361590Srgrimes (intptr_t*) &_pop_count_table, 5371590Srgrimes (intptr_t) NULL_WORD); 5381590Srgrimes if (res != NULL_WORD) { 5391590Srgrimes guarantee( _pop_count_table == (void*) res, "invariant" ); 5401590Srgrimes FREE_C_HEAP_ARRAY(bm_word_t, table); 5411590Srgrimes } 5421590Srgrimes } 5431590Srgrimes} 5441590Srgrimes 5451590SrgrimesBitMap::idx_t BitMap::num_set_bits(bm_word_t w) { 5461590Srgrimes idx_t bits = 0; 5471590Srgrimes 548138512Sharti while (w != 0) { 5491590Srgrimes while ((w & 1) == 0) { 550144026Sharti w >>= 1; 551145616Sharti } 5521590Srgrimes bits++; 553145616Sharti w >>= 1; 554145616Sharti } 555145616Sharti return bits; 556145616Sharti} 557144026Sharti 558144026ShartiBitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { 559145616Sharti assert(_pop_count_table != NULL, "precondition"); 560144026Sharti return _pop_count_table[c]; 561144026Sharti} 562144026Sharti 563144026ShartiBitMap::idx_t BitMap::count_one_bits() const { 5641590Srgrimes init_pop_count_table(); // If necessary. 56518730Ssteve idx_t sum = 0; 566144026Sharti typedef unsigned char uchar; 567144026Sharti for (idx_t i = 0; i < size_in_words(); i++) { 568144026Sharti bm_word_t w = map()[i]; 569144026Sharti for (size_t j = 0; j < sizeof(bm_word_t); j++) { 570144026Sharti sum += num_set_bits_from_table(uchar(w & 255)); 571144026Sharti w >>= 8; 572144026Sharti } 573144026Sharti } 574144026Sharti return sum; 575144026Sharti} 576144026Sharti 577144026Sharti 578144026Sharti#ifndef PRODUCT 579144026Sharti 580144026Shartivoid BitMap::print_on(outputStream* st) const { 581144026Sharti tty->print("Bitmap(%d):", size()); 582144026Sharti for (idx_t index = 0; index < size(); index++) { 58318730Ssteve tty->print("%c", at(index) ? '1' : '0'); 584144026Sharti } 585144026Sharti tty->cr(); 586144026Sharti} 587144026Sharti 588144026Sharti#endif 589144026Sharti 590144026Sharti 591144026ShartiBitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot) 592144026Sharti : _bits_per_slot(bits_per_slot) 593144026Sharti , _map(map, size_in_slots * bits_per_slot) 594144026Sharti{ 595144026Sharti} 596144026Sharti 597144026Sharti 598144026ShartiBitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) 599144026Sharti : _bits_per_slot(bits_per_slot) 60018730Ssteve , _map(size_in_slots * bits_per_slot) 601144026Sharti{ 602144026Sharti} 603144026Sharti