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

[Thomas Stuefe]

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

>> Nodes are now stable! This was not something I had considered, but it's possible with what Johan suggested above. Previously, keys and values were swapped around between nodes during deletion but now we re-point the node's pointers instead. With this the key and value stays constant in a node through its lifetime, given the user does not themself change the value.
>
> @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.

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

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