Skip to content

Instantly share code, notes, and snippets.

@daurnimator
Last active November 5, 2019 03:13
Show Gist options
  • Save daurnimator/832995e63e7545dad11ae6fbbbda7e10 to your computer and use it in GitHub Desktop.
Save daurnimator/832995e63e7545dad11ae6fbbbda7e10 to your computer and use it in GitHub Desktop.
// Simple byte FIFO
const std = @import("std");
const math = std.math;
const mem = std.mem;
const Allocator = mem.Allocator;
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
pub const Fifo = struct {
allocator: *Allocator,
buf: []u8,
head: usize,
count: usize,
pub fn init(allocator: *Allocator) Fifo {
return Fifo{
.allocator = allocator,
.buf = [_]u8{},
.head = 0,
.count = 0,
};
}
pub fn deinit(fifo: *Fifo) void {
fifo.allocator.free(fifo.buf);
fifo.* = undefined;
}
pub fn realign(fifo: *Fifo) void {
if (fifo.buf.len - fifo.head >= fifo.count) {
mem.copyBackwards(u8, fifo.buf[0..], fifo.buf[fifo.head..fifo.count]);
// TODO? set(fifo.buf[fifo.head..], undefined)
@memset(fifo.buf[fifo.count..].ptr, undefined, fifo.buf.len - fifo.count);
fifo.head = 0;
} else {
var tmp: [2048]u8 = undefined;
var m: usize = undefined;
var n: usize = undefined;
while (fifo.head != 0) {
n = math.min(fifo.head, tmp.len);
m = fifo.buf.len - n;
mem.copy(u8, tmp[0..], fifo.buf[0..n]);
mem.copyBackwards(u8, fifo.buf[0..], fifo.buf[n..m]);
mem.copy(u8, fifo.buf[m..], tmp[0..n]);
fifo.head -= n;
}
}
}
pub fn realloc(fifo: *Fifo, size: usize) error{OutOfMemory}!void {
if (fifo.buf.len >= size) return;
fifo.realign();
const new_size = math.ceilPowerOfTwo(usize, size) catch return error.OutOfMemory;
fifo.buf = try fifo.allocator.realloc(fifo.buf, new_size);
}
pub fn grow(fifo: *Fifo, size: usize) error{OutOfMemory}!void {
if (fifo.buf.len - fifo.count >= size) return;
return fifo.realloc(math.add(usize, fifo.count, size) catch return error.OutOfMemory);
}
/// Returns number of bytes currently in fifo
pub fn readableLen(fifo: *Fifo) usize {
return fifo.count;
}
/// Returns number of bytes available in fifo
pub fn writableLength(fifo: *Fifo) usize {
return fifo.buf.len - fifo.count;
}
/// Returns the first chunk of readable data
pub fn readable(fifo: *Fifo, allow_realign: bool) []const u8 {
if (allow_realign and fifo.head != 0 and fifo.head + fifo.count > fifo.buf.len)
fifo.realign();
return fifo.buf[fifo.head..math.min(fifo.buf.len, fifo.head + fifo.count)];
}
/// Returns the first section of writable buffer
/// Note that this may be of length 0
pub fn writable(fifo: *Fifo, allow_realign: bool) []u8 {
if (allow_realign and fifo.head != 0 and fifo.head + fifo.count < fifo.buf.len)
fifo.realign();
const tail = if (fifo.buf.len != 0) ((fifo.head + fifo.count) % fifo.buf.len) else 0;
return fifo.buf[tail..math.min(fifo.buf.len, tail + fifo.writableLength())];
}
/// Returns a readable slice from `offset` of up to length `count`
pub fn toSlice(fifo: *Fifo, offset: usize, count: usize, allow_realign: bool) []const u8 {
if (offset > fifo.count) return [_]u8{};
const n_count = math.min(count, fifo.count - offset);
if (allow_realign and fifo.head + offset < fifo.buf.len and fifo.head + offset + n_count > fifo.buf.len)
fifo.realign();
return fifo.buf[((fifo.head + offset) % fifo.buf.len)..][0..n_count];
}
/// Returns a readable slice up to but not including the passed character
pub fn tvec(fifo: *Fifo, ch: u8) []const u8 {
const slice = fifo.readable();
if (slice.len == 0) return slice;
if (mem.indexOfScalar(u8, slice, ch)) |p| {
return slice[0..p];
}
if (fifo.count > slice.len) {
if (mem.indexOfScalar(u8, fifo.base[0 .. fifo.count - slice.len], ch)) |p| {
const len = p + (fifo.buf.len - fifo.head) + 1;
fifo.realign();
return fifo.base[0..len];
}
}
return slice[0..0];
}
/// Returns a slice up to end-of-line
pub fn readLine(fifo: *Fifo) []const u8 {
return fifo.tvec('\n');
}
/// Returns a writable buffer of at least `size` bytes
pub fn writeBuffer(fifo: *Fifo, size: usize) ![]u8 {
try fifo.grow(size);
// try to avoid realigning buffer
var slice = fifo.writable(iov, false);
if (slice.len < size) {
slice = fifo.writable(iov, true);
}
return slice;
}
const autoalign = false;
/// Discard first `count` bytes of readable data
pub fn discard(fifo: *Fifo, count: usize) void {
const new_count = math.min(count, fifo.count);
fifo.head = (fifo.head + new_count) % fifo.buf.len;
// TODO: set old range to undefined? (note: may be wrapped around)
fifo.count -= new_count;
if (autoalign and fifo.count == 0)
fifo.head = 0;
}
/// Update the tail location of the buffer (usually follows use of writable/writeBuffer)
pub fn update(fifo: *Fifo, count: usize) void {
assert(fifo.count + count <= fifo.buf.len);
fifo.count += count;
}
/// Make `count` bytes available before the current read location
fn rewind(fifo: *Fifo, count: usize) !void {
const writableLength = fifo.writableLength();
if (count > writableLength) {
try fifo.grow(count - writableLength);
}
fifo.head = (fifo.head + (fifo.buf.len - new_count)) % fifo.buf.len;
fifo.count += count;
// TODO: mark as undefined? (note: may be wrapped around)
}
/// Appends the data in `src` to the fifo
pub fn write(fifo: *Fifo, src: []const u8) !void {
var src_left = src;
while (src_left.len > 0) {
const writable_slice = fifo.writable(false);
if (writable_slice.len == 0) {
try fifo.grow(src_left.len);
continue;
}
const n = math.min(writable_slice.len, src_left.len);
mem.copy(u8, writable_slice, src_left[0..n]);
fifo.update(n);
src_left = src_left[n..];
}
}
/// Peek data from the fifo into `dst`, returns number of bytes copied
pub fn peek(fifo: *Fifo, dst: []u8) usize {
var offset: usize = 0;
while (offset < dst.len) {
const slice = fifo.toSlice(offset, dst.len - offset, false);
if (slice.len == 0) break;
mem.copy(u8, dst[offset..], slice);
offset += slice.len;
}
return offset;
}
/// Read data from the fifo into `dst`, returns number of bytes copied
pub fn read(fifo: *Fifo, dst: []u8) usize {
var dst_left = dst;
while (dst_left.len > 0) {
const slice = fifo.readable(false);
if (slice.len == 0) break;
const n = math.min(slice.len, dst_left.len);
mem.copy(u8, dst_left, slice[0..n]);
fifo.discard(n);
dst_left = dst_left[n..];
}
return dst.len - dst_left.len;
}
pub fn writeByte(fifo: *Fifo, c: u8) !void {
try fifo.grow(1);
fifo.buf[(fifo.head + fifo.count) % fifo.buf.len] = c;
fifo.update(1);
}
pub fn print(fifo: *Fifo, comptime format: []const u8, args: ...) error{OutOfMemory}!void {
return std.fmt.format(fifo, error{OutOfMemory}, Fifo.write, format, args);
}
/// Place a byte back into the read stream
pub fn ungetByte(fifo: *Fifo, c: u8) !void {
try fifo.rewind(1);
fifo.base[fifo.head] = c;
}
/// Read the next byte from the fifo, advancing
pub fn readByte(fifo: *Fifo) !u8 {
if (fifo.count == 0)
return error.EndOfStream;
const c = fifo.buf[fifo.head];
fifo.discard(1);
return c;
}
/// Peek at the character at `offset`
pub fn peekByte(fifo: *Fifo, offset: usize) error{EndOfStream}!u8 {
if (offset >= fifo.count)
return error.EndOfStream;
return fifo.buf[(fifo.head + offset) % fifo.buf.len];
}
};
test "Fifo" {
var fifo = Fifo.init(debug.global_allocator);
defer fifo.deinit();
try fifo.writeByte('H');
try fifo.writeByte('E');
try fifo.writeByte('L');
try fifo.writeByte('L');
try fifo.writeByte('O');
{
var result: [5]u8 = undefined;
testing.expectEqual(usize(5), fifo.peek(&result));
testing.expectEqual("HELLO", result);
}
var i: usize = 0;
while (i < 5) : (i += 1) {
try fifo.writeByte(try fifo.peekByte(i));
}
{
var result: [10]u8 = undefined;
testing.expectEqual(usize(10), fifo.read(&result));
testing.expectEqual("HELLOHELLO", result);
}
try fifo.print("{}, {}!", "Hello", "World");
testing.expectEqualSlices(u8, "World", fifo.toSlice(7, 5, false));
{
var result: [30]u8 = undefined;
testing.expectEqual(usize(13), fifo.read(&result));
testing.expectEqualSlices(u8, "Hello, World!", result[0..13]);
}
}
@daurnimator
Copy link
Author

Merged as ziglang/zig#3592

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment