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

And this:


* For target hotspot_variant-server_libjvm_objs_memoryFileTracker.o:
In file included from /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/memoryFileTracker.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:
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.hpp:235:11: error: no matching member function for call to 'visit_in_order'
  235 |     _tree.visit_in_order(f);
      |     ~~~~~~^~~~~~~~~~~~~~
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/memoryFileTracker.cpp:75:15: note: in instantiation of function template specialization 'VMATree::visit_in_order<(lambda at /Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/memoryFileTracker.cpp:75:30)>' requested here
   75 |   file->_tree.visit_in_order([&](VMATree::TreapNode* current) {
      |               ^
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/utilities/rbTree.hpp:249:8: note: candidate function template not viable: 'this' argument has type 'const VMATreap' (aka 'const RBTree<unsigned long, VMATree::IntervalChange, VMATree::PositionComparator, RBTreeCHeapAllocator<(MemTag)'\f'>>'), but method is not marked const
  249 |   void visit_in_order(F f);
      |        ^
1 error generated.

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

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