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

[Albert Mingkun Yang]

On Thu, 28 Aug 2025 09:58:43 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
>
> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   renamed less to less_than

I noticed that in one place


(parent_cmp <= 0 && hint_cmp < 0)

becomes

(parent_cmp != RBTreeOrdering::greater && hint_cmp == RBTreeOrdering::less)


I wonder if compare-result can have some helper apis so that the new code looks like

(parent_cmp.is_less_equal() && hint_cmp.is_less())


Can't say for sure one is definitely better than the other; just throwing out some ideas.

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

> 54:       if (a < b) return RBTreeOrdering::less;
> 55:       if (a == b) return RBTreeOrdering::equal;
> 56:       if (a > b) return RBTreeOrdering::greater;

Preexisting: no need for 3 `if`s, can be identical to the impl in `printinlining.hpp`.

src/hotspot/share/utilities/rbTree.hpp line 217:

> 215: 
> 216:   template <typename CMP>
> 217:   static constexpr bool HasNodeVerifier = has_less_type<CMP, bool, const NodeType*, const NodeType*>::value;

Does this need to be `has_less_than_type`?

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

PR Review: https://git.openjdk.org/jdk/pull/26981#pullrequestreview-3164179820
PR Review Comment: https://git.openjdk.org/jdk/pull/26981#discussion_r2306922430
PR Review Comment: https://git.openjdk.org/jdk/pull/26981#discussion_r2306982476