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

[Johan Sjölen]

On Thu, 6 Feb 2025 08:06:04 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

Personally, I think we're fine with Tree and Node without the Type suffix, that'll be obvious from the usage sites anyway. Functionality wise, seems fine. Will look at tests in more detail later.

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

> 115:   }; // End: RBNode
> 116: 
> 117:   typedef RBTree<K, V, COMPARATOR, ALLOCATOR>::RBNode NodeType;

Can't do `typedef TreeType::RBNode`?

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

> 279: 
> 280:   // Returns leftmost node, nullptr if tree is empty.
> 281:   // If COMPARATOR::cmp(a, b) behaves canonically ("1" for a < b), this will the smallest key value.

That should be `-1` and not `1`, no? Copy-paste error with rightmost :-).

FWIW, you can use `-1` and it'll show up in my IDE rendered as-if markdown. Do with that info what you will.

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

> 302:   RBNode* leftmost()  { return const_cast<NodeType*>(static_cast<const TreeType*>(this)->leftmost()); }
> 303: 
> 304:   // Returns rightmost node (smallest key). Returns nullptr if tree is empty.

Inconsistent commenting re: result if tree is empty. Also, say "null" and not "nullptr" here.

src/hotspot/share/utilities/rbTree.inline.hpp line 561:

> 559: void print_T(outputStream* st, T x) {
> 560:   st->print(PTR_FORMAT, p2i(x));
> 561: }

I've done something like this before but ended up not integrating it. Seems like this is something we should have in a generic place, in the future. Just a note, nothing to fix.

src/hotspot/share/utilities/rbTree.inline.hpp line 568:

> 566:   st->sp(1 + depth * 2);
> 567:   st->print("@" PTR_FORMAT ": [", p2i(n));
> 568:   print_T<K>(st, n->key());

Do you need to provide the template parameter because key and val returns references? I would've assumed that C++ can infer the type and pick the right function.

src/hotspot/share/utilities/rbTree.inline.hpp line 572:

> 570:   print_T<V>(st, n->val());
> 571:   st->cr();
> 572:   depth ++;

Style: No space between depth and ++

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

> 547: 
> 548: struct PtrCmp {
> 549:   static int cmp(const void* a, const void* b) { return a == b ? 0 : (a > b ? 1 : -1); }

I'm fairly sure that it's UB to compare pointers with `>`, can you cast these to `uintptr_t` so we don't have to take the ubsan fix review later?

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

> 598:     stringStream ss;
> 599:     tree.print_on(&ss);
> 600:     // tty->print_cr("%s", ss.base());

Delete

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

PR Review: https://git.openjdk.org/jdk/pull/23486#pullrequestreview-2598727376
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1944755734
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1944763150
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1944765568
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1944770869
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1944772601
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1944773204
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1945175774
PR Review Comment: https://git.openjdk.org/jdk/pull/23486#discussion_r1945180019