RFR: 8304759: Add BitMap iterators [v2]

[Axel Boldt-Christmas]

On Wed, 29 Mar 2023 03:07:21 GMT, Kim Barrett <kbarrett at openjdk.org> wrote:

>> Please review this change which adds iteration over the set bit positions of a
>> BitMap via an iterator object.  This is in addition to the existing iterate()
>> and reverse_iterate() functions that apply a function to the set bit positions.
>> 
>> There are two iterator classes: BitMap::Iterator and BitMap::ReverseIterator.
>> Iteration uses a single, self-contained iterator object, rather than a pair of
>> iterator objects as is done with standard library iterators.  This is because
>> the desired form of iteration over bitmaps doesn't lend itself well to the
>> begin/end pair style.  Typical usage is something like
>> 
>> 
>> for (BitMap::Iterator it{map, beg, end}; !it.is_empty(); it.step()) {
>>   ... use it.index()
>> }
>> 
>> 
>> However, as a syntactic convenience, these iterator classes provide begin()
>> and end() member functions returning objects supporting the requirements for
>> range-based for loops.  By constraining these objects to this usage we can
>> cope with the "iterator pair" requirements.  Usage is something like
>> 
>> 
>> for (BitMap::idx_t index : BitMap::Iterator{map, beg, end}) {
>>   ...
>> }
>> 
>> 
>> Testing:
>> mach5 tier1, which includes running the updated gtests on all Oracle-supported
>> platforms.
>
> Kim Barrett has updated the pull request incrementally with one additional commit since the last revision:
> 
>   better names for step functions

lgtm. 

Just a comment about the comments for `first()`/`last()`

src/hotspot/share/utilities/bitMap.hpp line 420:

> 418:   // Returns the index of the last set bit in the remaining iteration range.
> 419:   // precondition: !is_empty()
> 420:   idx_t last() const;

The comments for `first()` and `last()` are a little misleading. The invariant that the `first()`/`last()` is a set bit is only true for `first()` in the forward iterator and for `last()` in the reverse iterator. 

It seems more like a contract that if you use `first()` then you must have created `IteratorImpl(const BitMap* map, idx_t beg, idx_t end)` with `beg` being a set bit. And if you use `last()` then you must have created it with `end` being a set bit.

-------------

Marked as reviewed by aboldtch (Committer).

PR Review: https://git.openjdk.org/jdk/pull/13184#pullrequestreview-1362629245
PR Review Comment: https://git.openjdk.org/jdk/pull/13184#discussion_r1151641853