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

[Johan Sjölen]

On Thu, 6 Feb 2025 13:10:32 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
>
> src/hotspot/share/utilities/rbTree.inline.hpp line 484:
> 
>> 482: template <typename F>
>> 483: inline void RBTree<K, V, COMPARATOR, ALLOCATOR>::visit_in_order(F f) const {
>> 484:   const RBNode* to_visit[64];
> 
> Note to self or others: This needs at least an assertion, better a visit-stop on release builds

An assertion is nice-to-have. A "visit-stop", you mean we should break if we exceed the limit?

I was thinking about this in the original PR. If we do actually have a RB-tree then we're bounded to 2log(n) depth, so this should be impossible to reach. That is, if we do have a RB-Tree, a bug would invalidate that assumption.

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

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