1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/bitMap.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,572 @@
1.4 +/*
1.5 + * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +# include "incls/_precompiled.incl"
1.29 +# include "incls/_bitMap.cpp.incl"
1.30 +
1.31 +
1.32 +BitMap::BitMap(idx_t* map, idx_t size_in_bits) {
1.33 + assert(size_in_bits >= 0, "just checking");
1.34 + _map = map;
1.35 + _size = size_in_bits;
1.36 +}
1.37 +
1.38 +
1.39 +BitMap::BitMap(idx_t size_in_bits) {
1.40 + assert(size_in_bits >= 0, "just checking");
1.41 + _size = size_in_bits;
1.42 + _map = NEW_RESOURCE_ARRAY(idx_t, size_in_words());
1.43 +}
1.44 +
1.45 +
1.46 +void BitMap::resize(idx_t size_in_bits) {
1.47 + assert(size_in_bits >= 0, "just checking");
1.48 + size_t old_size_in_words = size_in_words();
1.49 + uintptr_t* old_map = map();
1.50 + _size = size_in_bits;
1.51 + size_t new_size_in_words = size_in_words();
1.52 + _map = NEW_RESOURCE_ARRAY(idx_t, new_size_in_words);
1.53 + Copy::disjoint_words((HeapWord*) old_map, (HeapWord*) _map, MIN2(old_size_in_words, new_size_in_words));
1.54 + if (new_size_in_words > old_size_in_words) {
1.55 + clear_range_of_words(old_size_in_words, size_in_words());
1.56 + }
1.57 +}
1.58 +
1.59 +// Returns a bit mask for a range of bits [beg, end) within a single word. Each
1.60 +// bit in the mask is 0 if the bit is in the range, 1 if not in the range. The
1.61 +// returned mask can be used directly to clear the range, or inverted to set the
1.62 +// range. Note: end must not be 0.
1.63 +inline BitMap::idx_t
1.64 +BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
1.65 + assert(end != 0, "does not work when end == 0");
1.66 + assert(beg == end || word_index(beg) == word_index(end - 1),
1.67 + "must be a single-word range");
1.68 + idx_t mask = bit_mask(beg) - 1; // low (right) bits
1.69 + if (bit_in_word(end) != 0) {
1.70 + mask |= ~(bit_mask(end) - 1); // high (left) bits
1.71 + }
1.72 + return mask;
1.73 +}
1.74 +
1.75 +void BitMap::set_range_within_word(idx_t beg, idx_t end) {
1.76 + // With a valid range (beg <= end), this test ensures that end != 0, as
1.77 + // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
1.78 + if (beg != end) {
1.79 + idx_t mask = inverted_bit_mask_for_range(beg, end);
1.80 + *word_addr(beg) |= ~mask;
1.81 + }
1.82 +}
1.83 +
1.84 +void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
1.85 + // With a valid range (beg <= end), this test ensures that end != 0, as
1.86 + // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
1.87 + if (beg != end) {
1.88 + idx_t mask = inverted_bit_mask_for_range(beg, end);
1.89 + *word_addr(beg) &= mask;
1.90 + }
1.91 +}
1.92 +
1.93 +void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
1.94 + assert(value == 0 || value == 1, "0 for clear, 1 for set");
1.95 + // With a valid range (beg <= end), this test ensures that end != 0, as
1.96 + // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
1.97 + if (beg != end) {
1.98 + intptr_t* pw = (intptr_t*)word_addr(beg);
1.99 + intptr_t w = *pw;
1.100 + intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end);
1.101 + intptr_t nw = value ? (w | ~mr) : (w & mr);
1.102 + while (true) {
1.103 + intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);
1.104 + if (res == w) break;
1.105 + w = *pw;
1.106 + nw = value ? (w | ~mr) : (w & mr);
1.107 + }
1.108 + }
1.109 +}
1.110 +
1.111 +inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
1.112 + memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t));
1.113 +}
1.114 +
1.115 +inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
1.116 + memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t));
1.117 +}
1.118 +
1.119 +inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
1.120 + idx_t bit_rounded_up = bit + (BitsPerWord - 1);
1.121 + // Check for integer arithmetic overflow.
1.122 + return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
1.123 +}
1.124 +
1.125 +void BitMap::set_range(idx_t beg, idx_t end) {
1.126 + verify_range(beg, end);
1.127 +
1.128 + idx_t beg_full_word = word_index_round_up(beg);
1.129 + idx_t end_full_word = word_index(end);
1.130 +
1.131 + if (beg_full_word < end_full_word) {
1.132 + // The range includes at least one full word.
1.133 + set_range_within_word(beg, bit_index(beg_full_word));
1.134 + set_range_of_words(beg_full_word, end_full_word);
1.135 + set_range_within_word(bit_index(end_full_word), end);
1.136 + } else {
1.137 + // The range spans at most 2 partial words.
1.138 + idx_t boundary = MIN2(bit_index(beg_full_word), end);
1.139 + set_range_within_word(beg, boundary);
1.140 + set_range_within_word(boundary, end);
1.141 + }
1.142 +}
1.143 +
1.144 +void BitMap::clear_range(idx_t beg, idx_t end) {
1.145 + verify_range(beg, end);
1.146 +
1.147 + idx_t beg_full_word = word_index_round_up(beg);
1.148 + idx_t end_full_word = word_index(end);
1.149 +
1.150 + if (beg_full_word < end_full_word) {
1.151 + // The range includes at least one full word.
1.152 + clear_range_within_word(beg, bit_index(beg_full_word));
1.153 + clear_range_of_words(beg_full_word, end_full_word);
1.154 + clear_range_within_word(bit_index(end_full_word), end);
1.155 + } else {
1.156 + // The range spans at most 2 partial words.
1.157 + idx_t boundary = MIN2(bit_index(beg_full_word), end);
1.158 + clear_range_within_word(beg, boundary);
1.159 + clear_range_within_word(boundary, end);
1.160 + }
1.161 +}
1.162 +
1.163 +void BitMap::set_large_range(idx_t beg, idx_t end) {
1.164 + verify_range(beg, end);
1.165 +
1.166 + idx_t beg_full_word = word_index_round_up(beg);
1.167 + idx_t end_full_word = word_index(end);
1.168 +
1.169 + assert(end_full_word - beg_full_word >= 32,
1.170 + "the range must include at least 32 bytes");
1.171 +
1.172 + // The range includes at least one full word.
1.173 + set_range_within_word(beg, bit_index(beg_full_word));
1.174 + set_large_range_of_words(beg_full_word, end_full_word);
1.175 + set_range_within_word(bit_index(end_full_word), end);
1.176 +}
1.177 +
1.178 +void BitMap::clear_large_range(idx_t beg, idx_t end) {
1.179 + verify_range(beg, end);
1.180 +
1.181 + idx_t beg_full_word = word_index_round_up(beg);
1.182 + idx_t end_full_word = word_index(end);
1.183 +
1.184 + assert(end_full_word - beg_full_word >= 32,
1.185 + "the range must include at least 32 bytes");
1.186 +
1.187 + // The range includes at least one full word.
1.188 + clear_range_within_word(beg, bit_index(beg_full_word));
1.189 + clear_large_range_of_words(beg_full_word, end_full_word);
1.190 + clear_range_within_word(bit_index(end_full_word), end);
1.191 +}
1.192 +
1.193 +void BitMap::at_put(idx_t offset, bool value) {
1.194 + if (value) {
1.195 + set_bit(offset);
1.196 + } else {
1.197 + clear_bit(offset);
1.198 + }
1.199 +}
1.200 +
1.201 +// Return true to indicate that this thread changed
1.202 +// the bit, false to indicate that someone else did.
1.203 +// In either case, the requested bit is in the
1.204 +// requested state some time during the period that
1.205 +// this thread is executing this call. More importantly,
1.206 +// if no other thread is executing an action to
1.207 +// change the requested bit to a state other than
1.208 +// the one that this thread is trying to set it to,
1.209 +// then the the bit is in the expected state
1.210 +// at exit from this method. However, rather than
1.211 +// make such a strong assertion here, based on
1.212 +// assuming such constrained use (which though true
1.213 +// today, could change in the future to service some
1.214 +// funky parallel algorithm), we encourage callers
1.215 +// to do such verification, as and when appropriate.
1.216 +bool BitMap::par_at_put(idx_t bit, bool value) {
1.217 + return value ? par_set_bit(bit) : par_clear_bit(bit);
1.218 +}
1.219 +
1.220 +void BitMap::at_put_grow(idx_t offset, bool value) {
1.221 + if (offset >= size()) {
1.222 + resize(2 * MAX2(size(), offset));
1.223 + }
1.224 + at_put(offset, value);
1.225 +}
1.226 +
1.227 +void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
1.228 + if (value) {
1.229 + set_range(start_offset, end_offset);
1.230 + } else {
1.231 + clear_range(start_offset, end_offset);
1.232 + }
1.233 +}
1.234 +
1.235 +void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
1.236 + verify_range(beg, end);
1.237 +
1.238 + idx_t beg_full_word = word_index_round_up(beg);
1.239 + idx_t end_full_word = word_index(end);
1.240 +
1.241 + if (beg_full_word < end_full_word) {
1.242 + // The range includes at least one full word.
1.243 + par_put_range_within_word(beg, bit_index(beg_full_word), value);
1.244 + if (value) {
1.245 + set_range_of_words(beg_full_word, end_full_word);
1.246 + } else {
1.247 + clear_range_of_words(beg_full_word, end_full_word);
1.248 + }
1.249 + par_put_range_within_word(bit_index(end_full_word), end, value);
1.250 + } else {
1.251 + // The range spans at most 2 partial words.
1.252 + idx_t boundary = MIN2(bit_index(beg_full_word), end);
1.253 + par_put_range_within_word(beg, boundary, value);
1.254 + par_put_range_within_word(boundary, end, value);
1.255 + }
1.256 +
1.257 +}
1.258 +
1.259 +void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
1.260 + if (value) {
1.261 + set_large_range(beg, end);
1.262 + } else {
1.263 + clear_large_range(beg, end);
1.264 + }
1.265 +}
1.266 +
1.267 +void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
1.268 + verify_range(beg, end);
1.269 +
1.270 + idx_t beg_full_word = word_index_round_up(beg);
1.271 + idx_t end_full_word = word_index(end);
1.272 +
1.273 + assert(end_full_word - beg_full_word >= 32,
1.274 + "the range must include at least 32 bytes");
1.275 +
1.276 + // The range includes at least one full word.
1.277 + par_put_range_within_word(beg, bit_index(beg_full_word), value);
1.278 + if (value) {
1.279 + set_large_range_of_words(beg_full_word, end_full_word);
1.280 + } else {
1.281 + clear_large_range_of_words(beg_full_word, end_full_word);
1.282 + }
1.283 + par_put_range_within_word(bit_index(end_full_word), end, value);
1.284 +}
1.285 +
1.286 +bool BitMap::contains(const BitMap other) const {
1.287 + assert(size() == other.size(), "must have same size");
1.288 + uintptr_t* dest_map = map();
1.289 + uintptr_t* other_map = other.map();
1.290 + idx_t size = size_in_words();
1.291 + for (idx_t index = 0; index < size_in_words(); index++) {
1.292 + uintptr_t word_union = dest_map[index] | other_map[index];
1.293 + // If this has more bits set than dest_map[index], then other is not a
1.294 + // subset.
1.295 + if (word_union != dest_map[index]) return false;
1.296 + }
1.297 + return true;
1.298 +}
1.299 +
1.300 +bool BitMap::intersects(const BitMap other) const {
1.301 + assert(size() == other.size(), "must have same size");
1.302 + uintptr_t* dest_map = map();
1.303 + uintptr_t* other_map = other.map();
1.304 + idx_t size = size_in_words();
1.305 + for (idx_t index = 0; index < size_in_words(); index++) {
1.306 + if ((dest_map[index] & other_map[index]) != 0) return true;
1.307 + }
1.308 + // Otherwise, no intersection.
1.309 + return false;
1.310 +}
1.311 +
1.312 +void BitMap::set_union(BitMap other) {
1.313 + assert(size() == other.size(), "must have same size");
1.314 + idx_t* dest_map = map();
1.315 + idx_t* other_map = other.map();
1.316 + idx_t size = size_in_words();
1.317 + for (idx_t index = 0; index < size_in_words(); index++) {
1.318 + dest_map[index] = dest_map[index] | other_map[index];
1.319 + }
1.320 +}
1.321 +
1.322 +
1.323 +void BitMap::set_difference(BitMap other) {
1.324 + assert(size() == other.size(), "must have same size");
1.325 + idx_t* dest_map = map();
1.326 + idx_t* other_map = other.map();
1.327 + idx_t size = size_in_words();
1.328 + for (idx_t index = 0; index < size_in_words(); index++) {
1.329 + dest_map[index] = dest_map[index] & ~(other_map[index]);
1.330 + }
1.331 +}
1.332 +
1.333 +
1.334 +void BitMap::set_intersection(BitMap other) {
1.335 + assert(size() == other.size(), "must have same size");
1.336 + idx_t* dest_map = map();
1.337 + idx_t* other_map = other.map();
1.338 + idx_t size = size_in_words();
1.339 + for (idx_t index = 0; index < size; index++) {
1.340 + dest_map[index] = dest_map[index] & other_map[index];
1.341 + }
1.342 +}
1.343 +
1.344 +
1.345 +bool BitMap::set_union_with_result(BitMap other) {
1.346 + assert(size() == other.size(), "must have same size");
1.347 + bool changed = false;
1.348 + idx_t* dest_map = map();
1.349 + idx_t* other_map = other.map();
1.350 + idx_t size = size_in_words();
1.351 + for (idx_t index = 0; index < size; index++) {
1.352 + idx_t temp = map(index) | other_map[index];
1.353 + changed = changed || (temp != map(index));
1.354 + map()[index] = temp;
1.355 + }
1.356 + return changed;
1.357 +}
1.358 +
1.359 +
1.360 +bool BitMap::set_difference_with_result(BitMap other) {
1.361 + assert(size() == other.size(), "must have same size");
1.362 + bool changed = false;
1.363 + idx_t* dest_map = map();
1.364 + idx_t* other_map = other.map();
1.365 + idx_t size = size_in_words();
1.366 + for (idx_t index = 0; index < size; index++) {
1.367 + idx_t temp = dest_map[index] & ~(other_map[index]);
1.368 + changed = changed || (temp != dest_map[index]);
1.369 + dest_map[index] = temp;
1.370 + }
1.371 + return changed;
1.372 +}
1.373 +
1.374 +
1.375 +bool BitMap::set_intersection_with_result(BitMap other) {
1.376 + assert(size() == other.size(), "must have same size");
1.377 + bool changed = false;
1.378 + idx_t* dest_map = map();
1.379 + idx_t* other_map = other.map();
1.380 + idx_t size = size_in_words();
1.381 + for (idx_t index = 0; index < size; index++) {
1.382 + idx_t orig = dest_map[index];
1.383 + idx_t temp = orig & other_map[index];
1.384 + changed = changed || (temp != orig);
1.385 + dest_map[index] = temp;
1.386 + }
1.387 + return changed;
1.388 +}
1.389 +
1.390 +
1.391 +void BitMap::set_from(BitMap other) {
1.392 + assert(size() == other.size(), "must have same size");
1.393 + idx_t* dest_map = map();
1.394 + idx_t* other_map = other.map();
1.395 + idx_t size = size_in_words();
1.396 + for (idx_t index = 0; index < size; index++) {
1.397 + dest_map[index] = other_map[index];
1.398 + }
1.399 +}
1.400 +
1.401 +
1.402 +bool BitMap::is_same(BitMap other) {
1.403 + assert(size() == other.size(), "must have same size");
1.404 + idx_t* dest_map = map();
1.405 + idx_t* other_map = other.map();
1.406 + idx_t size = size_in_words();
1.407 + for (idx_t index = 0; index < size; index++) {
1.408 + if (dest_map[index] != other_map[index]) return false;
1.409 + }
1.410 + return true;
1.411 +}
1.412 +
1.413 +bool BitMap::is_full() const {
1.414 + uintptr_t* word = map();
1.415 + idx_t rest = size();
1.416 + for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
1.417 + if (*word != (uintptr_t) AllBits) return false;
1.418 + word++;
1.419 + }
1.420 + return rest == 0 || (*word | ~right_n_bits((int)rest)) == (uintptr_t) AllBits;
1.421 +}
1.422 +
1.423 +
1.424 +bool BitMap::is_empty() const {
1.425 + uintptr_t* word = map();
1.426 + idx_t rest = size();
1.427 + for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
1.428 + if (*word != (uintptr_t) NoBits) return false;
1.429 + word++;
1.430 + }
1.431 + return rest == 0 || (*word & right_n_bits((int)rest)) == (uintptr_t) NoBits;
1.432 +}
1.433 +
1.434 +void BitMap::clear_large() {
1.435 + clear_large_range_of_words(0, size_in_words());
1.436 +}
1.437 +
1.438 +// Note that if the closure itself modifies the bitmap
1.439 +// then modifications in and to the left of the _bit_ being
1.440 +// currently sampled will not be seen. Note also that the
1.441 +// interval [leftOffset, rightOffset) is right open.
1.442 +void BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
1.443 + verify_range(leftOffset, rightOffset);
1.444 +
1.445 + idx_t startIndex = word_index(leftOffset);
1.446 + idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words());
1.447 + for (idx_t index = startIndex, offset = leftOffset;
1.448 + offset < rightOffset && index < endIndex;
1.449 + offset = (++index) << LogBitsPerWord) {
1.450 + idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
1.451 + for (; offset < rightOffset && rest != (uintptr_t)NoBits; offset++) {
1.452 + if (rest & 1) {
1.453 + blk->do_bit(offset);
1.454 + // resample at each closure application
1.455 + // (see, for instance, CMS bug 4525989)
1.456 + rest = map(index) >> (offset & (BitsPerWord -1));
1.457 + // XXX debugging: remove
1.458 + // The following assertion assumes that closure application
1.459 + // doesn't clear bits (may not be true in general, e.g. G1).
1.460 + assert(rest & 1,
1.461 + "incorrect shift or closure application can clear bits?");
1.462 + }
1.463 + rest = rest >> 1;
1.464 + }
1.465 + }
1.466 +}
1.467 +
1.468 +BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset,
1.469 + idx_t r_offset) const {
1.470 + assert(l_offset <= size(), "BitMap index out of bounds");
1.471 + assert(r_offset <= size(), "BitMap index out of bounds");
1.472 + assert(l_offset <= r_offset, "l_offset > r_offset ?");
1.473 +
1.474 + if (l_offset == r_offset) {
1.475 + return l_offset;
1.476 + }
1.477 + idx_t index = word_index(l_offset);
1.478 + idx_t r_index = word_index(r_offset-1) + 1;
1.479 + idx_t res_offset = l_offset;
1.480 +
1.481 + // check bits including and to the _left_ of offset's position
1.482 + idx_t pos = bit_in_word(res_offset);
1.483 + idx_t res = map(index) >> pos;
1.484 + if (res != (uintptr_t)NoBits) {
1.485 + // find the position of the 1-bit
1.486 + for (; !(res & 1); res_offset++) {
1.487 + res = res >> 1;
1.488 + }
1.489 + assert(res_offset >= l_offset, "just checking");
1.490 + return MIN2(res_offset, r_offset);
1.491 + }
1.492 + // skip over all word length 0-bit runs
1.493 + for (index++; index < r_index; index++) {
1.494 + res = map(index);
1.495 + if (res != (uintptr_t)NoBits) {
1.496 + // found a 1, return the offset
1.497 + for (res_offset = index << LogBitsPerWord; !(res & 1);
1.498 + res_offset++) {
1.499 + res = res >> 1;
1.500 + }
1.501 + assert(res & 1, "tautology; see loop condition");
1.502 + assert(res_offset >= l_offset, "just checking");
1.503 + return MIN2(res_offset, r_offset);
1.504 + }
1.505 + }
1.506 + return r_offset;
1.507 +}
1.508 +
1.509 +BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset,
1.510 + idx_t r_offset) const {
1.511 + assert(l_offset <= size(), "BitMap index out of bounds");
1.512 + assert(r_offset <= size(), "BitMap index out of bounds");
1.513 + assert(l_offset <= r_offset, "l_offset > r_offset ?");
1.514 +
1.515 + if (l_offset == r_offset) {
1.516 + return l_offset;
1.517 + }
1.518 + idx_t index = word_index(l_offset);
1.519 + idx_t r_index = word_index(r_offset-1) + 1;
1.520 + idx_t res_offset = l_offset;
1.521 +
1.522 + // check bits including and to the _left_ of offset's position
1.523 + idx_t pos = res_offset & (BitsPerWord - 1);
1.524 + idx_t res = (map(index) >> pos) | left_n_bits((int)pos);
1.525 +
1.526 + if (res != (uintptr_t)AllBits) {
1.527 + // find the position of the 0-bit
1.528 + for (; res & 1; res_offset++) {
1.529 + res = res >> 1;
1.530 + }
1.531 + assert(res_offset >= l_offset, "just checking");
1.532 + return MIN2(res_offset, r_offset);
1.533 + }
1.534 + // skip over all word length 1-bit runs
1.535 + for (index++; index < r_index; index++) {
1.536 + res = map(index);
1.537 + if (res != (uintptr_t)AllBits) {
1.538 + // found a 0, return the offset
1.539 + for (res_offset = index << LogBitsPerWord; res & 1;
1.540 + res_offset++) {
1.541 + res = res >> 1;
1.542 + }
1.543 + assert(!(res & 1), "tautology; see loop condition");
1.544 + assert(res_offset >= l_offset, "just checking");
1.545 + return MIN2(res_offset, r_offset);
1.546 + }
1.547 + }
1.548 + return r_offset;
1.549 +}
1.550 +
1.551 +#ifndef PRODUCT
1.552 +
1.553 +void BitMap::print_on(outputStream* st) const {
1.554 + tty->print("Bitmap(%d):", size());
1.555 + for (idx_t index = 0; index < size(); index++) {
1.556 + tty->print("%c", at(index) ? '1' : '0');
1.557 + }
1.558 + tty->cr();
1.559 +}
1.560 +
1.561 +#endif
1.562 +
1.563 +
1.564 +BitMap2D::BitMap2D(uintptr_t* map, idx_t size_in_slots, idx_t bits_per_slot)
1.565 + : _bits_per_slot(bits_per_slot)
1.566 + , _map(map, size_in_slots * bits_per_slot)
1.567 +{
1.568 +}
1.569 +
1.570 +
1.571 +BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot)
1.572 + : _bits_per_slot(bits_per_slot)
1.573 + , _map(size_in_slots * bits_per_slot)
1.574 +{
1.575 +}
