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

[Casper Norrbin]

On Tue, 7 Jan 2025 13:07:44 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> 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)

I thought the recursive versions looked neater, but changed them now to the iterative version with pre-sized GAs

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

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