From f6385a0b3cae394aa8e21d7899fd22f0176c43e4 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Tue, 23 Jun 2026 19:26:57 +0200 Subject: Move seg_stack to lib. --- src/zisp/gc/ListPool.zig | 2 +- src/zisp/gc/seg_stack.zig | 84 ---------------------------------------------- src/zisp/io/Parser.zig | 2 -- src/zisp/lib.zig | 1 + src/zisp/lib/seg_stack.zig | 84 ++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 86 insertions(+), 87 deletions(-) delete mode 100644 src/zisp/gc/seg_stack.zig create mode 100644 src/zisp/lib/seg_stack.zig diff --git a/src/zisp/gc/ListPool.zig b/src/zisp/gc/ListPool.zig index 0735582..668735d 100644 --- a/src/zisp/gc/ListPool.zig +++ b/src/zisp/gc/ListPool.zig @@ -14,7 +14,7 @@ const Alloc = std.mem.Allocator; const ArrayList = std.ArrayListUnmanaged; const value = @import("../value.zig"); -const seg_stack = @import("seg_stack.zig"); +const seg_stack = @import("../lib/seg_stack.zig"); const Value = value.Value; const SegStack = seg_stack.SegStack; diff --git a/src/zisp/gc/seg_stack.zig b/src/zisp/gc/seg_stack.zig deleted file mode 100644 index 0867892..0000000 --- a/src/zisp/gc/seg_stack.zig +++ /dev/null @@ -1,84 +0,0 @@ -//! 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/Parser.zig b/src/zisp/io/Parser.zig index 53a7b8c..cddd397 100644 --- a/src/zisp/io/Parser.zig +++ b/src/zisp/io/Parser.zig @@ -82,8 +82,6 @@ pub const Error = enum { OutOfRange, }; -// TODO: Use SegStack for context stack - pub const Context = struct { /// What to do next. next: ?Fn = undefined, diff --git a/src/zisp/lib.zig b/src/zisp/lib.zig index 7752110..75c52ea 100644 --- a/src/zisp/lib.zig +++ b/src/zisp/lib.zig @@ -1 +1,2 @@ pub const list = @import("lib/list.zig"); +pub const seg_stack = @import("lib/seg_stack.zig"); diff --git a/src/zisp/lib/seg_stack.zig b/src/zisp/lib/seg_stack.zig new file mode 100644 index 0000000..0867892 --- /dev/null +++ b/src/zisp/lib/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]; + } + }; +} -- cgit v1.2.3