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

[Casper Norrbin]

On Thu, 16 Jan 2025 07:41:45 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.hpp line 273:
> 
>> 271:     NONCOPYABLE(IteratorImpl);
>> 272: 
>> 273:     IteratorImpl(const RBTree* tree) : _tree(tree) {
> 
> Given that our tree node have a parent pointer. I wonder why this is implemented with a GrowableArray rather than just keeping track of a node and walking the tree on next / previous. (Are we afraid that the pointer chasing back up the tree will be to costly? It seems very rare that you walk up the tree without also dereferencing the data)
> 
> This would have multiple benefits. We could make it O(1) space rather than O(log(n)).
> I think the biggest benefit is that it can be copy constructible and assignable making it much easier to work with including making it easily adaptable to work like a C++ iterator so that we can have begin() and end(), ranged for loops. Many of the APIs like find, enclosing range, visit etc could be implemented in terms of these, making it less cumbersome to design external algorithms which interacts with the tree rather than having to extend the functionality on the tree directly. It also makes iterators usable while inserting in the tree.
> 
> Johan talk about using a cursor to enable inserts and removals (to for example enable an intrusive node). I think we could also design an API which achieves the same with iterators. 
> ```c++
> auto it = tree.find_leq(key);
> if (cmp(key, *it) != 0) {
>   Node* node = get_intrusive_node(key);
>   tree.insert(it, node);
> } else {
>   Node* node = *it;
>   // Update node inplace or maybe replace it with a new intrusive node.
> }

After some thoughts, I've opted to remove the iterator code in its entirety. This would be replaced by cursors in the intrusive tree. The cursors have the same functionality and are more versatile, so it makes little sense to keep this in.

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

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