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

[Casper Norrbin]

On Thu, 16 Jan 2025 11:09:38 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
>
> Good work on the RB-tree implementation.
> 
> I am no expert in RB-trees but the implementation does not look obviously incorrect. And the gtest and verification looks comprehensive. (Only thing I might have extended is to randomness to also check the visitor and iterators. Something like generating a random ordered set of keys in a different container, insert them in some random order, maybe including insertions and removals of other keys and then check that the visitor and iterator visit this set correctly.) 
> 
> The RB-tree logic looks good to me.
> 
> Except for some small nits most of my feedback is about the API and the iteration.
> 
> I would like to avoid GrowableArrays in the implementation, but maybe I am missing a reason why they are preferable. If we could design the iterators to work more like standard C++ iterators (at least simplified but compatible versions) would make them more useful and ergonomic. There is also an opportunity to use such iterators as cursors and create a nice interface for using this tree in many different scenarios.
> 
> The second is if we should add more const version of the APIs to make it easier to work with the tree in const context (e.g. pass around the tree as a `const& Tree`). At least `const V* find(const K& key) const` seems useful to have a const `contains`.
> 
> Overall I think this is nice. But I would like some feedback on my comments w.r.t. the API before approving.

Thank you for reviewing @xmas92 and @tstuefe! I just pushed a bunch of changes based on your feedback, I'll reply with details on the specific comments.

Like Johan said, I'm working on an intrusive tree with cursors, and with that re-writing some of the internal logic to use those as well. That should also give more freedom of how and where nodes are allocated.

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

PR Comment: https://git.openjdk.org/jdk/pull/22360#issuecomment-2598712727