RFR: 8375621: Move RBTree implementation to inline file to minimize included headers

[Stefan Karlsson]

On Mon, 19 Jan 2026 11:14:18 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

> Hi everyone,
> 
> The red-black tree implementation is split across `rbTree.hpp` and `rbTree.inline.hpp`. Some small `AbstractRBTree` functions are kept in `rbTree.hpp`, and also all of `RBTree`'s implementation. This makes the file less readable and requires extra header inclusions, notably the `os` class, which in turn includes additional unnecessary dependancies.
> 
> In this PR I have moved all implementation code `rbTree.inline.hpp` instead. As a result, `rbTree.hpp` now only contains declarations, making it cleaner and limiting header inclusions to what is strictly necessary. Implementation-specific headers are now only included in the inline file.
> 
> Additionally, I changed `RBTreeCHeapAllocator` to use `AllocateHeap`/`FreeHeap` from `allocation` instead of `os::malloc`/`os::free`, which allows us to get rid of the `os` dependancy altogether.
> 
> Note: This PR is dependant on #29082, which adds arena-style tree allocators, which this PR then moves to the inline file.
> 
> Testing:
> - Oracle tiers 1-5

Thanks for doing this cleanup. I've left a few nits below.

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

> 66: class outputStream;
> 67: class Arena;
> 68: class ResourceArea;

Brownie points if you also sort the forward declarations.

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

> 234: 
> 235: template <typename K, typename V>
> 236: inline const RBNode<K, V>* RBNode<K, V>::next() const { return static_cast<const RBNode<K, V>*>(IntrusiveRBNode::next()); }

Not a strong request, but I would like to suggest that you skip writing one-liners for all these functions in the inline.hpp file:
Suggestion:

template <typename K, typename V>
inline const RBNode<K, V>* RBNode<K, V>::next() const {
  return static_cast<const RBNode<K, V>*>(IntrusiveRBNode::next());
}

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

> 1157: template <MemTag mem_tag, AllocFailType strategy>
> 1158: inline void* RBTreeCHeapAllocator<mem_tag, strategy>::allocate(size_t sz) {
> 1159:   return static_cast<void*>(AllocateHeap(sz, mem_tag, strategy));

Do you really need the cast here?

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

> 1176: inline void RBTreeArenaAllocator<strategy>::free(void* ptr) { /* NOP */ }
> 1177: 
> 1178: 

Suggestion:

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

Marked as reviewed by stefank (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/29295#pullrequestreview-3677888893
PR Review Comment: https://git.openjdk.org/jdk/pull/29295#discussion_r2704604313
PR Review Comment: https://git.openjdk.org/jdk/pull/29295#discussion_r2704592351
PR Review Comment: https://git.openjdk.org/jdk/pull/29295#discussion_r2704627054
PR Review Comment: https://git.openjdk.org/jdk/pull/29295#discussion_r2704596060