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.hpp line 114:

> 112:     if (node_place == nullptr) {
> 113:       return nullptr;
> 114:     }

Remove this and instead `assert` that it can't be `nullptr` with a message saying that allocators must exit on failure.

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

> 132:   RBNode* find_node(RBNode* curr, const K& k);
> 133: 
> 134:   RBNode* insert_node(const K& k, const V& v);

Comment that it replaces `v` (as `upsert` does) if found.

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

> 264:     const RBTree* const _tree;
> 265:     GrowableArrayCHeap<RBNode*, mtInternal> _to_visit;
> 266:     RBNode* _next;

This isn't used?

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

> 272:     NONCOPYABLE(IteratorImpl);
> 273: 
> 274:     IteratorImpl(const RBTree* tree) : _tree(tree) {

Initialize `_to_visit` explicitly with a `2log(n)` where n is number of nodes, unnecessary resizing happens otherwise.

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

> 98:     _right->visit_in_order_inner(f);
> 99:   }
> 100: }

This is basically fine, as stack depth will be at most `2log n`, but is there a reason that you can't use the iterative solution that's present in the Treap? Btw, having this method belonging to RBTree and take a `RBNode*` instead of RBNode allows you to just check if the current root node is null, letting you skip a check.

Here's `visit_in_order` as an iterative function:


  template<typename F>
  void visit_in_order(F f) const {
    GrowableArrayCHeap<TreapNode*, mtNMT> to_visit;
    TreapNode* head = _root;
    while (!to_visit.is_empty() || head != nullptr) {
      while (head != nullptr) {
        to_visit.push(head);
        head = head->left();
      }
      head = to_visit.pop();
      f(head);
      head = head->right();
    }
  }

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

> 170:       curr = curr->_left;
> 171:     } else {                    // k > key
> 172:       curr = curr->_right;

Nit: Unnecessary comments, should be clear what they do.

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

> 201:       curr = curr->_right;
> 202:     }
> 203:   }

Replace with `find_node` and write `parent` by reading `_parent`?

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

> 235: 
> 236:     RBNode* uncle = parent->is_left_child() ? grandparent->_right : grandparent->_left;
> 237:     if (is_black(uncle)) { // Parent is red, uncle is black

And uncle has to exist (can't be null) as per some invariant? Add assert.

test/hotspot/gtest/utilities/test_rbtree.cpp line 300:

> 298:       EXPECT_EQ(reverse_iterator.next()->val(), n);
> 299:     }
> 300:   }

At least also test:

1. Iterator on empty tree works as expected
2. `has_next` is false after the loops

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905163526
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905433593
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905676241
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905675907
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905175777
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905431887
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905434902
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905437920
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1905676906