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

[Casper Norrbin]

On Tue, 25 Feb 2025 13:04:11 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:
> 
>   insert node intrusive fix

Just pushed another change, this time separating the node class into `IntrusiveRBNode` and `RBNode<K, V>`. `IntrusiveRBNode` stores the tree pointers and is used for the intrusive tree, and no longer needs to be templated. `RBNode<K, V>` is used for the normal tree and also stores a key and a value. This means that the key is now stored outside the node for intrusive trees. To allow for this, I changed the compare function for intrusive trees to `cmp(K a, const IntrusiveRBNode* b)`. For the normal tree, both `cmp(K a, const RBNode<K, V>* b)` and `cmp(K a, K b)` can be used. With all the changes so far, the original example would now look something like this:

```c++
    struct MyIntrusiveStructure {
      IntrusiveRBNode node; // The tree node is part of an external structure
      int key;
      int data;

      MyIntrusiveStructure(int key, int data) : key(key), data(data) {}
      IntrusiveRBNode* get_node() { return &node; }
      static MyIntrusiveStructure* cast_to_self(IntrusiveRBNode* node) { return (MyIntrusiveStructure*)node; }
    };

    struct IntrusiveCmp {
      static int cmp(int a, const IntrusiveTreeNode* b) {
        return a - IntrusiveHolder::cast_to_self(b)->key;
      }
    };

    IntrusiveRBTree<int, IntrusiveCmp> my_intrusive_tree;
    const int key = 0;

    // Custom allocation here is just malloc
    MyIntrusiveStructure* place = (MyIntrusiveStructure*)os::malloc(sizeof(MyIntrusiveStructure), mtTest);
    new (place) MyIntrusiveStructure(key, 123);

    my_intrusive_tree.insert(key, place->get_node());

    IntrusiveRBNode* found_node = my_intrusive_tree.find_node(key);
    int found_data = MyIntrusiveStructure::cast_to_self(found_node)->data;


The key changes are:
- The key is stored in `MyIntrusiveStructure` and can be modified/changed whenever.
- No node constructor is needed and you simply need to pass the node pointer to `insert`.
- No cursors are needed (although you could still use them) to insert/lookup/delete nodes.

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

PR Comment: https://git.openjdk.org/jdk/pull/23416#issuecomment-2681950920