How Circular Buffers works

June 20, 2019 · 6 min read

author

A ring buffer is a data structure that works similar to a queue. Why similar? From the principle it is a queue, the difference to normal queues is that these have a fixed size in the normal case. A ring buffer works according to the FIFO principle like the queue.

FIFO = First In First Out. What comes in first also goes out first. The effort for queuing and unqueuing is $O(1)$ .

A ring buffer typically operates internally with a fixed length array and has two indices Head and Tail. Head is at the beginning of the queue for taking data. Tail, on the other hand, is at the end of the queue for queuing the data. The data is always overwritten after the head is not used or read out. This means that the capacity of this data queue is "infinitely larger".

Why are ring buffers needed? Ring buffers are one of the most important data structures in computer science, and can and are used in many areas. In streaming on Twitch, ring buffers are used for loading video frames and sound. In interprocess communication, the ring buffer is used in the PIPE as an example. Even the keyboard uses a ring buffer, which takes the input, which is later retrieved by the operating system via APIs.

I have included a small implementation of the ring buffer. We look at the header file of the ring buffer.

#include <iostream>

class RingBuffer
{
     private:
          int head = 0;
          int tail = 0;
          int *v;
          int _size;
          int _used;

     public:
          RingBuffer();
          RingBuffer(int size);
          ~RingBuffer();
          void put(int x);
          int get();
          void show();
          int used();
          int total();
          int free();
          float usage();
};

Here we see head and tail as indices which later tell us where start and end are. A dynamic array v of type integer where later our data will be stored. We see the attribute _size which will later tell us how big the ring buffer should be. The attribute _used tells us later how full the ring buffer is.

The ring buffer has defined constructors, the default constructor and an overloaded constructor. Both are responsible for the creation of the ring buffer.

RingBuffer::RingBuffer()
{
	this->_size = 64;
	this->v = new int[this->_size];
}

RingBuffer::RingBuffer(int size)
{
	this->_size = size;
	this->v = new int[size];
}

With the default constructor, the maximum size of the ring buffer is set to 64 entries, and the array v is created with this size. The overlanded constructor does something similar, except that the size is specified by the parameter size.

The destructor here is a one-liner because only the array must be deleted.

RingBuffer::~RingBuffer()
{
 delete[] this->v;
}

The method put is there to add data in the ring buffer. Here first tail is incremented by 1 and modulo of the buffer size is calculated.

This ensures that tail does not point outside the buffer. This saves us an if query, which would have done the same thing. With this recalculation of the index tail, we make sure that our tail always moves by 1. If tail reaches the end and still continues to move, a turnaround takes place here through the modulo. Tail then lands again at the index 0.

At the new position to which our tail points, our data set x is inserted. At the end the number _used of occupied places is increased by 1 if the maximum size is not exceeded. Otherwise we just keep the number. It's a bit inaccurate but for this example it's still sufficient. Here we have an overhead of $O(1)$ since only one operation is needed to insert a record.

void RingBuffer::put(int x)
{
    this->tail = (this->tail + 1) % this->_size;
    this->v[tail] = x;
    if(this->_used < this->_size)
        this->_used++;

}

Let's move on to the get method. This takes the data from the buffer. Here also an overhead $O(1)$ is needed since we read here only data to the index head.

Here head is incremented by 1 and also held with a modulo computation inside the array v. Here we have on a turnaround by the modulo calculation.

At the new location head the value is read and the value in the array is set to 0. The count _used is decreased by 1 but so that no negative count is possible. If 0 then 0. At the end the read value is returned.

int RingBuffer::get()
{
	this->head = (this->head + 1) % this->_size;
	int val = this->v[head];
	this->v[head] = 0;
	if(this->_used == 0)
		this->_used--;

	return val;
}

The show method simply outputs our complete ring buffer. Here you can see how our ring buffer looks like after a few operations. Head and tail are taken into account in the output and are also output. This method has an overhead of $O(n)$ since it goes through the whole array $v$ .

void RingBuffer::show()
{
	std::cout << "[";
	for(int i = 0; i < this->_size; i++)
	{
		if(i == this->head)
		{
			std::cout << "head[" << this->v[i] << "] |";
		}
		else if(i == this->tail)
		{
			std::cout << "tail[" << this->v[i] << "] |";
		}
		else
		{
			std::cout << this->v[i] << " |";
		}
		
	}

	std::cout << "]" << std::endl;
}

The less important but still useful methods total, used, free and usage should give us some information about how busy our ring buffer is. Each of the individual methods has a cost $O(1)$ .

int RingBuffer::total()
{
	return this->_size;
}

int RingBuffer::used()
{
	return this->_used;
}

int RingBuffer::free()
{
	return this->_size - this->_used;
}

float RingBuffer::usage()
{
	return (float(this->_used) / float(this->_size)) * 100.0;
}

When you run the whole thing it looks like this example output:

[head[0] |tail[0] |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |]
TOTAL: 13
FREE: 12
USED: 1
USAGE: 7.69231

[0 |head[0] |tail[1] |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |]
TOTAL: 13
FREE: 11
USED: 2
USAGE: 15.3846

[0 |head[0] |1 |tail[2] |0 |0 |0 |0 |0 |0 |0 |0 |0 |]
TOTAL: 13
FREE: 10
USED: 3
USAGE: 23.0769

[0 |0 |head[0] |2 |tail[3] |0 |0 |0 |0 |0 |0 |0 |0 |]
TOTAL: 13
FREE: 9
USED: 4
USAGE: 30.7692
...

I hope I was able to give a little insight into ring buffers 😄