Queue.zig

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);
}

RingBuffer.zig

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);
}