Here's a "fun" challenge for Zig's comptime design. I have implemented the Adaptive Radix Tree and am now looking to generalize it. To save you from having to read the whole paper, it's a radix tree but inner nodes can be one of several types in an attempt to reduce node size and corresponding memory cache issues. My Zig implementation of the paper works fine, but I want to generalize so that, for instance, when using smaller key types, the types of the inner nodes can be changed. For instance, if using []const u5
, a fully dense node has only 32 children so the Node48
type doesn't make sense.
Here's a sketch of what the ART types look like with various details elided:
pub const Key = []const u8;
pub const KeySegment = u8;
pub const Payload = usize;
pub const KeySpace = std.math.maxInt(KeySegment) + 1;