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

[Casper Norrbin]

On Wed, 22 Jan 2025 14:24:51 GMT, Gerard Ziemski <gziemski at openjdk.org> wrote:

>> 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.

@gerard-ziemski I ran in to both of these trying to verify that swapping still worked. 
I pushed an update earlier today to fix the second issue, the `const` of `visit_in_order` had disappeared when I moved functions around. For the first issue, you would need to `#include rbTree.inline.hpp` with/instead of `rbTree.hpp`  in vmatree.

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

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