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

[Casper Norrbin]

On Mon, 10 Feb 2025 18:01:59 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 268:
> 
>> 266:     const Cursor cursor = cursor_find(key);
>> 267:     return cursor.found() ? &cursor.node()->_value : nullptr;
>> 268:   }
> 
> Are these important to have?

Depends on what you mean by important. I think it's useful for those who want to interact with the tree on a higher level, by for example only using `upsert(k,v)`, `remove(k)`, and `find(k)`. Of course, I could remove this and force people to use cursors instead, but that feels unnecessary, especially if they don't need cursors otherwise.

> src/hotspot/share/utilities/rbTree.hpp line 283:
> 
>> 281:   // Inserts a node with the given key into the tree,
>> 282:   // does nothing if the key already exist.
>> 283:   void upsert(const K& key) {
> 
> `upsert` is a bad name for function, as it is a portmanteau of "update" and "insert", indicating that this should change something if the key is found. What's the goal with this function? It should probably return the allocated node if it's to be useful.

This follows the pattern of the other value-less functions keeping the name, but I agree that it's less logical here. Would one `insert(k)` and one `upsert(k, v)` be a good solution?

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

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