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

[Johan Sjölen]

On Thu, 9 Jan 2025 13:05:09 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

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

Good point, thanks!

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

Oh right, could've found that out if I read the definition of `is_black`, thanks!

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

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