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

Hmm, I still can't compile it, I see:


/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:235:18: error: expected ';' after expression
  235 |   VMATreap::Range range(nullptr, nullptr);
      |                  ^
      |                  ;
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:235:13: error: no member named 'Range' in 'RBTree<unsigned long, VMATree::IntervalChange, VMATree::PositionComparator, RBTreeCHeapAllocator<MemTag::mtNMT>>'
  235 |   VMATreap::Range range(nullptr, nullptr);
      |   ~~~~~~~~~~^
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:235:19: error: use of undeclared identifier 'range'
  235 |   VMATreap::Range range(nullptr, nullptr);
      |                   ^
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:240:5: error: use of undeclared identifier 'range'
  240 |     range = _tree.find_enclosing_range(from);
      |     ^
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:240:19: error: no member named 'find_enclosing_range' in 'RBTree<unsigned long, VMATree::IntervalChange, VMATree::PositionComparator, RBTreeCHeapAllocator<MemTag::mtNMT>>'
  240 |     range = _tree.find_enclosing_range(from);
      |             ~~~~~ ^
/Users/gerard/Work/bugs/8317453/jdk/src/hotspot/share/nmt/vmatree.cpp:241:10: error: use of undeclared identifier 'range'
  241 |     if ((range.start == nullptr && range.end == nullptr) ||
      |          ^

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

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