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

[Thomas Stuefe]

On Thu, 6 Feb 2025 13:44:33 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

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

Our linters will definitely complain about that suspected buffer override and are probably not smart enough to figure out the tree limit. Definitely an assert. As long as we don't use the iteration for anything too intensive, either a guarantee or a bailout. If we start using iteration in performance-critical paths, we can rethink.

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

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