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

[Casper Norrbin]

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

This pull request has now been integrated.

Changeset: 53d4e928
Author:    Casper Norrbin <cnorrbin at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/53d4e928ef2851f3e16d1d200b5c3fb036e15e00
Stats:     267 lines in 7 files changed: 167 ins; 9 del; 91 mod

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

Reviewed-by: jsjolen, ayang

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

PR: https://git.openjdk.org/jdk/pull/26981