-
Notifications
You must be signed in to change notification settings - Fork 1
/
dual-list.zig
215 lines (197 loc) · 7.56 KB
/
dual-list.zig
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
const std = @import("std");
const testing = std.testing;
/// Fixed size managed buffer which stores two separate implicitly linked
/// lists of integer IDs (e.g. resource identifiers) in the same space.
/// Only uses N+2 ints of configured type. No extra space needed for links
/// between cells. The first list stores IDs currently in use, the other
/// stores currently available IDs.
///
/// Any unsigned int type is supported for IDs. The max. list capacity
/// depends on that chosen type (e.g. 255 for `u8`, 65535 for `u16`...)
///
/// Structural diagram:
/// https://mastodon.thi.ng/@toxi/111449052682849612
pub fn FixedBufferDualList(comptime SIZE: u16, comptime T: type) type {
const info = @typeInfo(T);
if (!(info == .Int and info.Int.signedness == .unsigned)) {
@compileError("unsupported type: expected an uint, but got: " ++ @typeName(T));
}
const sentinel = std.math.maxInt(T);
if (SIZE > sentinel) {
var buf: [64]u8 = undefined;
@compileError(std.fmt.bufPrint(&buf, "unsupported size: {d} (max allowed {d})", .{ SIZE, sentinel }) catch "");
}
return extern struct {
active: T = SENTINEL,
available: T = 0,
slots: [SIZE]T = undefined,
/// Sentinel value used to mark the end of a list
pub const SENTINEL = sentinel;
const Self = @This();
const Iterator = struct {
parent: *Self,
nextID: ?T,
fn init(parent: *Self) Iterator {
return Iterator{
.parent = parent,
.nextID = null,
};
}
/// Returns next ID in the active list or null if there're no
/// further items. Any newly allocated IDs *after* the first
/// call to this function will *not* be seen by this iterator
/// instance.
/// IMPORTANT: Freeing an active ID during iterator processing
/// is **only** safe to do for the ID most recently returned by
/// this function. Freeing any other ID will result in
/// undefined behavior.
pub fn next(self: *Iterator) ?T {
const id = self.nextID orelse self.parent.active;
if (id == SENTINEL) {
self.nextID = SENTINEL;
return null;
}
self.nextID = self.parent.slots[id];
return id;
}
};
/// Returns a new, fully initialized instance (see `init()`)
pub fn new() Self {
var inst = Self{};
inst.init();
return inst;
}
/// Initializes (or resets) both lists and marks all IDs as available
pub fn init(self: *Self) void {
self.active = SENTINEL;
self.available = 0;
for (1..SIZE + 1) |i| {
self.slots[i - 1] = if (i < SIZE) @intCast(i) else SENTINEL;
}
}
/// Attempts to mark the next available ID as active and if
/// successful returns it, otherwise returns null (O(1) op).
pub fn alloc(self: *Self) ?T {
const nextID = self.available;
if (nextID == SENTINEL) return null;
self.available = self.slots[nextID];
self.slots[nextID] = self.active;
self.active = nextID;
return nextID;
}
/// Attempts to mark the given ID as free/available again
/// and returns true if successful (O(n) op).
pub fn free(self: *Self, id: T) bool {
if (id >= SIZE) return false;
var prev: *T = &self.active;
var nextID = self.active;
while (true) {
if (nextID == SENTINEL) return false;
const curr = &self.slots[nextID];
if (nextID == id) {
nextID = curr.*;
prev.* = nextID;
curr.* = self.available;
self.available = id;
return true;
}
prev = curr;
nextID = self.slots[nextID];
}
}
/// Returns an iterator of all currently active IDs
pub fn iterator(self: *Self) Iterator {
return Iterator.init(self);
}
};
}
test "FixedBufferDualList" {
const ListU8 = FixedBufferDualList(4, u8);
var list = ListU8.new();
try testing.expectEqualDeep(
list,
ListU8{ .active = 255, .available = 0, .slots = [4]u8{ 1, 2, 3, 255 } },
);
try testing.expect(list.alloc() == 0);
try testing.expect(list.alloc() == 1);
try testing.expect(list.alloc() == 2);
var iter = list.iterator();
while (iter.next()) |i| {
std.debug.print("active: {d}\n", .{i});
}
try testing.expect(!list.free(100));
try testing.expect(list.free(0));
try testing.expect(!list.free(0));
try testing.expect(list.free(2));
try testing.expect(!list.free(2));
try testing.expect(list.free(1));
try testing.expect(!list.free(1));
try testing.expectEqualDeep(
list,
ListU8{ .active = 255, .available = 1, .slots = [4]u8{ 3, 2, 0, 255 } },
);
try testing.expect(list.alloc() == 1);
try testing.expect(list.alloc() == 2);
try testing.expect(list.alloc() == 0);
try testing.expect(list.alloc() == 3);
try testing.expect(list.alloc() == null);
}
test "FixedBufferDualList.iterator() basic" {
const ListU8 = FixedBufferDualList(4, u8);
var list = ListU8.new();
try testing.expect(list.alloc() == 0);
try testing.expect(list.alloc() == 1);
try testing.expect(list.alloc() == 2);
var iter = list.iterator();
try testing.expect(iter.next() == 2);
try testing.expect(iter.next() == 1);
try testing.expect(iter.next() == 0);
try testing.expect(iter.next() == null);
}
test "iterator alloc post creation" {
const ListU8 = FixedBufferDualList(4, u8);
var list = ListU8.new();
try testing.expect(list.alloc() == 0);
try testing.expect(list.alloc() == 1);
var iter = list.iterator();
try testing.expect(list.alloc() == 2);
try testing.expect(iter.next() == 2);
// alloc after 1st iter.next() will NOT be seen by iter
try testing.expect(list.alloc() == 3);
try testing.expect(iter.next() == 1);
// new iterator
iter = list.iterator();
// now should see #4...
try testing.expect(iter.next() == 3);
try testing.expect(iter.next() == 2);
}
test "iterator free" {
const ListU8 = FixedBufferDualList(4, u8);
var list = ListU8.new();
try testing.expect(list.alloc() == 0);
try testing.expect(list.alloc() == 1);
try testing.expect(list.alloc() == 2);
try testing.expect(list.alloc() == 3);
var iter = list.iterator();
try testing.expect(list.free(3));
try testing.expect(iter.next() == 2);
try testing.expect(list.free(2));
try testing.expect(iter.next() == 1);
try testing.expect(list.free(1));
try testing.expect(iter.next() == 0);
try testing.expect(list.free(0));
try testing.expect(list.alloc() == 0);
try testing.expect(iter.next() == null);
try testing.expect(list.alloc() == 1);
try testing.expect(iter.next() == null);
}
test "iterator empty" {
const ListU8 = FixedBufferDualList(4, u8);
var list = ListU8.new();
var iter = list.iterator();
try testing.expect(iter.next() == null);
// once end has been reached, new allocs must not impact iterator
// checking a special case here since list is empty so next() call is different
try testing.expect(list.alloc() == 0);
try testing.expect(iter.next() == null);
}