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

[Johan Sjölen]

On Wed, 5 Feb 2025 15:01:58 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

>> 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 :)

Yeah, it's a bit "ugly", but I'm willing to pay the price for a little bit of complexity in order to have this feature work as expected. Please add "empty base optimization" as a phrase in a comment regarding this, so that people can find out on their own why the code looks as it does.

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

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