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_index(idx_t index) const {
178 assert(index < _size, "BitMap index out of bounds");
179 }
180
181 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
182 assert(beg_index <= end_index, "BitMap range error");
183 // Note that [0,0) and [size,size) are both valid ranges.
184 if (end_index != _size) verify_index(end_index);
185 }
186 #endif // #ifdef ASSERT
187
188 void BitMap::pretouch() {
189 os::pretouch_memory(word_addr(0), word_addr(size()));
190 }
191
192 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
193 // With a valid range (beg <= end), this test ensures that end != 0, as
194 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
195 if (beg != end) {
196 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
197 *word_addr(beg) |= ~mask;
198 }
199 }
200
201 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
202 // With a valid range (beg <= end), this test ensures that end != 0, as
203 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
204 if (beg != end) {
211 assert(value == 0 || value == 1, "0 for clear, 1 for set");
212 // With a valid range (beg <= end), this test ensures that end != 0, as
213 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
214 if (beg != end) {
215 bm_word_t* pw = word_addr(beg);
216 bm_word_t w = *pw;
217 bm_word_t mr = inverted_bit_mask_for_range(beg, end);
218 bm_word_t nw = value ? (w | ~mr) : (w & mr);
219 while (true) {
220 bm_word_t res = Atomic::cmpxchg(pw, w, nw);
221 if (res == w) break;
222 w = res;
223 nw = value ? (w | ~mr) : (w & mr);
224 }
225 }
226 }
227
228 void BitMap::set_range(idx_t beg, idx_t end) {
229 verify_range(beg, end);
230
231 idx_t beg_full_word = word_index_round_up(beg);
232 idx_t end_full_word = word_index(end);
233
234 if (beg_full_word < end_full_word) {
235 // The range includes at least one full word.
236 set_range_within_word(beg, bit_index(beg_full_word));
237 set_range_of_words(beg_full_word, end_full_word);
238 set_range_within_word(bit_index(end_full_word), end);
239 } else {
240 // The range spans at most 2 partial words.
241 idx_t boundary = MIN2(bit_index(beg_full_word), end);
242 set_range_within_word(beg, boundary);
243 set_range_within_word(boundary, end);
244 }
245 }
246
247 void BitMap::clear_range(idx_t beg, idx_t end) {
248 verify_range(beg, end);
249
250 idx_t beg_full_word = word_index_round_up(beg);
251 idx_t end_full_word = word_index(end);
252
253 if (beg_full_word < end_full_word) {
254 // The range includes at least one full word.
255 clear_range_within_word(beg, bit_index(beg_full_word));
256 clear_range_of_words(beg_full_word, end_full_word);
257 clear_range_within_word(bit_index(end_full_word), end);
258 } else {
259 // The range spans at most 2 partial words.
260 idx_t boundary = MIN2(bit_index(beg_full_word), end);
261 clear_range_within_word(beg, boundary);
262 clear_range_within_word(boundary, end);
263 }
264 }
265
266 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
267 // There is little point to call large version on small ranges.
268 // Need to check carefully, keeping potential idx_t underflow in mind.
269 // The threshold should be at least one word.
270 STATIC_ASSERT(small_range_words >= 1);
271 return (beg_full_word + small_range_words >= end_full_word);
272 }
273
274 void BitMap::set_large_range(idx_t beg, idx_t end) {
275 verify_range(beg, end);
276
277 idx_t beg_full_word = word_index_round_up(beg);
278 idx_t end_full_word = word_index(end);
279
280 if (is_small_range_of_words(beg_full_word, end_full_word)) {
281 set_range(beg, end);
282 return;
283 }
284
285 // The range includes at least one full word.
286 set_range_within_word(beg, bit_index(beg_full_word));
287 set_large_range_of_words(beg_full_word, end_full_word);
288 set_range_within_word(bit_index(end_full_word), end);
289 }
290
291 void BitMap::clear_large_range(idx_t beg, idx_t end) {
292 verify_range(beg, end);
293
294 idx_t beg_full_word = word_index_round_up(beg);
295 idx_t end_full_word = word_index(end);
296
297 if (is_small_range_of_words(beg_full_word, end_full_word)) {
298 clear_range(beg, end);
299 return;
300 }
301
302 // The range includes at least one full word.
303 clear_range_within_word(beg, bit_index(beg_full_word));
304 clear_large_range_of_words(beg_full_word, end_full_word);
305 clear_range_within_word(bit_index(end_full_word), end);
306 }
307
308 void BitMap::at_put(idx_t offset, bool value) {
309 if (value) {
310 set_bit(offset);
311 } else {
312 clear_bit(offset);
313 }
314 }
315
326 // make such a strong assertion here, based on
327 // assuming such constrained use (which though true
328 // today, could change in the future to service some
329 // funky parallel algorithm), we encourage callers
330 // to do such verification, as and when appropriate.
331 bool BitMap::par_at_put(idx_t bit, bool value) {
332 return value ? par_set_bit(bit) : par_clear_bit(bit);
333 }
334
335 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
336 if (value) {
337 set_range(start_offset, end_offset);
338 } else {
339 clear_range(start_offset, end_offset);
340 }
341 }
342
343 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
344 verify_range(beg, end);
345
346 idx_t beg_full_word = word_index_round_up(beg);
347 idx_t end_full_word = word_index(end);
348
349 if (beg_full_word < end_full_word) {
350 // The range includes at least one full word.
351 par_put_range_within_word(beg, bit_index(beg_full_word), value);
352 if (value) {
353 set_range_of_words(beg_full_word, end_full_word);
354 } else {
355 clear_range_of_words(beg_full_word, end_full_word);
356 }
357 par_put_range_within_word(bit_index(end_full_word), end, value);
358 } else {
359 // The range spans at most 2 partial words.
360 idx_t boundary = MIN2(bit_index(beg_full_word), end);
361 par_put_range_within_word(beg, boundary, value);
362 par_put_range_within_word(boundary, end, value);
363 }
364
365 }
366
367 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
368 if (value) {
369 set_large_range(beg, end);
370 } else {
371 clear_large_range(beg, end);
372 }
373 }
374
375 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
376 verify_range(beg, end);
377
378 idx_t beg_full_word = word_index_round_up(beg);
379 idx_t end_full_word = word_index(end);
380
381 if (is_small_range_of_words(beg_full_word, end_full_word)) {
382 par_at_put_range(beg, end, value);
383 return;
384 }
385
386 // The range includes at least one full word.
387 par_put_range_within_word(beg, bit_index(beg_full_word), value);
388 if (value) {
389 set_large_range_of_words(beg_full_word, end_full_word);
390 } else {
391 clear_large_range_of_words(beg_full_word, end_full_word);
392 }
393 par_put_range_within_word(bit_index(end_full_word), end, value);
394 }
395
396 inline bm_word_t tail_mask(idx_t tail_bits) {
397 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
398 assert(tail_bits < (idx_t)BitsPerWord, "precondition");
399 return (bm_word_t(1) << tail_bits) - 1;
403 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
404 return value & tail_mask(tail_bits);
405 }
406
407 // Compute the new last word of a map with a non-aligned length.
408 // new_value has the new trailing bits of the map in the low tail_bits.
409 // old_value is the last word of the map, including bits beyond the end.
410 // Returns old_value with the low tail_bits replaced by the corresponding
411 // bits in new_value.
412 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
413 bm_word_t old_value,
414 idx_t tail_bits) {
415 bm_word_t mask = tail_mask(tail_bits);
416 return (new_value & mask) | (old_value & ~mask);
417 }
418
419 bool BitMap::contains(const BitMap& other) const {
420 assert(size() == other.size(), "must have same size");
421 const bm_word_t* dest_map = map();
422 const bm_word_t* other_map = other.map();
423 idx_t limit = word_index(size());
424 for (idx_t index = 0; index < limit; ++index) {
425 // false if other bitmap has bits set which are clear in this bitmap.
426 if ((~dest_map[index] & other_map[index]) != 0) return false;
427 }
428 idx_t rest = bit_in_word(size());
429 // true unless there is a partial-word tail in which the other
430 // bitmap has bits set which are clear in this bitmap.
431 return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0;
432 }
433
434 bool BitMap::intersects(const BitMap& other) const {
435 assert(size() == other.size(), "must have same size");
436 const bm_word_t* dest_map = map();
437 const bm_word_t* other_map = other.map();
438 idx_t limit = word_index(size());
439 for (idx_t index = 0; index < limit; ++index) {
440 if ((dest_map[index] & other_map[index]) != 0) return true;
441 }
442 idx_t rest = bit_in_word(size());
443 // false unless there is a partial-word tail with non-empty intersection.
444 return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0;
445 }
446
447 void BitMap::set_union(const BitMap& other) {
448 assert(size() == other.size(), "must have same size");
449 bm_word_t* dest_map = map();
450 const bm_word_t* other_map = other.map();
451 idx_t limit = word_index(size());
452 for (idx_t index = 0; index < limit; ++index) {
453 dest_map[index] |= other_map[index];
454 }
455 idx_t rest = bit_in_word(size());
456 if (rest > 0) {
457 bm_word_t orig = dest_map[limit];
458 dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest);
459 }
460 }
461
462 void BitMap::set_difference(const BitMap& other) {
463 assert(size() == other.size(), "must have same size");
464 bm_word_t* dest_map = map();
465 const bm_word_t* other_map = other.map();
466 idx_t limit = word_index(size());
467 for (idx_t index = 0; index < limit; ++index) {
468 dest_map[index] &= ~other_map[index];
469 }
470 idx_t rest = bit_in_word(size());
471 if (rest > 0) {
472 bm_word_t orig = dest_map[limit];
473 dest_map[limit] = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
474 }
475 }
476
477 void BitMap::set_intersection(const BitMap& other) {
478 assert(size() == other.size(), "must have same size");
479 bm_word_t* dest_map = map();
480 const bm_word_t* other_map = other.map();
481 idx_t limit = word_index(size());
482 for (idx_t index = 0; index < limit; ++index) {
483 dest_map[index] &= other_map[index];
484 }
485 idx_t rest = bit_in_word(size());
486 if (rest > 0) {
487 bm_word_t orig = dest_map[limit];
488 dest_map[limit] = merge_tail_of_map(orig & other_map[limit], orig, rest);
489 }
490 }
491
492 bool BitMap::set_union_with_result(const BitMap& other) {
493 assert(size() == other.size(), "must have same size");
494 bool changed = false;
495 bm_word_t* dest_map = map();
496 const bm_word_t* other_map = other.map();
497 idx_t limit = word_index(size());
498 for (idx_t index = 0; index < limit; ++index) {
499 bm_word_t orig = dest_map[index];
500 bm_word_t temp = orig | other_map[index];
501 changed = changed || (temp != orig);
502 dest_map[index] = temp;
503 }
504 idx_t rest = bit_in_word(size());
505 if (rest > 0) {
506 bm_word_t orig = dest_map[limit];
507 bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest);
508 changed = changed || (temp != orig);
509 dest_map[limit] = temp;
510 }
511 return changed;
512 }
513
514 bool BitMap::set_difference_with_result(const BitMap& other) {
515 assert(size() == other.size(), "must have same size");
516 bool changed = false;
517 bm_word_t* dest_map = map();
518 const bm_word_t* other_map = other.map();
519 idx_t limit = word_index(size());
520 for (idx_t index = 0; index < limit; ++index) {
521 bm_word_t orig = dest_map[index];
522 bm_word_t temp = orig & ~other_map[index];
523 changed = changed || (temp != orig);
524 dest_map[index] = temp;
525 }
526 idx_t rest = bit_in_word(size());
527 if (rest > 0) {
528 bm_word_t orig = dest_map[limit];
529 bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
530 changed = changed || (temp != orig);
531 dest_map[limit] = temp;
532 }
533 return changed;
534 }
535
536 bool BitMap::set_intersection_with_result(const BitMap& other) {
537 assert(size() == other.size(), "must have same size");
538 bool changed = false;
539 bm_word_t* dest_map = map();
540 const bm_word_t* other_map = other.map();
541 idx_t limit = word_index(size());
542 for (idx_t index = 0; index < limit; ++index) {
543 bm_word_t orig = dest_map[index];
544 bm_word_t temp = orig & other_map[index];
545 changed = changed || (temp != orig);
546 dest_map[index] = temp;
547 }
548 idx_t rest = bit_in_word(size());
549 if (rest > 0) {
550 bm_word_t orig = dest_map[limit];
551 bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest);
552 changed = changed || (temp != orig);
553 dest_map[limit] = temp;
554 }
555 return changed;
556 }
557
558 void BitMap::set_from(const BitMap& other) {
559 assert(size() == other.size(), "must have same size");
560 bm_word_t* dest_map = map();
561 const bm_word_t* other_map = other.map();
562 idx_t copy_words = word_index(size());
563 Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
564 idx_t rest = bit_in_word(size());
565 if (rest > 0) {
566 dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
567 dest_map[copy_words],
568 rest);
569 }
570 }
571
572 bool BitMap::is_same(const BitMap& other) const {
573 assert(size() == other.size(), "must have same size");
574 const bm_word_t* dest_map = map();
575 const bm_word_t* other_map = other.map();
576 idx_t limit = word_index(size());
577 for (idx_t index = 0; index < limit; ++index) {
578 if (dest_map[index] != other_map[index]) return false;
579 }
580 idx_t rest = bit_in_word(size());
581 return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
582 }
583
584 bool BitMap::is_full() const {
585 const bm_word_t* words = map();
586 idx_t limit = word_index(size());
587 for (idx_t index = 0; index < limit; ++index) {
588 if (~words[index] != 0) return false;
589 }
590 idx_t rest = bit_in_word(size());
591 return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
592 }
593
594 bool BitMap::is_empty() const {
595 const bm_word_t* words = map();
596 idx_t limit = word_index(size());
597 for (idx_t index = 0; index < limit; ++index) {
598 if (words[index] != 0) return false;
599 }
600 idx_t rest = bit_in_word(size());
601 return (rest == 0) || (tail_of_map(words[limit], rest) == 0);
602 }
603
604 void BitMap::clear_large() {
605 clear_large_range_of_words(0, size_in_words());
606 }
607
608 // Note that if the closure itself modifies the bitmap
609 // then modifications in and to the left of the _bit_ being
610 // currently sampled will not be seen. Note also that the
611 // interval [leftOffset, rightOffset) is right open.
612 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
613 verify_range(leftOffset, rightOffset);
614
615 idx_t startIndex = word_index(leftOffset);
616 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words());
617 for (idx_t index = startIndex, offset = leftOffset;
618 offset < rightOffset && index < endIndex;
619 offset = (++index) << LogBitsPerWord) {
620 idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
621 for (; offset < rightOffset && rest != 0; offset++) {
622 if (rest & 1) {
623 if (!blk->do_bit(offset)) return false;
624 // resample at each closure application
625 // (see, for instance, CMS bug 4525989)
626 rest = map(index) >> (offset & (BitsPerWord -1));
627 }
628 rest = rest >> 1;
629 }
630 }
631 return true;
632 }
633
634 const BitMap::idx_t* BitMap::_pop_count_table = NULL;
635
636 void BitMap::init_pop_count_table() {
|
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_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 bit) const {
183 assert(bit < _size,
184 "BitMap index out of bounds: " SIZE_FORMAT " >= " SIZE_FORMAT,
185 bit, _size);
186 }
187
188 void BitMap::verify_limit(idx_t bit) const {
189 assert(bit <= _size,
190 "BitMap limit out of bounds: " SIZE_FORMAT " > " SIZE_FORMAT,
191 bit, _size);
192 }
193
194 void BitMap::verify_range(idx_t beg, idx_t end) const {
195 assert(beg <= end,
196 "BitMap range error: " SIZE_FORMAT " > " SIZE_FORMAT, beg, end);
197 verify_limit(end);
198 }
199 #endif // #ifdef ASSERT
200
201 void BitMap::pretouch() {
202 os::pretouch_memory(word_addr(0), word_addr(size()));
203 }
204
205 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
206 // With a valid range (beg <= end), this test ensures that end != 0, as
207 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
208 if (beg != end) {
209 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
210 *word_addr(beg) |= ~mask;
211 }
212 }
213
214 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
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) {
224 assert(value == 0 || value == 1, "0 for clear, 1 for set");
225 // With a valid range (beg <= end), this test ensures that end != 0, as
226 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
227 if (beg != end) {
228 bm_word_t* pw = word_addr(beg);
229 bm_word_t w = *pw;
230 bm_word_t mr = inverted_bit_mask_for_range(beg, end);
231 bm_word_t nw = value ? (w | ~mr) : (w & mr);
232 while (true) {
233 bm_word_t res = Atomic::cmpxchg(pw, w, nw);
234 if (res == w) break;
235 w = res;
236 nw = value ? (w | ~mr) : (w & mr);
237 }
238 }
239 }
240
241 void BitMap::set_range(idx_t beg, idx_t end) {
242 verify_range(beg, end);
243
244 idx_t beg_full_word = to_words_align_up(beg);
245 idx_t end_full_word = to_words_align_down(end);
246
247 if (beg_full_word < end_full_word) {
248 // The range includes at least one full word.
249 set_range_within_word(beg, bit_index(beg_full_word));
250 set_range_of_words(beg_full_word, end_full_word);
251 set_range_within_word(bit_index(end_full_word), end);
252 } else {
253 // The range spans at most 2 partial words.
254 idx_t boundary = MIN2(bit_index(beg_full_word), end);
255 set_range_within_word(beg, boundary);
256 set_range_within_word(boundary, end);
257 }
258 }
259
260 void BitMap::clear_range(idx_t beg, idx_t end) {
261 verify_range(beg, end);
262
263 idx_t beg_full_word = to_words_align_up(beg);
264 idx_t end_full_word = to_words_align_down(end);
265
266 if (beg_full_word < end_full_word) {
267 // The range includes at least one full word.
268 clear_range_within_word(beg, bit_index(beg_full_word));
269 clear_range_of_words(beg_full_word, end_full_word);
270 clear_range_within_word(bit_index(end_full_word), end);
271 } else {
272 // The range spans at most 2 partial words.
273 idx_t boundary = MIN2(bit_index(beg_full_word), end);
274 clear_range_within_word(beg, boundary);
275 clear_range_within_word(boundary, end);
276 }
277 }
278
279 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
280 // There is little point to call large version on small ranges.
281 // Need to check carefully, keeping potential idx_t over/underflow in mind,
282 // because beg_full_word > end_full_word can occur when beg and end are in
283 // the same word.
284 // The threshold should be at least one word.
285 STATIC_ASSERT(small_range_words >= 1);
286 return beg_full_word + small_range_words >= end_full_word;
287 }
288
289 void BitMap::set_large_range(idx_t beg, idx_t end) {
290 verify_range(beg, end);
291
292 idx_t beg_full_word = to_words_align_up(beg);
293 idx_t end_full_word = to_words_align_down(end);
294
295 if (is_small_range_of_words(beg_full_word, end_full_word)) {
296 set_range(beg, end);
297 return;
298 }
299
300 // The range includes at least one full word.
301 set_range_within_word(beg, bit_index(beg_full_word));
302 set_large_range_of_words(beg_full_word, end_full_word);
303 set_range_within_word(bit_index(end_full_word), end);
304 }
305
306 void BitMap::clear_large_range(idx_t beg, idx_t end) {
307 verify_range(beg, end);
308
309 idx_t beg_full_word = to_words_align_up(beg);
310 idx_t end_full_word = to_words_align_down(end);
311
312 if (is_small_range_of_words(beg_full_word, end_full_word)) {
313 clear_range(beg, end);
314 return;
315 }
316
317 // The range includes at least one full word.
318 clear_range_within_word(beg, bit_index(beg_full_word));
319 clear_large_range_of_words(beg_full_word, end_full_word);
320 clear_range_within_word(bit_index(end_full_word), end);
321 }
322
323 void BitMap::at_put(idx_t offset, bool value) {
324 if (value) {
325 set_bit(offset);
326 } else {
327 clear_bit(offset);
328 }
329 }
330
341 // make such a strong assertion here, based on
342 // assuming such constrained use (which though true
343 // today, could change in the future to service some
344 // funky parallel algorithm), we encourage callers
345 // to do such verification, as and when appropriate.
346 bool BitMap::par_at_put(idx_t bit, bool value) {
347 return value ? par_set_bit(bit) : par_clear_bit(bit);
348 }
349
350 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
351 if (value) {
352 set_range(start_offset, end_offset);
353 } else {
354 clear_range(start_offset, end_offset);
355 }
356 }
357
358 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
359 verify_range(beg, end);
360
361 idx_t beg_full_word = to_words_align_up(beg);
362 idx_t end_full_word = to_words_align_down(end);
363
364 if (beg_full_word < end_full_word) {
365 // The range includes at least one full word.
366 par_put_range_within_word(beg, bit_index(beg_full_word), value);
367 if (value) {
368 set_range_of_words(beg_full_word, end_full_word);
369 } else {
370 clear_range_of_words(beg_full_word, end_full_word);
371 }
372 par_put_range_within_word(bit_index(end_full_word), end, value);
373 } else {
374 // The range spans at most 2 partial words.
375 idx_t boundary = MIN2(bit_index(beg_full_word), end);
376 par_put_range_within_word(beg, boundary, value);
377 par_put_range_within_word(boundary, end, value);
378 }
379
380 }
381
382 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
383 if (value) {
384 set_large_range(beg, end);
385 } else {
386 clear_large_range(beg, end);
387 }
388 }
389
390 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
391 verify_range(beg, end);
392
393 idx_t beg_full_word = to_words_align_up(beg);
394 idx_t end_full_word = to_words_align_down(end);
395
396 if (is_small_range_of_words(beg_full_word, end_full_word)) {
397 par_at_put_range(beg, end, value);
398 return;
399 }
400
401 // The range includes at least one full word.
402 par_put_range_within_word(beg, bit_index(beg_full_word), value);
403 if (value) {
404 set_large_range_of_words(beg_full_word, end_full_word);
405 } else {
406 clear_large_range_of_words(beg_full_word, end_full_word);
407 }
408 par_put_range_within_word(bit_index(end_full_word), end, value);
409 }
410
411 inline bm_word_t tail_mask(idx_t tail_bits) {
412 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
413 assert(tail_bits < (idx_t)BitsPerWord, "precondition");
414 return (bm_word_t(1) << tail_bits) - 1;
418 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
419 return value & tail_mask(tail_bits);
420 }
421
422 // Compute the new last word of a map with a non-aligned length.
423 // new_value has the new trailing bits of the map in the low tail_bits.
424 // old_value is the last word of the map, including bits beyond the end.
425 // Returns old_value with the low tail_bits replaced by the corresponding
426 // bits in new_value.
427 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
428 bm_word_t old_value,
429 idx_t tail_bits) {
430 bm_word_t mask = tail_mask(tail_bits);
431 return (new_value & mask) | (old_value & ~mask);
432 }
433
434 bool BitMap::contains(const BitMap& other) const {
435 assert(size() == other.size(), "must have same size");
436 const bm_word_t* dest_map = map();
437 const bm_word_t* other_map = other.map();
438 idx_t limit = to_words_align_down(size());
439 for (idx_t index = 0; index < limit; ++index) {
440 // false if other bitmap has bits set which are clear in this bitmap.
441 if ((~dest_map[index] & other_map[index]) != 0) return false;
442 }
443 idx_t rest = bit_in_word(size());
444 // true unless there is a partial-word tail in which the other
445 // bitmap has bits set which are clear in this bitmap.
446 return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0;
447 }
448
449 bool BitMap::intersects(const BitMap& other) const {
450 assert(size() == other.size(), "must have same size");
451 const bm_word_t* dest_map = map();
452 const bm_word_t* other_map = other.map();
453 idx_t limit = to_words_align_down(size());
454 for (idx_t index = 0; index < limit; ++index) {
455 if ((dest_map[index] & other_map[index]) != 0) return true;
456 }
457 idx_t rest = bit_in_word(size());
458 // false unless there is a partial-word tail with non-empty intersection.
459 return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0;
460 }
461
462 void BitMap::set_union(const BitMap& other) {
463 assert(size() == other.size(), "must have same size");
464 bm_word_t* dest_map = map();
465 const bm_word_t* other_map = other.map();
466 idx_t limit = to_words_align_down(size());
467 for (idx_t index = 0; index < limit; ++index) {
468 dest_map[index] |= other_map[index];
469 }
470 idx_t rest = bit_in_word(size());
471 if (rest > 0) {
472 bm_word_t orig = dest_map[limit];
473 dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest);
474 }
475 }
476
477 void BitMap::set_difference(const BitMap& other) {
478 assert(size() == other.size(), "must have same size");
479 bm_word_t* dest_map = map();
480 const bm_word_t* other_map = other.map();
481 idx_t limit = to_words_align_down(size());
482 for (idx_t index = 0; index < limit; ++index) {
483 dest_map[index] &= ~other_map[index];
484 }
485 idx_t rest = bit_in_word(size());
486 if (rest > 0) {
487 bm_word_t orig = dest_map[limit];
488 dest_map[limit] = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
489 }
490 }
491
492 void BitMap::set_intersection(const BitMap& other) {
493 assert(size() == other.size(), "must have same size");
494 bm_word_t* dest_map = map();
495 const bm_word_t* other_map = other.map();
496 idx_t limit = to_words_align_down(size());
497 for (idx_t index = 0; index < limit; ++index) {
498 dest_map[index] &= other_map[index];
499 }
500 idx_t rest = bit_in_word(size());
501 if (rest > 0) {
502 bm_word_t orig = dest_map[limit];
503 dest_map[limit] = merge_tail_of_map(orig & other_map[limit], orig, rest);
504 }
505 }
506
507 bool BitMap::set_union_with_result(const BitMap& other) {
508 assert(size() == other.size(), "must have same size");
509 bool changed = false;
510 bm_word_t* dest_map = map();
511 const bm_word_t* other_map = other.map();
512 idx_t limit = to_words_align_down(size());
513 for (idx_t index = 0; index < limit; ++index) {
514 bm_word_t orig = dest_map[index];
515 bm_word_t temp = orig | other_map[index];
516 changed = changed || (temp != orig);
517 dest_map[index] = temp;
518 }
519 idx_t rest = bit_in_word(size());
520 if (rest > 0) {
521 bm_word_t orig = dest_map[limit];
522 bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest);
523 changed = changed || (temp != orig);
524 dest_map[limit] = temp;
525 }
526 return changed;
527 }
528
529 bool BitMap::set_difference_with_result(const BitMap& other) {
530 assert(size() == other.size(), "must have same size");
531 bool changed = false;
532 bm_word_t* dest_map = map();
533 const bm_word_t* other_map = other.map();
534 idx_t limit = to_words_align_down(size());
535 for (idx_t index = 0; index < limit; ++index) {
536 bm_word_t orig = dest_map[index];
537 bm_word_t temp = orig & ~other_map[index];
538 changed = changed || (temp != orig);
539 dest_map[index] = temp;
540 }
541 idx_t rest = bit_in_word(size());
542 if (rest > 0) {
543 bm_word_t orig = dest_map[limit];
544 bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
545 changed = changed || (temp != orig);
546 dest_map[limit] = temp;
547 }
548 return changed;
549 }
550
551 bool BitMap::set_intersection_with_result(const BitMap& other) {
552 assert(size() == other.size(), "must have same size");
553 bool changed = false;
554 bm_word_t* dest_map = map();
555 const bm_word_t* other_map = other.map();
556 idx_t limit = to_words_align_down(size());
557 for (idx_t index = 0; index < limit; ++index) {
558 bm_word_t orig = dest_map[index];
559 bm_word_t temp = orig & other_map[index];
560 changed = changed || (temp != orig);
561 dest_map[index] = temp;
562 }
563 idx_t rest = bit_in_word(size());
564 if (rest > 0) {
565 bm_word_t orig = dest_map[limit];
566 bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest);
567 changed = changed || (temp != orig);
568 dest_map[limit] = temp;
569 }
570 return changed;
571 }
572
573 void BitMap::set_from(const BitMap& other) {
574 assert(size() == other.size(), "must have same size");
575 bm_word_t* dest_map = map();
576 const bm_word_t* other_map = other.map();
577 idx_t copy_words = to_words_align_down(size());
578 Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
579 idx_t rest = bit_in_word(size());
580 if (rest > 0) {
581 dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
582 dest_map[copy_words],
583 rest);
584 }
585 }
586
587 bool BitMap::is_same(const BitMap& other) const {
588 assert(size() == other.size(), "must have same size");
589 const bm_word_t* dest_map = map();
590 const bm_word_t* other_map = other.map();
591 idx_t limit = to_words_align_down(size());
592 for (idx_t index = 0; index < limit; ++index) {
593 if (dest_map[index] != other_map[index]) return false;
594 }
595 idx_t rest = bit_in_word(size());
596 return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
597 }
598
599 bool BitMap::is_full() const {
600 const bm_word_t* words = map();
601 idx_t limit = to_words_align_down(size());
602 for (idx_t index = 0; index < limit; ++index) {
603 if (~words[index] != 0) return false;
604 }
605 idx_t rest = bit_in_word(size());
606 return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
607 }
608
609 bool BitMap::is_empty() const {
610 const bm_word_t* words = map();
611 idx_t limit = to_words_align_down(size());
612 for (idx_t index = 0; index < limit; ++index) {
613 if (words[index] != 0) return false;
614 }
615 idx_t rest = bit_in_word(size());
616 return (rest == 0) || (tail_of_map(words[limit], rest) == 0);
617 }
618
619 void BitMap::clear_large() {
620 clear_large_range_of_words(0, size_in_words());
621 }
622
623 // Note that if the closure itself modifies the bitmap
624 // then modifications in and to the left of the _bit_ being
625 // currently sampled will not be seen. Note also that the
626 // interval [leftOffset, rightOffset) is right open.
627 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
628 verify_range(leftOffset, rightOffset);
629
630 idx_t startIndex = to_words_align_down(leftOffset);
631 idx_t endIndex = to_words_align_up(rightOffset);
632 for (idx_t index = startIndex, offset = leftOffset;
633 offset < rightOffset && index < endIndex;
634 offset = (++index) << LogBitsPerWord) {
635 idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
636 for (; offset < rightOffset && rest != 0; offset++) {
637 if (rest & 1) {
638 if (!blk->do_bit(offset)) return false;
639 // resample at each closure application
640 // (see, for instance, CMS bug 4525989)
641 rest = map(index) >> (offset & (BitsPerWord -1));
642 }
643 rest = rest >> 1;
644 }
645 }
646 return true;
647 }
648
649 const BitMap::idx_t* BitMap::_pop_count_table = NULL;
650
651 void BitMap::init_pop_count_table() {
|