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

[Casper Norrbin]

On Tue, 7 Jan 2025 13:11:06 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 203:
> 
>> 201:       curr = curr->_right;
>> 202:     }
>> 203:   }
> 
> Replace with `find_node` and write `parent` by reading `_parent`?

`find_node` either returns the node matching the key or `nullptr`, where here we go down the tree and stay on the parent if the exact key wasn't found in order to insert below it. This would be lost if using `find_node`

> src/hotspot/share/utilities/rbTree.inline.hpp line 237:
> 
>> 235: 
>> 236:     RBNode* uncle = parent->is_left_child() ? grandparent->_right : grandparent->_left;
>> 237:     if (is_black(uncle)) { // Parent is red, uncle is black
> 
> And uncle has to exist (can't be null) as per some invariant? Add assert.

A NIL node (nullptr) is considered black, so `is_black(nullptr)` is valid and returns true.

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

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