RFR: 8345314: Add a red–black tree as a utility data structure [v12]

[Casper Norrbin]

On Thu, 16 Jan 2025 10:26:27 GMT, Axel Boldt-Christmas <aboldtch at openjdk.org> wrote:

>> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   clarified comment
>
> src/hotspot/share/utilities/rbTree.inline.hpp line 444:
> 
>> 442: template <typename K, typename V, typename COMPARATOR, typename ALLOCATOR>
>> 443: template <typename F>
>> 444: inline void RBTree<K, V, COMPARATOR, ALLOCATOR>::visit_range_in_order(const K& from, const K& to, F f) {
> 
> This could be written in terms of `closest_leq` and `closest_gt` and just walk the tree between these nodes, and only do `O(log(n))` `CMP` calls instead of `O(log(n) + log(k))` where `k` is the size of the node range.

I added a `BoundMode` to closest_(leq/gt) to allow for this. Now we use two `closest_gt(INCLUSIVE)` calls (becoming more like closest_geq)

Since the we want to go through the range [from, to}, these additions were needed to guarantee that the start node is found.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920464808