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

[Johan Sjölen]

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.

This LGTM. What testing did you run?

src/hotspot/share/nmt/vmatree.hpp line 196:

> 194: 
> 195: public:
> 196:   using VMARBTree = RBTreeCHeap<position, IntervalChange, PositionComparator, MemTag::mtNMT>;

You should be abl to just write 'mtNMT', same for all other `MemTag::` prefixes.

src/hotspot/share/opto/printinlining.cpp line 90:

> 88: 
> 89:   return node->val();
> 90: }

Could you expand the `auto`s? It should be a code action in VSCode if you use clangd. We tend to only use auto when it's a lambda.

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

Marked as reviewed by jsjolen (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/26655#pullrequestreview-3091786865
PR Review Comment: https://git.openjdk.org/jdk/pull/26655#discussion_r2256636655
PR Review Comment: https://git.openjdk.org/jdk/pull/26655#discussion_r2256634808