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

[Axel Boldt-Christmas]

On Thu, 16 Jan 2025 06:58:14 GMT, Axel Boldt-Christmas <aboldtch 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 119:
> 
>> 117:     _allocator.free(node);
>> 118:     _num_nodes--;
>> 119:   }
> 
> Are we assuming that the key is always trivially destructible? Maybe we should document and statically assert this. Even if it is not, it is usually nice to call the destructor to end the objects lifetime.

I saw that this was discussed further down.

> src/hotspot/share/utilities/rbTree.hpp line 183:
> 
>> 181:     _num_nodes = 0;
>> 182:     _root = nullptr;
>> 183:   }
> 
> I feel like this could have been done recursively and using the stack as a stack. Or at least skip the heap allocation with fixed sized array `RBNode* stack[128];`.

Can probably do this for a lot of the other iteration done in this patch. I would think for most we would only need 64 entries. And even this could be written to just use at most a stack depth of 64.

> src/hotspot/share/utilities/rbTree.hpp line 236:
> 
>> 234:     RBNode* end = closest_gt(addr);
>> 235:     return Range(start, end);
>> 236:   }
> 
> This seems somewhat out of place. The signature is miss-matched from all the other APIs both in terms of the name and type.
> 
> I am wrong in that end is always the next node after start? I think the closest_gt call is unnecessary and we can simply find the next node after start.

Also note that this is not tested in the gtest.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1917890551
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1918200769
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1918210898