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

[Thomas Stuefe]

On Fri, 10 Jan 2025 10:03:22 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:
> 
>   clarified comment

Checked basic tree rotation functions, more to follow later

src/hotspot/share/utilities/rbTree.hpp line 93:

> 91:     void replace_child(RBNode* old_child, RBNode* new_child);
> 92: 
> 93:     // Move node down to the left, and right child up

Suggestion:

    // This node down, right child up
    // Returns right child (now parent)

(different papers use left/right in different ways, I always get confused. A clear concise comment helps)

src/hotspot/share/utilities/rbTree.hpp line 96:

> 94:     RBNode* rotate_left();
> 95: 
> 96:     // Move node down to the right, and left child up

Suggestion:

    // This node down, left child up
    // Returns left child (now parent)

src/hotspot/share/utilities/rbTree.inline.hpp line 39:

> 37:   } else if (_right == old_child) {
> 38:     _right = new_child;
> 39:   }

I would add an assert for the else case here, since not matching any child is an error in all call cases.

src/hotspot/share/utilities/rbTree.inline.hpp line 51:

> 49:   if (old_right->_left != nullptr) {
> 50:     old_right->_left->_parent = this;
> 51:   }

Suggestion:

  if (_right != nullptr) {
    _right->_parent = this;
  }

Alternatively  a `set_parent(node)`, equivalent to the existing `set_child()`, with nullptr handling, would be even better

src/hotspot/share/utilities/rbTree.inline.hpp line 58:

> 56:   } else if (is_right_child()) {
> 57:     _parent->_right = old_right;
> 58:   }

Suggestion:

   _parent->replace_child(this, old_right);

src/hotspot/share/utilities/rbTree.inline.hpp line 75:

> 73:   if (old_left->_right != nullptr) {
> 74:     old_left->_right->_parent = this;
> 75:   }

Suggestion:

  if (_left != nullptr) {
    _left->_parent = this;
  }

src/hotspot/share/utilities/rbTree.inline.hpp line 82:

> 80:   } else if (is_right_child()) {
> 81:     _parent->_right = old_left;
> 82:   }

Suggestion:

  _parent->replace_child(this, old_left);

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

PR Review: https://git.openjdk.org/jdk/pull/22360#pullrequestreview-2559047396
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920281600
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920282747
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920209864
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920275899
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920277700
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920291041
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920292496