Christoper looks through a circular tube

I created a ring buffer library for embedded systems in C some years ago and have been using it when I need to add a simple queue to my software. I knew it worked correctly since I created unit tests to validate the code. However, I noticed that it wasn’t interrupt safe since one of the consumer variables is shared by the producer (the count). This library requires disabling interrupts when consuming. Not what I wanted.

There are a number of difficulties when designing ring buffers, mostly dealing with efficiencies of code or data, or the struggle between consumers and producers. My generic ringbuf library had used a single fill count, but the count had to be updated by the interrupt service routine (producer) and by the routine that retrieved the data (consumer). I tried to use read and write offset indices, but that required that I always keep an element open since the you can’t tell if the ring is empty or full when the head and tail are the same.

Absolute indices appeared to be interrupt safe, although they require that the buffer length be a power of two. That seemed to be flexible enough for most embedded work. I modified and tested my ring buffer library using that method, but my ringbuf, which allowed for a fixed length element, seemed to be overkill for what I was using it for – gathering bytes from a serial interrupt service routine. Its API also had a slight flaw such that if the consumer retrieved the data (via Pop rather than just viewing the first element), the producer was free to put new data into the buffer, overwriting the data just retrieved.

I had started my ring buffer library as a simple character (one byte) FIFO – first in, first out. So, I revisited that code, and modified it to use absolute indices. A simple byte ring buffer, first in, first out. Now I had interrupt safe code that would work in my serial interrupt service routine.

Why go to the trouble to make a library module to handle a ring buffer when slapping the following quick and dirty ring buffer code (from Stefan) into the serial module would have worked as well?

   #define N 128
   volatile unsigned int head, tail;
   volatile char buffer[N];
   unsigned int inuse() { return head - tail; }
   void put(char c) { if (inuse() != N) { buffer[head++%N] = c; } }
   void get(char* c) { if (inuse() != 0) { *c = buffer[tail++%N]; } }

Because I needed to know that it worked correctly, and I like reusable library modules. Especially high quality reusable modules. Especially high quality reusable modules that include unit tests to validate functionality. Unit tests that also serve as guides for implementers.

The new module files are ringbuf.c and ringbuf.h for the ring buffer with fixed sized elements, and fifo.c and fifo.h for the ring buffer with byte sized elements. All my versions of the ring buffer and the unit testing framework can be found in the file.

One of my original non-interrupt safe ringbuffer libraries that uses a count can be found in the ringbuf.tgz file archive. Another buffer library I wrote is a linked list that is sorted by key as elements are added, and the elements can be retrieved by key, index, or FIFO. This keylist library is useful for caching dynamic data by key.