.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.

Adding Queue Status Flags

When working with the queue we will need to know when the buffer is full or empty. This information may also be useful to consumers of the class so we will create two Boolean properties that indicate these statuses. The queue is empty when the current length is zero and full when the current length is the same as the buffer size.

The code for the properties is as follows:

public bool IsEmpty
{
    get { return _length == 0; }
}

public bool IsFull
{
    get { return _length == _bufferSize; }
}

Dequeuing Values

We can now add the Dequeue method that extracts and returns the oldest item from the buffer. This is a simple process that follows a few steps. Firstly, if the queue is empty, we throw an exception. This prevents consumers from dequeuing too many items, potentially returning data that has been dequeued previously or extracting data from empty buffer spaces.

Next we retrieve the array value at the tail position, which will be returned at the end of the process. We then advance the tail one space by incrementing the index value. If the pointer reaches the size of the buffer, we reset it to zero to follow the cyclic nature of the data structure. In the code this is achieved using the modulus operator. The advancement is defined in the separate NextPosition method as this functionality will be reused. As the number of items in the buffer is now smaller we decrement the length variable to the correct value.

The code for the method is shown below. Note that the functionality is contained within a lock statement to ensure that the pointers cannot be changed by another process.

public T Dequeue()
{
    lock (_lock)
    {
        if (IsEmpty) throw new InvalidOperationException("Queue exhausted");

        T dequeued = _buffer[_tail];
        _tail = NextPosition(_tail);
        _length--;
        return dequeued;
    }
}

private int NextPosition(int position)
{
    return (position + 1) % _bufferSize;
}

Queuing Values

The last method to implement allows queuing of new values. When an item is added to the queue we advance the head pointer first and store the new value at the new index. This means that the pointer always indicates the position of the newest item in the queue. If the queue is already full, this will overwrite the oldest value in the buffer so we advance the tail position to point to the next item, which is now the oldest. If the buffer is not already full the tail index is left unchanged and the current length is incremented.

public void Enqueue(T toAdd)
{
    lock (_lock)
    {
        _head = NextPosition(_head);
        _buffer[_head] = toAdd;
        if (IsFull)
            _tail = NextPosition(_tail);
        else
            _length++;
    }
}

Using the Circular Buffer

We can now test the circular buffer by enqueuing and dequeuing items. For a first test, try the code shown below. This creates a small buffer with a capacity of five integers. Five values are enqueued and then dequeued, showing that the order of items is maintained.

CircularBuffer<int> queue = new CircularBuffer<int>(5);

queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
queue.Enqueue(5);

while (!queue.IsEmpty)
{
    Console.WriteLine("Dequeued {0}", queue.Dequeue());
}

/* OUTPUT

Dequeued 1
Dequeued 2
Dequeued 3
Dequeued 4
Dequeued 5

*/

The second example shows what happens when the queue's capacity is exceeded. Here six items are added to a queue that can only hold five. When dequeued, we see that the oldest item has been discarded.

CircularBuffer<int> queue = new CircularBuffer<int>(5);

queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
queue.Enqueue(5);
queue.Enqueue(6);
queue.Enqueue(7);

while (!queue.IsEmpty)
{
    Console.WriteLine("Dequeued {0}", queue.Dequeue());
}

/* OUTPUT

Dequeued 3
Dequeued 4
Dequeued 5
Dequeued 6
Dequeued 7

*/