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

[Thomas Stuefe]

On Fri, 7 Feb 2025 11:00:09 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

>> Thomas Stuefe has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   feedback johan
>
> 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.

I think iteration is way rarer than insert, so I would save the cycles and the added complexity.

Different way to look at it:
- for small trees, depth is small, so few hops to the first node, so not much gained my keeping _first
- for last trees, the majority of cycles is spent hopping between nodes, not hopping to the first node. Even then, as @jdksjolen remarked, the tree is balanced so the depth is predictable.

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

These are different things. ASSERT breaks immediately, EXPECT continues to run. I prefer ASSERT in general, to cut down on error message flood if asserting in a loop.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946572485
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1946574383