So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure.
It was just surprisingly annoying to write, due to reasons we'll get to in a bit. After giving it a bit of thought, I realized I'd always been writing ring buffers "wrong", and there was a better way.
Array + two indices
There are two common ways of implementing a queue with a ring buffer.
One is to use an array as the backing storage plus two indices to the array; read and write. To shift a value from the head of the queue, index into the array by the read index, and then increment the read index. To push a value to the back, index into the array by the write index, store the value in that offset, and then increment the write index.
Both indices will always be in the range 0..(capacity - 1). This is done by masking the value after an index gets incremented.
That implementation looks basically like:
uint32 read; uint32 write; mask(val) { return val & (array.capacity - 1); } inc(index) { return mask(index + 1); } push(val) { assert(!full()); array[write] = val; write = inc(write); } shift() { assert(!empty()); ret = array[read]; read = inc(read); return ret; } empty() { return read == write; } full() { return inc(write) == read; } size() { return mask(write - read); }
The downside of this representation is that you always waste one element in the array. If the array is 4 elements, the queue can hold at most 3. Why? Well, an empty buffer will have a read pointer that's equal to the write pointer; a buffer with capacity N and size N would also have have a read pointer equal to the write pointer. Like this:
The 0 and 4 element cases are indistinguishable, so we need to prevent one from ever happening. Since empty queues are kind of necessary, it follows that the latter case needs to go. The queue has to be defined as full when one element in the array is still unused. And that's the way I've always done it.
... continue reading