Hello again!
I’m hoping y’all would be willing to review some beginner code! I’m working through Crafting Interpreters (kinda) and am working on string interning, and I built a unicode code point aware string trie which can return known u32-sized integers for each individual string.
Any comments would be well appreciated, thank you!
const std = @import("std");
const rune = @import("code_point").CodePoint;
const RuneIterator = @import("code_point").Iterator;
pub const Node = struct {
alloc: std.mem.Allocator,
terminal: bool,
children: std.AutoHashMap(rune, Node),
pub fn init(self: *Node, terminal: bool, alloc: std.mem.Allocator) void {
self.alloc = alloc;
self.terminal = terminal;
self.children = std.AutoHashMap(rune, Node).init(alloc);
}
pub fn deinit(self: *Node) void {
var iter = self.children.iterator();
while (iter.next()) |entry| {
entry.value_ptr.deinit();
}
self.children.deinit();
}
pub fn insert(self: *Node, iterator: *RuneIterator) !*Node {
// if there's another character, keep walking the trie
if (iterator.next()) |r| {
const result = try self.children.getOrPut(r);
if (!result.found_existing) {
result.value_ptr.init(false, self.alloc);
}
return result.value_ptr.insert(iterator);
}
// if we hit the end of the iterator, we're a terminal
else {
self.terminal = true;
return self;
}
}
};
const Self = @This();
alloc: std.mem.Allocator,
index: std.AutoArrayHashMap(*Node, void),
root: *Node,
pub fn init(alloc: std.mem.Allocator) !Self {
const root = try alloc.create(Node);
root.init(false, alloc);
return .{
.alloc = alloc,
.index = std.AutoArrayHashMap(*Node, void).init(alloc),
.root = root,
};
}
pub fn deinit(self: *Self) void {
self.root.deinit();
self.alloc.destroy(self.root);
self.index.deinit();
}
pub fn insert(self: *Self, iterator: *RuneIterator) !u32 {
const node = try self.root.insert(iterator);
const entry = try self.index.getOrPut(node);
return @truncate(entry.index);
}
pub fn insert_string(self: *Self, input: []const u8) !u32 {
var iterator = RuneIterator{ .bytes = input };
return self.insert(&iterator);
}
test "trie stuff" {
var trie = try Self.init(std.testing.allocator);
defer trie.deinit();
const idxa = try trie.insert_string("hello");
const idxb = try trie.insert_string("goodbye");
const idxc = try trie.insert_string("hello");
try std.testing.expect(idxa == idxc);
try std.testing.expect(idxa != idxb);
}
