zig/lib/std /
fifo.zig
// FIFO of fixed size items
// Usually used for e.g. byte buffers
const std = @import("std");
const math = std.math;
const mem = std.mem;
const Allocator = mem.Allocator;
const assert = std.debug.assert;
const testing = std.testing;
LinearFifoBufferType
pub const LinearFifoBufferType = union(enum) {
Static: usize,
Slice,
Dynamic,
};
LinearFifo()
The buffer is internal to the fifo; it is of the specified size. The buffer is passed as a slice to the initialiser. The buffer is managed dynamically using a mem.Allocator.
pub fn LinearFifo(
comptime T: type,
comptime buffer_type: LinearFifoBufferType,
) type {
const autoalign = false;
const powers_of_two = switch (buffer_type) {
.Static => std.math.isPowerOfTwo(buffer_type.Static),
.Slice => false, // Any size slice could be passed in
.Dynamic => true, // This could be configurable in future
};
return struct {
allocator: if (buffer_type == .Dynamic) Allocator else void,
buf: if (buffer_type == .Static) [buffer_type.Static]T else []T,
head: usize,
count: usize,
const Self = @This();
pub const Reader = std.io.Reader(*Self, error{}, readFn);
pub const Writer = std.io.Writer(*Self, error{OutOfMemory}, appendWrite);
// Type of Self argument for slice operations.
// If buffer is inline (Static) then we need to ensure we haven't
// returned a slice into a copy on the stack
const SliceSelfArg = if (buffer_type == .Static) *Self else Self;
pub usingnamespace switch (buffer_type) {
.Static => struct {
init()
pub fn init() Self {
return .{
.allocator = {},
.buf = undefined,
.head = 0,
.count = 0,
};
}
},
.Slice => struct {
init()
pub fn init(buf: []T) Self {
return .{
.allocator = {},
.buf = buf,
.head = 0,
.count = 0,
};
}
},
.Dynamic => struct {
init()
pub fn init(allocator: Allocator) Self {
return .{
.allocator = allocator,
.buf = &[_]T{},
.head = 0,
.count = 0,
};
}
},
};
deinit()
pub fn deinit(self: Self) void {
if (buffer_type == .Dynamic) self.allocator.free(self.buf);
}
realign()
pub fn realign(self: *Self) void {
if (self.buf.len - self.head >= self.count) {
mem.copyForwards(T, self.buf[0..self.count], self.buf[self.head..][0..self.count]);
self.head = 0;
} else {
var tmp: [mem.page_size / 2 / @sizeOf(T)]T = undefined;
while (self.head != 0) {
const n = @min(self.head, tmp.len);
const m = self.buf.len - n;
@memcpy(tmp[0..n], self.buf[0..n]);
mem.copyForwards(T, self.buf[0..m], self.buf[n..][0..m]);
@memcpy(self.buf[m..][0..n], tmp[0..n]);
self.head -= n;
}
}
{ // set unused area to undefined
const unused = mem.sliceAsBytes(self.buf[self.count..]);
@memset(unused, undefined);
}
}
shrink()
Reduce allocated capacity to size.
pub fn shrink(self: *Self, size: usize) void {
assert(size >= self.count);
if (buffer_type == .Dynamic) {
self.realign();
self.buf = self.allocator.realloc(self.buf, size) catch |e| switch (e) {
error.OutOfMemory => return, // no problem, capacity is still correct then.
};
}
}
ensureTotalCapacity()
Ensure that the buffer can fit at least size items
pub fn ensureTotalCapacity(self: *Self, size: usize) !void {
if (self.buf.len >= size) return;
if (buffer_type == .Dynamic) {
self.realign();
const new_size = if (powers_of_two) math.ceilPowerOfTwo(usize, size) catch return error.OutOfMemory else size;
self.buf = try self.allocator.realloc(self.buf, new_size);
} else {
return error.OutOfMemory;
}
}
ensureUnusedCapacity()
Makes sure at least size items are unused
pub fn ensureUnusedCapacity(self: *Self, size: usize) error{OutOfMemory}!void {
if (self.writableLength() >= size) return;
return try self.ensureTotalCapacity(math.add(usize, self.count, size) catch return error.OutOfMemory);
}
readableLength()
Returns number of items currently in fifo
pub fn readableLength(self: Self) usize {
return self.count;
}
fn readableSliceMut(self: SliceSelfArg, offset: usize) []T {
if (offset > self.count) return &[_]T{};
var start = self.head + offset;
if (start >= self.buf.len) {
start -= self.buf.len;
return self.buf[start .. start + (self.count - offset)];
} else {
const end = @min(self.head + self.count, self.buf.len);
return self.buf[start..end];
}
}
readableSlice()
Returns a writable slice from the 'read' end of the fifo Returns a readable slice from offset
pub fn readableSlice(self: SliceSelfArg, offset: usize) []const T {
return self.readableSliceMut(offset);
}
readableSliceOfLen()
pub fn readableSliceOfLen(self: *Self, len: usize) []const T {
assert(len <= self.count);
const buf = self.readableSlice(0);
if (buf.len >= len) {
return buf[0..len];
} else {
self.realign();
return self.readableSlice(0)[0..len];
}
}
discard()
Discard first count items in the fifo
pub fn discard(self: *Self, count: usize) void {
assert(count <= self.count);
{ // set old range to undefined. Note: may be wrapped around
const slice = self.readableSliceMut(0);
if (slice.len >= count) {
const unused = mem.sliceAsBytes(slice[0..count]);
@memset(unused, undefined);
} else {
const unused = mem.sliceAsBytes(slice[0..]);
@memset(unused, undefined);
const unused2 = mem.sliceAsBytes(self.readableSliceMut(slice.len)[0 .. count - slice.len]);
@memset(unused2, undefined);
}
}
if (autoalign and self.count == count) {
self.head = 0;
self.count = 0;
} else {
var head = self.head + count;
if (powers_of_two) {
// Note it is safe to do a wrapping subtract as
// bitwise & with all 1s is a noop
head &= self.buf.len -% 1;
} else {
head %= self.buf.len;
}
self.head = head;
self.count -= count;
}
}
readItem()
Read the next item from the fifo
pub fn readItem(self: *Self) ?T {
if (self.count == 0) return null;
const c = self.buf[self.head];
self.discard(1);
return c;
}
read()
Read data from the fifo into dst, returns number of items copied.
pub fn read(self: *Self, dst: []T) usize {
var dst_left = dst;
while (dst_left.len > 0) {
const slice = self.readableSlice(0);
if (slice.len == 0) break;
const n = @min(slice.len, dst_left.len);
@memcpy(dst_left[0..n], slice[0..n]);
self.discard(n);
dst_left = dst_left[n..];
}
return dst.len - dst_left.len;
}
fn readFn(self: *Self, dest: []u8) error{}!usize {
return self.read(dest);
}
reader()
Same as read except it returns an error union The purpose of this function existing is to match std.io.Reader API.
pub fn reader(self: *Self) Reader {
return .{ .context = self };
}
writableLength()
Returns number of items available in fifo
pub fn writableLength(self: Self) usize {
return self.buf.len - self.count;
}
writableSlice()
Returns the first section of writable buffer. Note that this may be of length 0
pub fn writableSlice(self: SliceSelfArg, offset: usize) []T {
if (offset > self.buf.len) return &[_]T{};
const tail = self.head + offset + self.count;
if (tail < self.buf.len) {
return self.buf[tail..];
} else {
return self.buf[tail - self.buf.len ..][0 .. self.writableLength() - offset];
}
}
writableWithSize()
Returns a writable buffer of at least size items, allocating memory as needed. Use fifo.update once you've written data to it.
pub fn writableWithSize(self: *Self, size: usize) ![]T {
try self.ensureUnusedCapacity(size);
// try to avoid realigning buffer
var slice = self.writableSlice(0);
if (slice.len < size) {
self.realign();
slice = self.writableSlice(0);
}
return slice;
}
update()
Update the tail location of the buffer (usually follows use of writable/writableWithSize)
pub fn update(self: *Self, count: usize) void {
assert(self.count + count <= self.buf.len);
self.count += count;
}
writeAssumeCapacity()
Appends the data in src to the fifo. You must have ensured there is enough space.
pub fn writeAssumeCapacity(self: *Self, src: []const T) void {
assert(self.writableLength() >= src.len);
var src_left = src;
while (src_left.len > 0) {
const writable_slice = self.writableSlice(0);
assert(writable_slice.len != 0);
const n = @min(writable_slice.len, src_left.len);
@memcpy(writable_slice[0..n], src_left[0..n]);
self.update(n);
src_left = src_left[n..];
}
}
writeItem()
Write a single item to the fifo
pub fn writeItem(self: *Self, item: T) !void {
try self.ensureUnusedCapacity(1);
return self.writeItemAssumeCapacity(item);
}
writeItemAssumeCapacity()
pub fn writeItemAssumeCapacity(self: *Self, item: T) void {
var tail = self.head + self.count;
if (powers_of_two) {
tail &= self.buf.len - 1;
} else {
tail %= self.buf.len;
}
self.buf[tail] = item;
self.update(1);
}
write()
Appends the data in src to the fifo. Allocates more memory as necessary
pub fn write(self: *Self, src: []const T) !void {
try self.ensureUnusedCapacity(src.len);
return self.writeAssumeCapacity(src);
}
fn appendWrite(self: *Self, bytes: []const u8) error{OutOfMemory}!usize {
try self.write(bytes);
return bytes.len;
}
writer()
Same as write except it returns the number of bytes written, which is always the same as bytes.len. The purpose of this function existing is to match std.io.Writer API.
pub fn writer(self: *Self) Writer {
return .{ .context = self };
}
fn rewind(self: *Self, count: usize) void {
assert(self.writableLength() >= count);
var head = self.head + (self.buf.len - count);
if (powers_of_two) {
head &= self.buf.len - 1;
} else {
head %= self.buf.len;
}
self.head = head;
self.count += count;
}
unget()
Make count items available before the current read location Place data back into the read stream
pub fn unget(self: *Self, src: []const T) !void {
try self.ensureUnusedCapacity(src.len);
self.rewind(src.len);
const slice = self.readableSliceMut(0);
if (src.len < slice.len) {
@memcpy(slice[0..src.len], src);
} else {
@memcpy(slice, src[0..slice.len]);
const slice2 = self.readableSliceMut(slice.len);
@memcpy(slice2[0 .. src.len - slice.len], src[slice.len..]);
}
}
peekItem()
Returns the item at offset. Asserts offset is within bounds.
pub fn peekItem(self: Self, offset: usize) T {
assert(offset < self.count);
var index = self.head + offset;
if (powers_of_two) {
index &= self.buf.len - 1;
} else {
index %= self.buf.len;
}
return self.buf[index];
}
pump()
Pump data from a reader into a writer. Stops when reader returns 0 bytes (EOF). Buffer size must be set before calling; a buffer length of 0 is invalid.
pub fn pump(self: *Self, src_reader: anytype, dest_writer: anytype) !void {
assert(self.buf.len > 0);
while (true) {
if (self.writableLength() > 0) {
const n = try src_reader.read(self.writableSlice(0));
if (n == 0) break; // EOF
self.update(n);
}
self.discard(try dest_writer.write(self.readableSlice(0)));
}
// flush remaining data
while (self.readableLength() > 0) {
self.discard(try dest_writer.write(self.readableSlice(0)));
}
}
toOwnedSlice()
pub fn toOwnedSlice(self: *Self) Allocator.Error![]T {
if (self.head != 0) self.realign();
assert(self.head == 0);
assert(self.count <= self.buf.len);
const allocator = self.allocator;
if (allocator.resize(self.buf, self.count)) {
const result = self.buf[0..self.count];
self.* = Self.init(allocator);
return result;
}
const new_memory = try allocator.dupe(T, self.buf[0..self.count]);
allocator.free(self.buf);
self.* = Self.init(allocator);
return new_memory;
}
};
}
Test:
LinearFifo(u8, .Dynamic) discard(0) from empty buffer should not error on overflow
test "LinearFifo(u8, .Dynamic) discard(0) from empty buffer should not error on overflow" {
var fifo = LinearFifo(u8, .Dynamic).init(testing.allocator);
defer fifo.deinit();
// If overflow is not explicitly allowed this will crash in debug / safe mode
fifo.discard(0);
}
Test:
LinearFifo(u8, .Dynamic)
test "LinearFifo(u8, .Dynamic)" {
var fifo = LinearFifo(u8, .Dynamic).init(testing.allocator);
defer fifo.deinit();
try fifo.write("HELLO");
try testing.expectEqual(@as(usize, 5), fifo.readableLength());
try testing.expectEqualSlices(u8, "HELLO", fifo.readableSlice(0));
{
var i: usize = 0;
while (i < 5) : (i += 1) {
try fifo.write(&[_]u8{fifo.peekItem(i)});
}
try testing.expectEqual(@as(usize, 10), fifo.readableLength());
try testing.expectEqualSlices(u8, "HELLOHELLO", fifo.readableSlice(0));
}
{
try testing.expectEqual(@as(u8, 'H'), fifo.readItem().?);
try testing.expectEqual(@as(u8, 'E'), fifo.readItem().?);
try testing.expectEqual(@as(u8, 'L'), fifo.readItem().?);
try testing.expectEqual(@as(u8, 'L'), fifo.readItem().?);
try testing.expectEqual(@as(u8, 'O'), fifo.readItem().?);
}
try testing.expectEqual(@as(usize, 5), fifo.readableLength());
{ // Writes that wrap around
try testing.expectEqual(@as(usize, 11), fifo.writableLength());
try testing.expectEqual(@as(usize, 6), fifo.writableSlice(0).len);
fifo.writeAssumeCapacity("6Test:
LinearFifo
test "LinearFifo" {
inline for ([_]type{ u1, u8, u16, u64 }) |T| {
inline for ([_]LinearFifoBufferType{ LinearFifoBufferType{ .Static = 32 }, .Slice, .Dynamic }) |bt| {
const FifoType = LinearFifo(T, bt);
var buf: if (bt == .Slice) [32]T else void = undefined;
var fifo = switch (bt) {
.Static => FifoType.init(),
.Slice => FifoType.init(buf[0..]),
.Dynamic => FifoType.init(testing.allocator),
};
defer fifo.deinit();
try fifo.write(&[_]T{ 0, 1, 1, 0, 1 });
try testing.expectEqual(@as(usize, 5), fifo.readableLength());
{
try testing.expectEqual(@as(T, 0), fifo.readItem().?);
try testing.expectEqual(@as(T, 1), fifo.readItem().?);
try testing.expectEqual(@as(T, 1), fifo.readItem().?);
try testing.expectEqual(@as(T, 0), fifo.readItem().?);
try testing.expectEqual(@as(T, 1), fifo.readItem().?);
try testing.expectEqual(@as(usize, 0), fifo.readableLength());
}
{
try fifo.writeItem(1);
try fifo.writeItem(1);
try fifo.writeItem(1);
try testing.expectEqual(@as(usize, 3), fifo.readableLength());
}
{
var readBuf: [3]T = undefined;
const n = fifo.read(&readBuf);
try testing.expectEqual(@as(usize, 3), n); // NOTE: It should be the number of items.
}
}
}
}