Ring buffers / circular buffers

A ring buffer, also known as a circular buffer or cyclic buffer, is a very useful data structure for certain situations, and worth having around in your programmer’s toolchest. It’s a fixed-size buffer but treated as though it’s connected end to end (that is, the end is connected to the start) and data is written and read in a FIFO (first-in first-out) way. Usually this is all hidden behind an API to make it easy to read and write to it.

They are often used when there is a need to read and write data in a streaming manner, for example, streaming audio to a sound card, I/O buffering for a UART in an embedded device, and in fact any I/O buffer situation (e.g. a network device or a disk). Because the buffer is fixed in size you know what the memory footprint will be up front and this makes it ideal for use in embedded systems or on consoles where memory is constrained and you don’t want to dynamically allocate memory.

Overview

You can imagine a ring buffer as a circular block of memory that cycles around like this (the numbers represent the indices into the block of memory, which is treated as an array of bytes):

Fig. 1 – Imaginary ring buffer

But of course in reality the memory is really laid out like this:

Fig. 2 – Actual memory layout

The current read and write locations in the buffer are tracked, and the ring buffer operation is as follows:

• When writing, we copy new data into the buffer starting at the write location, and if the new data goes off the end of the buffer, we wrap around and write the remaining data starting at the start of the buffer, until we have written all data or we run out of space.
• When reading, we copy data out of the buffer starting at the read location until we have read some specified amount of data, or we reach the write location, wrapping around the end of the buffer as above.

We know we’ve run out of space for writing when we reach the read location, and we know we have no more data to read when we reach the write location. In those cases we can just stop and return the amount of data actually written or read.

Implementation

Phew! That seems complicated! Let’s break this down and look at how we might implement it. We need to keep track of a few things:

• A pointer to the start of the memory for the buffer.
• The size of the buffer in bytes.
• The current read index in the buffer.
• The current write index in the buffer.

The read and write indices represent where the current read and write location is in the buffer (these could instead be kept as pointers if we wanted).

In my implementation I also choose to track:

• The number of bytes available for reading.
• The number of bytes available for writing.

We can actually avoid tracking these two if we want, but it makes everything a bit clearer and doesn’t cost us much more.

We also want to be able to read and write to the buffer. Let’s sketch out a class for what we have so far:

class RingBuffer
{
    public:
        RingBuffer(int sizeBytes);
        ~RingBuffer();

        // Copies 'length' bytes from 'source' to the ring buffer.
        // Returns the number of bytes actually written, which may be less than 'length'
        // if there was insufficient space to write into the ring buffer.
        int Write(const void* source, int length);

        // Reads 'length' bytes from the ring buffer into 'dest'.
        // Returns the number of bytes actually read, which may be less than 'length'
        // if there was insufficient data in the ring buffer.
        int Read(void* dest, int length);

    private:
        char* m_buffer;
        int m_sizeBytes;
        int m_readIndex;
        int m_writeIndex;
        int m_readBytesAvailable;
        int m_writeBytesAvailable;
}

For our write function we’ll clamp the length to the amount of space available for writing, and for our read function we’ll clamp it to the amount of data available in the buffer for reading.

Reading and Writing

We have two possible situations we need to handle when implementing reading and writing. The case where the current write index is greater than the current read index:

Fig. 3 – Write index greater than read index

And the case where the current write index is less than the current read index:

Fig. 4 – Write index less than read index

For writing in figure 3, we need to split the write up into two regions. The first region is from the current write index to the end of the buffer (index 11 to 15 inclusive), and the second region is from the start of the buffer to just before the current read index (index 0 to 3 inclusive):

Fig. 5 – Two regions for writing

For the figure 4 case, we have just one region, from the current write index to just before the current read index (index 1 to 8 inclusive):

Fig. 6 – One region for writing

Reading is pretty much the same, but opposite! For reading in the figure 3 case, we just read from the current read index to just before the current write index (index 4 to 10 inclusive). For the figure 4 case we need to split the read up into two regions. The first region is from the current read index to the end of the buffer (index 9 to 15 inclusive), and the second region is from the start of the buffer to just before the current write index (index 0 only).

When there are two regions, it’s possible that the length of data we want to write or read isn’t enough to take us into the second region! So we may only end up requiring one region. Clamping the length makes it easy to determine this without a whole lot of nested if statements, because we can compare the clamped length to the remaining bytes in the buffer from the current read or write index. I think this is easier to explain in code, so putting this all together, we can come up with a write function like this:

int RingBuffer::Write(const void* source, int length)
{
    assert(m_buffer);
    assert(source);
    assert(length >= 0);
    assert(m_writeBytesAvailable >= 0);

    // If there is no space or nothing to write then don't do anything.
    if (m_writeBytesAvailable == 0 || length == 0)
        return 0;

    // Clamp the length to the number of bytes available for writing.
    if (length > m_writeBytesAvailable)
        length = m_writeBytesAvailable;

    int remainingWriteBytes = m_sizeBytes - m_writeIndex;
    if (length > remainingWriteBytes)
    {
        // If the number of bytes to write is bigger than the remaining bytes
        // in the buffer, we have to wrap around and write into two regions.
        memcpy(m_buffer + m_writeIndex, source, remainingWriteBytes);
        memcpy(m_buffer, (char*)source + remainingWriteBytes, length - remainingWriteBytes);
    }
    else
    {
        // No wrapping, only one region to write to, which starts from the write index.
        memcpy(m_buffer + m_writeIndex, source, length);
    }

    // Increment the write index and wrap around at the end.
    m_writeIndex = (m_writeIndex + length) % m_sizeBytes;

    // Update the read and write sizes.
    m_writeBytesAvailable -= length;
    m_readBytesAvailable += length;

    return length;
}

Our read function will look pretty similar:

int RingBuffer::Read(void* dest, int length)
{
    assert(m_buffer);
    assert(dest);
    assert(length >= 0);
    assert(m_readBytesAvailable >= 0);

    // If there is no data in the buffer or nothing to read then don't do anything.
    if (IsEmpty() || length == 0)
        return 0;

    // Clamp the length to the maximum number of bytes available for reading.
    if (length > m_readBytesAvailable)
        length = m_readBytesAvailable;

    int remainingReadBytes = m_sizeBytes - m_readIndex;
    if (length > remainingReadBytes)
    {
        // If the number of bytes to read is bigger than the remaining bytes
        // in the buffer, we have to wrap around and read from two regions.
        memcpy(dest, m_buffer + m_readIndex, remainingReadBytes);
        memcpy((char*)dest + remainingReadBytes, m_buffer, length - remainingReadBytes);
    }
    else
    {
        // No wrapping, only one region to read from, which starts from the read index.
        memcpy(dest, m_buffer + m_readIndex, length);
    }

    // Increment the read index and wrap around at the end.
    m_readIndex = (m_readIndex + length) % m_sizeBytes;

    // Update the read and write sizes.
    m_writeBytesAvailable += length;
    m_readBytesAvailable -= length;

    return length;
}

And that’s it! There is a full implementation available here. Note that it makes no attempt to be thread safe! You should lock as appropriate if you use this in a multi-threaded environment.

Next time we’ll look at using this class to dynamically generate a continuous audio stream!