RFR: 8345314: Add a red–black tree as a utility data structure [v12]

[Johan Sjölen]

On Thu, 16 Jan 2025 11:26:12 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Hi @tstuefe ,
>> 
>>>Consider this scenario: I want to have two short-lived trees, nodes live longer than their trees they temporarily occupy, and I want the nodes to reside in physically different preallocated pools. I want to use the same allocator and tree classes, though, so template parameters must be the same.
>> 
>>>There are two ways to do this. The most obvious would be to keep a reference to an allocator instance that the caller hands in via constructor. So, make _allocator a pointer, and if omitted by the caller use your own C-heap allocator. Otherwise, use the caller's allocator.
>> 
>> Or you have a reference as the template type and you alter the constructor of the `RBTree` to take such a type to construct its own allocator with.
>> 
>> It seems like you want an intrusive RBTree. That's really no problem, it just means that we have to extend the API slightly and make it so that you can avoid using an allocator.
>> 
>> I do want an allocator instance in the tree, because then you can make very nice things such as a `IndexWithFreeList` allocator that doesn't need protection from concurrent writes. You could also, for example, avoid the cost of freeing separate elements and eliminate the whole tree at once when the lifetime of the tree has ended (since the lifetime of the allocator is identical). In short: When your tree isn't intrusive, it's very nice to have a custom allocator.
>> 
>> For your use case, you basically need a very similar addition to the API. It'd look something like this in pseudo-code:
>> 
>> ```c++
>> // I hold the data, but the node holds the key
>> struct IntrusiveHolder {
>>   int data;
>>   RBNode node;
>>   static IntrusiveHolder* cast_to_self(RBNode* node) ; // offset_of() magic
>> };
>> 
>> struct Compare {
>>   int cmp(int a, int b);
>> }
>> 
>> template<typename K, typename V, typename Cmp, typename Allocator>
>> struct RBTree{
>> public:
>>   enum Dir { left, right };
>>   // Describes the parent node and whether the next node is to be inserted on the left or the right.
>>   struct InsertionCursor {
>>    RBNode* parent; Dir dir;
>>    RBNode* position(); // Get the node (potentially nullptr)
>>   };
>> 
>>   // Walks the tree in the obvious order, using Comparator::cmp overload to find the place to insert.
>>   // However does not allocate.
>>   InsertionCursor find_insertion_point(K k);
>>   // Inserts the node at the position and rebalances the tree.
>>   void insert_at_cursor(InsertionCursor, RBNode* node);
>> 
>>   // For removals we need to unlink t...
>
>> Hi @jdksjolen, @caspernorrbin
>> 
>> sorry for the delay, work is piled up.
>> 
>> > It seems like you want an intrusive RBTree. That's really no problem, it just means that we have to extend the API slightly and make it so that you can avoid using an allocator.
>> 
>> intrusive - I did not know this term, even though I wrote containers like this all my life, go figure :-).
>> 
>> Yes, that's precisely what I want.
>> 
>>     * I want to create/store nodes myself
>> 
>>     * I want to avoid copying node content; in fact, I don't want to even bother with assignment operators.
>> 
>>     * I want to be able to add child nodes to a node to handle duplicates if my tree allows duplicates (which is of no concern to the tree, but since these child nodes should live in the same pool, again, my wish for wanting to create nodes myself)
>> 
>> 
>> All of this points to a tree where I manage the node myself. So, have a function to find a reference to an existing node by key and have a function to hand in a node for storage. Pretty much like you line it out in your example:
>> 
>> ```
>> MyTree::add_my_bulky_and_possible_varsized_node(Node* n) {
>> 	- find node n2 with key n->key
>> 		- found? Add n as child node under n2
>> 		- not found? add n as new node
>> }
>> ```
>> 
>> I have two immediate examples where I want to use this RB tree: the reworked c2 memory statistic (in fact, I withhold the patch to wait for this RB tree to drop) and - somewhat later - the metaspace binary tree dictionary replacement. Both cases would be perfectly served with an intrusive key that allows me to handle duplicates.
> 
> This requires the tree to have nodes `<` strictly on the left, and `>=` strictly on the right (as opposed to `>` strictly on the right), or the opposite. I have no clue what having duplicates does to a RBTree when rebalancing. If it's that important to have duplicates, then why have them live inside the tree anyway? Just link them together with an intrusive linked list.
> 
> ```c++
> struct Foo {
>   RBNode rb; // with some K as key
>   Foo* next;
>   struct { /* ... */ } data;
> };
> 
> void a_m_b_a_p_v_n(Foo* n) {
>   Cursor c = tree.find_insertion_point(n);
>   if (c.exists()) {
>     Foo* f = Foo::cast_to_self(c.node());
>     n->next = f->next;
>     f->next = n->next;
>   }
>   tree.insert(c, n);
> };
> 
> 
> Just do that. Let's us entirely skip the headache of the rest of it, at the cost of 8 bytes.
>  
>> > I do want an allocator instance in the tree, because then you can make very nice things such as a `IndexWithFreeList` alloca...

> > > Hi @jdksjolen,
> 
> > > I have two immediate examples where I want to use this RB tree: the reworked c2 memory statistic (in fact, I withhold the patch to wait for this RB tree to drop) and - somewhat later - the metaspace binary tree dictionary replacement. Both cases would be perfectly served with an intrusive key that allows me to handle duplicates.
> > 
> > 
> > This requires the tree to have nodes `<` strictly on the left, and `>=` strictly on the right (as opposed to `>` strictly on the right), or the opposite. I have no clue what having duplicates does to a RBTree when rebalancing. If it's that important to have duplicates, then why have them live inside the tree anyway? Just link them together with an intrusive linked list.
> 
> You misunderstood me - a linked list is exactly what I meant. That is why I talked about a "child node". I did this in metaspace:
> 

Phew! Good to hear that we're talking about the same thing.

> https://github.com/openjdk/jdk/blob/f64f22b360f68df68ebb875bd0ef08ba61702952/src/hotspot/share/memory/metaspace/blockTree.hpp#L89-L96
> 
> I can do that myself, as I wrote, this does not concern the tree. So for the tree we can keep things without duplicates. But for simplicity the easiest solution is for child nodes to be of the Node class itself, because then you can just swap them around and make them the leader node for this key value later. That would require a child Node to be allocated in the same pool as the "real" tree nodes, and have the same type as well. All of that can happen outside the tree. It is, however, an argument for giving the caller the ability to allocate and manage nodes himself and passing them in pre-formed for insertion.
> 
 
Right, and you should get that with the intrusive tree. My pseudo-code that you saw above, unfortunately, does not tell you that.


>Oh, sure. But again, not a strong argument for non-intrusiveness. In my original comment, I argued for having the ability to pass in an allocator instance into the destructor, or alternatively use a token of some sort when calling functions in a AllStatic allocator that identifies the tree.

>But as I wrote, I think we don't have to choose. We can have an allocator instance as optional ctor argument, and let the tree create its own allocator itself if nothing is passed in. Or, you know, just use malloc and free instead.

I think that the major argument for non-intrusive datastructures is that they require less ceremony to use. But as you say, we don't have to choose one or the other, and I don't want us to have to.

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

PR Comment: https://git.openjdk.org/jdk/pull/22360#issuecomment-2595749485