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

[Casper Norrbin]

On Thu, 16 Jan 2025 12:02:31 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> src/hotspot/share/utilities/rbTree.hpp line 167:
>> 
>>> 165:   // Removes the given node from the tree.
>>> 166:   // Returns true if the node was successfully removed, false otherwise.
>>> 167:   bool remove(RBNode* node);
>> 
>> I find it confusing that removing a node can fail. It seems to be to handle `nullptr`. I'd rather restrict this and have `bool remove(const K& k)` check the return value of `find_node`.
>
> Wouldn't that require two traversals down the tree? Would a `enum RemovalResult { Removed, NotFound }` be preferred?

`remove(RBNode* node)` doesn't traverse the tree, so it is only ever one traversal. I moved the check to `remove(const K& k)` like you suggested, with an added assumption with a comment and assert that the node has to be valid.

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

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