Skip to content

Instantly share code, notes, and snippets.

@likern
Created February 4, 2022 11:53
Show Gist options
  • Save likern/ac01b315434c68622f70cc0228863971 to your computer and use it in GitHub Desktop.
Save likern/ac01b315434c68622f70cc0228863971 to your computer and use it in GitHub Desktop.
const std = @import("std");
const assert = std.debug.assert;
const expect = std.testing.expect;
const expectError = std.testing.expectError;
const Allocator = std.mem.Allocator;
const RingBuffer = @import("./RingBuffer.zig");
pub const QueueCreateError = std.mem.Allocator.Error;
pub const QueueEnqueueError = error{IsFull};
pub const QueueDequeueError = error{IsEmpty};
pub fn Queue(comptime T: type) type {
return struct {
const Self = @This();
__ring_buffer: RingBuffer(T),
__allocator: Allocator,
/// Create new queue with max capacity of elements.
pub fn create(allocator: Allocator, _capacity: usize) QueueCreateError!Self {
const ring_buffer = try RingBuffer(T).create(allocator, _capacity); // <-- THIS FAILS
errdefer ring_buffer.delete();
return Self{ .__ring_buffer = ring_buffer, .__allocator = allocator };
}
// Delete queue
pub fn delete(self: *Self) void {
self.__ring_buffer.delete();
}
pub fn capacity(self: *const Self) usize {
return self.__ring_buffer.capacity();
}
pub fn length(self: *const Self) usize {
return self.__ring_buffer.length();
}
pub fn full(self: *const Self) bool {
return self.__ring_buffer.full();
}
pub fn empty(self: *const Self) bool {
return self.__ring_buffer.empty();
}
pub fn reset(self: *Self) void {
self.__ring_buffer.reset();
}
/// Add element to queue.
pub fn enqueue(self: *Self, item: T) QueueEnqueueError!void {
const result = self.__ring_buffer.add(item);
if (result) |_| {} else |err| {
return err;
}
}
/// Delete first inserted element from queue.
pub fn dequeue(self: *Self) QueueDequeueError!T {
const result = self.__ring_buffer.remove();
if (result) |value| {
return value;
} else |err| {
return err;
}
}
};
}
test "empty queue invariants" {
const QueueOfInts = Queue(u64);
try QueueOfInts.create(std.testing.allocator, 8);
}
const std = @import("std");
const assert = std.debug.assert;
const expect = std.testing.expect;
const expectError = std.testing.expectError;
const Allocator = std.mem.Allocator;
pub const RingBufferCreateError = std.mem.Allocator.Error;
pub const RingBufferAddError = error{IsFull};
pub const RingBufferRemoveError = error{IsEmpty};
pub fn RingBuffer(comptime T: type) type {
return struct {
const Self = @This();
__head: usize,
__tail: usize,
__length: usize,
__buffer: []T,
__allocator: Allocator,
pub fn create(allocator: Allocator, _capacity: usize) RingBufferCreateError!Self {
const buffer = try allocator.alloc(T, _capacity);
errdefer allocator.free(buffer);
return Self{
.__head = 0,
.__tail = 0,
.__length = 0,
.__buffer = buffer,
.__allocator = allocator,
};
}
pub fn delete(self: *Self) void {
self.__allocator.free(self.__buffer);
}
pub fn capacity(self: *const Self) usize {
return self.__buffer.len;
}
pub fn length(self: *const Self) usize {
return self.__length;
}
pub fn full(self: *const Self) bool {
return self.__length == self.__buffer.len;
}
pub fn empty(self: *const Self) bool {
return self.__length == 0;
}
pub fn reset(self: *Self) void {
self.__head = 0;
self.__tail = 0;
self.__length = 0;
}
/// Allow to overflow the least recently inserted data,
/// if ring is full.
pub fn addOverflow(self: *Self, item: T) void {
assert(self.__head >= 0 and self.__head < self.__buffer.len);
assert(self.__tail >= 0 and self.__tail < self.__buffer.len);
assert(self.__length >= 0 and self.__length <= self.__buffer.len);
const buffer_len = self.__buffer.len;
if (self.__length == buffer_len) {
// Overflow is happening, we also need to adjust head.
self.__head = @mod(self.__head +% 1, buffer_len);
}
self.__buffer[self.__tail] = item;
self.__tail = @mod(self.__tail +% 1, buffer_len);
self.__length = @minimum(self.__length +| 1, buffer_len);
}
/// Add item at the end of ring buffer.
/// Overflow is not allowed.
pub fn add(self: *Self, item: T) RingBufferAddError!void {
assert(self.__head >= 0 and self.__head < self.__buffer.len);
assert(self.__tail >= 0 and self.__tail < self.__buffer.len);
assert(self.__length >= 0 and self.__length <= self.__buffer.len);
const buffer_len = self.__buffer.len;
if (self.__length < buffer_len) {
self.__buffer[self.__tail] = item;
self.__tail = @mod(self.__tail +% 1, buffer_len);
self.__length = @minimum(self.__length +| 1, buffer_len);
} else {
// Overflow will happen, we don not allow this.
return RingBufferAddError.IsFull;
}
}
/// Remove the last recently inserted item.
pub fn remove(self: *Self) RingBufferRemoveError!T {
assert(self.__head >= 0 and self.__head < self.__buffer.len);
assert(self.__tail >= 0 and self.__tail < self.__buffer.len);
assert(self.__length >= 0 and self.__length <= self.__buffer.len);
const buffer_len = self.__buffer.len;
if (self.__length > 0) {
const head = self.__head;
self.__head = @mod(head +% 1, buffer_len);
// We checked invariant length > 0 and can safely subtract 1.
self.__length -= 1;
return self.__buffer[head];
} else {
return RingBufferRemoveError.IsEmpty;
}
}
};
}
test "empty buffer invariants" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
try expect(buf.capacity() == 7);
try expect(buf.length() == 0);
try expect(buf.full() == false);
try expect(buf.empty() == true);
}
test "buffer with one element invariants" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
try buf.add(1);
try expect(buf.capacity() == 7);
try expect(buf.length() == 1);
try expect(buf.full() == false);
try expect(buf.empty() == false);
}
test "full buffer invariants" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
try buf.add(1);
try buf.add(2);
try buf.add(3);
try buf.add(4);
try buf.add(5);
try buf.add(6);
try buf.add(7);
try expect(buf.capacity() == 7);
try expect(buf.length() == 7);
try expect(buf.full() == true);
try expect(buf.empty() == false);
}
test "add and remove one element" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 1);
defer buf.delete();
try expect(buf.capacity() == 1);
try expect(buf.length() == 0);
try expect(buf.full() == false);
try expect(buf.empty() == true);
try buf.add(1);
try expect(buf.capacity() == 1);
try expect(buf.length() == 1);
try expect(buf.full() == true);
try expect(buf.empty() == false);
const head = try buf.remove();
try expect(buf.capacity() == 1);
try expect(buf.length() == 0);
try expect(buf.full() == false);
try expect(buf.empty() == true);
try expect(head == 1);
}
test "buffer reset" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
try buf.add(1);
try buf.add(2);
buf.reset();
try expect(buf.capacity() == 7);
try expect(buf.length() == 0);
try expect(buf.full() == false);
try expect(buf.empty() == true);
}
test "error when add to full buffer" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
try buf.add(1);
try buf.add(2);
try buf.add(3);
try buf.add(4);
try buf.add(5);
try buf.add(6);
try buf.add(7);
try expect(buf.capacity() == 7);
try expect(buf.length() == 7);
try expect(buf.full() == true);
try expect(buf.empty() == false);
const err = buf.add(8);
try expectError(RingBufferAddError.IsFull, err);
try expect(buf.capacity() == 7);
try expect(buf.length() == 7);
try expect(buf.full() == true);
try expect(buf.empty() == false);
}
test "buffer overflow invariants" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
try buf.add(1);
try buf.add(2);
try buf.add(3);
try buf.add(4);
try buf.add(5);
try buf.add(6);
try buf.add(7);
try expect(buf.capacity() == 7);
try expect(buf.length() == 7);
try expect(buf.full() == true);
try expect(buf.empty() == false);
// Overflow is allowed, should overwrite head element
buf.addOverflow(8);
try expect(buf.capacity() == 7);
// Length has not changed, since it's already max capacity.
try expect(buf.length() == 7);
try expect(buf.full() == true);
try expect(buf.empty() == false);
// Head now is element 2, since 1 was overwritten.
const second = try buf.remove();
try expect(second == 2);
_ = try buf.remove();
_ = try buf.remove();
_ = try buf.remove();
_ = try buf.remove();
_ = try buf.remove();
_ = try buf.remove();
// Removing element 9, which doesn't exist
const err = buf.remove();
try expectError(RingBufferRemoveError.IsEmpty, err);
try expect(buf.capacity() == 7);
try expect(buf.length() == 0);
try expect(buf.full() == false);
try expect(buf.empty() == true);
}
test "cyclic overflow" {
var buf = try RingBuffer(u64).create(std.testing.allocator, 7);
defer buf.delete();
buf.addOverflow(1);
buf.addOverflow(2);
buf.addOverflow(3);
buf.addOverflow(4);
buf.addOverflow(5);
buf.addOverflow(6);
buf.addOverflow(7);
// Overflow is happening.
buf.addOverflow(8);
buf.addOverflow(9);
buf.addOverflow(10);
buf.addOverflow(11);
buf.addOverflow(12);
buf.addOverflow(13);
buf.addOverflow(14);
try expect(buf.capacity() == 7);
try expect(buf.length() == 7);
try expect(buf.full() == true);
try expect(buf.empty() == false);
const n8 = try buf.remove();
try expect(n8 == 8);
const n9 = try buf.remove();
try expect(n9 == 9);
const n10 = try buf.remove();
try expect(n10 == 10);
const n11 = try buf.remove();
try expect(n11 == 11);
const n12 = try buf.remove();
try expect(n12 == 12);
const n13 = try buf.remove();
try expect(n13 == 13);
const n14 = try buf.remove();
try expect(n14 == 14);
try expect(buf.capacity() == 7);
try expect(buf.length() == 0);
try expect(buf.full() == false);
try expect(buf.empty() == true);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment