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

[Albert Mingkun Yang]

On Thu, 28 Aug 2025 11:21:00 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:
> 
>   albert feedback

Marked as reviewed by ayang (Reviewer).

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

PR Review: https://git.openjdk.org/jdk/pull/26981#pullrequestreview-3164838757