RFR: 8366238: Improve RBTree API with stricter comparator semantics and pluggable validation/printing hooks.

[Albert Mingkun Yang]

On Thu, 28 Aug 2025 09:06:26 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

> Hi everyone,
> 
> The current red-black tree can be made safer, and its inspection capabilities improved.
> 
> As briefly discussed in #26904, `COMPARATOR::cmp` could be made clearer and more robust. In particular, its `int` return type invites unsafe `return a ‑ b` arithmetic, and the boolean validation function also named `cmp` is misleading.
> 
> To address this, I’ve introduced the `RBTreeOrdering` enum, inspired by C++20’s `<=>`, which makes incorrect arithmetic impossible. The return type of `COMPARATOR::cmp` is now this enum, forcing users to write an explicit and safe comparison. From the discussion in that PR, I have also renamed the boolean `cmp` to `less`, making its purpose obvious and preventing confusion between the two functions.
> 
> Inspection has also been improved, especially for intrusive trees. Previously, `verify_self` only verified core RB-tree properties, yet intrusive nodes often hold additional data with their own separate invariants. Users had to perform those checks in a second traversal, and if an error occurs `print_on` produced little diagnostic value by only printing node addresses.
> 
> To solve this, the tree now accepts user-supplied verification and printing callables. This lets users validate their custom node data during the same walk and print richer information when errors occur.
> 
> Everything is implemented via template parameters with set defaults, so existing code remains unchanged while new code can opt in to the expanded functionality.
> 
> Testing:
> - Oracle tiers 1-3

src/hotspot/share/gc/z/zMappedCache.cpp line 121:

> 119: }
> 120: 
> 121: bool ZMappedCache::EntryCompare::less(const IntrusiveRBNode* a, const IntrusiveRBNode* b) {

I feel `less_than` sounds more natural as a method name; it also avoids "conflicting" with `RBTreeOrdering::less`.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/26981#discussion_r2306853612