RFR: 8349525: RBTree: provide leftmost, rightmost, and a simple way to print trees [v2]

[Casper Norrbin]

On Fri, 7 Feb 2025 07:28:55 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

>> For things I currently work on (compilation memory statistic), I need this functionality.
>> 
>> Changes:
>> 
>> - added leftmost() and rightmost() (pretty self-explanatory)
>> - added print_on(outputStream*) (likewise)
>> - const correctness
>> - other minor cleanups
>> - gtests for all added functions
>> 
>> Tests: GHA (all clean), manual tests on Linux x64
>
> Thomas Stuefe has updated the pull request incrementally with one additional commit since the last revision:
> 
>   feedback johan

Hi, think this looks good overall! Just have a couple small comments.

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

> 280:   // Returns leftmost node, nullptr if tree is empty.
> 281:   // If COMPARATOR::cmp(a, b) behaves canonically (positive value for a > b), this will the smallest key value.
> 282:   const RBNode* leftmost() const {

Just a thought, no change needed:

The intrusive tree PR has the member `RBNode* _first` to get the leftmost node in constant time instead of having to traverse down the tree, but at the cost of an extra check when inserting/removing. Which solution do you prefer? I don't really have a preference so can adapt that PR either which way.

test/hotspot/gtest/utilities/test_rbtree.cpp line 402:

> 400:       for (int j = 0; j < 10; j++) {
> 401:         if (j == 0) {
> 402:           ASSERT_EQ(rbtree_const.leftmost(), (const Node*)nullptr);

Style: All the previous tests use `EXPECT`s instead of `ASSERT`s. Goes for the other new tests as well.

test/hotspot/gtest/utilities/test_rbtree.cpp line 417:

> 415:         max = MAX2(max, r);
> 416:       }
> 417:       // rbtree_const.print_on(tty);

Delete

test/hotspot/gtest/utilities/test_rbtree.cpp line 424:

> 422:       n = rbtree.leftmost();
> 423:       ASSERT_EQ(n->key(), min);
> 424:       n->set_val(1);

Why are the node's values set to 1?

test/hotspot/gtest/utilities/test_rbtree.cpp line 557:

> 555: 
> 556: TEST_VM(RBTreeTestNonFixture, TestPrintPointerTree) {
> 557:   typedef RBTree<const void*, unsigned, PtrCmp, RBTreeCHeapAllocator<mtTest> > TreeType;

Can use `RBTreeCHeap<const void*, unsigned, PtrCmp, mtTest>` here instead.

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

PR Review: https://git.openjdk.org/jdk/pull/23486#pullrequestreview-2601442477
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946353181
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946357902
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946358076
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946370029
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946364698