-
Notifications
You must be signed in to change notification settings - Fork 17
/
Copy pathring_buffer.zig
132 lines (105 loc) · 3.85 KB
/
ring_buffer.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
const std = @import("std");
const mem = std.mem;
const math = std.math;
const assert = std.debug.assert;
pub fn StaticRingBuffer(comptime T: type, comptime Counter: type, comptime capacity: usize) type {
assert(math.isPowerOfTwo(capacity));
return struct {
const Self = @This();
head: Counter = 0,
tail: Counter = 0,
entries: [capacity]T = undefined,
pub usingnamespace Mixin(Self, T, Counter);
};
}
pub fn DynamicRingBuffer(comptime T: type, comptime Counter: type) type {
return struct {
const Self = @This();
head: Counter = 0,
tail: Counter = 0,
entries: []T,
pub usingnamespace Mixin(Self, T, Counter);
pub fn initCapacity(gpa: *mem.Allocator, capacity: usize) !Self {
assert(math.isPowerOfTwo(capacity));
return Self{ .entries = try gpa.alloc(T, capacity) };
}
pub fn deinit(self: *Self, gpa: *mem.Allocator) void {
gpa.free(self.entries);
}
};
}
pub fn SliceRingBuffer(comptime T: type, comptime Counter: type) type {
return struct {
const Self = @This();
head: Counter = 0,
tail: Counter = 0,
entries: []T,
pub usingnamespace Mixin(Self, T);
pub fn from(slice: []T) Self {
assert(math.isPowerOfTwo(slice.len));
return Self{ .entries = slice };
}
};
}
fn Mixin(comptime Self: type, comptime T: type, comptime Counter: type) type {
return struct {
/// This routine pushes an item, and optionally returns an evicted item should
/// the insertion of the provided item overflow the existing buffer.
pub fn pushOrNull(self: *Self, item: T) ?T {
const evicted = evicted: {
if (self.count() == self.entries.len) {
break :evicted self.pop();
}
break :evicted null;
};
self.push(item);
return evicted;
}
pub fn push(self: *Self, item: T) void {
assert(self.count() < self.entries.len);
self.entries[self.head & (self.entries.len - 1)] = item;
self.head +%= 1;
}
pub fn pushOne(self: *Self) *T {
assert(self.count() < self.entries.len);
const slot = &self.entries[self.head & (self.entries.len - 1)];
self.head +%= 1;
return slot;
}
pub fn prepend(self: *Self, item: T) void {
assert(self.count() < self.entries.len);
self.entries[(self.tail -% 1) & (self.entries.len - 1)] = item;
self.tail -%= 1;
}
/// This routine pops an item from the tail of the buffer and returns it provided
/// that the buffer is not empty.
///
/// This routine is typically used in order to pop and de-initialize all items
/// stored in the buffer.
pub fn popOrNull(self: *Self) ?T {
if (self.count() == 0) return null;
return self.pop();
}
pub fn pop(self: *Self) T {
assert(self.count() > 0);
const evicted = self.entries[self.tail & (self.entries.len - 1)];
self.tail +%= 1;
return evicted;
}
pub fn get(self: Self, i: Counter) ?T {
if (i < self.tail or i >= self.head) return null;
return self.entries[i & (self.entries.len - 1)];
}
pub fn count(self: Self) usize {
return self.head -% self.tail;
}
pub fn latest(self: Self) ?T {
if (self.count() == 0) return null;
return self.entries[(self.head -% 1) & (self.entries.len - 1)];
}
pub fn oldest(self: *Self) ?T {
if (self.count() == 0) return null;
return self.entries[self.tail & (self.entries.len - 1)];
}
};
}