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