summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main.zig2
-rw-r--r--src/zisp/gc/ListPool.zig58
-rw-r--r--src/zisp/gc/seg_stack.zig84
-rw-r--r--src/zisp/io/Printer.zig8
-rw-r--r--src/zisp/value.zig6
-rw-r--r--src/zisp/value/list.zig7
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);
}
generated by cgit v1.2.3 (git 2.39.1) at 2026-08-05 01:06:43 +0000