Created
February 4, 2022 11:53
-
-
Save likern/ac01b315434c68622f70cc0228863971 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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