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

[Albert Mingkun Yang]

On Wed, 6 Aug 2025 11:07:42 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
>
> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   feedback fixes

Marked as reviewed by ayang (Reviewer).

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

PR Review: https://git.openjdk.org/jdk/pull/26655#pullrequestreview-3105279452