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
|
const std = @import("std");
const assert = std.debug.assert;
/// An intrusive first in/first out linked list.
/// The element type T must have a field called "next" of type ?*T
pub fn FIFO(comptime T: type) type {
return struct {
const Self = @This();
in: ?*T = null,
out: ?*T = null,
pub fn push(self: *Self, elem: *T) void {
assert(elem.next == null);
if (self.in) |in| {
in.next = elem;
self.in = elem;
} else {
assert(self.out == null);
self.in = elem;
self.out = elem;
}
}
pub fn pop(self: *Self) ?*T {
const ret = self.out orelse return null;
self.out = ret.next;
ret.next = null;
if (self.in == ret) self.in = null;
return ret;
}
pub fn peek(self: Self) ?*T {
return self.out;
}
/// Remove an element from the FIFO. Asserts that the element is
/// in the FIFO. This operation is O(N), if this is done often you
/// probably want a different data structure.
pub fn remove(self: *Self, to_remove: *T) void {
if (to_remove == self.out) {
_ = self.pop();
return;
}
var it = self.out;
while (it) |elem| : (it = elem.next) {
if (to_remove == elem.next) {
if (to_remove == self.in) self.in = elem;
elem.next = to_remove.next;
to_remove.next = null;
break;
}
} else unreachable;
}
};
}
test "push/pop/peek/remove" {
const testing = @import("std").testing;
const Foo = struct { next: ?*@This() = null };
var one: Foo = .{};
var two: Foo = .{};
var three: Foo = .{};
var fifo: FIFO(Foo) = .{};
fifo.push(&one);
try testing.expectEqual(@as(?*Foo, &one), fifo.peek());
fifo.push(&two);
fifo.push(&three);
try testing.expectEqual(@as(?*Foo, &one), fifo.peek());
fifo.remove(&one);
try testing.expectEqual(@as(?*Foo, &two), fifo.pop());
try testing.expectEqual(@as(?*Foo, &three), fifo.pop());
try testing.expectEqual(@as(?*Foo, null), fifo.pop());
fifo.push(&one);
fifo.push(&two);
fifo.push(&three);
fifo.remove(&two);
try testing.expectEqual(@as(?*Foo, &one), fifo.pop());
try testing.expectEqual(@as(?*Foo, &three), fifo.pop());
try testing.expectEqual(@as(?*Foo, null), fifo.pop());
fifo.push(&one);
fifo.push(&two);
fifo.push(&three);
fifo.remove(&three);
try testing.expectEqual(@as(?*Foo, &one), fifo.pop());
try testing.expectEqual(@as(?*Foo, &two), fifo.pop());
try testing.expectEqual(@as(?*Foo, null), fifo.pop());
fifo.push(&one);
fifo.push(&two);
fifo.remove(&two);
fifo.push(&three);
try testing.expectEqual(@as(?*Foo, &one), fifo.pop());
try testing.expectEqual(@as(?*Foo, &three), fifo.pop());
try testing.expectEqual(@as(?*Foo, null), fifo.pop());
}
|
