Empty a ring buffer when full

Question

I am using a ring buffer to keep track of bytes being downloaded for an embedded c application. In this small example, when there are 5 bytes in the ring buffer, I want 'empty' the buffer. In the real application I would be coping the bytes to be written to flash. My issue is, I keep skipping the 5th byte. Here is my code:

#include <stdio.h>
#include <stdint.h>

uint8_t outData;
uint8_t myDatBuf[32];


typedef struct {
    uint8_t * buffer;
    int head;
    int tail;
    int maxLen;
} ring_buffer_t;

ring_buffer_t rb;

int ring_buffer_get(ring_buffer_t *c, uint8_t *data);
int ring_buffer_put(ring_buffer_t *c, uint8_t data);
int ring_buffer_full(ring_buffer_t *c);
int ring_buffer_has_data(ring_buffer_t *c);

int main()
{
    uint8_t a = 0;

    rb.buffer = myDatBuf;
    rb.head = 0;
    rb.tail = 0;
    rb.maxLen = 5;

    for (uint8_t i = 0; i < 12; i++) {          

        if (ring_buffer_put(&rb, i) == -1) { // rb is full

            printf("Ring Buffer is full! Lets empty it\n\r");       

            for (int x = 0; x < 5; x++) {

                if (ring_buffer_get(&rb, &outData) == - 1) {        
                    printf("Buffer is Empty\n\r");              
                } else {
                    printf("val: %d\n\r", outData);
                }               
            }
        }           
    }
    printf("Empty the remaining bytes\n\r");

    while (ring_buffer_has_data(&rb)) {

        if (ring_buffer_get(&rb, &outData) == -1) {
            printf("Buffer is Empty\n\r");
        }
        else {
            printf("Rest: %d\n\r", outData);        
        }
    }   
    return 0;
}

int ring_buffer_put(ring_buffer_t *c, uint8_t data)
{
    // next is where head will point to after this write.
    int next = c->head + 1;
    if (next >= c->maxLen) {
        next = 0;
    }

    if (next == c->tail) { // check if circular buffer is full
        return -1;
    } // and return with an error.

    c->buffer[c->head] = data; // Load data and then move
    c->head = next;            // head to next data offset.
    return 0;  // return success to indicate successful push.
}

int ring_buffer_get(ring_buffer_t *c, uint8_t *data)
{
    // if the head isn't ahead of the tail, we don't have any characters
    if (c->head == c->tail) // check if circular buffer is empty
        return -1;          // and return with an error

                            // next is where tail will point to after this read.
    int next = c->tail + 1;
    if (next >= c->maxLen)
        next = 0;
    uint8_t t = c->tail;
    *data = c->buffer[t]; // Read data and then move

    c->tail = next;             // tail to next data offset.

    return 0;  // return success to indicate successful pop.
}
int ring_buffer_full(ring_buffer_t *c) {
    return c->head  == c->maxLen ? 1 : 0;
}
int ring_buffer_has_data(ring_buffer_t *c) {
    return (c->head != c->tail) ? 1 : 0;
}

Here is the output - As you can see the 5th element in the array is skipped. Any help is appreciated.

Ring Buffer is full! Lets empty it

val: 0

val: 1

val: 2

val: 3

Buffer is Empty

Ring Buffer is full! Lets empty it

val: 5

val: 6

val: 7

val: 8

Buffer is Empty

Empty the remaining bytes

Rest: 10

Rest: 11

Answer 1

As other answers say, you must distinguish between buffer full and buffer empty, and one way to do this is to hold one less than the buffer size. But that makes the buffer maintenance harder, because of it being a ring buffer, and you can't make a direct comparison without fiddling.

So my usual way is to have another variable for the number of items in the buffer, which makes it easy for the writer to tell if it is full, and the reader to tell if it is empty. The variable needs to be defined as volatile such as volatile int bufcount so it won't suffer from compiler optimisation.

It should also be atomic to guarantee that altering its value can't be interrupted, by using increment or decrement instructions in a single operation, rather than read-modify-write.

Answer 2

It is time to learn how to use a debugger. Your circular buffer has currently the following convention:

• tail : oldest character (when head != tail)
• head : where next character will go
• tail == head => buffer empty
• head = (tail - 1) modulo maxlen => buffer full (*)

That means that you will only be able to store maxlen - 1 characters in it!

Anyway, there is little more to do if you want to be able to discriminate between buffer full and buffer empty.

---

(*) the current implementation of ring_buffer_full is wrong...

Answer 3

The problem is that head == tail is an ambiguous situation. Does it mean that the buffer is empty, or does it mean that it's full? You can't have it both ways. You seem to have realised this, because ring_buffer_put returns error just before head would become equal to tail, avoiding the ambiguity. And ring_buffer_get also assumes that head == tail means empty buffer. So in fact, such a ring buffer with maxLen == 5 can contain only 4 elements!

So why does the value 4 appear to be lost? Simply because if ring_buffer_put returns -1, the buffer is flushed, but there is no attempt to put the value into the buffer another time. So the issue is not with the ring buffer implementation itself (it looks fine to me), but with the code in main that's driving it.

You could fix this by having ring_buffer_put execute the put operation, and then check whether the buffer has become full. Or you could add a separate ring_buffer_is_full function that you call before attempting to write to the buffer.