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

[Casper Norrbin]

On Thu, 16 Jan 2025 10:23:29 GMT, Axel Boldt-Christmas <aboldtch at openjdk.org> wrote:

>> 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.

I removed all the GAs in favour of the stack solution. In the future intrusive tree, these could be replaced with cursors instead.

>> 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.

I believe I got this from the treap, but it is not actively used anywhere. After a second look I feel like this belongs more on the caller's side. If someone would want this in the future, it would be trivial for them to implement instead.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920454567
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1920458691