Home / Programming / Implementing Circular/Ring Buffer in Embedded C

Implementing Circular/Ring Buffer in Embedded C

Most embedded programmers come to realize that majority of the code that they write in a day are either related to state machines or circular buffers or queues. In this article we will have a look at circular buffers and how you can implement them in low memory devices.

For those of you who don’t know what a circular buffer is, its a kind of array that will loop back to 0 after it reaches the maximum number of bytes in the buffer. This is done by having two pointers to the array one points to the “head” and the other points to the “tail” of the buffer. As data is added to the buffer, the head pointer moves up and as the data is being removed (read) the tail pointer moves up. This is implementation dependent and varies with perspective. So for the sake of argument we will agree, you write at head and read from tail.

The next big thing about circular buffers is that there is no “clean way” to differentiate the buffer full and buffer empty cases. This is because at both cases, head is equal to tail. There are a lot of ways/workarounds to deal with this issue but none IMHO is as readable as the one I am presenting here.

In this method, there are two critical cases (boundary conditions) that have to be considered while implementing a circular buffer,

  • Head is equal to tail -> the buffer is empty
  • (Head + 1) is equal to tail -> the buffer is full

The essence is that every time you try to push, you check for “is-buffer-full” condition and every time there is pop, you check for “is-buffer-empty”. Armed with knowledge, I will proceed to define the data types!

There goes our primary structure to handle the buffer and its pointers. Notice that buffer is uint8_t * const buffer .  const uint8_t * is a pointer to a const uint8_t value being pointed to can’t be changed but the pointer can be. On the other hand uint8_t * const is a constant pointer to a uint8_t the value being pointed at can change but the pointer can’t.

This done so that you will be able to make changes to the buffer but you will not be able to accidentally orphan the pointer. This is a very good safety measure and I so strongly suggest you not skip that part.

The variable ‘next’ in the functions will point to the location that the successive call to the routines will write-to/read-from. As discussed earlier, if the next location points to the location pointed by the tail then we know that the buffer is full so we don’t write the new data into the buffer (return -1). Depending on the operation push/pop if there is space/data in the buffer, we will append/remove that data and move the head/tail pointer to the location pointed by the ‘next’ variable.

How use it?

I think its pretty obvious. You have to define a buffer of a certain length and then create a instance of circBuf_t and assign the pointer to buffer and its max len. It goes without saying that the buffer has to be global (in most cases) or it has to be in stack so long as you need to use it if you prefer it be local.

To make life a little easy I wrote a macro that will make this look a lot better.

So for example if you need a circular buffer of length 32 bytes, you would do something like this in your application,

I hope this post was of some help in understanding circular buffers. We will see more such data structures in the future.

Update (2o Sep 2015):

I think some of you might have guessed the drawback of this method like Onufry Zagloba. Yes we use only maxLen - 1 space of the buffer. That is we never actually completely use the space. That is one element is wasted all the time. Some of you might have mistaken it for a off-by-one but trust me its not. I feel it is a very necessary evil for data units less than or equal to size of pointer.

I will take this up a separate discussion. Hope fully you should find it here soon.

About Siddharth

Siddharth is a Firmware Engineer, techie, and a movie-buff. His interests include, Programming, Embedded Systems, Linux, Robotics, CV, Carpentry and a lot more. At times, you could see some of his sunday projects converge on release quality. You get to know him on the following social channels.
  • Pingback: Arduino Based Iambic Keyer(s) | WB8NBS()

  • Onufry Zagloba

    you will never fill all elements in the buffer using provided functions

    • Though it might look like an off by one error, it’s intentionally left blank. I will try to cover this separately.

  • fixer

    uint8_t circBufPop(circBuf_t *c) returns a signed int (-1) for the error case for a function defined to return uint.

    • Fixed it. Thanks. The right way to do it is to use the return values purely for error handling. (in-band signalling always sucks!)

  • Pingback: Arduino Iambic Keyer 2016 – Part 3: Operation | WB8NBS()

  • Luis Manuel Sánchez

    Good article! thanks.
    What if I want to make a function pointer ring buffer?
    I mean, to use a ring buffer to handle function pointers so that each function is called sequentially from the ring buffer.

    • Luis Manuel Sánchez

      he he… just did it. Just had to replace the data type from uint8_t to the function typedef. IT’s working! 🙂 thanks!

  • Supreeth Anil

    Why we are using buffer as a constant pointer? What are the possible pitfalls in embedded system if I use a pointer variable?

    • The buffer is usually allocated globally. In that case, there is no need for it to be changed at runtime. It just adds one more level of security from some other buffer flow from corrupting this space.

      • Supreeth Anil

        Good article and thanks for the reply

  • Cole Jepson

    What does ## do in c? I haven’t seen that before. This article was very helpful. Thanks!

  • Martin Peevski

    Hello, I think you have a bug at the circBufPop function. You must first increment the tail index and then get the data.

Keep in touch with the current trends!
Did you like this article? Sign up and get our latest posts delivered to your inbox!
  We hate spam and never share your details.