Generic ring-buffer

Question

What would be the preferred C way of implementing a simple generic ring-buffer.
Which approach from the 2 below (or even some 3rd) would you use and why?
Specifically, this will be part of an embedded automotive application, which should conform to MISRA C:2012. I am looking for an approach that is the easiest to understand and maintain. Performance is not a deciding factor.

Option 1, having common structure and using void pointers:

typedef struct ring_buffer
{
    void *start_of_buffer; // inclusive
    void *end_of_buffer; // exclusive
    size_t element_size;
    void *head;
    void *tail;
    size_t count;
} ring_buffer_t;

void * next_pointer(ring_buffer_t *handle, void *pointer)
{
    void *next = (char *)pointer + handle->element_size;
    if (next == handle->end_of_buffer)
        next = handle->start_of_buffer;
    
    return next;
}

void push(ring_buffer_t *handle, void *element)
{
    memcpy(handle->head, element, handle->element_size);
    handle->head = next_pointer(handle, handle->head);
    handle-count++;
}

void pop(ring_buffer_t *handle, void *element)
{
    memcpy(element, handle->tail, handle->element_size);
    handle->tail = next_pointer(handle, handle->tail);
    handle->count--;
}

Option 2, generating type specific structure and using macros:

#define ring_buffer_t(type)    \
    struct                     \
    {                          \
        type *start_of_buffer; \
        type *end_of_buffer;   \
        type *head;            \
        type *tail;            \
        size_t count;          \
    }

#define NEXT_POINTER(handle, pointer) \
    (pointer == (handle.end_of_buffer - 1)) ? start_of_buffer : pointer + 1

#define PUSH(handle, element)                            \
    do                                                   \
    {                                                    \
        *handle.head = element;                          \
        handle.head = NEXT_POINTER(handle, handle.head); \
        handle.count++;                                  \
    } while (0)

#define POP(handle, element)                             \
    do                                                   \
    {                                                    \
        element = *handle.tail;                          \
        handle.tail = NEXT_POINTER(handle, handle.tail); \
        handle.count--;                                  \
    } while (0)

I am leaning more towards option 2 because:

this is a simple data structure with very simple API and not much logic in push and pop functions
option 1 includes some overhead having to store element size and then increment pointers based on this size
using clear variable assignment instead of memcpy() as in option 1
type-safe pushing and popping as opposed to option 1

What I dislike about option 2:

macros complicating maintainability and possibly making it hard for new developers to understand (although in this case I think it is pretty straightforward)
macros making it more difficult to debug (although not much to debug)
multiple statements in push and pop macros (although only 3)

"embedded automotive application" It would be helpful if you'd cite the MISRA / AUTOSAR standards the code should conform to. — J_H
– J_H, Commented Sep 23, 2024 at 3:45

Lundin · Accepted Answer · 2024-09-25 11:57:05Z

My comment when you posted this on SO:

Why do you need it to be generic in the first place? The normal way to implement this is option #3, use a typedef. Which means there can only be one ring buffer type in the project, but that probably covers some 95% of all use-cases. So why do you need multiple ring buffers with different types in your project?

That was before I noticed here that you also need MISRA C compliance. So likely a mission-critical product. As it turns out, that's a strong argument to avoid any form of type-generic programming.

The need for type-generic programming appears when we for some reason don't know what types the application programmer will use, for example when we are writing some manner of PC library for use in end applications. This can never be allowed to be a valid scenario in mission-critical software! Everything and I mean everything needs to be deterministic. Types, numeric limits, maximum memory use etc etc. So the use of something like void* is already highly questionable, let alone using a whole type-generic library. Common best practices in safety-related software is instead to make a hard-coded, project-specific version.

For MISRA C specifically, there's lots of rules against function-like macros and the # or ## operators. Their rationale is sound, function-like macros is a well-known source of bugs and maintenance problems. We can dodge our way around those rules in MISRA C though and sometimes it is justified. But to dodge numerous MISRA rules just to be able to use type-generic libraries isn't a sensible rationale.

Now if you truly need generic programming because you truly need different ring buffers for multiple types as per project requirements, then the way to go is probably to convert the macro version to a "X macro" based one, where you maintain a finite list of types allowed in the project, then generate code based on that list. This eliminates code-reuse but eats a lot of program size, since such a solution will work just like C++ template and generate a version of each function per type.

An implementation detail of your ring buffer is that it doesn't support any lock or data protection mechanism to avoid race condition. The most common use of ring buffers in embedded systems by far is when communicating from an ISR or process to the rest of the program, meaning that the buffer access need protection against race conditions. Something to consider.

Regarding do while(0) it's a handy trick but perhaps not when going for MISRA C compliance. Check out What is do { } while(0) in macros and should we use it? which also addresses the MISRA aspect. In fact MISRA C used to enforce do while(0) macros back in the 2004 version but it was removed as a requirement in the 2012 version since there's already a rule enforcing you to always use {} compound statements. do while(0) will only mess up compiler diagnostics in that case.

Amusingly, I just looked up some proprietary code for a ring buffer implementation I did back in 2009. It has race condition locks so it's more complex than your version #1. But as it turns out, I did implement it type-generic with void pointers just like your code and then put it through MISRA C compliance. So much for arguing against generic programming in safety-related software! :) That code was tested very extensive with stress tests & dynamic analysis etc and it now runs inside lots of heavy machinery since 15 years back. But I wouldn't have written code like that today. — Lundin
– Lundin, Commented Sep 25, 2024 at 12:00

Toby Speight · Accepted Answer · 2024-09-23 08:21:40Z

If you choose to go with the macros, we should be doing more to improve their safety. For example, use the scope introduced by the do … while(0) idiom to avoid expanding handle multiple times (we'll need to pass the object type, but that's no bad thing), and use parentheses around each expanded argument to prevent operator-precedence surprises.

Personally, I steer away from macros as far as possible, because they add to the cognitive load on the reader.

An option you haven't considered is to use a macro to define the structure and its accessor functions, perhaps giving the best of both worlds (type safety with simple C function interface):

#include <stddef.h>

#define DECLARE_RING_BUFFER(type)                                       \
    typedef struct ring_buffer_##type                                   \
    {                                                                   \
        type *start_of_buffer;                                          \
        type *end_of_buffer;                                            \
        type *head;                                                     \
        type *tail;                                                     \
        size_t count;                                                   \
    } ring_buffer_##type;                                               \
                                                                        \
    void ring_buffer_##type##_push(ring_buffer_##type *ring, type value) \
    {                                                                   \
        *ring->head++ = value;                                          \
        if (ring->head == ring->end_of_buffer) {                        \
            ring->head = ring->start_of_buffer;                         \
        }                                                               \
        ++ring->count;                                                  \
    }                                                                   \
                                                                        \
    type ring_buffer_##type##_pop(ring_buffer_##type *ring)             \
    {                                                                   \
        type value = *ring->tail++;                                     \
        if (ring->tail == ring->end_of_buffer) {                        \
            ring->tail = ring->start_of_buffer;                         \
        }                                                               \
        --ring->count;                                                  \
        return value;                                                   \
    }

Example usage:

#include <stdio.h>

DECLARE_RING_BUFFER(int)

int main(void)
{
    int storage[20];
    ring_buffer_int r = {
        storage,
        storage + 20,
        storage,
        storage,
        0
    };

    for (int i = 100;  i < 115;  ++i)
        ring_buffer_int_push(&r, i);

    for (int i = 0;  i < 10;  ++i)
        printf("%d ", ring_buffer_int_pop(&r));
    puts("");

    for (int i = 0;  i < 15;  ++i)
        ring_buffer_int_push(&r, i);

    for (int i = 0;  i < 20;  ++i)
        printf("%d ", ring_buffer_int_pop(&r));
    puts("");
}

In all these implementations, the responsibility to avoid overflow or underflow is on the user. Could we provide functions to make that easier? Simple empty() and full() predicates could be helpful.

Stack Exchange Network

Generic ring-buffer

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Generic ring-buffer

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions