RFR: 8345314: Add a red–black tree as a utility data structure [v13]
Thomas Stuefe
stuefe at openjdk.org
Tue Jan 28 14:15:06 UTC 2025
On Fri, 17 Jan 2025 16:15:18 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:
>> Hi everyone,
>>
>> This effort began as an exploration of replacing the current NMT treap with a red-black tree. Along the way, I discovered that others were also interested in having a general-purpose tree structure available within HotSpot.
>>
>> The red-black tree is designed to serve as a drop-in replacement for the existing NMT treap, keeping a nearly identical interface. However, I’ve also added a few additional requested features, such as an iterator.
>>
>> Testing builds off the treap tests, adding a few extra that inserts/removes and checks that the tree is correct. Testing uses the function `verify_self`, which iterates over the tree and checks that all red-black tree properties hold. Additionally, the tree has been tested in vmatree instead of the treap without any errors.
>>
>> For those who may want to revisit the fundamentals of red-black trees, [Wikipedia](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) offers a great summary with tables covering the various balancing cases. Alternatively, your favorite data structure book could provide even more insight.
>
> Casper Norrbin has updated the pull request incrementally with two additional commits since the last revision:
>
> - thomas feedback
> - axel feedback
src/hotspot/share/utilities/rbTree.hpp line 76:
> 74:
> 75: void set_black() { _parent = _parent | 0x1; }
> 76: void set_red() { _parent = _parent & ~0x1; }
Why not just |= and &= ?
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1923165338
More information about the hotspot-dev
mailing list