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