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

[Johan Sjölen]

On Tue, 7 Jan 2025 09:41:05 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   renamed coloring functions
>
> src/hotspot/share/utilities/rbTree.inline.hpp line 100:
> 
>> 98:     _right->visit_in_order_inner(f);
>> 99:   }
>> 100: }
> 
> This is basically fine, as stack depth will be at most `2log n`, but is there a reason that you can't use the iterative solution that's present in the Treap? Btw, having this method belonging to RBTree and take a `RBNode*` instead of RBNode allows you to just check if the current root node is null, letting you skip a check.
> 
> Here's `visit_in_order` as an iterative function:
> 
> 
>   template<typename F>
>   void visit_in_order(F f) const {
>     GrowableArrayCHeap<TreapNode*, mtNMT> to_visit;
>     TreapNode* head = _root;
>     while (!to_visit.is_empty() || head != nullptr) {
>       while (head != nullptr) {
>         to_visit.push(head);
>         head = head->left();
>       }
>       head = to_visit.pop();
>       f(head);
>       head = head->right();
>     }
>   }

In fact, you can pre-size the GA such that it starts with a capacity of 2log(n+1)

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

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