.NET 2.0+

A Generic Circular Buffer

by Richard Carr, published at http://www.blackwasp.co.uk/CircularBuffer.aspx

A circular buffer is a type of fixed size, first in, first out queue. The spaces in the buffer can be thought of as connected in a ring. Items in the buffer are never moved. Instead, changeable pointers are used to identify the head and tail of the queue.

What is a Circular Buffer?

A circular buffer, also known as a circular queue or ring buffer, is a high performance, first in, first out (FIFO) queue. As with any other type of queue, values can be added to the end of the queue and extracted from the start, so that items are dequeued in the same order that they were enqueued.

In some queue structures, when items are added or removed, the contents of the queue are physically moved in memory. With a circular buffer the positions are fixed. The head and tail of the queue are identified using two pointers that are updated when items are added or removed. In addition, the buffer spaces can be thought of as cyclic. After the last space in the buffer is used, the next item enqueued is stored in the first space. The diagram below shows a conceptual model of a circular buffer.

The diagram represents a circular buffer with sixteen spaces, thirteen of which are in use. In this case, the values one to thirteen have been added in order. The head of the queue is pointing at the latest value, thirteen, and the tail is at the space containing the number one. When the next item is enqueued it will be added in the next available empty space after the thirteen and the head pointer will be shifted to point to this position. When the next dequeue operation takes place the number one at the tail pointer will be extracted and the tail will move clockwise one space. When dequeuing there is no need to clear the old buffer space as the value will be overwritten at some point in the future.

The nature of the circular buffer means that it is possible for the head of the queue to catch the tail. When the next item to be enqueued would overwrite the tail item there are several possible actions. The most common options are:

• Allow the new item to overwrite the tail item, moving the tail pointer onwards to point at the next oldest item. This approach is useful for real-time signal processing. For example, when applying a filter to a video feed. If the tail of the queue is overwritten this may cause a 'blip' in the video or a momentary loss of quality but can allow the output video to continue playing without pausing or slowing.
• Throw an exception when trying to add to a full queue or read from an empty buffer. This ensures that no data is lost but is less useful for real-time queues or where the speed of enqueuing and dequeuing is dissimilar.
• Block the thread when trying to add to a full queue or read from an empty queue. As when throwing exceptions this ensures that no data is lost. It is useful in parallel applications, when separate threads are used for enqueuing and dequeuing. Only one of the two threads may be blocked at any time and no exceptions will be thrown so the queue can be used to process large streams of data without the risk of failure.

In this article we will implement the first option. When adding to a full queue the oldest item in the buffer will be overwritten. When dequeuing from an empty buffer we will throw an exception. The code can easily be modified for other scenarios.

Implementing the Circular Buffer

We can begin by creating the class for the circular buffer. To allow the buffer to hold any type of data we'll declare it as a generic class with a single type parameter.

public class CircularBuffer<T>
{
}

Next we need several class-level variables. Firstly we need somewhere to store the buffer data. For this we'll use an array of the type defined in the class' type parameter. We'll use two integer values as the head and tail pointers. These will hold index values for the buffer array. Two further integers will hold the current length of the queue and the size of the buffer. These will be used when determining if the buffer is completely full or empty. Finally, to prevent synchronisation errors if multiple threads are trying to enqueue or dequeue simultaneously we'll create an object to control locks.

The code for the class-level variables is as follows:

T[] _buffer;
int _head;
int _tail;
int _length;
int _bufferSize;
object _lock = new object();

Adding the Constructor

When a CircularBuffer object is instantiated we initialise the buffer and the head pointer using the constructor. The constructor includes a single parameter that allows the buffer size to be specified. This is stored and used to initialise the array. The head pointer is set to point at the last item in the array. When the first item is enqueued, the pointer will be moved forward to the first item before storing, at which point both the head and tail values will be zero.

public CircularBuffer(int bufferSize)
{
    _buffer = new T[bufferSize];
    _bufferSize = bufferSize;
    _head = bufferSize - 1;
}