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

[Johan Sjölen]

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

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

Yes!

>> src/hotspot/share/utilities/rbTree.inline.hpp line 192:
>> 
>>> 190: template <typename K, typename V, typename COMPARATOR, typename ALLOCATOR>
>>> 191: inline const typename RBTree<K, V, COMPARATOR, ALLOCATOR>::Cursor
>>> 192: RBTree<K, V, COMPARATOR, ALLOCATOR>::cursor_find(const K& key) const {
>> 
>> ```c++
>> using Tree = RBTree<K, V, COMPARATOR, ALLOCATOR:
>> using Cur = typename RBTree<K, V, COMPARATOR, ALLOCATOR>::Cursor;
>> 
>> 
>> Though I'm pretty sure Thomas gave you a `typedef` for `Tree`, I don't think the `Cur` can be done with a `typedef`.
>
> I don't think we can access `TreeType` here in any meaningful way, since that is a part of the tree class and we're outside the class here, and we would still need to specify the template parameters.  But please correct me if I'm wrong :)

I don't know :-), you might be right!

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

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