Simple Ring Buffer Trick

A ring buffer, a queue or a circular buffer can have rather complicated implementations. I am going to show you a math trick to make it simple.

A ring buffer is defined by two operations, pop and push. It is a FIFO data structure: First In, First Out.

The trick requires to use a fixed size array. When you have an array, you are going to maintain two cursors, head and tail to know where to read and where to write. You end-up in a situation where you will constantly need to loop over the buffer size.

Basics

Let say you have a ring buffer with a capacity of 5 elements. You have A queued already.

You push B and C.

You push D and E.

What is interesting us here is the computation of tail circling back. If you can do that, implementing a simple ring buffer is trivial.

The Code

Let’s define a function MoveCursor doing exactly that:

int MoveCursor(int cursor, int relative)
{
	return ( Cursor + relative + Size) % Size;
}

Instead of incrementing the cursor by 1, we kept it fun and allowed to pass an arbitrary size. For example let say I was coding a GGPO style network rollback system. I keep all my inputs in a ring buffer, one entry per frame. If I need to rollback by 4 frames, I will just move the cursor with relative value of -4. It is just a very powerful little piece of math, it does indeed goes FORWARD but also BACKWARD.

You see I am sneaky this way, this is just not a tool to implement a queue, you have thousands different styles on the internet already. It is a little building block that allows you to craft a piece of code for your particular design. In the case of input frames, you usually go forward by 1, but you also want to rollback and replay those frames in order. With a real queue, it would get annoying very fast, having to dequeue and requeue as you replay.

The Optimization

This code can be optimized. My good colleague Kalas showed it to me the other day. If you can guarantee that the size of the buffer is a power of 2, it unlocks a faster MoveCursor function. You do not need the modulo anymore which is faster.

int GetRelativeCursor(int relative)
{
	return Cursor + relative & (Size - 1);
}

It is pretty slick.

Find The Next Power Of Two

I use this little function to find the next power of two from an arbitrary number. Let say I am trying to initialize a ring buffer of size 5 in my code. I will use this function in the initializer to “correct” the size and allocate a buffer size allowing me to use the code above.

int NextPowerOfTwo(int n)
{
	// Handle edge cases: 0 or negative numbers
	if (n <= 0)
	{
		return 1;
	}

	// Decrement n to handle cases where n is already a power of 2
	n--;

	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;
	n |= n >> 16;

	// For 64-bit integers (long), add n |= n >> 32;
	n++;
		
	return n;
}

Conclusion

Of course as with everything, the devil is in the details. There can be a lot of edge cases and we could debate about it for ages if it matters or not. The idea here is to empower you to free yourself from some of the annoying book-keeping of indexes that want to loop around and write some cool code.