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

Some more comments, continue next week

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

> 119:   }
> 120: 
> 121:   static inline bool is_black(RBNode* node) {

Suggestion:

  // True if node is black (nil nodes count as black)
  static inline bool is_black(const RBNode* node) {

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

> 123:   }
> 124: 
> 125:   static inline bool is_red(RBNode* node) {

Suggestion:

  static inline bool is_red(const RBNode* node) {

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

> 127:   }
> 128: 
> 129:   RBNode* find_node(RBNode* curr, const K& k);

All callers start at `_root`, you may just as well scrap the `curr` parameter and hard-wire root as starting point.
Also, as others remarked, a const version would be good (const_cast<> redirection is fine). Then, `find()` can also be const.

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

> 134: RBTree<K, V, COMPARATOR, ALLOCATOR>::find_node(RBNode* curr, const K& k) {
> 135:   while (curr != nullptr) {
> 136:     int key_cmp_k = COMPARATOR::cmp(k, curr->key());

Suggestion:

    const int key_cmp_k = COMPARATOR::cmp(k, curr->key());

(Matter of taste, up to you. I litter my code with const, but others don't.)

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

PR Review: https://git.openjdk.org/jdk/pull/22360#pullrequestreview-2559217922
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920308441
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920311319
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920319795
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920327264