1//! This is an abstraction on top of ArrayListUnmanaged primarily intended for
2//! unbounded temporary memory. Allocations must be freed last-in-first-out, but
3//! the ability for memory reuse is high.
4//!
5//! This structure allows for a mark -> append -> gather pattern, which is
6//! typically used with a block expression and it's contents, but it also allows
7//! arbitrary temporary allocations that re-use this memory space.
8pub fn Stack(comptime Base: type) type {
9 return struct {
10 const Self = @This();
11
12 list: std.ArrayListUnmanaged(Base),
13
14 pub const empty: Self = .{ .list = .empty };
15
16 pub const Mark = struct {
17 stack: *Self,
18 index: u32,
19
20 pub fn deinit(m: Mark) void {
21 if (core.runtime_safety)
22 @memset(m.slice(Base), undefined);
23 m.stack.list.shrinkRetainingCapacity(m.index);
24 }
25
26 pub fn len(m: Mark) u32 {
27 return @intCast(m.stack.list.items.len - m.index);
28 }
29
30 pub fn slice(m: Mark, comptime T: type) []T {
31 comptime assert(@alignOf(T) == @alignOf(Base));
32 comptime assert(@sizeOf(T) == @sizeOf(Base));
33 return @ptrCast(m.stack.list.items[m.index..]);
34 }
35 };
36
37 /// Mark this point of the stack, where all future appends are owned by
38 /// the mark. You can then use `slice()` to collect the appends.
39 pub fn mark(stack: *Self) Mark {
40 return .{
41 .stack = stack,
42 .index = @intCast(stack.list.items.len),
43 };
44 }
45
46 pub fn add(stack: *Self, allocator: Allocator, comptime T: type, item: T) !void {
47 comptime assert(@alignOf(T) == @alignOf(Base));
48 comptime assert(@sizeOf(T) == @sizeOf(Base));
49 try stack.list.append(allocator, @as(*const Base, @ptrCast(&item)).*);
50 }
51
52 pub fn Reserve(comptime T: type) type {
53 assert(@alignOf(T) == @alignOf(Base));
54 assert(@sizeOf(T) == @sizeOf(Base));
55
56 return struct {
57 stack: *Self,
58 start: usize,
59 len: usize,
60
61 pub fn deinit(r: @This()) void {
62 const from = r.stack.list.items[r.start + r.len ..];
63 const dest = r.stack.list.items[r.start..][0..from.len];
64 std.mem.copyForwards(u32, dest, from);
65 r.stack.list.shrinkRetainingCapacity(r.start + from.len);
66 }
67
68 pub fn at(r: @This(), i: usize) *T {
69 assert(i < r.len);
70 return @ptrCast(&r.stack.list.items[r.start + i]);
71 }
72
73 pub fn slice(r: @This()) []T {
74 return @ptrCast(r.stack.list.items[r.start..][0..r.len]);
75 }
76
77 pub fn sliceReinterpret(r: @This(), comptime Reinterpret: type) []Reinterpret {
78 assert(@alignOf(Reinterpret) == @alignOf(Base));
79 assert(@sizeOf(Reinterpret) == @sizeOf(Base));
80 return @ptrCast(r.slice());
81 }
82 };
83 }
84
85 pub fn reserve(
86 stack: *Self,
87 allocator: Allocator,
88 comptime T: type,
89 len: usize,
90 ) !Reserve(T) {
91 try stack.list.ensureUnusedCapacity(allocator, len);
92 const start = stack.list.items.len;
93 stack.list.items.len += len;
94 return .{ .stack = stack, .start = start, .len = len };
95 }
96
97 pub fn ReserveMulti(comptime types: anytype) type {
98 const Types = @TypeOf(types);
99 const fields = std.meta.fields(Types);
100 const FieldEnum = std.meta.FieldEnum(Types);
101
102 return struct {
103 stack: *Self,
104 starts: [fields.len]u32,
105 lengths: [fields.len]u32,
106
107 pub const reserve_types = types;
108
109 fn Type(comptime field: FieldEnum) type {
110 return @field(types, @tagName(field));
111 }
112
113 pub fn items(r: @This(), comptime field: FieldEnum) []Type(field) {
114 const f = comptime std.meta.fieldIndex(Types, @tagName(field)).?;
115 return @ptrCast(r.stack.list.items[r.starts[f]..][0..r.lengths[f]]);
116 }
117
118 pub fn at(r: @This(), comptime field: FieldEnum, i: usize) *Type(field) {
119 const f = comptime std.meta.fieldIndex(Types, @tagName(field)).?;
120 assert(i < r.lengths[f]);
121 return @ptrCast(&r.stack.list.items[r.starts[f] + i]);
122 }
123
124 pub fn deinit(r: @This()) void {
125 const start = r.starts[0];
126 const len = r.starts[fields.len - 1] - r.starts[0] + r.lengths[fields.len - 1];
127
128 const from = r.stack.list.items[start + len ..];
129 const dest = r.stack.list.items[start..][0..from.len];
130 std.mem.copyForwards(u32, dest, from);
131 r.stack.list.shrinkRetainingCapacity(start + from.len);
132 }
133
134 pub fn index(r: @This()) u32 {
135 return r.starts[0];
136 }
137
138 pub fn fromIndex(
139 stack: *Self,
140 start: u32,
141 lengths: [std.meta.fields(@TypeOf(types)).len]u32,
142 ) @This() {
143 var all_lengths: u32 = 0;
144 var starts: [std.meta.fields(@TypeOf(types)).len]u32 = undefined;
145 inline for (lengths, &starts) |len, *slice_start| {
146 slice_start.* = start + all_lengths;
147 all_lengths += len;
148 }
149 stack.list.items.len += all_lengths;
150 return .{ .stack = stack, .starts = starts, .lengths = lengths };
151 }
152 };
153 }
154
155 /// Same as `reserve` but able to group multiple allocations of different types
156 /// into a singular push and pop.
157 pub fn reserveMulti(
158 stack: *Self,
159 allocator: Allocator,
160 comptime types: anytype,
161 lengths: [@typeInfo(@TypeOf(types)).@"struct".fields.len]u32,
162 ) !ReserveMulti(types) {
163 var all_lengths: usize = 0;
164 var starts: [@typeInfo(@TypeOf(types)).@"struct".fields.len]u32 = undefined;
165 const start = stack.list.items.len;
166 inline for (lengths, &starts) |len, *slice_start| {
167 slice_start.* = @intCast(start + all_lengths);
168 all_lengths += len;
169 }
170 try stack.list.ensureUnusedCapacity(allocator, all_lengths);
171 stack.list.items.len += all_lengths;
172 return .{ .stack = stack, .starts = starts, .lengths = lengths };
173 }
174 };
175}
176
177const std = @import("std");
178const assert = std.debug.assert;
179const Allocator = std.mem.Allocator;
180
181const core = @import("./mod.zig");