bitMap.cpp revision 8003:9a470350393c
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1997, 2015, Oracle and/or its affiliates. All rights reserved. 31541Srgrimes * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 41541Srgrimes * 51541Srgrimes * This code is free software; you can redistribute it and/or modify it 61541Srgrimes * under the terms of the GNU General Public License version 2 only, as 71541Srgrimes * published by the Free Software Foundation. 81541Srgrimes * 91541Srgrimes * This code is distributed in the hope that it will be useful, but WITHOUT 101541Srgrimes * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 111541Srgrimes * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 121541Srgrimes * version 2 for more details (a copy is included in the LICENSE file that 131541Srgrimes * accompanied this code). 141541Srgrimes * 151541Srgrimes * You should have received a copy of the GNU General Public License version 161541Srgrimes * 2 along with this work; if not, write to the Free Software Foundation, 171541Srgrimes * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 181541Srgrimes * 191541Srgrimes * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 201541Srgrimes * or visit www.oracle.com if you need additional information or have any 211541Srgrimes * questions. 221541Srgrimes * 231541Srgrimes */ 241541Srgrimes 251541Srgrimes#include "precompiled.hpp" 261541Srgrimes#include "memory/allocation.inline.hpp" 271541Srgrimes#include "memory/resourceArea.hpp" 281541Srgrimes#include "runtime/atomic.inline.hpp" 291541Srgrimes#include "utilities/bitMap.inline.hpp" 301541Srgrimes#include "utilities/copy.hpp" 311541Srgrimes 321541SrgrimesBitMap::BitMap(bm_word_t* map, idx_t size_in_bits) : 331541Srgrimes _map(map), _size(size_in_bits), _map_allocator(false) 3444510Swollman{ 351541Srgrimes assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); 361541Srgrimes} 37116182Sobrien 38116182Sobrien 39116182SobrienBitMap::BitMap(idx_t size_in_bits, bool in_resource_area) : 40187664Srwatson _map(NULL), _size(0), _map_allocator(false) 41187664Srwatson{ 421541Srgrimes assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); 431541Srgrimes resize(size_in_bits, in_resource_area); 44177859Sjeff} 4533392Sphk 46127969Scpercivavoid BitMap::resize(idx_t size_in_bits, bool in_resource_area) { 47177859Sjeff idx_t old_size_in_words = size_in_words(); 481541Srgrimes bm_word_t* old_map = map(); 49133229Srwatson 5074914Sjhb _size = size_in_bits; 51177859Sjeff idx_t new_size_in_words = size_in_words(); 5268840Sjhb if (in_resource_area) { 53150188Sjhb _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words); 54187664Srwatson Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map, 55171053Sattilio MIN2(old_size_in_words, new_size_in_words)); 56115810Sphk } else { 57177859Sjeff _map = _map_allocator.reallocate(new_size_in_words); 581541Srgrimes } 59220456Sattilio 60220456Sattilio if (new_size_in_words > old_size_in_words) { 61220456Sattilio clear_range_of_words(old_size_in_words, new_size_in_words); 62220456Sattilio } 63187664Srwatson} 64211616Srpaulo 65187664Srwatsonvoid BitMap::set_range_within_word(idx_t beg, idx_t end) { 66187664Srwatson // With a valid range (beg <= end), this test ensures that end != 0, as 67211616Srpaulo // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 68187664Srwatson if (beg != end) { 69187664Srwatson bm_word_t mask = inverted_bit_mask_for_range(beg, end); 70187664Srwatson *word_addr(beg) |= ~mask; 71115810Sphk } 72115810Sphk} 73115810Sphk 74115810Sphkvoid BitMap::clear_range_within_word(idx_t beg, idx_t end) { 75115810Sphk // With a valid range (beg <= end), this test ensures that end != 0, as 76115810Sphk // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 77173760Sattilio if (beg != end) { 78173760Sattilio bm_word_t mask = inverted_bit_mask_for_range(beg, end); 79173760Sattilio *word_addr(beg) &= mask; 80115810Sphk } 81115810Sphk} 82115810Sphk 8333392Sphkvoid BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { 8433392Sphk assert(value == 0 || value == 1, "0 for clear, 1 for set"); 8533392Sphk // With a valid range (beg <= end), this test ensures that end != 0, as 8633392Sphk // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 87243853Salfred if (beg != end) { 882112Swollman intptr_t* pw = (intptr_t*)word_addr(beg); 89200510Sluigi intptr_t w = *pw; 90220456Sattilio intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end); 91220456Sattilio intptr_t nw = value ? (w | ~mr) : (w & mr); 92220456Sattilio while (true) { 93220456Sattilio intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w); 94220456Sattilio if (res == w) break; 95220456Sattilio w = res; 96220456Sattilio nw = value ? (w | ~mr) : (w & mr); 97220456Sattilio } 98220456Sattilio } 99220456Sattilio} 100220456Sattilio 101220456Sattiliovoid BitMap::set_range(idx_t beg, idx_t end) { 102220456Sattilio verify_range(beg, end); 103220456Sattilio 104220456Sattilio idx_t beg_full_word = word_index_round_up(beg); 105200510Sluigi idx_t end_full_word = word_index(end); 106200510Sluigi 107200510Sluigi if (beg_full_word < end_full_word) { 108200510Sluigi // The range includes at least one full word. 109200510Sluigi set_range_within_word(beg, bit_index(beg_full_word)); 110200510Sluigi set_range_of_words(beg_full_word, end_full_word); 111200510Sluigi set_range_within_word(bit_index(end_full_word), end); 112200510Sluigi } else { 113200510Sluigi // The range spans at most 2 partial words. 114200510Sluigi idx_t boundary = MIN2(bit_index(beg_full_word), end); 115200510Sluigi set_range_within_word(beg, boundary); 116200510Sluigi set_range_within_word(boundary, end); 117200510Sluigi } 118200510Sluigi} 119200510Sluigi 120200510Sluigivoid BitMap::clear_range(idx_t beg, idx_t end) { 121177859Sjeff verify_range(beg, end); 122242402Sattilio 123242402Sattilio idx_t beg_full_word = word_index_round_up(beg); 124177859Sjeff idx_t end_full_word = word_index(end); 125177859Sjeff 126177859Sjeff if (beg_full_word < end_full_word) { 127177859Sjeff // The range includes at least one full word. 128177859Sjeff clear_range_within_word(beg, bit_index(beg_full_word)); 129177859Sjeff clear_range_of_words(beg_full_word, end_full_word); 130200510Sluigi clear_range_within_word(bit_index(end_full_word), end); 131177859Sjeff } else { 132177859Sjeff // The range spans at most 2 partial words. 133177859Sjeff idx_t boundary = MIN2(bit_index(beg_full_word), end); 134212541Smav clear_range_within_word(beg, boundary); 135177859Sjeff clear_range_within_word(boundary, end); 136128024Scperciva } 137177859Sjeff} 138220456Sattilio 139220456Sattiliovoid BitMap::set_large_range(idx_t beg, idx_t end) { 140220456Sattilio verify_range(beg, end); 141220456Sattilio 142220456Sattilio idx_t beg_full_word = word_index_round_up(beg); 143177859Sjeff idx_t end_full_word = word_index(end); 144220456Sattilio 145177859Sjeff assert(end_full_word - beg_full_word >= 32, 146177859Sjeff "the range must include at least 32 bytes"); 147177859Sjeff 148177859Sjeff // The range includes at least one full word. 149177859Sjeff set_range_within_word(beg, bit_index(beg_full_word)); 150177859Sjeff set_large_range_of_words(beg_full_word, end_full_word); 151177859Sjeff set_range_within_word(bit_index(end_full_word), end); 152177859Sjeff} 153177859Sjeff 154220456Sattiliovoid BitMap::clear_large_range(idx_t beg, idx_t end) { 155177859Sjeff verify_range(beg, end); 156177859Sjeff 157212541Smav idx_t beg_full_word = word_index_round_up(beg); 158177859Sjeff idx_t end_full_word = word_index(end); 159227293Sed 160177859Sjeff assert(end_full_word - beg_full_word >= 32, 161139831Scperciva "the range must include at least 32 bytes"); 162177859Sjeff 163177859Sjeff // The range includes at least one full word. 164155957Sjhb clear_range_within_word(beg, bit_index(beg_full_word)); 165177859Sjeff clear_large_range_of_words(beg_full_word, end_full_word); 166127969Scperciva clear_range_within_word(bit_index(end_full_word), end); 167177859Sjeff} 168141428Siedowse 169141428Siedowsevoid BitMap::at_put(idx_t offset, bool value) { 170173760Sattilio if (value) { 171155957Sjhb set_bit(offset); 172173760Sattilio } else { 173177859Sjeff clear_bit(offset); 174155957Sjhb } 175128024Scperciva} 176127969Scperciva 177128024Scperciva// Return true to indicate that this thread changed 1781541Srgrimes// the bit, false to indicate that someone else did. 179220456Sattilio// In either case, the requested bit is in the 180220456Sattilio// requested state some time during the period that 181220456Sattilio// this thread is executing this call. More importantly, 182220456Sattilio// if no other thread is executing an action to 183220456Sattilio// change the requested bit to a state other than 184220456Sattilio// the one that this thread is trying to set it to, 185220456Sattilio// then the the bit is in the expected state 186220456Sattilio// at exit from this method. However, rather than 187220456Sattilio// make such a strong assertion here, based on 188220456Sattilio// assuming such constrained use (which though true 189220456Sattilio// today, could change in the future to service some 190220456Sattilio// funky parallel algorithm), we encourage callers 191220456Sattilio// to do such verification, as and when appropriate. 192220456Sattiliobool BitMap::par_at_put(idx_t bit, bool value) { 193220456Sattilio return value ? par_set_bit(bit) : par_clear_bit(bit); 194220456Sattilio} 195220456Sattilio 196220456Sattiliovoid BitMap::at_put_grow(idx_t offset, bool value) { 197220456Sattilio if (offset >= size()) { 198220456Sattilio resize(2 * MAX2(size(), offset)); 199220456Sattilio } 200220456Sattilio at_put(offset, value); 201220456Sattilio} 202220456Sattilio 203220456Sattiliovoid BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { 204220456Sattilio if (value) { 205220456Sattilio set_range(start_offset, end_offset); 206220456Sattilio } else { 207220456Sattilio clear_range(start_offset, end_offset); 20882127Sdillon } 20982127Sdillon} 21082127Sdillon 21182127Sdillonvoid BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { 21282127Sdillon verify_range(beg, end); 21382127Sdillon 21482127Sdillon idx_t beg_full_word = word_index_round_up(beg); 21582127Sdillon idx_t end_full_word = word_index(end); 216177859Sjeff 217177859Sjeff if (beg_full_word < end_full_word) { 218177859Sjeff // The range includes at least one full word. 219177859Sjeff par_put_range_within_word(beg, bit_index(beg_full_word), value); 22082127Sdillon if (value) { 221243853Salfred set_range_of_words(beg_full_word, end_full_word); 222243853Salfred } else { 22382127Sdillon clear_range_of_words(beg_full_word, end_full_word); 224243853Salfred } 22582127Sdillon par_put_range_within_word(bit_index(end_full_word), end, value); 22682127Sdillon } else { 227177859Sjeff // The range spans at most 2 partial words. 228177859Sjeff idx_t boundary = MIN2(bit_index(beg_full_word), end); 229177859Sjeff par_put_range_within_word(beg, boundary, value); 230177859Sjeff par_put_range_within_word(boundary, end, value); 23182127Sdillon } 23282127Sdillon 23382127Sdillon} 234177859Sjeff 235177859Sjeffvoid BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { 236177859Sjeff if (value) { 237177859Sjeff set_large_range(beg, end); 238177859Sjeff } else { 239177859Sjeff clear_large_range(beg, end); 240177859Sjeff } 241177859Sjeff} 242177859Sjeff 243177859Sjeffvoid BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { 244177859Sjeff verify_range(beg, end); 245220456Sattilio 246177859Sjeff idx_t beg_full_word = word_index_round_up(beg); 247177859Sjeff idx_t end_full_word = word_index(end); 248177859Sjeff 249177859Sjeff assert(end_full_word - beg_full_word >= 32, 250177859Sjeff "the range must include at least 32 bytes"); 251177859Sjeff 252177859Sjeff // The range includes at least one full word. 253177859Sjeff par_put_range_within_word(beg, bit_index(beg_full_word), value); 254177859Sjeff if (value) { 255177859Sjeff set_large_range_of_words(beg_full_word, end_full_word); 256220456Sattilio } else { 25782127Sdillon clear_large_range_of_words(beg_full_word, end_full_word); 258220456Sattilio } 259220456Sattilio par_put_range_within_word(bit_index(end_full_word), end, value); 260220456Sattilio} 261220456Sattilio 262220456Sattiliobool BitMap::contains(const BitMap other) const { 263220456Sattilio assert(size() == other.size(), "must have same size"); 264220456Sattilio bm_word_t* dest_map = map(); 265220456Sattilio bm_word_t* other_map = other.map(); 266220456Sattilio idx_t size = size_in_words(); 267220456Sattilio for (idx_t index = 0; index < size_in_words(); index++) { 268220456Sattilio bm_word_t word_union = dest_map[index] | other_map[index]; 269220456Sattilio // If this has more bits set than dest_map[index], then other is not a 270225057Sattilio // subset. 271225057Sattilio if (word_union != dest_map[index]) return false; 272225057Sattilio } 273225057Sattilio return true; 274225057Sattilio} 275220456Sattilio 276225057Sattiliobool BitMap::intersects(const BitMap other) const { 277220456Sattilio assert(size() == other.size(), "must have same size"); 278220456Sattilio bm_word_t* dest_map = map(); 279220456Sattilio bm_word_t* other_map = other.map(); 280225057Sattilio idx_t size = size_in_words(); 281220456Sattilio for (idx_t index = 0; index < size_in_words(); index++) { 282220456Sattilio if ((dest_map[index] & other_map[index]) != 0) return true; 283220456Sattilio } 284220456Sattilio // Otherwise, no intersection. 285220456Sattilio return false; 286220456Sattilio} 28782127Sdillon 28882127Sdillonvoid BitMap::set_union(BitMap other) { 28982127Sdillon assert(size() == other.size(), "must have same size"); 29082127Sdillon bm_word_t* dest_map = map(); 29182127Sdillon bm_word_t* other_map = other.map(); 29282127Sdillon idx_t size = size_in_words(); 29382127Sdillon for (idx_t index = 0; index < size_in_words(); index++) { 29482127Sdillon dest_map[index] = dest_map[index] | other_map[index]; 29582127Sdillon } 296177859Sjeff} 297177859Sjeff 29882127Sdillon 299177859Sjeffvoid BitMap::set_difference(BitMap other) { 300177859Sjeff assert(size() == other.size(), "must have same size"); 301177859Sjeff bm_word_t* dest_map = map(); 302177859Sjeff bm_word_t* other_map = other.map(); 303177859Sjeff idx_t size = size_in_words(); 304177859Sjeff for (idx_t index = 0; index < size_in_words(); index++) { 305177859Sjeff dest_map[index] = dest_map[index] & ~(other_map[index]); 306177859Sjeff } 307177859Sjeff} 308177859Sjeff 309177859Sjeff 310177859Sjeffvoid BitMap::set_intersection(BitMap other) { 311177859Sjeff assert(size() == other.size(), "must have same size"); 312214746Sjhb bm_word_t* dest_map = map(); 313177859Sjeff bm_word_t* other_map = other.map(); 314177859Sjeff idx_t size = size_in_words(); 315209059Sjhb for (idx_t index = 0; index < size; index++) { 316177859Sjeff dest_map[index] = dest_map[index] & other_map[index]; 317177859Sjeff } 318177859Sjeff} 319177859Sjeff 320177859Sjeff 321177859Sjeffvoid BitMap::set_intersection_at_offset(BitMap other, idx_t offset) { 322177859Sjeff assert(other.size() >= offset, "offset not in range"); 323177859Sjeff assert(other.size() - offset >= size(), "other not large enough"); 324177859Sjeff // XXX Ideally, we would remove this restriction. 325177859Sjeff guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0, 326177859Sjeff "Only handle aligned cases so far."); 32782127Sdillon bm_word_t* dest_map = map(); 328177859Sjeff bm_word_t* other_map = other.map(); 329177859Sjeff idx_t offset_word_ind = word_index(offset); 330177859Sjeff idx_t size = size_in_words(); 331177859Sjeff for (idx_t index = 0; index < size; index++) { 332177859Sjeff dest_map[index] = dest_map[index] & other_map[offset_word_ind + index]; 333177859Sjeff } 334177859Sjeff} 335177859Sjeff 336177859Sjeffbool BitMap::set_union_with_result(BitMap other) { 337180608Sjeff assert(size() == other.size(), "must have same size"); 338180608Sjeff bool changed = false; 339177859Sjeff bm_word_t* dest_map = map(); 340177859Sjeff bm_word_t* other_map = other.map(); 341177859Sjeff idx_t size = size_in_words(); 342177859Sjeff for (idx_t index = 0; index < size; index++) { 343177859Sjeff idx_t temp = dest_map[index] | other_map[index]; 344180608Sjeff changed = changed || (temp != dest_map[index]); 345177859Sjeff dest_map[index] = temp; 346177859Sjeff } 347212541Smav return changed; 348200510Sluigi} 349180608Sjeff 350180608Sjeff 351180608Sjeffbool BitMap::set_difference_with_result(BitMap other) { 352180608Sjeff assert(size() == other.size(), "must have same size"); 353180608Sjeff bool changed = false; 354180608Sjeff bm_word_t* dest_map = map(); 355177859Sjeff bm_word_t* other_map = other.map(); 356177859Sjeff idx_t size = size_in_words(); 357177859Sjeff for (idx_t index = 0; index < size; index++) { 358177859Sjeff bm_word_t temp = dest_map[index] & ~(other_map[index]); 359177859Sjeff changed = changed || (temp != dest_map[index]); 360177859Sjeff dest_map[index] = temp; 361177859Sjeff } 362177859Sjeff return changed; 363177859Sjeff} 364212541Smav 365212603Smav 366212541Smavbool BitMap::set_intersection_with_result(BitMap other) { 367212541Smav assert(size() == other.size(), "must have same size"); 368212541Smav bool changed = false; 369212541Smav bm_word_t* dest_map = map(); 370212541Smav bm_word_t* other_map = other.map(); 371212541Smav idx_t size = size_in_words(); 372212541Smav for (idx_t index = 0; index < size; index++) { 373212541Smav bm_word_t orig = dest_map[index]; 374212541Smav bm_word_t temp = orig & other_map[index]; 375212541Smav changed = changed || (temp != orig); 376212603Smav dest_map[index] = temp; 377212541Smav } 378212541Smav return changed; 379212541Smav} 380214597Smav 381212541Smav 382212541Smavvoid BitMap::set_from(BitMap other) { 383212541Smav assert(size() == other.size(), "must have same size"); 384212541Smav bm_word_t* dest_map = map(); 385212541Smav bm_word_t* other_map = other.map(); 386212541Smav idx_t size = size_in_words(); 387212541Smav for (idx_t index = 0; index < size; index++) { 388212541Smav dest_map[index] = other_map[index]; 389212541Smav } 390212541Smav} 391177859Sjeff 392177859Sjeff 393177859Sjeffbool BitMap::is_same(BitMap other) { 394177859Sjeff assert(size() == other.size(), "must have same size"); 395177859Sjeff bm_word_t* dest_map = map(); 396177859Sjeff bm_word_t* other_map = other.map(); 397177859Sjeff idx_t size = size_in_words(); 398177859Sjeff for (idx_t index = 0; index < size; index++) { 399220456Sattilio if (dest_map[index] != other_map[index]) return false; 400220456Sattilio } 401220456Sattilio return true; 402220456Sattilio} 403220456Sattilio 404220456Sattiliobool BitMap::is_full() const { 405220456Sattilio bm_word_t* word = map(); 406177859Sjeff idx_t rest = size(); 407177859Sjeff for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 408177859Sjeff if (*word != ~(bm_word_t)0) return false; 409177859Sjeff word++; 410177859Sjeff } 41182127Sdillon return rest == 0 || (*word | ~right_n_bits((int)rest)) == ~(bm_word_t)0; 412177859Sjeff} 41382127Sdillon 41482127Sdillon 415220456Sattiliobool BitMap::is_empty() const { 416220456Sattilio bm_word_t* word = map(); 417220456Sattilio idx_t rest = size(); 418220456Sattilio for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 419220456Sattilio if (*word != 0) return false; 420220456Sattilio word++; 421220456Sattilio } 422220456Sattilio return rest == 0 || (*word & right_n_bits((int)rest)) == 0; 423220456Sattilio} 424220456Sattilio 425220456Sattiliovoid BitMap::clear_large() { 426220456Sattilio clear_large_range_of_words(0, size_in_words()); 427220456Sattilio} 428220456Sattilio 429220456Sattilio// Note that if the closure itself modifies the bitmap 430220456Sattilio// then modifications in and to the left of the _bit_ being 431220456Sattilio// currently sampled will not be seen. Note also that the 432220456Sattilio// interval [leftOffset, rightOffset) is right open. 433220456Sattiliobool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { 434220456Sattilio verify_range(leftOffset, rightOffset); 435220456Sattilio 436220456Sattilio idx_t startIndex = word_index(leftOffset); 437220456Sattilio idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); 438234981Skib for (idx_t index = startIndex, offset = leftOffset; 439234981Skib offset < rightOffset && index < endIndex; 440234981Skib offset = (++index) << LogBitsPerWord) { 441234981Skib idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); 442234981Skib for (; offset < rightOffset && rest != 0; offset++) { 443234981Skib if (rest & 1) { 444234981Skib if (!blk->do_bit(offset)) return false; 445234981Skib // resample at each closure application 446234981Skib // (see, for instance, CMS bug 4525989) 447234981Skib rest = map(index) >> (offset & (BitsPerWord -1)); 448234981Skib } 449234981Skib rest = rest >> 1; 450234981Skib } 451234981Skib } 452234981Skib return true; 453234981Skib} 454234981Skib 455234981SkibBitMap::idx_t* BitMap::_pop_count_table = NULL; 456234981Skib 457234981Skibvoid BitMap::init_pop_count_table() { 458234981Skib if (_pop_count_table == NULL) { 459234981Skib BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal); 460234981Skib for (uint i = 0; i < 256; i++) { 461234981Skib table[i] = num_set_bits(i); 462234981Skib } 463234981Skib 464234981Skib intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table, 465234981Skib (intptr_t*) &_pop_count_table, 466234981Skib (intptr_t) NULL_WORD); 467234981Skib if (res != NULL_WORD) { 468234981Skib guarantee( _pop_count_table == (void*) res, "invariant" ); 469234981Skib FREE_C_HEAP_ARRAY(idx_t, table); 470234981Skib } 471234981Skib } 472234981Skib} 473234981Skib 474234981SkibBitMap::idx_t BitMap::num_set_bits(bm_word_t w) { 475234981Skib idx_t bits = 0; 476234981Skib 477234981Skib while (w != 0) { 478234981Skib while ((w & 1) == 0) { 479234981Skib w >>= 1; 480234981Skib } 481234981Skib bits++; 482234981Skib w >>= 1; 483234981Skib } 484234981Skib return bits; 485234981Skib} 486234981Skib 487234981SkibBitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { 488234981Skib assert(_pop_count_table != NULL, "precondition"); 489234981Skib return _pop_count_table[c]; 490234981Skib} 491234981Skib 492234981SkibBitMap::idx_t BitMap::count_one_bits() const { 493234981Skib init_pop_count_table(); // If necessary. 494234981Skib idx_t sum = 0; 495234981Skib typedef unsigned char uchar; 496234981Skib for (idx_t i = 0; i < size_in_words(); i++) { 497234981Skib bm_word_t w = map()[i]; 498234981Skib for (size_t j = 0; j < sizeof(bm_word_t); j++) { 499234981Skib sum += num_set_bits_from_table(uchar(w & 255)); 500234981Skib w >>= 8; 501234981Skib } 502234981Skib } 503234981Skib return sum; 504234981Skib} 505234981Skib 506234981Skibvoid BitMap::print_on_error(outputStream* st, const char* prefix) const { 507234981Skib st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")", 508234981Skib prefix, p2i(map()), p2i((char*)map() + (size() >> LogBitsPerByte))); 509234981Skib} 510234981Skib 511234981Skib#ifndef PRODUCT 512234981Skib 513234981Skibvoid BitMap::print_on(outputStream* st) const { 514234981Skib tty->print("Bitmap(" SIZE_FORMAT "):", size()); 515234981Skib for (idx_t index = 0; index < size(); index++) { 516234981Skib tty->print("%c", at(index) ? '1' : '0'); 517234981Skib } 518234981Skib tty->cr(); 519234981Skib} 520234981Skib 521234981Skibclass TestBitMap : public AllStatic { 522234981Skib const static BitMap::idx_t BITMAP_SIZE = 1024; 523234981Skib static void fillBitMap(BitMap& map) { 524234981Skib map.set_bit(1); 525234981Skib map.set_bit(3); 526234981Skib map.set_bit(17); 527234981Skib map.set_bit(512); 528234981Skib } 529234981Skib 530234981Skib static void testResize(bool in_resource_area) { 531234981Skib { 532234981Skib BitMap map(0, in_resource_area); 533234981Skib map.resize(BITMAP_SIZE, in_resource_area); 534234981Skib fillBitMap(map); 535234981Skib 536234981Skib BitMap map2(BITMAP_SIZE, in_resource_area); 537234981Skib fillBitMap(map2); 538234981Skib assert(map.is_same(map2), "could be"); 539234981Skib } 540234981Skib 541234981Skib { 542234981Skib BitMap map(128, in_resource_area); 543234981Skib map.resize(BITMAP_SIZE, in_resource_area); 544234981Skib fillBitMap(map); 545234981Skib 546234981Skib BitMap map2(BITMAP_SIZE, in_resource_area); 547234981Skib fillBitMap(map2); 548234981Skib assert(map.is_same(map2), "could be"); 549234981Skib } 550234981Skib 551234981Skib { 552234981Skib BitMap map(BITMAP_SIZE, in_resource_area); 553234981Skib map.resize(BITMAP_SIZE, in_resource_area); 554234981Skib fillBitMap(map); 555234981Skib 556234981Skib BitMap map2(BITMAP_SIZE, in_resource_area); 557234981Skib fillBitMap(map2); 558234981Skib assert(map.is_same(map2), "could be"); 559234981Skib } 560234981Skib } 561234981Skib 562234981Skib static void testResizeResource() { 563234981Skib ResourceMark rm; 564234981Skib testResize(true); 565234981Skib } 566234981Skib 567234981Skib static void testResizeNonResource() { 568234981Skib const size_t bitmap_bytes = BITMAP_SIZE / BitsPerByte; 569234981Skib 570234981Skib // Test the default behavior 571234981Skib testResize(false); 572234981Skib 573234981Skib { 574234981Skib // Make sure that AllocatorMallocLimit is larger than our allocation request 575234981Skib // forcing it to call standard malloc() 576234981Skib SizeTFlagSetting fs(ArrayAllocatorMallocLimit, bitmap_bytes * 4); 577234981Skib testResize(false); 578234981Skib } 579234981Skib { 580234981Skib // Make sure that AllocatorMallocLimit is smaller than our allocation request 581234981Skib // forcing it to call mmap() (or equivalent) 582234981Skib SizeTFlagSetting fs(ArrayAllocatorMallocLimit, bitmap_bytes / 4); 583234981Skib testResize(false); 584234981Skib } 585234981Skib } 586234981Skib 587234981Skib public: 588234981Skib static void test() { 589234981Skib testResizeResource(); 590234981Skib testResizeNonResource(); 591234981Skib } 592234981Skib 593234981Skib}; 594234981Skib 595234981Skibvoid TestBitMap_test() { 596234981Skib TestBitMap::test(); 597234981Skib} 598234981Skib#endif 599234981Skib 600234981Skib 601234981SkibBitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot) 602234981Skib : _bits_per_slot(bits_per_slot) 603234981Skib , _map(map, size_in_slots * bits_per_slot) 604234981Skib{ 605234981Skib} 606234981Skib 607234981Skib 608234981SkibBitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) 609234981Skib : _bits_per_slot(bits_per_slot) 610234981Skib , _map(size_in_slots * bits_per_slot) 611234981Skib{ 612234981Skib} 61382127Sdillon