src/share/vm/utilities/bitMap.cpp

*** 610,614 ****
--- 610,698 ----
  BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot)
    : _bits_per_slot(bits_per_slot)
    , _map(size_in_slots * bits_per_slot)
  {
  }
+ 
+ // What is the first set bit in a 8 bit integer?
+ const uint8_t BitMapIterator::_first_bit[256] = {
+   8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
+ };
+ 
+ // What is the second set bit in a 8 bit integer?
+ const uint8_t BitMapIterator::_second_bit[256] = {
+   8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1,
+   8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
+   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
+   6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
+   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
+   7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
+   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
+   6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
+   6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
+   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
+ };
+ 
+ BitMapIterator::BitMapIterator(BitMap* bs) {
+   _bs = bs;
+   _current = 0;
+   _value = 0;
+   _last_word = -1;
+   _max_word = _bs->size_in_words();
+ }
+ 
+ BitMap::idx_t BitMapIterator::next() {
+   bm_word_t current = _current;
+   if (current != 0) {
+     idx_t value = _value;
+     bm_word_t masked = mask_bits(current,window_mask);
+     while (masked == 0) {
+       current >>= window_size;
+       value += window_size;
+       masked = mask_bits(current,window_mask);
+     }
+ 
+     uint advance = _second_bit[masked];
+     _current = current >> advance;
+     _value = value + advance;
+ 
+     idx_t val = value + _first_bit[masked];
+     assert (val != 0, "can not return zero for existing offset");
+     assert (val < _bs->_size, "returned index is out of bounds");
+     assert (_bs->at(val), "returned index is not found in the map");
+     return val;
+   } else {
+     bm_word_t* map = _bs->_map;
+     for (idx_t i = _last_word + 1; i < _max_word; i++) {
+       bm_word_t w = map[i];
+       if (w != 0) {
+         _current = w;
+         _value = i * BitsPerWord;
+         _last_word = i;
+         return next();
+       };
+     }
+     _last_word = _max_word;
+     return 0;
+   }
+ }