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

[Casper Norrbin]

On Tue, 7 Jan 2025 18:38:12 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   renamed coloring functions
>
> 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 instead 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.

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

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