RFR: 8345314: Add a red–black tree as a utility data structure [v12]

[Casper Norrbin]

On Thu, 16 Jan 2025 17:27:02 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

>> Casper Norrbin has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   clarified comment
>
> src/hotspot/share/utilities/rbTree.hpp line 55:
> 
>> 53:   class RBNode {
>> 54:     friend RBTree;
>> 55:     friend class RBTreeTest;
> 
> Is there a reason to be friends of RBTree? Even RBTreeTest?

RBTree edits the private fields of the nodes during insertion, and RBTreeTest is for more access to verification in the tests.

> src/hotspot/share/utilities/rbTree.hpp line 66:
> 
>> 64: 
>> 65:     enum Color : uint8_t { BLACK, RED };
>> 66:     Color _color;
> 
> Possibly for a future optimization. You could keep the color information as one bit overlayed in one of the pointers. That saves four to eight bytes per Node structure.
> 
> The Node pointers have to be aligned to `sizeof(void*)`, so we will always have an alignment shadow of at least two bits. If you encapsulate accessing the tagged pointer correctly, this should not be complicated.
> 
> (I believe the kernel RB tree does the same thing)

The LSB of the parent pointer now encodes the color information of the node

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920468182
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920467256