# The Core Idea ### Ring Buffers A ring buffer is a fixed-size queue that reuses its storage. A normal queue has a front and a back: ```text front back [10][20][30][40] ``` When you remove from the front, the front moves forward: ```text [old][20][30][40] ^ front ``` After many removals, unused space builds up at the beginning. A ring buffer solves this by wrapping around to the start of the array. ```text [50][60][old][40] ^ ^ back front ``` The storage is treated like a circle. ## The Core Idea A ring buffer keeps three pieces of state: ```zig buffer: []T head: usize len: usize ``` `head` is the index of the first item. `len` is the number of stored items. The next item to remove is at `head`. The next place to insert is: ```zig (head + len) % buffer.len ``` The `%` operator wraps the index back to zero when it reaches the end. Example with capacity 4: ```text buffer indexes: 0 1 2 3 ``` If `head = 3` and `len = 2`, the items are at: ```text 3, 0 ``` The buffer wraps around. ## Why Ring Buffers Are Useful Ring buffers are useful when you want queue behavior without repeated allocation. They are common in: ```text task queues audio buffers network buffers logging buffers producer-consumer systems embedded systems event loops ``` They are especially useful when the maximum capacity is known. ## A Simple Fixed Ring Buffer Here is a small ring buffer for `i32` values: ```zig const std = @import("std"); const RingBuffer = struct { buffer: []i32, head: usize, len: usize, pub fn init(buffer: []i32) RingBuffer { return RingBuffer{ .buffer = buffer, .head = 0, .len = 0, }; } pub fn capacity(self: *const RingBuffer) usize { return self.buffer.len; } pub fn isEmpty(self: *const RingBuffer) bool { return self.len == 0; } pub fn isFull(self: *const RingBuffer) bool { return self.len == self.buffer.len; } pub fn push(self: *RingBuffer, value: i32) !void { if (self.isFull()) return error.Full; const index = (self.head + self.len) % self.buffer.len; self.buffer[index] = value; self.len += 1; } pub fn pop(self: *RingBuffer) ?i32 { if (self.isEmpty()) return null; const value = self.buffer[self.head]; self.head = (self.head + 1) % self.buffer.len; self.len -= 1; return value; } }; ``` Using it: ```zig pub fn main() !void { var storage: [4]i32 = undefined; var queue = RingBuffer.init(&storage); try queue.push(10); try queue.push(20); try queue.push(30); std.debug.print("{}\n", .{queue.pop().?}); std.debug.print("{}\n", .{queue.pop().?}); try queue.push(40); try queue.push(50); while (queue.pop()) |value| { std.debug.print("{}\n", .{value}); } } ``` Output: ```text 10 20 30 40 50 ``` The storage array never moves and never reallocates. ## Push The push operation inserts at the back. ```zig const index = (self.head + self.len) % self.buffer.len; self.buffer[index] = value; self.len += 1; ``` Suppose: ```text capacity = 4 head = 2 len = 2 ``` The occupied indexes are: ```text 2, 3 ``` The next insert index is: ```text (2 + 2) % 4 = 0 ``` So the new item goes at index `0`. ```text [new][ ][old][old] ``` That is the wraparound. ## Pop The pop operation removes from the front. ```zig const value = self.buffer[self.head]; self.head = (self.head + 1) % self.buffer.len; self.len -= 1; return value; ``` If `head` reaches the end, it wraps back to zero. ```text (head + 1) % capacity ``` For capacity `4`: ```text 0 -> 1 -> 2 -> 3 -> 0 ``` ## Full and Empty A ring buffer must know whether it is full or empty. In this design: ```zig len == 0 ``` means empty. ```zig len == buffer.len ``` means full. This is clear because we store `len`. Some ring buffers store only `head` and `tail`. Those designs often need one unused slot or an extra flag to distinguish full from empty. For beginners, storing `len` is simpler. ## Why Capacity Cannot Be Zero The code uses `% self.buffer.len`. If `buffer.len` is zero, that would divide by zero. A production version should reject empty storage: ```zig pub fn init(buffer: []i32) !RingBuffer { if (buffer.len == 0) return error.EmptyBuffer; return RingBuffer{ .buffer = buffer, .head = 0, .len = 0, }; } ``` Then callers must use `try`: ```zig var queue = try RingBuffer.init(&storage); ``` ## Generic Ring Buffer The previous version works only for `i32`. We can make it generic with `comptime`. ```zig const std = @import("std"); fn RingBuffer(comptime T: type) type { return struct { const Self = @This(); buffer: []T, head: usize, len: usize, pub fn init(buffer: []T) !Self { if (buffer.len == 0) return error.EmptyBuffer; return Self{ .buffer = buffer, .head = 0, .len = 0, }; } pub fn capacity(self: *const Self) usize { return self.buffer.len; } pub fn isEmpty(self: *const Self) bool { return self.len == 0; } pub fn isFull(self: *const Self) bool { return self.len == self.buffer.len; } pub fn push(self: *Self, value: T) !void { if (self.isFull()) return error.Full; const index = (self.head + self.len) % self.buffer.len; self.buffer[index] = value; self.len += 1; } pub fn pop(self: *Self) ?T { if (self.isEmpty()) return null; const value = self.buffer[self.head]; self.head = (self.head + 1) % self.buffer.len; self.len -= 1; return value; } }; } ``` Using it: ```zig pub fn main() !void { var storage: [8][]const u8 = undefined; var queue = try RingBuffer([]const u8).init(&storage); try queue.push("alpha"); try queue.push("beta"); try queue.push("gamma"); while (queue.pop()) |name| { std.debug.print("{s}\n", .{name}); } } ``` Output: ```text alpha beta gamma ``` Now the same ring buffer works for many types. ## Overwrite Mode Some ring buffers reject new items when full. Others overwrite the oldest item. Overwrite mode is useful for logs, telemetry, and recent-history buffers. Example rule: ```text capacity = 3 push A -> [A] push B -> [A, B] push C -> [A, B, C] push D -> [B, C, D] ``` The oldest item is dropped. A push function for overwrite mode can look like this: ```zig pub fn pushOverwrite(self: *Self, value: T) void { if (self.isFull()) { self.buffer[self.head] = value; self.head = (self.head + 1) % self.buffer.len; } else { const index = (self.head + self.len) % self.buffer.len; self.buffer[index] = value; self.len += 1; } } ``` When full, the new value replaces the oldest value at `head`, then `head` moves forward. ## Looking Without Removing A queue often needs `peek`. ```zig pub fn peek(self: *const Self) ?T { if (self.isEmpty()) return null; return self.buffer[self.head]; } ``` This returns the front value without changing the buffer. For large values, you might prefer returning a pointer: ```zig pub fn peekPtr(self: *Self) ?*T { if (self.isEmpty()) return null; return &self.buffer[self.head]; } ``` This avoids copying the value. But be careful: the pointer is valid only while the buffer item remains in place. ## Iterating Over a Ring Buffer A ring buffer may wrap, so iteration must use modular indexing. ```zig pub fn at(self: *const Self, offset: usize) ?T { if (offset >= self.len) return null; const index = (self.head + offset) % self.buffer.len; return self.buffer[index]; } ``` Using it: ```zig var i: usize = 0; while (i < queue.len) : (i += 1) { const value = queue.at(i).?; std.debug.print("{}\n", .{value}); } ``` This visits items in queue order. ## Ring Buffer vs ArrayList Queue An `ArrayList` queue with a head index can grow dynamically, but old space may accumulate until you compact it. A ring buffer has fixed capacity and reuses the same storage. | Structure | Capacity | Allocation | Good for | |---|---:|---:|---| | `ArrayList` queue | Can grow | May allocate | Unknown size | | Ring buffer | Fixed | Usually none after setup | Known maximum size | | Linked list queue | Can grow | Per node | Stable node pointers | A ring buffer is often the best choice when the maximum size is bounded. ## Stack Allocation One nice feature of a fixed ring buffer is that the storage can live on the stack. ```zig var storage: [128]u8 = undefined; var rb = try RingBuffer(u8).init(&storage); ``` No heap allocator is needed. This is useful in embedded systems, parsers, temporary buffers, and performance-sensitive code. ## Heap Allocation If the capacity is known only at runtime, allocate the storage: ```zig const storage = try allocator.alloc(u8, capacity); defer allocator.free(storage); var rb = try RingBuffer(u8).init(storage); ``` The ring buffer itself does not own the memory in this design. It only borrows the slice. The caller owns and frees the storage. This makes ownership clear. ## Common Beginner Mistakes The first mistake is forgetting the wraparound. The insert index is not always `head + len`; it must be `(head + len) % capacity`. The second mistake is allowing zero capacity. Modulo by zero is invalid. The third mistake is confusing full and empty when using only head and tail. Storing `len` avoids that problem. The fourth mistake is assuming a ring buffer grows. A ring buffer usually has fixed capacity. The fifth mistake is returning pointers and then modifying the buffer in ways that overwrite the pointed item. ## A Useful Mental Model Think of a ring buffer as an array bent into a circle. ```text 0 -> 1 -> 2 -> 3 ^ | | v 7 <- 6 <- 5 <- 4 ``` When the index reaches the end, it returns to the beginning. The queue order is logical. The storage order may wrap. ## Summary A ring buffer is a queue backed by fixed-size circular storage. It keeps a `head`, a `len`, and a buffer. Push inserts at: ```zig (head + len) % capacity ``` Pop removes from: ```zig head ``` Then `head` moves forward with wraparound. Ring buffers are useful for bounded queues, logs, audio buffers, network buffers, event loops, and embedded systems. They are simple, fast, allocation-free after setup, and predictable.