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

[Casper Norrbin]

On Tue, 28 Jan 2025 14:11:55 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

> 
> Sorry, I have not forgotten you, but am booked out with FOSDEM preparations. I can continue the review when I come back (end of next week), or the week after.
> 
> I would have liked to prod at the meat of the insertion/deletion logic more, since I remember that part being particularly fiddly. We should get this right, this needs close review.
> 
> But I don't want to hold you up, so if you feel you need to push now, go ahead. I would definitely like to look at the intrusive variant, since I expect I will use that one quite a bit.

Thank you! The intrusive tree is [done](/caspernorrbin/jdk/tree/rb-tree-intrusive), waiting for this PR. It keeps the insertion/deletion logic identical, but reworks a lot of the surrounding functions. Since the tree isn't used anywhere yet, perhaps you could have a closer look at the insertion/deletion logic then? If there are any issues we can fix it there before the tree sees any real use.

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

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