1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "memory/resourceArea.hpp"
28 #include "runtime/atomic.hpp"
29 #include "utilities/bitMap.inline.hpp"
30 #include "utilities/copy.hpp"
31 #include "utilities/debug.hpp"
32
33 STATIC_ASSERT(sizeof(BitMap::bm_word_t) == BytesPerWord); // "Implementation assumption."
34
35 typedef BitMap::bm_word_t bm_word_t;
36 typedef BitMap::idx_t idx_t;
37
38 class ResourceBitMapAllocator : StackObj {
39 public:
40 bm_word_t* allocate(idx_t size_in_words) const {
41 return NEW_RESOURCE_ARRAY(bm_word_t, size_in_words);
42 }
43 void free(bm_word_t* map, idx_t size_in_words) const {
44 // Don't free resource allocated arrays.
45 }
46 };
47
48 class CHeapBitMapAllocator : StackObj {
49 MEMFLAGS _flags;
50
51 public:
52 CHeapBitMapAllocator(MEMFLAGS flags) : _flags(flags) {}
53 bm_word_t* allocate(size_t size_in_words) const {
54 return ArrayAllocator<bm_word_t>::allocate(size_in_words, _flags);
55 }
56 void free(bm_word_t* map, idx_t size_in_words) const {
57 ArrayAllocator<bm_word_t>::free(map, size_in_words);
58 }
59 };
60
61 class ArenaBitMapAllocator : StackObj {
62 Arena* _arena;
63
64 public:
65 ArenaBitMapAllocator(Arena* arena) : _arena(arena) {}
66 bm_word_t* allocate(idx_t size_in_words) const {
67 return (bm_word_t*)_arena->Amalloc(size_in_words * BytesPerWord);
68 }
69 void free(bm_word_t* map, idx_t size_in_words) const {
70 // ArenaBitMaps currently don't free memory.
71 }
72 };
73
74 template <class Allocator>
75 BitMap::bm_word_t* BitMap::reallocate(const Allocator& allocator, bm_word_t* old_map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear) {
76 size_t old_size_in_words = calc_size_in_words(old_size_in_bits);
77 size_t new_size_in_words = calc_size_in_words(new_size_in_bits);
78
79 bm_word_t* map = NULL;
80
81 if (new_size_in_words > 0) {
82 map = allocator.allocate(new_size_in_words);
83
84 if (old_map != NULL) {
85 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) map,
86 MIN2(old_size_in_words, new_size_in_words));
87 }
88
89 if (clear && new_size_in_words > old_size_in_words) {
90 clear_range_of_words(map, old_size_in_words, new_size_in_words);
91 }
92 }
93
94 if (old_map != NULL) {
95 allocator.free(old_map, old_size_in_words);
96 }
97
98 return map;
99 }
100
101 template <class Allocator>
102 bm_word_t* BitMap::allocate(const Allocator& allocator, idx_t size_in_bits, bool clear) {
103 // Reuse reallocate to ensure that the new memory is cleared.
104 return reallocate(allocator, NULL, 0, size_in_bits, clear);
105 }
106
107 template <class Allocator>
108 void BitMap::free(const Allocator& allocator, bm_word_t* map, idx_t size_in_bits) {
109 bm_word_t* ret = reallocate(allocator, map, size_in_bits, 0);
110 assert(ret == NULL, "Reallocate shouldn't have allocated");
111 }
112
113 template <class Allocator>
114 void BitMap::resize(const Allocator& allocator, idx_t new_size_in_bits, bool clear) {
115 bm_word_t* new_map = reallocate(allocator, map(), size(), new_size_in_bits, clear);
116
117 update(new_map, new_size_in_bits);
118 }
119
120 template <class Allocator>
121 void BitMap::initialize(const Allocator& allocator, idx_t size_in_bits, bool clear) {
122 assert(map() == NULL, "precondition");
123 assert(size() == 0, "precondition");
124
125 resize(allocator, size_in_bits, clear);
126 }
127
128 template <class Allocator>
129 void BitMap::reinitialize(const Allocator& allocator, idx_t new_size_in_bits, bool clear) {
130 // Remove previous bits - no need to clear
131 resize(allocator, 0, false /* clear */);
132
133 initialize(allocator, new_size_in_bits, clear);
134 }
135
136 ResourceBitMap::ResourceBitMap(idx_t size_in_bits)
137 : BitMap(allocate(ResourceBitMapAllocator(), size_in_bits), size_in_bits) {
138 }
139
140 void ResourceBitMap::resize(idx_t new_size_in_bits) {
141 BitMap::resize(ResourceBitMapAllocator(), new_size_in_bits, true /* clear */);
142 }
143
144 void ResourceBitMap::initialize(idx_t size_in_bits) {
145 BitMap::initialize(ResourceBitMapAllocator(), size_in_bits, true /* clear */);
146 }
147
148 void ResourceBitMap::reinitialize(idx_t size_in_bits) {
149 BitMap::reinitialize(ResourceBitMapAllocator(), size_in_bits, true /* clear */);
150 }
151
152 ArenaBitMap::ArenaBitMap(Arena* arena, idx_t size_in_bits)
153 : BitMap(allocate(ArenaBitMapAllocator(arena), size_in_bits), size_in_bits) {
154 }
155
156 CHeapBitMap::CHeapBitMap(idx_t size_in_bits, MEMFLAGS flags, bool clear)
157 : BitMap(allocate(CHeapBitMapAllocator(flags), size_in_bits, clear), size_in_bits), _flags(flags) {
158 }
159
160 CHeapBitMap::~CHeapBitMap() {
161 free(CHeapBitMapAllocator(_flags), map(), size());
162 }
163
164 void CHeapBitMap::resize(idx_t new_size_in_bits, bool clear) {
165 BitMap::resize(CHeapBitMapAllocator(_flags), new_size_in_bits, clear);
166 }
167
168 void CHeapBitMap::initialize(idx_t size_in_bits, bool clear) {
169 BitMap::initialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
170 }
171
172 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
173 BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
174 }
175
176 #ifdef ASSERT
177 void BitMap::verify_valid_size(idx_t size_in_bits) {
178 assert(size_in_bits <= max_size_in_bits(),
179 "out of bounds: " SIZE_FORMAT, size_in_bits);
180 }
181
182 void BitMap::verify_index(idx_t index) const {
183 assert(index < _size, "BitMap index out of bounds");
184 }
185
186 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
187 assert(beg_index <= end_index, "BitMap range error");
188 // Note that [0,0) and [size,size) are both valid ranges.
189 assert(end_index <= _size, "BitMap range out of bounds");
190 }
191 #endif // #ifdef ASSERT
192
193 void BitMap::pretouch() {
194 os::pretouch_memory(word_addr(0), word_addr(size()));
195 }
196
197 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
198 // With a valid range (beg <= end), this test ensures that end != 0, as
199 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
200 if (beg != end) {
201 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
202 *word_addr(beg) |= ~mask;
203 }
204 }
205
206 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
207 // With a valid range (beg <= end), this test ensures that end != 0, as
208 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
209 if (beg != end) {
210 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
211 *word_addr(beg) &= mask;
212 }
213 }
214
215 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
216 assert(value == 0 || value == 1, "0 for clear, 1 for set");
217 // With a valid range (beg <= end), this test ensures that end != 0, as
218 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
219 if (beg != end) {
220 bm_word_t* pw = word_addr(beg);
221 bm_word_t w = *pw;
222 bm_word_t mr = inverted_bit_mask_for_range(beg, end);
223 bm_word_t nw = value ? (w | ~mr) : (w & mr);
224 while (true) {
225 bm_word_t res = Atomic::cmpxchg(nw, pw, w);
226 if (res == w) break;
227 w = res;
228 nw = value ? (w | ~mr) : (w & mr);
229 }
230 }
231 }
232
233 void BitMap::set_range(idx_t beg, idx_t end) {
234 verify_range(beg, end);
235
236 idx_t beg_aligned = range_begin_align_up(beg);
237 idx_t end_aligned = range_end_align_down(end);
238
239 if (beg_aligned < end_aligned) {
240 // The range includes at least one full word.
241 set_range_within_word(beg, beg_aligned);
242 set_range_of_words(word_index(beg_aligned), word_index(end_aligned));
243 set_range_within_word(end_aligned, end);
244 } else {
245 // The range spans at most 2 partial words.
246 idx_t boundary = MIN2(beg_aligned, end);
247 set_range_within_word(beg, boundary);
248 set_range_within_word(boundary, end);
249 }
250 }
251
252 void BitMap::clear_range(idx_t beg, idx_t end) {
253 verify_range(beg, end);
254
255 idx_t beg_aligned = range_begin_align_up(beg);
256 idx_t end_aligned = range_end_align_down(end);
257
258 if (beg_aligned < end_aligned) {
259 // The range includes at least one full word.
260 clear_range_within_word(beg, beg_aligned);
261 clear_range_of_words(word_index(beg_aligned), word_index(end_aligned));
262 clear_range_within_word(end_aligned, end);
263 } else {
264 // The range spans at most 2 partial words.
265 idx_t boundary = MIN2(beg_aligned, end);
266 clear_range_within_word(beg, boundary);
267 clear_range_within_word(boundary, end);
268 }
269 }
270
271 bool BitMap::is_small_aligned_range(idx_t beg_aligned, idx_t end_aligned) {
272 // There is little point to call large version on small ranges.
273 // Need to check carefully, keeping potential idx_t over/underflow in mind,
274 // because beg_aligned > end_aligned can occur when beg and end are in the
275 // same word.
276 // The threshold should be at least one word.
277 STATIC_ASSERT(small_range_words >= 1);
278 return word_index(beg_aligned) + small_range_words >= word_index(end_aligned);
279 }
280
281 void BitMap::set_large_range(idx_t beg, idx_t end) {
282 verify_range(beg, end);
283
284 idx_t beg_aligned = range_begin_align_up(beg);
285 idx_t end_aligned = range_end_align_down(end);
286
287 if (is_small_aligned_range(beg_aligned, end_aligned)) {
288 set_range(beg, end);
289 return;
290 }
291
292 // The range includes at least one full word.
293 set_range_within_word(beg, beg_aligned);
294 set_large_range_of_words(word_index(beg_aligned), word_index(end_aligned));
295 set_range_within_word(end_aligned, end);
296 }
297
298 void BitMap::clear_large_range(idx_t beg, idx_t end) {
299 verify_range(beg, end);
300
301 idx_t beg_aligned = range_begin_align_up(beg);
302 idx_t end_aligned = range_end_align_down(end);
303
304 if (is_small_aligned_range(beg_aligned, end_aligned)) {
305 clear_range(beg, end);
306 return;
307 }
308
309 // The range includes at least one full word.
310 clear_range_within_word(beg, beg_aligned);
311 clear_large_range_of_words(word_index(beg_aligned), word_index(end_aligned));
312 clear_range_within_word(end_aligned, end);
313 }
314
315 void BitMap::at_put(idx_t offset, bool value) {
316 if (value) {
317 set_bit(offset);
318 } else {
319 clear_bit(offset);
320 }
321 }
322
323 // Return true to indicate that this thread changed
324 // the bit, false to indicate that someone else did.
325 // In either case, the requested bit is in the
326 // requested state some time during the period that
327 // this thread is executing this call. More importantly,
328 // if no other thread is executing an action to
329 // change the requested bit to a state other than
330 // the one that this thread is trying to set it to,
331 // then the the bit is in the expected state
332 // at exit from this method. However, rather than
333 // make such a strong assertion here, based on
334 // assuming such constrained use (which though true
335 // today, could change in the future to service some
336 // funky parallel algorithm), we encourage callers
337 // to do such verification, as and when appropriate.
338 bool BitMap::par_at_put(idx_t bit, bool value) {
339 return value ? par_set_bit(bit) : par_clear_bit(bit);
340 }
341
342 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
343 if (value) {
344 set_range(start_offset, end_offset);
345 } else {
346 clear_range(start_offset, end_offset);
347 }
348 }
349
350 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
351 verify_range(beg, end);
352
353 idx_t beg_aligned = range_begin_align_up(beg);
354 idx_t end_aligned = range_end_align_down(end);
355
356 if (beg_aligned < end_aligned) {
357 // The range includes at least one full word.
358 par_put_range_within_word(beg, beg_aligned, value);
359 idx_t beg_full_word = word_index(beg_aligned);
360 idx_t end_full_word = word_index(end_aligned);
361 if (value) {
362 set_range_of_words(beg_full_word, end_full_word);
363 } else {
364 clear_range_of_words(beg_full_word, end_full_word);
365 }
366 par_put_range_within_word(end_aligned, end, value);
367 } else {
368 // The range spans at most 2 partial words.
369 idx_t boundary = MIN2(beg_aligned, end);
370 par_put_range_within_word(beg, boundary, value);
371 par_put_range_within_word(boundary, end, value);
372 }
373
374 }
375
376 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
377 if (value) {
378 set_large_range(beg, end);
379 } else {
380 clear_large_range(beg, end);
381 }
382 }
383
384 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
385 verify_range(beg, end);
386
387 idx_t beg_aligned = range_begin_align_up(beg);
388 idx_t end_aligned = range_end_align_down(end);
389
390 if (is_small_aligned_range(beg_aligned, end_aligned)) {
391 par_at_put_range(beg, end, value);
392 return;
393 }
394
395 // The range includes at least one full word.
396 par_put_range_within_word(beg, beg_aligned, value);
397 idx_t beg_full_word = word_index(beg_aligned);
398 idx_t end_full_word = word_index(end_aligned);
399 if (value) {
400 set_large_range_of_words(beg_full_word, end_full_word);
401 } else {
402 clear_large_range_of_words(beg_full_word, end_full_word);
403 }
404 par_put_range_within_word(end_aligned, end, value);
405 }
406
407 inline bm_word_t tail_mask(idx_t tail_bits) {
408 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
409 assert(tail_bits < (idx_t)BitsPerWord, "precondition");
410 return (bm_word_t(1) << tail_bits) - 1;
411 }
412
413 // Get the low tail_bits of value, which is the last partial word of a map.
414 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
415 return value & tail_mask(tail_bits);
416 }
417
418 // Compute the new last word of a map with a non-aligned length.
419 // new_value has the new trailing bits of the map in the low tail_bits.
420 // old_value is the last word of the map, including bits beyond the end.
421 // Returns old_value with the low tail_bits replaced by the corresponding
422 // bits in new_value.
423 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
424 bm_word_t old_value,
425 idx_t tail_bits) {
426 bm_word_t mask = tail_mask(tail_bits);
427 return (new_value & mask) | (old_value & ~mask);
428 }
429
430 bool BitMap::contains(const BitMap& other) const {
431 assert(size() == other.size(), "must have same size");
432 const bm_word_t* dest_map = map();
433 const bm_word_t* other_map = other.map();
434 idx_t limit = word_index(size());
435 for (idx_t index = 0; index < limit; ++index) {
436 // false if other bitmap has bits set which are clear in this bitmap.
437 if ((~dest_map[index] & other_map[index]) != 0) return false;
438 }
439 idx_t rest = bit_in_word(size());
440 // true unless there is a partial-word tail in which the other
441 // bitmap has bits set which are clear in this bitmap.
442 return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0;
443 }
444
445 bool BitMap::intersects(const BitMap& other) const {
446 assert(size() == other.size(), "must have same size");
447 const bm_word_t* dest_map = map();
448 const bm_word_t* other_map = other.map();
449 idx_t limit = word_index(size());
450 for (idx_t index = 0; index < limit; ++index) {
451 if ((dest_map[index] & other_map[index]) != 0) return true;
452 }
453 idx_t rest = bit_in_word(size());
454 // false unless there is a partial-word tail with non-empty intersection.
455 return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0;
456 }
457
458 void BitMap::set_union(const BitMap& other) {
459 assert(size() == other.size(), "must have same size");
460 bm_word_t* dest_map = map();
461 const bm_word_t* other_map = other.map();
462 idx_t limit = word_index(size());
463 for (idx_t index = 0; index < limit; ++index) {
464 dest_map[index] |= other_map[index];
465 }
466 idx_t rest = bit_in_word(size());
467 if (rest > 0) {
468 bm_word_t orig = dest_map[limit];
469 dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest);
470 }
471 }
472
473 void BitMap::set_difference(const BitMap& other) {
474 assert(size() == other.size(), "must have same size");
475 bm_word_t* dest_map = map();
476 const bm_word_t* other_map = other.map();
477 idx_t limit = word_index(size());
478 for (idx_t index = 0; index < limit; ++index) {
479 dest_map[index] &= ~other_map[index];
480 }
481 idx_t rest = bit_in_word(size());
482 if (rest > 0) {
483 bm_word_t orig = dest_map[limit];
484 dest_map[limit] = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
485 }
486 }
487
488 void BitMap::set_intersection(const BitMap& other) {
489 assert(size() == other.size(), "must have same size");
490 bm_word_t* dest_map = map();
491 const bm_word_t* other_map = other.map();
492 idx_t limit = word_index(size());
493 for (idx_t index = 0; index < limit; ++index) {
494 dest_map[index] &= other_map[index];
495 }
496 idx_t rest = bit_in_word(size());
497 if (rest > 0) {
498 bm_word_t orig = dest_map[limit];
499 dest_map[limit] = merge_tail_of_map(orig & other_map[limit], orig, rest);
500 }
501 }
502
503 bool BitMap::set_union_with_result(const BitMap& other) {
504 assert(size() == other.size(), "must have same size");
505 bool changed = false;
506 bm_word_t* dest_map = map();
507 const bm_word_t* other_map = other.map();
508 idx_t limit = word_index(size());
509 for (idx_t index = 0; index < limit; ++index) {
510 bm_word_t orig = dest_map[index];
511 bm_word_t temp = orig | other_map[index];
512 changed = changed || (temp != orig);
513 dest_map[index] = temp;
514 }
515 idx_t rest = bit_in_word(size());
516 if (rest > 0) {
517 bm_word_t orig = dest_map[limit];
518 bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest);
519 changed = changed || (temp != orig);
520 dest_map[limit] = temp;
521 }
522 return changed;
523 }
524
525 bool BitMap::set_difference_with_result(const BitMap& other) {
526 assert(size() == other.size(), "must have same size");
527 bool changed = false;
528 bm_word_t* dest_map = map();
529 const bm_word_t* other_map = other.map();
530 idx_t limit = word_index(size());
531 for (idx_t index = 0; index < limit; ++index) {
532 bm_word_t orig = dest_map[index];
533 bm_word_t temp = orig & ~other_map[index];
534 changed = changed || (temp != orig);
535 dest_map[index] = temp;
536 }
537 idx_t rest = bit_in_word(size());
538 if (rest > 0) {
539 bm_word_t orig = dest_map[limit];
540 bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
541 changed = changed || (temp != orig);
542 dest_map[limit] = temp;
543 }
544 return changed;
545 }
546
547 bool BitMap::set_intersection_with_result(const BitMap& other) {
548 assert(size() == other.size(), "must have same size");
549 bool changed = false;
550 bm_word_t* dest_map = map();
551 const bm_word_t* other_map = other.map();
552 idx_t limit = word_index(size());
553 for (idx_t index = 0; index < limit; ++index) {
554 bm_word_t orig = dest_map[index];
555 bm_word_t temp = orig & other_map[index];
556 changed = changed || (temp != orig);
557 dest_map[index] = temp;
558 }
559 idx_t rest = bit_in_word(size());
560 if (rest > 0) {
561 bm_word_t orig = dest_map[limit];
562 bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest);
563 changed = changed || (temp != orig);
564 dest_map[limit] = temp;
565 }
566 return changed;
567 }
568
569 void BitMap::set_from(const BitMap& other) {
570 assert(size() == other.size(), "must have same size");
571 bm_word_t* dest_map = map();
572 const bm_word_t* other_map = other.map();
573 idx_t copy_words = word_index(size());
574 Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
575 idx_t rest = bit_in_word(size());
576 if (rest > 0) {
577 dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
578 dest_map[copy_words],
579 rest);
580 }
581 }
582
583 bool BitMap::is_same(const BitMap& other) const {
584 assert(size() == other.size(), "must have same size");
585 const bm_word_t* dest_map = map();
586 const bm_word_t* other_map = other.map();
587 idx_t limit = word_index(size());
588 for (idx_t index = 0; index < limit; ++index) {
589 if (dest_map[index] != other_map[index]) return false;
590 }
591 idx_t rest = bit_in_word(size());
592 return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
593 }
594
595 bool BitMap::is_full() const {
596 const bm_word_t* words = map();
597 idx_t limit = word_index(size());
598 for (idx_t index = 0; index < limit; ++index) {
599 if (~words[index] != 0) return false;
600 }
601 idx_t rest = bit_in_word(size());
602 return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
603 }
604
605 bool BitMap::is_empty() const {
606 const bm_word_t* words = map();
607 idx_t limit = word_index(size());
608 for (idx_t index = 0; index < limit; ++index) {
609 if (words[index] != 0) return false;
610 }
611 idx_t rest = bit_in_word(size());
612 return (rest == 0) || (tail_of_map(words[limit], rest) == 0);
613 }
614
615 void BitMap::clear_large() {
616 clear_large_range_of_words(0, size_in_words());
617 }
618
619 // Note that if the closure itself modifies the bitmap
620 // then modifications in and to the left of the _bit_ being
621 // currently sampled will not be seen. Note also that the
622 // interval [leftOffset, rightOffset) is right open.
623 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
624 verify_range(leftOffset, rightOffset);
625
626 idx_t startIndex = word_index(leftOffset);
627 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words());
628 for (idx_t index = startIndex, offset = leftOffset;
629 offset < rightOffset && index < endIndex;
630 offset = (++index) << LogBitsPerWord) {
631 idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
632 for (; offset < rightOffset && rest != 0; offset++) {
633 if (rest & 1) {
634 if (!blk->do_bit(offset)) return false;
635 // resample at each closure application
636 // (see, for instance, CMS bug 4525989)
637 rest = map(index) >> (offset & (BitsPerWord -1));
638 }
639 rest = rest >> 1;
640 }
641 }
642 return true;
643 }
644
645 const BitMap::idx_t* BitMap::_pop_count_table = NULL;
646
647 void BitMap::init_pop_count_table() {
648 if (_pop_count_table == NULL) {
649 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal);
650 for (uint i = 0; i < 256; i++) {
651 table[i] = num_set_bits(i);
652 }
653
654 if (!Atomic::replace_if_null(table, &_pop_count_table)) {
655 guarantee(_pop_count_table != NULL, "invariant");
656 FREE_C_HEAP_ARRAY(idx_t, table);
657 }
658 }
659 }
660
661 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) {
662 idx_t bits = 0;
663
664 while (w != 0) {
665 while ((w & 1) == 0) {
666 w >>= 1;
667 }
668 bits++;
669 w >>= 1;
670 }
671 return bits;
672 }
673
674 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) {
675 assert(_pop_count_table != NULL, "precondition");
676 return _pop_count_table[c];
677 }
678
679 BitMap::idx_t BitMap::count_one_bits() const {
680 init_pop_count_table(); // If necessary.
681 idx_t sum = 0;
682 typedef unsigned char uchar;
683 for (idx_t i = 0; i < size_in_words(); i++) {
684 bm_word_t w = map()[i];
685 for (size_t j = 0; j < sizeof(bm_word_t); j++) {
686 sum += num_set_bits_from_table(uchar(w & 255));
687 w >>= 8;
688 }
689 }
690 return sum;
691 }
692
693 void BitMap::print_on_error(outputStream* st, const char* prefix) const {
694 st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")",
695 prefix, p2i(map()), p2i((char*)map() + (size() >> LogBitsPerByte)));
696 }
697
698 void BitMap::write_to(bm_word_t* buffer, size_t buffer_size_in_bytes) const {
699 assert(buffer_size_in_bytes == size_in_bytes(), "must be");
700 memcpy(buffer, _map, size_in_bytes());
701 }
702
703 #ifndef PRODUCT
704
705 void BitMap::print_on(outputStream* st) const {
706 tty->print("Bitmap(" SIZE_FORMAT "):", size());
707 for (idx_t index = 0; index < size(); index++) {
708 tty->print("%c", at(index) ? '1' : '0');
709 }
710 tty->cr();
711 }
712
713 #endif