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

[Casper Norrbin]

On Tue, 3 Dec 2024 01:41:15 GMT, David Holmes <dholmes 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 that 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 1:
> 
>> 1: /*
> 
> Just a drive-by comment but why is this all in the hpp file instead of being split into hpp (and maybe .inline.hpp) and cpp files?

The entire tree is templated, so we can't easily move the implementation to a cpp file

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

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