Circular Buffers in C/C++

Circular buffers are fixed-size buffers that work as if the memory is contiguous & circular in nature. As memory is generated and consumed, data does not need to be reshuffled - rather, the head/tail pointers are adjusted. When data is added, the head pointer advances. When data is consumed, the tail pointer advances. If you reach the end of the buffer, you simply wrap around to the beginning and continue moving.

Due to the resource constrained nature of embedded systems, circular buffer data structures abound. I can point to 2-3 circular buffers used for each of my projects, though most commonly a circular buffer is used in logging infrastructure: as the buffer fills up, the oldest log data is overwritten by the newest data.

For a more detailed summary of circular buffer operation, please refer ot the Wikipedia article. I am continuing the article assuming that you know how a circular buffer works and will simply describe the source implementation.

Why use a circular buffer?

Circular buffers are often used as fixed-sized queues. The fixed size is beneficial for embedded systems, as developers often try to use static data storage methods rather than dynamic allocations.

Circular buffers are also useful structures for situations where data production and consumption happen at different rates: the most recent data is always available. If the consumer cannot keep up with production, the stale data will be overwritten with more recent data.

If you are curious, Embedded's ring buffer article provides more potential usage models, but for now I'll jump into a basic implementation of this data structure.

Important Implementation Note

Both the "full" and "empty" cases of the circular buffer look the same: head and tail pointer are equal.

To simplify the implementation, my example libraries waste one slot in the buffer to differentiate between full (tail + 1 == head) and empty (head == tail). This resource waste is not required, but avoiding it does require additional logic.

One alternative strategy is to use a bool to indicate whether the buffer is empty. The empty flag should only be set during initialization and by the dequeue operation. The empty flag should only be cleared when data is added during the enqueue operation.

With the empty flag, you can differentiate between the two cases easily:

empty:
    (head == tail) && empty

full:
    (head == tail) && !empty

I leave the adjustment of the circular buffer class as an exercise to the reader.

C

We will start with the C implementation and follow with C++, which provides a cleaner implementation.

The C version of the circular buffer is not threadsafe: no locks have been added to the underlying circular buffer library.

I have chosen uint8_t as the underlying data type in this example library. You can use any particular type that you like - just remember to manage the underlying bytes appropriately.

Circular Buffer Container Type

First we need to define our circular buffer container. We use this structure for managing the state of the buffer. This container is intended to be kept by the caller.

typedef struct {
    uint8_t * buffer;
    size_t head;
    size_t tail;
    size_t size; //of the buffer
} circular_buf_t;

Required APIs

I've selected a small set of functionality for this demonstration library:

  • We need to reset the circular buffer container (at the very least as an initializer)
  • We need to be able to add data to the buffer
  • We need to be able to get the next value from the buffer
  • We need to know whether the buffer is full or empty

Here are the APIs:

int circular_buf_reset(circular_buf_t * cbuf);
int circular_buf_put(circular_buf_t * cbuf, uint8_t data);
int circular_buf_get(circular_buf_t * cbuf, uint8_t * data);
bool circular_buf_empty(circular_buf_t cbuf);
bool circular_buf_full(circular_buf_t cbuf);

You may want to expand these APIs to allow you to add/remove multiple elements at once time.

Reset/initialize the buffer

Resetting the buffer is pretty simple: we just reset the head and tail pointers to "0" (marking the buffer as empty).

int circular_buf_reset(circular_buf_t * cbuf)
{
    int r = -1;

    if(cbuf)
    {
        cbuf->head = 0;
        cbuf->tail = 0;
        r = 0;
    }

    return r;
}

State Checks

Next up we'll implement our state checks. As described in the introduction, I've decided to keep the "full" definition as tail-one-behind-head, which wastes a slot.

Here's the empty function:

bool circular_buf_empty(circular_buf_t cbuf)
{
    // We define empty as head == tail
    return (cbuf.head == cbuf.tail);
}

And likewise the full function:

bool circular_buf_full(circular_buf_t cbuf)
{
    // We determine "full" case by head being one position behind the tail
    // Note that this means we are wasting one space in the buffer!
    // Instead, you could have an "empty" flag and determine buffer full that way
    return ((cbuf.head + 1) % cbuf.size) == cbuf.tail;
}

Adding Data

With the bookkeeping functions out of the way, it's time to dig into the meat: adding and removing data from the queue.

Adding data to the buffer is straightforward, but some thought needs to be used for housekeeping of the head and tail pointers. The head pointer is easy, as we always add 1 and use the modulo operator to make sure the value wraps around to 0 when the size is reached:

cbuf->head = (cbuf->head + 1) % cbuf->size;

However, we need to keep our queue at a fixed max size, so we need to cause the tail pointer to advance if we're adding data faster than we're computing it. If the head pointer and tail pointer are equal after we've incremented head, we also need to increment tail by 1:

if(cbuf->head == cbuf->tail)
{
    cbuf->tail = (cbuf->tail + 1) % cbuf->size;
}

Here's what our completed circular_buf_put function looks like:

int circular_buf_put(circular_buf_t * cbuf, uint8_t data)
{
    int r = -1;

    if(cbuf)
    {
        cbuf->buffer[cbuf->head] = data;
        cbuf->head = (cbuf->head + 1) % cbuf->size;

        if(cbuf->head == cbuf->tail)
        {
            cbuf->tail = (cbuf->tail + 1) % cbuf->size;
        }

        r = 0;
    }

    return r;
}

Retrieving Data

circular_buf_get involves getting data from the current tail location and incrementing the tail location each time:

*data = cbuf->buffer[cbuf->tail];
cbuf->tail = (cbuf->tail + 1) % cbuf->size;

How can we prevent advancing the pointer past head? One simple way is to make sure that the circular buffer isn't empty before we read from the buffer.

if(cbuf && data && !circular_buf_empty(*cbuf))
{
    //...
}

Note: the above is an example where lack of thread safety can bite you!

Here's what our completed circular_buf_get function looks like:

int circular_buf_get(circular_buf_t * cbuf, uint8_t * data)
{
    int r = -1;

    if(cbuf && data && !circular_buf_empty(*cbuf))
    {
        *data = cbuf->buffer[cbuf->tail];
        cbuf->tail = (cbuf->tail + 1) % cbuf->size;

        r = 0;
    }

    return r;
}

That wraps up the C circular buffer implementation!

Usage

A quick note on usage. With this library, the caller should instanitiate a circular buffer container and define some initial values, calling reset to wrap it up:

circular_buf_t cbuf;
cbuf.size = 5;
cbuf.buffer = malloc(cbuf.size);
circular_buf_reset(&cbuf);

You could wrap all of this up into an init function, or expand reset functionality.

Once you've setup the buffer, you can add and remove values:

for(int i = 0; i < cbuf.size - 1; i++)
{
    circular_buf_put(&cbuf, i);
}

uint8_t data;
circular_buf_get(&cbuf, &data);

C++

C++ lends itself to a cleaner circular buffer implementation than C. One of the nice things about C++ is that we can create a templated circular buffer class that will work for any type available.

Class Definition

We'll start off by defining our C++ class. As mentioned above, we want to make this a templated class so we can account for any data type we want to handle.

Our APIs are similar to the C implementation, providing:

  • initialization
  • adding data
  • removing data
  • checking full/empty state
  • size of the circular buffer

The C++ circular buffer size represents the number of elements in the queue, which means the total amount of bytes allocated is dependent on the data type. However, this allows us to be agnostic to the underlying size and keeps the math the same across types.

We will also utilize C++ smart pointers to make sure we don't leave any data around once our buffer is destroyed.

Another benefit of C++ is the triviality of making this class thread-safe: we can rely on the std::mutex type (assuming this is defined for your platform).

Here's our class definition:

template <class T>
class circular_buffer {
public:
    circular_buffer(size_t size) :
        buf_(std::unique_ptr<T[]>(new T[size])),
        size_(size)
    {
        //empty constructor
    }

    void put(T item);
    T get(void);

    void reset(void)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        head_ = tail_;
    }

    bool empty(void);
    bool full(void);
    size_t size(void);

private:
    std::mutex mutex_;
    std::unique_ptr<T[]> buf_;
    size_t head_ = 0;
    size_t tail_ = 0;
    size_t size_;
};

Initialization

When constructing our class, we allocate the data for our underlying buffer and set the buffer size. This removes the overhead required with the C implementation.

circular_buffer(size_t size) :
    buf_(std::unique_ptr<T[]>(new T[size])),
    size_(size)
{
    //empty constructor
}

Resetting is the same as the C implementation:

void reset(void)
{
    std::lock_guard<std::mutex> lock(mutex_);
    head_ = tail_;
}

State Tracking

The logic of the empty and full cases is the same as the C example:

bool empty(void)
{
    //if head and tail are equal, we are empty
    return head_ == tail_;
}

bool full(void)
{
    //If tail is ahead the head by 1, we are full
    return ((head_ + 1) % size_) == tail_;
}

I also added a function to get the size of the buffer. Here I have chosen to account for the "reserved entry" and represent the actual full data size:

size_t size(void)
{
    return size_ - 1;
}

Adding Data

The logic for put matches the C implementation:

void put(T item)
{
    std::lock_guard<std::mutex> lock(mutex_);

    buf_[head_] = item;
    head_ = (head_ + 1) % size_;

    if(head_ == tail_)
    {
        tail_ = (tail_ + 1) % size_;
    }
}

Retrieving Data

The logic for get matches the C implementation:

T get(void)
{
    std::lock_guard<std::mutex> lock(mutex_);

    if(empty())
    {
        return T();
    }

    //Read data and advance the tail (we now have a free space)
    auto val = buf_[tail_];
    tail_ = (tail_ + 1) % size_;

    return val;
}

Usage

The C++ circular buffer is much simpler to use than the C implementation.

To instantiate a circular buffer, we just declare an object and specify the templated type for our buffer. Here's an example using a buffer of 10 uint32_t entries:

circular_buffer<uint32_t> circle(10);

Adding data is easy:

uint32_t x = 100;
circle.put(x);

And getting data is equally easy:

x = circle.get()

Remember that since this is a templated class, you can create a circular buffer of any type that you need.

Putting it All Together

Example implementations can be found in the embedded-resources Github repository.

Please remember that the C example is not currently threadsafe!

Further Reading