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

[Gerard Ziemski]

On Mon, 20 Jan 2025 15:03:06 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 incrementally with one additional commit since the last revision:
> 
>   const functions

I remember Lois asked, during your presentation at the staff meeting, how to change our existing code to start using your RBTree and your answer was a single line change. Could you please remind me what that line was? I'd like to benchmark the new RBTree using my NMT benchmark to see whether there is any performance difference from Treap.

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

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