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

[Gerard Ziemski]

On Wed, 22 Jan 2025 12:13:04 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:
> 
>   treap swap fix

I see this when trying to compile:


* For target hotspot_variant-server_libjvm_objs_vmatree.o:
In file included from /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:1:
In file included from /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/precompiled/precompiled.hpp:45:
In file included from /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/memTracker.hpp:30:
In file included from /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/memoryFileTracker.hpp:32:
In file included from /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.hpp:34:
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/utilities/rbTree.hpp:253:8: error: function 'RBTree<unsigned long, VMATree::IntervalChange, VMATree::PositionComparator, RBTreeCHeapAllocator<MemTag::mtNMT>>::visit_range_in_order<(lambda at /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:136:44)>' is used but not defined in this translation unit, and cannot be defined in any other translation unit because its type does not have linkage
  253 |   void visit_range_in_order(const K& from, const K& to, F f);
      |        ^
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:136:9: note: used here
  136 |   _tree.visit_range_in_order(A + 1, B + 1, [&](TreapNode* head) {

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

PR Comment: https://git.openjdk.org/jdk/pull/22360#issuecomment-2607378308