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

[Axel Boldt-Christmas]

On Tue, 28 Jan 2025 11:04:08 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 with a new target base due to a merge or a rebase. The pull request now contains 36 commits:
> 
>  - merge fixes
>  - Merge branch 'master' into rb-tree
>  - readd find_enclosing_range
>  - Merge branch 'master' into rb-tree
>  - treap swap fix
>  - const functions
>  - thomas feedback
>  - axel feedback
>  - clarified comment
>  - Improved comments
>  - ... and 26 more: https://git.openjdk.org/jdk/compare/ad01dfb6...b7219a93

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

> 77: 
> 78:     RBNode* parent() const { return (RBNode*)(_parent & ~0x1); }
> 79:     void set_parent(RBNode* new_parent) {_parent = (_parent & 0x1) | ((uintptr_t)new_parent & ~0x1); }

When would `new_parent` not have a valid `RBNode*` pointer value? AFAICT it is only called with valid pointers. The lsb masking is unnecessary. If it is actually required from somewhere, I missed it, in which case we should use `uintptr_t`.

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

> 202:   // Finds the node with the closest key <= the given key
> 203:   // Change mode to EXCLUSIVE to not include node matching key
> 204:   RBNode* closest_leq(const K& key, BoundMode mode = INCLUSIVE) {

Having a parameter value change the behaviour to contradict the name of the function feels a little evil. Might cause confusion and bugs in the future. I would rather have one `closest(Key, Direction, BoundMode)` and/or four `closest_[ls,leq,geq,gt](Key)`.

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

> 245: 
> 246:   const RBNode* closest_leq(const K& k, BoundMode mode = INCLUSIVE) const {
> 247:     return const_cast<RBTree<K, V, COMPARATOR, ALLOCATOR>*>(this)->closest_leq(k, mode);

When it comes to `const` overloads of `accessor` like member functions I prefer that we invert the `const` cast logic. That is that it is the `const` variant that includes the implementation. And that the non-`const` variant dispatches to the `const` versions and then casts away the the `const` qualifier on the result. This ensures that the implementation does not break the `const` property of the class, and is less bug prone.

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

> 249: 
> 250:   const RBNode* closest_gt(const K& k, BoundMode mode = EXCLUSIVE) const {
> 251:     return const_cast<RBTree<K, V, COMPARATOR, ALLOCATOR>*>(this)->closest_gt(k, mode);

Same.

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

> 272: 
> 273:   const RBNode* find_node(const K& k) const {
> 274:     return const_cast<RBTree<K, V, COMPARATOR, ALLOCATOR>*>(this)->find_node(k);

Same.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1933329704
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1933320201
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1933309763
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1933321189
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1933321261