How do I implement a circular list (ring buffer) in C?

A very simple implementation, expressed in C. Implements a circular buffer style FIFO queue. Could be made more generic by creating a structure containing the queue size, queue data, and queue indexes (in and out), which would be passed in with the data to add or remove from the queue. These same routines could then handle several queues. Also note that this allows queues of any size, although speedups can be used if you use powers of 2 and customize the code further.

/* Very simple queue
 * These are FIFO queues which discard the new data when full.
 *
 * Queue is empty when in == out.
 * If in != out, then 
 *  - items are placed into in before incrementing in
 *  - items are removed from out before incrementing out
 * Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE;
 *
 * The queue will hold QUEUE_ELEMENTS number of items before the
 * calls to QueuePut fail.
 */

/* Queue structure */
#define QUEUE_ELEMENTS 100
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1)
int Queue[QUEUE_SIZE];
int QueueIn, QueueOut;

void QueueInit(void)
{
    QueueIn = QueueOut = 0;
}

int QueuePut(int new)
{
    if(QueueIn == (( QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE))
    {
        return -1; /* Queue Full*/
    }

    Queue[QueueIn] = new;

    QueueIn = (QueueIn + 1) % QUEUE_SIZE;

    return 0; // No errors
}

int QueueGet(int *old)
{
    if(QueueIn == QueueOut)
    {
        return -1; /* Queue Empty - nothing to get*/
    }

    *old = Queue[QueueOut];

    QueueOut = (QueueOut + 1) % QUEUE_SIZE;

    return 0; // No errors
}

Use a linked list. Maintain separate pointers for the head and tail. Pop from the head of the list, push onto the tail. If you want it circular, just make sure the new tail always points to the head.

I can understand why you might want to implement a FIFO using a linked list, but why make it a circular list?

If you want a fixed length circular list. You can use a (dynamic) array. Use two variables for houskeeping. One for the position of the next element, one to count the number of elements.

Put: put element on free place. move the position (modulo length). Add 1 to the count unless count equals the lengtht of the list. Get: only if count>0. move the position to the left (modulo length). Decrement the count.

Use an array and keep a variable P with the first available position.

Increase P every time you add a new element.

To know the equivalent index of P in your array do (P % n) where n is the size of your array.

I am using this for my microcontroller. For code simplicity one byte will be unfilled. Aka size - 1 is the full capacity actually.

fifo_t* createFifoToHeap(size_t size)
{
    byte_t* buffer = (byte_t*)malloc(size);

    if (buffer == NULL)
        return NULL;

    fifo_t* fifo = (fifo_t*)malloc(sizeof(fifo_t));

    if (fifo == NULL)
    {
       free(buffer);
       return NULL;
    }

    fifo->buffer = buffer;
    fifo->head = 0;
    fifo->tail = 0;
    fifo->size = size;

    return fifo;
}

#define CHECK_FIFO_NULL(fifo) MAC_FUNC(if (fifo == NULL) return 0;)

size_t fifoPushByte(fifo_t* fifo, byte_t byte)
{
    CHECK_FIFO_NULL(fifo);

    if (fifoIsFull(fifo) == true)
       return 0;

    fifo->buffer[fifo->head] = byte;

    fifo->head++;
    if (fifo->head == fifo->size)
       fifo->head = 0;

    return 1;
}

size_t fifoPushBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
    CHECK_FIFO_NULL(fifo);

    for (uint32_t i = 0; i < count; i++)
    {
        if (fifoPushByte(fifo, bytes[i]) == 0)
            return i;
    }

    return count;
}

size_t fifoPopByte(fifo_t* fifo, byte_t* byte)
{
    CHECK_FIFO_NULL(fifo);

    if (fifoIsEmpty(fifo) == true)
        return 0;

    *byte = fifo->buffer[fifo->tail];

    fifo->tail++;
    if (fifo->tail == fifo->size)
        fifo->tail = 0;

    return 1;
}

size_t fifoPopBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
    CHECK_FIFO_NULL(fifo);

    for (uint32_t i = 0; i < count; i++)
    {
        if (fifoPopByte(fifo, bytes + i) == 0)
            return i;
    }

    return count;
}

bool fifoIsFull(fifo_t* fifo)
{
    if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
        return true;
    else
        return false;
}

bool fifoIsEmpty(fifo_t* fifo)
{
    if (fifo->head == fifo->tail)
        return true;
    else
        return false;
}

size_t fifoBytesFilled(fifo_t* fifo)
{
    if (fifo->head == fifo->tail)
        return 0;
    else if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
        return fifo->size;
    else if (fifo->head < fifo->tail)
        return (fifo->head) + (fifo->size - fifo->tail);
    else
        return fifo->head - fifo->tail; 
}