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 }
|
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 uint 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 uint 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 }
|