Proposal: Make Red-Black tree in std.rb generic

[joachimschmidt557]

At the moment, the implementation of red-black trees in the standard library are not generic and need to be embedded in other structs in order to work as intended.

https://github.com/ziglang/zig/blob/a2bb246db4c2bb88f402215d5db79a535dbff4b6/lib/std/rb.zig#L16-L27

This is in contrast to other data structures in the standard library such as the linked lists, which are generic:

https://github.com/ziglang/zig/blob/a2bb246db4c2bb88f402215d5db79a535dbff4b6/lib/std/linked_list.zig#L15

https://github.com/ziglang/zig/blob/a2bb246db4c2bb88f402215d5db79a535dbff4b6/lib/std/linked_list.zig#L164

https://github.com/ziglang/zig/blob/a2bb246db4c2bb88f402215d5db79a535dbff4b6/lib/std/atomic/queue.zig#L10

https://github.com/ziglang/zig/blob/a2bb246db4c2bb88f402215d5db79a535dbff4b6/lib/std/atomic/stack.zig#L8

Are there any downsides to making the RBTree Node and Tree data structures generic like the other pointer-oriented data structures?

[daurnimator]

This is in contrast to other data structures in the standard library such as the linked lists, which are generic

I've seen it proposed that the genericity of the other data structures should be removed. ziglang/zig#5584 is the only related issue I can find right now though

[joachimschmidt557]

I see the point in having these pointer-oriented data structures be non-generic: If we have the item stored, we can immediately access the node "containing" the item.

I would advocate for a unified handling of generics in these pointer-oriented data structures then. Either we have all of them generic or all of them non-generic. It would help with removing confusion, I think.

[tadeokondrak]

std.rb is no longer in the standard library: ziglang/zig@6368519

[data-man]

@joachimschmidt557 https://github.com/pedromsilvapt/zig-stack-vm/blob/master/src/rbt.zig