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

[Johan Sjölen]

On Tue, 11 Feb 2025 16:30:51 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

>> 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.

OK, then leave it as is :-).

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

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