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

[Johan Sjölen]

On Wed, 18 Dec 2024 10:46:53 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

>> Hi everyone,
>> 
>> This effort began as an exploration of replacing the current NMT treap with a red-black tree. Along the way, I discovered that others were also interested in having a general-purpose tree structure available within HotSpot.
>> 
>> The red-black tree is designed to serve as a drop-in replacement for the existing NMT treap, keeping a nearly identical interface. However, I’ve also added a few additional requested features, such as an iterator.
>> 
>> Testing builds off the treap tests, adding a few extra that inserts/removes and checks that the tree is correct. Testing uses the function `verify_self`, which iterates over the tree and checks that all red-black tree properties hold. Additionally, the tree has been tested in vmatree instead of the treap without any errors.
>> 
>> For those who may want to revisit the fundamentals of red-black trees, [Wikipedia](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) offers a great summary with tables covering the various balancing cases. Alternatively, your favorite data structure book could provide even more insight.
>
> 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;
  }

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

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