RFR: 8349211: Add support for intrusive trees to the utilities red-black tree [v7]

[Casper Norrbin]

On Mon, 10 Feb 2025 18:17:05 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   empty base optimization reference
>
> src/hotspot/share/utilities/rbTree.hpp line 166:
> 
>> 164:     bool found() const { return *_insert_location != nullptr; }
>> 165:     RBNode* node() { return _insert_location == nullptr ? nullptr : *_insert_location; }
>> 166:     RBNode* node() const { return _insert_location == nullptr ? nullptr : *_insert_location; }
> 
> Is there any case where I don't need to check the validity of the cursor? That is, do I ever want to use `node()` without first calling `valid()` or afterwards checking whether the returned value was null?
> 
> If the answer to that is: "No, there is no such case", then we shouldn't return null on `!valid()` node. We should instead add `assert(valid(), "must be");". If the answer is yes, then could you please tell me what that situation is :P?

It's been useful in a couple of places, where we want "the node or nullptr otherwise", since you get the valid check and the node in one. A few examples where we don't check validity:
In `visit_range_in_order`, we iterate until the node (or nullptr) is reached.
In `upsert`, we extract the node node into a local variable and either modify the node or reuse the variable.
In `closest_gt`, we return the next node from the cursor, which could be invalid.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/23416#discussion_r1951182600