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