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

[Johan Sjölen]

On Mon, 2 Dec 2024 08:51: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 60:
> 
>> 58:     RBNode* _left;
>> 59:     RBNode* _right;
>> 60:     unsigned int _black_height; // MSB encodes Red/Black, 0 - red, 1 - black
> 
> Suggestion: Use explicitly sized type `uint32_t`

If you remove this, move the `color` to the end, after K and V.

> src/hotspot/share/utilities/rbTree.hpp line 61:
> 
>> 59:     RBNode* _left;
>> 60:     RBNode* _right;
>> 61:     Color _color;
> 
> Move to the end, this avoids padding and might save us some memory.

Actually, we could even use the MSB of `_black_height` to encode the red/black-ness of a node. 0 bytes used, then.

> src/hotspot/share/utilities/rbTree.hpp line 79:
> 
>> 77:     #endif // ASSERT
>> 78:       _key = new_key;
>> 79:     }
> 
> Seems unused? Kill it, it's too dangerous to be left alive!

If it's needed, save it for a future PR. We'll take the pain of getting it past reviewers then.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1865723089
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1856625894
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1856626719