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

[Thomas Stuefe]

On Thu, 9 Jan 2025 13:12:21 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

>> src/hotspot/share/utilities/rbTree.inline.hpp line 438:
>> 
>>> 436: 
>>> 437:     node = curr;
>>> 438:   }
>> 
>> @tstuefe,
>> 
>> Seems like nodes are not stable. To quote Wikipedia:
>> 
>>>- When the deleted node has 2 children (non-NIL), then we can swap its value with its in-order successor (the leftmost child of the right subtree), and then delete the successor instead. Since the successor is leftmost, it can only have a right child (non-NIL) or no child at all. 
>> 
>> This is quite unfortunate, as it becomes very difficult (impossible?) to have intrusive RB-trees with this. 
>> 
>> @caspernorrbin,
>> 
>> Finding information on this in the literature seems like it takes quite a bit of digging. Can't we replace this with swapping everything *but* the key and value?
>> 
>> ```c++
>>   if (node->_left != nullptr && node->_right != nullptr) { // node has two children
>>     RBNode* curr = node->_right;
>>     while (curr->_left != nullptr) {
>>       curr = curr->_left;
>>     }
>>   // Swap parent, left, right, and color
>>   std::swap(curr->_parent, node->_parent);
>>   std::swap(curr->_left, node->_left);
>>   std::swap(curr->_right, node->_right);
>>   std::swap(curr->_color, node->_color);
>>   // Swap the parent's child pointer
>>   if (curr->_parent->_left == node) curr->_parent->_left = curr;
>>   if (curr->_parent->_right == node) curr->_parent->_right = curr;
>>   // Set the children's parent pointers 
>>   curr->_left->_parent = curr; curr->_right->_parent = curr;
>> 
>>   // and then the identical writes for node
>>   if (node->_parent->_left == curr) node->_parent->_left = node;
>>   if (node->_parent->_right == curr) node->_parent->_right = node;
>>   // Set the children's parent pointers 
>>   node->_left->_parent = node; node->_right->_parent = node;
>> 
>>   // Done, they've swapped places in the tree.
>>   // node = curr; <- Don't do this anymore, should still delete node
>>   }
>
> Nodes are now stable! This was not something I had considered, but it's possible with what Johan suggested above. Previously, keys and values were swapped around between nodes during deletion but now we re-point the node's pointers instead. With this the key and value stays constant in a node through its lifetime, given the user does not themself change the value.

@caspernorrbin @jdksjolen Excellent, thank you. 

For the Doubting Thomas I am, could you write a little gtest like this:

- node (key = size) value don't matter I guess.
- malloc n times, with random sizes, so variable sized, but large enough to hold at least a node structure
- then in a loop, add or remove a randomly chosen malloc block to the tree.

If we survive that, I am happy and will use this in the future in Metaspace. Probably also in other areas.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1908793974