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

[Casper Norrbin]

On Mon, 2 Dec 2024 09:19:55 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Hi everyone,
>> 
>> This effort began as an exploration of replacing the current NMT treap with a red-black tree. Along the way, I discovered that others were also interested in having a general-purpose tree structure available within HotSpot.
>> 
>> The red-black tree is designed to serve as a drop-in replacement for the existing NMT treap, keeping a nearly identical interface. However, I’ve also added a few additional requested features, such as an iterator.
>> 
>> Testing builds off the treap tests, adding a few extra that inserts/removes and checks that the tree is correct. Testing uses the function `verify_self`, which iterates over the tree and checks att all red-black tree properties hold. Additionally, the tree has been tested in vmatree instead of the treap without any errors.
>> 
>> For those who may want to revisit the fundamentals of red-black trees, [Wikipedia](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) offers a great summary with tables covering the various balancing cases. Alternatively, your favorite data structure book could provide even more insight.
>
> src/hotspot/share/utilities/rbTree.hpp line 377:
> 
>> 375:   }
>> 376: 
>> 377:   void remove_inner(RBNode* node) {
> 
> Seems like this function is made to remove nodes whose color is black and whose removal would cause an imbalance. Maybe we can have a better name for this function or documentation, and also a few asserts?

Renamed to `remove_black_leaf()`

> src/hotspot/share/utilities/rbTree.hpp line 381:
> 
>> 379:     RBNode* parent = node->_parent;
>> 380:     while (parent != nullptr) {
>> 381:       RBNode* sibling = node->is_left_child() ? parent->_right : parent->_left;
> 
> I'm missing why this is guaranteed to not be null

Once we reach here, node is a leaf node and black, which means that a sibling has to exist to not cause a black-violation where the path through the sibling has one less black node.
I added an explaining comment + changed the function name to be clearer.

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

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