RFR: 8352067: Remove the NMT treap and replace its uses with the utilities red-black tree
Casper Norrbin
cnorrbin at openjdk.org
Wed Aug 6 09:40:16 UTC 2025
Hi everyone,
The utilities red-black tree and the NMT treap serve similar functions. Given the red-black tree's versatility and stricter constraints, 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.
-------------
Commit messages:
- Replace nmttreap with rbtree
Changes: https://git.openjdk.org/jdk/pull/26655/files
Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=26655&range=00
Issue: https://bugs.openjdk.org/browse/JDK-8352067
Stats: 1016 lines in 14 files changed: 124 ins; 816 del; 76 mod
Patch: https://git.openjdk.org/jdk/pull/26655.diff
Fetch: git fetch https://git.openjdk.org/jdk.git pull/26655/head:pull/26655
PR: https://git.openjdk.org/jdk/pull/26655
More information about the hotspot-dev
mailing list