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

[Casper Norrbin]

On Mon, 25 Nov 2024 13:11:52 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.

This pull request has now been integrated.

Changeset: 2efb6aaa
Author:    Casper Norrbin <cnorrbin at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/2efb6aaadb0df50b5cc4b2495d988802f9dbff50
Stats:     1455 lines in 3 files changed: 1455 ins; 0 del; 0 mod

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

Reviewed-by: aboldtch, jsjolen, stuefe

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

PR: https://git.openjdk.org/jdk/pull/22360