src/share/vm/utilities/bitMap.cpp

@@ -610,5 +610,89 @@
 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;
+  }
+}