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

[Axel Boldt-Christmas]

On Mon, 17 Mar 2025 14:47:36 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

>> Hi everyone,
>> 
>> The recently integrated red-black tree can be made more flexible by adding support of intrusive trees. In an intrusive tree, the user has full control over node allocation and placement instead of having the tree manage it internally.
>> 
>> Two key changes enable this feature:
>> 1. Nodes can now be created outside of the tree's internal allocation mechanism, enabling users to allocate and prepare nodes before inserting them into the tree.
>> 2. Cursors have been added to simplify navigation and iteration over the tree. These cursors are when inserting and removing nodes in an intrusive tree, where the internal tree allocator is not used. Additionally, cursors enable iteration over the tree and provide a convenient way to access node values.
>> 
>> 
>> Many of the auxiliary tree functions have been updated to use these new features, resulting in simplified and cleaned-up code. More tests have also been added to cover both new and existing functionality.
>> 
>> An example of how you could use the intrusive tree is found below:
>> 
>> ```c++
>>     struct MyIntrusiveStructure {
>>       Node node; // The tree node is part of an external structure
>>       int data;
>> 
>>       MyIntrusiveStructure(int data, Node node) : node(node), data(data) {}
>>       Node* get_node() { return &node; }
>>       static MyIntrusiveStructure* cast_to_self(Node* node) { return (MyIntrusiveStructure*)node; }
>>     };
>> 
>>     Tree my_intrusive_tree;
>> 
>>     Cursor insert_cursor = my_intrusive_tree.cursor_find(0);
>>     Node insert_node = Node(0);
>> 
>>     // Custom allocation here is just malloc
>>     MyIntrusiveStructure* place = (MyIntrusiveStructure*)os::malloc(sizeof(MyIntrusiveStructure), mtTest);
>>     new (place) MyIntrusiveStructure(0, insert_node);
>> 
>>     my_intrusive_tree.insert_at_cursor(place->get_node(), insert_cursor);
>> 
>>     Cursor find_cursor = my_intrusive_tree.cursor_find(0);
>>     int found_data = MyIntrusiveStructure::cast_to_self(find_cursor.node())->data;
>> 
>> 
>> 
>> Please let me know any feedback or concerns!
>
> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Allow non-debug verify_self + comparator readability

Sorry for being slow in reviewing. 

The changes look good. I've also tried using this tree as a replacement for the tree we have been using in our ZGC project and its been working almost seamless.

I have a couple comments, I'll leave it up to you if it is something we want to fix in this PR or as followups if at all. 

Thanks for all the work. I'll talk with you next week and then approve.

src/hotspot/share/utilities/rbTree.inline.hpp line 502:

> 500: template <typename F>
> 501: inline void RBTree<K, V, COMPARATOR, ALLOCATOR>::visit_range_in_order(const K& from, const K& to, F f) const {
> 502:   assert(COMPARATOR::cmp(from, to) <= 0, "from must be less or equal to to");

Seem unfortunate to loose these assert, would be nice to find these sort of errors early.

Maybe we can have some verification functions on the tree which takes (const K& from, const K& to, const NodeType* end_node) which can dispatch to the correct COMPARATOR function.

src/hotspot/share/utilities/rbTree.inline.hpp line 548:

> 546:     return;
> 547:   }
> 548: 

This could be a future enhancement. But it would be nice that if the COMPARATOR (or the NodeType) supplied a `cmp(const NodeType* a, const NodeType* b)` we could use it to check the order invariants for the children and parent.

src/hotspot/share/utilities/rbTree.inline.hpp line 600:

> 598: template <typename K, typename NodeType, typename COMPARATOR>
> 599: template <typename F>
> 600: inline void AbstractRBTree<K, NodeType, COMPARATOR>::visit_range_in_order(const K& from, const K& to, F f) const {

Preexisting.

This is an exclusive end. I would think inclusive end would be more natural. Otherwise you cannot iterate all the way to the end. (Currently can be worked around if the largest possible K is not in the tree, by using it as `to`).

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

PR Review: https://git.openjdk.org/jdk/pull/23416#pullrequestreview-2724962236
PR Review Comment: https://git.openjdk.org/jdk/pull/23416#discussion_r2018308634
PR Review Comment: https://git.openjdk.org/jdk/pull/23416#discussion_r2018403030
PR Review Comment: https://git.openjdk.org/jdk/pull/23416#discussion_r2018303212