RFR: 8349211: Add support for intrusive trees to the utilities red-black tree [v3]

[Casper Norrbin]

On Mon, 3 Feb 2025 19:38:28 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   build fix
>
> src/hotspot/share/utilities/rbTree.hpp line 33:
> 
>> 31: #include <type_traits>
>> 32: 
>> 33: struct Empty {};
> 
> This will export the name `Empty` to everyone, is it possible to move it to inside of the class?

`Empty` was used as the value type for the intrusive tree, but I discovered that it didn't quite work as expected, because `sizeof(Empty) == 1` due to it requiring a unique address. This means that we would waste space in a lot of cases. For example, 8-byte keys would lead to 40-byte `RBNode`s despite storing only three 8-byte pointers and one 8-byte key.

I explored an alternative approach by adding the option to use void as the value type instead, and removing the need for a value member altogether. By using a base class containing only the value and using conditional inheritance from either it or `Empty` (which benefits from [empty base optimization](https://en.cppreference.com/w/cpp/language/ebo)), we can have a zero-size overhead.

Code-wise, this solution doesn't look as clean. We need added templating and `ENABLE_IF`s for functions with value references (since `void&` doesn't work). Another positive however is that this enables key-only red-black trees for scenarios where values aren't necessary.

Let me know what you think :)

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

PR Review Comment: https://git.openjdk.org/jdk/pull/23416#discussion_r1943110358