Integrated: 8352067: Remove the NMT treap and replace its uses with the utilities red-black tree

[Casper Norrbin]

On Wed, 6 Aug 2025 09:29:05 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

> Hi everyone,
> 
> The utilities red-black tree and the NMT treap serve similar functions. Given the red-black tree's versatility and stricter time complexity, the treap can be removed in favour of it.
> 
> I made some modifications to the red-black tree to make it compatible with previous treap usages:
> - Updated the `visit_in_order` and `visit_range_in_order` functions to require the supplied callback to return a bool, which allows us to stop traversing early.
> - Improved const-correctness by ensuring that invoking these functions on a const reference provides const pointers to nodes, while non-const references provide mutable pointers. Previously the two functions behaved differently.
> 
> Changes to NMT include:
> - Modified components to align with the updated const-correctness of the red-black tree functions
> - Renamed structures and variables to remove "treap" from their names to reflect the new tree
> 
> The treap was also used in one place in C2. I changed this to use the red-black tree and its cursor interface, which I felt was most fitting for the use case.
> 
> Testing:
> - Oracle tiers 1-3

This pull request has now been integrated.

Changeset: 0ad919c1
Author:    Casper Norrbin <cnorrbin at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/0ad919c1e54895b000b58f6a1b54d79f76970845
Stats:     1016 lines in 14 files changed: 124 ins; 816 del; 76 mod

8352067: Remove the NMT treap and replace its uses with the utilities red-black tree

Reviewed-by: jsjolen, ayang

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

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