yippie

6 files changed, 138 insertions, 27 deletions

diff --git a/src/main.zig b/src/main.zig
index 592d317..e601020 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -39,5 +39,7 @@ pub fn main() !u8 {
         try zisp.io.print(writer, datum);
         try writer.writeAll("\n");
         try writer.flush();
+
+        if (datum.isList()) try zisp.value.list.free(datum);
     }
 }
diff --git a/src/zisp/gc/ListPool.zig b/src/zisp/gc/ListPool.zig
index 6c34074..a843ae5 100644
--- a/src/zisp/gc/ListPool.zig
+++ b/src/zisp/gc/ListPool.zig
@@ -14,52 +14,70 @@ const Alloc = std.mem.Allocator;
 const ArrayList = std.ArrayListUnmanaged;
 
 const value = @import("../value.zig");
+const seg_stack = @import("seg_stack.zig");
 
 const Value = value.Value;
+const SegStack = seg_stack.SegStack;
 
 const Self = @This();
 
-// How many Value elements fit in a block. A good value should be 512, since
-// each Value is 8 bytes: 512 * 8 = 4 KiB
+/// How many Value elements fit in a block. A good value should be 512, since
+/// each Value is 8 bytes: 512 * 8 = 4 KiB
 const block_value_cap = 512;
 
-// Initial capacity of ArrayList of pointers to filled blocks.  Also 512, since
-// pointers are 8 bytes as well.
-const def_full_blocks_cap = 512;
-
 const Block = [block_value_cap]Value;
 
 alloc: Alloc,
 
 current_block: *Block,
-current_index: usize,
+current_index: usize = 0,
 
-full_blocks: ArrayList(*Block),
+full_list: SegStack(*Block, 4096),
+free_lists: [7]SegStack([*]Value, 512),
 
 pub fn init(alloc: Alloc) !Self {
     return .{
         .alloc = alloc,
         .current_block = try alloc.create(Block),
-        .current_index = 0,
-        .full_blocks = try .initCapacity(alloc, def_full_blocks_cap),
+        .full_list = try .init(alloc),
+        .free_lists = .{
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+        },
     };
 }
 
 pub fn deinit(self: *Self) void {
+    for (self.free_lists) |l| l.deinit(self.alloc);
+    while (self.full_list.pop(self.alloc)) |block| self.alloc.destroy(block);
+    self.full_list.deinit(self.alloc);
     self.alloc.destroy(self.current_block);
-    for (self.full_blocks) |block| self.alloc.destroy(block);
-    self.full_blocks.deinit(self.alloc);
 }
 
 fn newBlock(self: *Self) !void {
-    try self.full_blocks.append(self.alloc, self.current_block);
+    try self.full_list.push(self.alloc, self.current_block);
     self.current_block = try self.alloc.create(Block);
     self.current_index = 0;
 }
 
-pub fn create(self: *Self, len: u3) ![*]Value {
+fn popFree(self: *Self, len: u3) ?[*]Value {
+    return self.free_lists[len - 1].pop(self.alloc);
+}
+
+fn pushFree(self: *Self, len: u3, ptr: [*]Value) !void {
+    try self.free_lists[len - 1].push(self.alloc, ptr);
+}
+
+pub fn allocVals(self: *Self, len: u3) ![*]Value {
     std.debug.assert(len != 0);
 
+    if (self.popFree(len)) |ptr| return ptr;
+
     if (len > block_value_cap - self.current_index) {
         try self.newBlock();
     }
@@ -67,3 +85,15 @@ pub fn create(self: *Self, len: u3) ![*]Value {
     defer self.current_index += len;
     return @ptrCast(&self.current_block[self.current_index]);
 }
+
+pub fn freeVals(self: *Self, len: u3, ptr: [*]Value) !void {
+    std.debug.assert(len != 0);
+
+    try self.pushFree(len, ptr);
+}
+
+pub fn freeList(self: *Self, list: Value) !void {
+    const len = value.list.getLenTag(list);
+    const ptr = value.list.getValPtr(list);
+    try self.freeVals(len, ptr);
+}
diff --git a/src/zisp/gc/seg_stack.zig b/src/zisp/gc/seg_stack.zig
new file mode 100644
index 0000000..0867892
--- /dev/null
+++ b/src/zisp/gc/seg_stack.zig
@@ -0,0 +1,84 @@
+//! Segmented linked list backed stack
+
+const std = @import("std");
+
+const Alloc = std.mem.Allocator;
+
+/// Segmented linked list backed stack
+pub fn SegStack(T: type, seg_max_bytes: usize) type {
+    const seg_size: usize = (seg_max_bytes - @sizeOf(usize)) / @sizeOf(T);
+
+    comptime {
+        if (seg_size < 4) {
+            @panic("Surely you didn't want to have segments this small?");
+        }
+    }
+
+    const Node = struct {
+        const Self = @This();
+
+        prev: ?*Self = null,
+        elts: [seg_size]T = undefined,
+
+        pub fn new(alloc: Alloc) !*Self {
+            const self = try alloc.create(Self);
+            self.* = .{};
+            return self;
+        }
+    };
+
+    return struct {
+        const Self = @This();
+
+        head: *Node,
+        idx: usize = 0,
+
+        // To prevent "thrashing" we don't immediately deallocate the current
+        // node when it's emptied but rather save it aside.
+        aside: ?*Node = null,
+
+        pub fn init(alloc: Alloc) !Self {
+            return .{ .head = try .new(alloc) };
+        }
+
+        pub fn deinit(self: *Self, alloc: Alloc) void {
+            if (self.aside) |aside| alloc.destroy(aside);
+            var node: ?Node = self.head;
+            while (node) |n| {
+                alloc.destroy(n);
+                node = n.prev;
+            }
+        }
+
+        pub fn push(self: *Self, alloc: Alloc, elt: T) !void {
+            if (self.idx == seg_size) {
+                if (self.aside) |aside| {
+                    self.head = aside;
+                    self.aside = null;
+                } else {
+                    const prev = self.head;
+                    self.head = try .new(alloc);
+                    self.head.prev = prev;
+                }
+                self.idx = 0;
+            }
+            self.head.elts[self.idx] = elt;
+            self.idx += 1;
+        }
+
+        pub fn pop(self: *Self, alloc: Alloc) ?T {
+            if (self.idx == 0) {
+                if (self.head.prev) |prev| {
+                    if (self.aside) |aside| alloc.destroy(aside);
+                    self.aside = self.head;
+                    self.head = prev;
+                    self.idx = seg_size;
+                } else {
+                    return null;
+                }
+            }
+            self.idx -= 1;
+            return self.head.elts[self.idx];
+        }
+    };
+}
diff --git a/src/zisp/io/Printer.zig b/src/zisp/io/Printer.zig
index 4b06005..abc4ebc 100644
--- a/src/zisp/io/Printer.zig
+++ b/src/zisp/io/Printer.zig
@@ -237,13 +237,7 @@ fn printListDirect(p: *Printer, len: u3, vals: [*]Value) !void {
             close = "}";
             i = 1;
         },
-        else => {
-            if (vals[0].isRune()) {
-                try p.printRune(vals[0]);
-                i = 1;
-            }
-            try p.write("(");
-        },
+        else => try p.write("("),
     }
 
     if (len != 0) {
diff --git a/src/zisp/value.zig b/src/zisp/value.zig
index 4ff683a..4ce6cd2 100644
--- a/src/zisp/value.zig
+++ b/src/zisp/value.zig
@@ -265,15 +265,11 @@ pub const Value = packed union {
         const ptr_bits: u20 = hi16_tag_ptr;
         const tag_bits: u20 = @intFromEnum(ht);
         if (hi20_bits != ptr_bits << 4 | tag_bits) return null;
-
-        // A zero payload value here would actually indicate that the value is
-        // not a pointer at all, but the Positive cqNaN value; this is totally
-        // fine, because @ptrFromInt() turns zero into null anyway.
         return @ptrFromInt(v.bits << 20 >> 16);
     }
 
     /// Checks for a pointer and returns the value and tag separately, or null
-    /// if this isn't a pointer at all.  Could be useful for a dispatch table.
+    /// if this isn't a pointer or null.  Could be useful for a dispatch table.
     pub fn getPtrAny(v: Value) ?struct { Zptr, HeapType } {
         const hi16_bits: u16 = @intCast(v.bits >> 48);
         if (hi16_bits != hi16_tag_ptr) return null;
diff --git a/src/zisp/value/list.zig b/src/zisp/value/list.zig
index d040a34..52c665e 100644
--- a/src/zisp/value/list.zig
+++ b/src/zisp/value/list.zig
@@ -26,7 +26,7 @@ pub fn assert(v: Value) void {
 pub fn new(alloc: Alloc, pool: ?*ListPool, vals: []const Value) !Value {
     var len_tagged_ptr: u48 = undefined;
     if (vals.len < 8 and pool != null) {
-        const ptr = try pool.?.create(@intCast(vals.len));
+        const ptr = try pool.?.allocVals(@intCast(vals.len));
         for (vals, 0..) |v, i| ptr[i] = v;
         len_tagged_ptr = @intCast(@intFromPtr(ptr) | vals.len);
     } else {
@@ -38,6 +38,11 @@ pub fn new(alloc: Alloc, pool: ?*ListPool, vals: []const Value) !Value {
     return .{ .list = .{ .len_tagged_ptr = len_tagged_ptr } };
 }
 
+// TODO: this is just a test
+pub fn free(list: Value) !void {
+    try gc.mainListPool().freeList(list);
+}
+
 pub fn getLenTag(v: Value) u3 {
     return @truncate(v.bits);
 }