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

[Gerard Ziemski]

On Fri, 24 Jan 2025 11:21:37 GMT, Casper Norrbin <cnorrbin 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.
>
> Casper Norrbin has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 34 commits:
> 
>  - readd find_enclosing_range
>  - Merge branch 'master' into rb-tree
>  - treap swap fix
>  - const functions
>  - thomas feedback
>  - axel feedback
>  - clarified comment
>  - Improved comments
>  - chaged assert to EXPECTs in node tests
>  - additonal node stability test
>  - ... and 24 more: https://git.openjdk.org/jdk/compare/0fbf10a9...aa0d1ee0

>From the point of view of my benchmark, using data recorded from a java server with 10k accesses, the performance looks identical. I ran benchmark 100 times for each and chose the fastest run:

`time:194,279[ns] [samples:1,803]` vs `time:194,516[ns] [samples:1,803]`

No recursion and deterministic behavior (no dependency on 64bit random), however, in my opinion gives RBTree an advantage over Treaps. Good job!

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

PR Comment: https://git.openjdk.org/jdk/pull/22360#issuecomment-2612923335