Dear Ziggers,
I’ve been hard at work this month, wrapping my head around Andrew Kelley’s programming without pointers, and around @mnemnion’s Zelda Linked Lists.
This got me wondering: if I can have heterogeneous nodes in a linked list, can’t I just shove them all in a list of arrays - one array per backing data type?
Ideally, I’d want the list to be generated at comptime:
const node_types = struct{
type_1 = type,
type_2 = type,
// etc.
};
const Storage = ArrayOfArrays(node_types);
// under the hood:
const Storage = [_]Arrays{
array_type_1 = [_]type_1,
arary_type_2 = [_]type_2,
}
Well, there’s the multi array list and its tagged-unions for that.
Yes and no - in some cases, the memory occupation of a tagged-union doesn’t justify the use of a multi-array list. This particularity has badly plagued some of my projects.
So I set out to building this exploratory library: TreeList.
I wrote some blog posts to detail the adventure:
part1: the basic design
part2: how the array pool woks
part3: traversing trees in zig
part4: performance shoot-out with the multi array list
A little example usage from the tests:
// Create TreeList instance
const Tree = TreeList(NodeTypes);
var tree: Tree = .empty;
tree.init();
defer tree.deinit(std.testing.allocator);
// Create and add a root node
const int_loc = try tree.append(Tree.Reg.idFromType(IntNode), .{ .value = 42 }, std.testing.allocator);
try tree.addRoot("root", int_loc, std.testing.allocator);
// Create and add a child node
const float_loc = try tree.append(Tree.Reg.idFromType(FloatNode), .{ .value = 3.14 }, std.testing.allocator);
tree.addChild(int_loc, float_loc);
// Retrieve the root node
const root_loc = tree.getRoot("root") orelse return std.testing.expect(false);
const root_node = tree.getNodeAs(IntNode, root_loc).?;
try std.testing.expectEqual(@as(i32, 42), root_node.value);
// Get the child node by traversing from root
const child_u64 = root_node.child orelse return std.testing.expect(false);
const child_loc = Tree.Loc.fromU64(child_u64);
try std.testing.expectEqual(child_u64, float_loc.toU64());
Hope you like it!