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

[Casper Norrbin]

On Thu, 9 Jan 2025 13:28:04 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

>> @caspernorrbin @jdksjolen Excellent, thank you. 
>> 
>> For the Doubting Thomas I am, could you write a little gtest like this:
>> 
>> - node (key = size) value don't matter I guess.
>> - malloc n times, with random sizes, so variable sized, but large enough to hold at least a node structure
>> - then in a loop, add or remove a randomly chosen malloc block to the tree.
>> 
>> If we survive that, I am happy and will use this in the future in Metaspace. Probably also in other areas.
>
> I realize that a simpler test would be to just create random nodes (key=size, value=this node's address), then add/remove randomly while checking that the node address still equals the node value. The old implementation would fail that test.

(Forgot to mention) I added a gtest that allocates and stores nodes together with their keys, then performs a bunch of deletions to then check that the value of the nodes remain unchanged. Can add another with addresses too to be extra safe

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

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