Instance specific code generation

Question

Disclaimer: I've asked this question before on Stack overflow and got a response that this place would be a better fit so I am copy pasting the question here.

I've come up with two different approaches for implementing generic algorithms and data structures in C. And I need your help in deciding which is better.

I've been juggling between the two for the past couple of weeks trying to decide on which approach is better suitable to be used inside of company environment. Which approach produces higher code quality, is easier to debug, is more future proof, is more readable, maintainable and easier for new people to grasp. The better approach will not necessary excel at all of the aforementioned qualities.

Below I will show the two implementations with code samples and some benefits and weaknesses that I've observed. These samples are only a tiny fraction of what an actual generic data structure would contain.

#1 Instance specific compile-time code generation

FIFO.h

#if !defined(FIFO_H_)
#define FIFO_H_

#include <stdbool.h>
#include <stddef.h>

#define ARRAY_SIZE(array)       (sizeof(array) / sizeof(array[0]))

#define PREPROC_PASTE_TWO(_1, _2)   PREPROC_PASTE_TWO_(_1, _2)
#define PREPROC_PASTE_TWO_(_1, _2)  _1##_2

#define PREPROC_PASTE_THREE(_1, _2, _3)     PREPROC_PASTE_THREE_(_1, _2, _3)
#define PREPROC_PASTE_THREE_(_1, _2, _3)    _1##_2##_3

/**
 * FIFO control.
 */
typedef struct FIFO_Control
{
    size_t Head;        /**< Head index. */
    size_t Tail;        /**< Tail index. */
    size_t NofAdds;     /**< Total number of elements added to FIFO. */
    size_t NofTakes;    /**< Total number of elements taken from FIFO. */
} FIFO_Control_s;

#define FIFO_t(tag)     struct PREPROC_PASTE_TWO(FIFO_, tag)

#define FIFO_STATIC_DEFINE(handle)  {.Control = {0}, .Size = ARRAY_SIZE((handle).Buffer)}

#define FIFO_Occupied(tag, pHandle)         PREPROC_PASTE_THREE(FIFO_, tag, _Occupied)(pHandle)
#define FIFO_Free(tag, pHandle)             PREPROC_PASTE_THREE(FIFO_, tag, _Free)(pHandle)
#define FIFO_IsFull(tag, pHandle)           PREPROC_PASTE_THREE(FIFO_, tag, _IsFull)(pHandle)
#define FIFO_IsEmpty(tag, pHandle)          PREPROC_PASTE_THREE(FIFO_, tag, _IsEmpty)(pHandle)
#define FIFO_Add(tag, pHandle, pElement)    PREPROC_PASTE_THREE(FIFO_, tag, _Add)(pHandle, pElement)
#define FIFO_Take(tag, pHandle, pElement)   PREPROC_PASTE_THREE(FIFO_, tag, _Take)(pHandle, pElement)
#define FIFO_Seek(tag, pHandle, offset)     PREPROC_PASTE_THREE(FIFO_, tag, _Seek)(pHandle, offset)    
#define FIFO_Peek(tag, pHandle, offset)     PREPROC_PASTE_THREE(FIFO_, tag, _Peek)(pHandle, offset)

static inline void FIFO_AdvanceIndex(size_t *const pIndex, const size_t size, const size_t n)
{
    *pIndex = (*pIndex < (size - n)) ? *pIndex + n : *pIndex - (size - n);
}

static inline void FIFO_AdvanceHead(FIFO_Control_s *const pControl, const size_t size, const size_t n)
{
    FIFO_AdvanceIndex(&pControl->Head, size, n);
    pControl->NofAdds += n;
}

static inline void FIFO_AdvanceTail(FIFO_Control_s *const pControl, const size_t size, const size_t n)
{
    FIFO_AdvanceIndex(&pControl->Tail, size, n);
    pControl->NofTakes += n;
}

static inline size_t FIFO_Head(const FIFO_Control_s *const pControl)
{
    return pControl->Head;
}

static inline size_t FIFO_Tail(const FIFO_Control_s *const pControl)
{
    return pControl->Tail;
}

static inline size_t FIFO_NofOccupied(const FIFO_Control_s *const pControl)
{
    return (pControl->NofAdds - pControl->NofTakes);
}

static inline size_t FIFO_NofFree(const FIFO_Control_s *const pControl, const size_t size)
{
    return (size - FIFO_NofOccupied(pControl));
}

static inline bool FIFO_IsBufferFull(const FIFO_Control_s *const pControl, const size_t size)
{
    return (FIFO_NofOccupied(pControl) == size);
}

static inline bool FIFO_IsBufferEmpty(const FIFO_Control_s *const pControl)
{
    return (FIFO_NofOccupied(pControl) == 0);
}

#endif /* FIFO_H_ */

/* Instance specific compile-time code generation from here to end of file. */

#if !defined(FIFO_CONFIG_ADD_LOCK) && !defined(FIFO_CONFIG_ADD_UNLOCK)
    #define FIFO_CONFIG_ADD_LOCK()      (void)0
    #define FIFO_CONFIG_ADD_UNLOCK()    (void)0
#endif

#if !defined(FIFO_CONFIG_TAKE_LOCK) && !defined(FIFO_CONFIG_TAKE_UNLOCK)
    #define FIFO_CONFIG_TAKE_LOCK()     (void)0
    #define FIFO_CONFIG_TAKE_UNLOCK()   (void)0
#endif

/**
 * Instance specific FIFO.
 */
FIFO_t(FIFO_CONFIG_TAG)
{
    FIFO_Control_s Control;                     /**< FIFO control. */
    const size_t Size;                          /**< Buffer size. */
    FIFO_CONFIG_TYPE Buffer[FIFO_CONFIG_SIZE];  /**< Statically allocated buffer. */
};

static inline size_t FIFO_Occupied(FIFO_CONFIG_TAG, const FIFO_t(FIFO_CONFIG_TAG) *const pHandle)
{
    return FIFO_NofOccupied(&pHandle->Control);
}

static inline size_t FIFO_Free(FIFO_CONFIG_TAG, const FIFO_t(FIFO_CONFIG_TAG) *const pHandle)
{
    return FIFO_NofFree(&pHandle->Control, pHandle->Size);
}

static inline bool FIFO_IsFull(FIFO_CONFIG_TAG, const FIFO_t(FIFO_CONFIG_TAG) *const pHandle)
{
    return FIFO_IsBufferFull(&pHandle->Control, pHandle->Size);
}

static inline bool FIFO_IsEmpty(FIFO_CONFIG_TAG, const FIFO_t(FIFO_CONFIG_TAG) *const pHandle)
{
    return FIFO_IsBufferEmpty(&pHandle->Control);
}

static bool FIFO_Add(FIFO_CONFIG_TAG, FIFO_t(FIFO_CONFIG_TAG) *const pHandle, const FIFO_CONFIG_TYPE *const pElement)
{
#if !defined(FIFO_CONFIG_OVERWRITE_FULL)
    if (FIFO_IsFull(FIFO_CONFIG_TAG, pHandle))
    {
        return false;
    }
#endif

    FIFO_CONFIG_ADD_LOCK();

    pHandle->Buffer[FIFO_Head(&pHandle->Control)] = *pElement;
    FIFO_AdvanceHead(&pHandle->Control, pHandle->Size, 1);

    FIFO_CONFIG_ADD_UNLOCK();

    return true;
}

static bool FIFO_Take(FIFO_CONFIG_TAG, FIFO_t(FIFO_CONFIG_TAG) *const pHandle, FIFO_CONFIG_TYPE *const pElement)
{
    if (FIFO_IsEmpty(FIFO_CONFIG_TAG, pHandle))
    {
        return false;
    }

    FIFO_CONFIG_TAKE_LOCK();

    *pElement = pHandle->Buffer[FIFO_Tail(&pHandle->Control)];
    FIFO_AdvanceTail(&pHandle->Control, pHandle->Size, 1);

    FIFO_CONFIG_TAKE_UNLOCK();

    return true;
}

static void FIFO_Seek(FIFO_CONFIG_TAG, FIFO_t(FIFO_CONFIG_TAG) *const pHandle, const size_t offset)
{
    FIFO_CONFIG_TAKE_LOCK();

    FIFO_AdvanceTail(&pHandle->Control, pHandle->Size, offset);

    FIFO_CONFIG_TAKE_UNLOCK();
}

static FIFO_CONFIG_TYPE * FIFO_Peek(FIFO_CONFIG_TAG, const FIFO_t(FIFO_CONFIG_TAG) *const pHandle, const size_t offset)
{
    size_t index = FIFO_Tail(&pHandle->Control);
    FIFO_AdvanceIndex(&index, pHandle->Size, offset);

    return &pHandle->Buffer[index];
}

#undef FIFO_CONFIG_TAG
#undef FIFO_CONFIG_TYPE
#undef FIFO_CONFIG_SIZE
#undef FIFO_CONFIG_OVERWRITE_FULL
#undef FIFO_CONFIG_ADD_LOCK
#undef FIFO_CONFIG_ADD_UNLOCK
#undef FIFO_CONFIG_TAKE_LOCK
#undef FIFO_CONFIG_TAKE_UNLOCK

main.c

#include <stdio.h>

#define FIFO_CONFIG_TAG     MyFIFO
#define FIFO_CONFIG_TYPE    int
#define FIFO_CONFIG_SIZE    10
#include "FIFO.h"

static FIFO_t(MyFIFO) gFIFO = FIFO_STATIC_DEFINE(gFIFO);
static FIFO_t(MyFIFO) gFIFO2 = FIFO_STATIC_DEFINE(gFIFO2); // Same FIFO instance

// By reconfiguring and reincluding FIFO.h another different FIFO instance can be created
#define FIFO_CONFIG_TAG     OtherFIFO
#define FIFO_CONFIG_TYPE    float
#define FIFO_CONFIG_SIZE    3
#include "FIFO.h"  

static FIFO_t(OtherFIFO) gFIFO3 = FIFO_STATIC_DEFINE(gFIFO3);

int main(void)
{
    for (int i = 0; i < 10; i++)
    {
        FIFO_Add(MyFIFO, &gFIFO, &i);
    }
    
    int x;
    while (FIFO_Take(MyFIFO, &gFIFO, &x))
    {
        printf("%d\n", x);
    }

    FIFO_Add(OtherFIFO, &gFIFO3, &x);
    FIFO_Take(OtherFIFO, &gFIFO3, &x);
    printf("%d\n", x);
    
    return 0;
}

Benefits

• Using functions instead of macros provide type safety
• Because functions are used instead of macros means we can cleanly return and pass in variables
• Functions not necessary to be inlined at place of call which reduces overall code size
• Simple to integrate any user provided functions using through macros (see example for FIFO_CONFIG_ADD_LOCK, FIFO_CONFIG_ADD_UNLOCK)
• Code not relevant for specific configuration can be #ifdef'd out of compilation

Weaknesses

• Debugging is somewhat clumsy because placing breakpoint inside of function will result in breakpoint being placed in one of randomly selected generated function or in all functions (that's my guess)
• Functions required to be passed in the FIFO Tag (or call the tagged function)
• Unconventional (? I haven't seen anyone use this) C coding practice which feels a bit out of place
• Need to include FIFO header for every instance (unconventional C coding practice)
• Macro magic can be hard to follow
• Need separate macros to define the instance (for example #define FIFO_STATIC_DEFINE(handle) and #define FIFO_DYNAMIC_DEFINE() if instance types are different enough that they require different initializations
• Cannot include header inside a function which means that all FIFOs must be delcared at global scope

#2 Function-like macro code implementation

Queue.h

#if !defined(QUEUE_H_)
#define QUEUE_H_

#include <stdbool.h>
#include <stddef.h>

#define ARRAY_SIZE(array)       (sizeof(array) / sizeof(array[0]))

/**
 * Queue control structure.
 */
typedef struct Queue_Control
{
    size_t Head;        /**< Head index. */
    size_t Tail;        /**< Tail index. */
    size_t TotalPushed; /**< Total number of elements pushed to queue. */
    size_t TotalPopped; /**< Total number of elements popped from queue. */
} Queue_Control_s;

/**
 * Declare statically allocated queue.
 */
#define QUEUE_DECLARE_STATIC(type, size)                                        \
struct                                                                          \
{                                                                               \
    Queue_Control_s Control;    /**< Queue control. */                          \
    const size_t Size;          /**< Queue size (number of elements). */        \
    type Buffer[size];          /**< Statically allocated element buffer. */    \
}

/**
 * Define statically allocated queue.
 */
#define QUEUE_DEFINE_STATIC(handle) {.Control = {0}, .Size = ARRAY_SIZE((handle).Buffer)}

inline static size_t Queue_Generic_AdvanceIndex(const size_t index, const size_t size, const size_t n)
{
    return ((index < (size - n)) ? index + n : index - (size - n));
}

inline static void Queue_Generic_AdvanceHead(Queue_Control_s *const pControl, const size_t size, const size_t n)
{
    pControl->Head = Queue_Generic_AdvanceIndex(pControl->Head, size, n);
    pControl->TotalPushed += n;
}

inline static void Queue_Generic_AdvanceTail(Queue_Control_s *const pControl, const size_t size, const size_t n)
{
    pControl->Tail = Queue_Generic_AdvanceIndex(pControl->Tail, size, n);
    pControl->TotalPopped += n;
}

inline static size_t Queue_Generic_Count(const Queue_Control_s control)
{
    return (control.TotalPushed - control.TotalPopped);
}

inline static size_t Queue_Generic_Free(const Queue_Control_s control, const size_t size)
{
    return (size - Queue_Generic_Count(control));
}

inline static bool Queue_Generic_IsFull(const Queue_Control_s control, const size_t size)
{
    return (Queue_Generic_Count(control) == size);
}

inline static bool Queue_Generic_IsEmpty(const Queue_Control_s control)
{
    return (Queue_Generic_Count(control) == 0);
}

#define Queue_Count(handle)      Queue_Generic_Count((handle).Control)

#define Queue_Free(handle)       Queue_Generic_Free((handle).Control, (handle).Size)

#define Queue_IsFull(handle)     Queue_Generic_IsFull((handle).Control, (handle).Size)

#define Queue_IsEmpty(handle)    Queue_Generic_IsEmpty((handle).Control)

#define Queue_Push(handle, element)                                     \
    do                                                                  \
    {                                                                   \
        (handle).Buffer[(handle).Control.Head] = (element);             \
        Queue_Generic_AdvanceHead(&(handle).Control, (handle).Size, 1); \
    } while(0)

#define Queue_Pop(handle, pElement)                                     \
    do                                                                  \
    {                                                                   \
        *(pElement) = (handle).Buffer[(handle).Control.Tail];           \
        Queue_Generic_AdvanceTail(&(handle).Control, (handle).Size, 1);  \
    } while (0)

#define Queue_Seek(handle, offset) Queue_Generic_AdvanceTail(&(handle).Control, (handle).Size, offset)

#define Queue_Peek(handle, offset)  (&(handle).Buffer[Queue_Generic_AdvanceIndex(Queue_Generic_Tail(handle), size, offset)])

#endif /* QUEUE_H_ */

main.c

#include <stdio.h>
static QUEUE_DECLARE_STATIC(int, 10) gQueue = QUEUE_DEFINE_STATIC(gQueue);
static QUEUE_DECLARE_STATIC(float, 3) gQueue2 = QUEUE_DEFINE_STATIC(gQueue2);

int main(void)
{
    for (int i = 0; i < 10; i++)
    {
        Queue_Push(gQueue, i);
    }

    int x;
    while (!Queue_IsEmpty(gQueue))
    {
        Queue_Pop(gQueue, &x);
        printf("%d\n", x);
    }
    return 0;
}

Benefits

• Header is included only once regardless of how many queue instances are used in single source file (conventional C coding practice)
• More conventional C code compared to #1 approach
• Pass into function-like macros queue handle directly (no pointers)
• One single function definition for all types of queues (dont' need Tag)
• Queue configuration (type, size) is in the declaration of queue so don'te need to #define the configuration and include the header

Weaknesses

• Can result in long macros
• Debugging macros can be painful
• Because macros are used instead of functions they sometimes need to rely on do{} while(0) and comma operator constructs which have their drawbacks especially when returning values (which is really easy with functions)
• Macros are always inlined at place of call so code size can blow up
• Compiler warnings and errors related to macros can sometimes appear as incoherent and not understandable
• All possible functions for different instance configuration must be provided by the header even if the specific instance does not use it, which means that multiple functions-like macros (with different names) will have to be provided to achieve some functionality in different ways (adding/taking multiple elements described at start of this post)
• Cannot have easily accessible user provided functions (like thread lock and unlock from previous example) depending on the configuration

For a mental excercise try to imagine how both of the approaches would implement adding and taking multiple elements from FIFO/Queue using either element-by-element copy or standard memcpy(). FIFO would implement only one set of functions: FIFO_AddMultiple(), FIFO_TakeMultiple() while queue would have to implement two set of functions: Queue_PushMultipleElementWise(), Queue_PushMultipleMemoryWise(), Queue_PopMultipleElementWise(), Queue_PopMultipleMemoryWise().

Which one would you use and why?

I am leaning towards #1 but am also afraid that if our code base will use approach #1 heavily then it will not be easy for new employees to grasp and maintain the code. Also, and more importantly, I am not sure how the approach #1 integrates and plays nicely with testing, static analysis and automotive standards.

Any improvements, changes or comments to either approach is welcome.

Answer 1

Enable compiler warnings and fix all of them

Your first approach compiles, but my compiler shows a lot of warnings, including const-correctness issues and pointers to incorrect types being passed.

Usage is more important than the implementation

When it comes to libraries and utilities, the primary goal is to make their usage safe, easy and reliable. How it is implemented is of secondary concern. So if I had to choose between the two approaches, I will definitely go with the second one, mainly because it is much less error-prone: there is no chance I can forget a #define or #include "FIFO.h", and I cannot accidentally pass the wrong tag.

About the benefits and weaknesses

There are several things you mention in your benefits and weaknesses analysis that are incorrect. For example

• Using functions instead of macros provide type safety

You still rely on macros to call those functions. Also, functions are not necessarily more type safe than macros. You can have functions take void pointers and be type unsafe.

• Functions not necessary to be inlined at place of call which reduces overall code size
• Macros are always inlined at place of call so code size can blow up

This is wrong. Macros are expanded at the place of call, but that doesn't mean the compiler cannot see that it expands the same code over and over, and decide to un-inline it (this is sometimes called "outlining"). Also, compilers nowadays inline functions heavily, because it makes other optimizations work much better.

• Debugging is somewhat clumsy because placing breakpoint inside of function will result in breakpoint being placed in one of randomly selected generated function or in all functions (that's my guess)

Putting a breakpoint in a macro is not possible. However, there is a clear definition of what a function is, and there is no function overloading in C, so setting a breakpoint for a given function name should be unambiguous. In your first approach, there is no function FIFO_Add() for example, but there will be a function FIFO_MyFIFO_Add() that you can set a breakpoint for.

• Cannot have easily accessible user provided functions (like thread lock and unlock from previous example) depending on the configuration

Why not? You could easily put pointers to those functions in struct Queue_Control, and create a version of QUEUE_DEFINE_STATIC() that takes those function pointers as arguments to store in the control block.

Consider using C++

Writing type-safe generic code in C is hard or impossible. However, nowadays there is almost no excuse not to consider to migrate to C++: the compilers are very good, and it is easy to port C to C++. The C++ standard library even comes with a queue type, so you could write this:

import std;

int main()
{
    std::queue<int> gQueue;

    for (int i = 0; i < 10; i++)
    {
        gQueue.push(i);
    }

    while (!gQueue.empty())
    {
        std::print("{}\n", gQueue.front());
        gQueue.pop();
    }
}

There are no macros here, everything is type-safe, and gQueue.front() returns a value, so no need to pass a pointer to a variable. (I've used C++23 here to show off import and std::print(), but the std::queue part has been around since C++98.)

std::queue uses a dynamic array under the hood, so you don't specify a size, and it can grow unbounded. You could also implement your own statically-sized queue type as a templated class:

template<typename T, std::size_t Size>
class Queue
{
    size_t Head = 0;
    size_t Tail = 0;
    size_t TotalPushed = 0;
    size_t TotalPopped = 0;
    T Buffer[Size];

    static std::size_t AdvanceIndex(const std::size_t index, const std::size_t n)
    {
        return ((index < (Size - n)) ? index + n : index - (Size - n));
    }

    void AdvanceHead(const std::size_t n = 1)
    {
        Head = AdvanceIndex(Head, n);
        TotalPushed += n;
    }
    …
public:
    void Push(const T& element)
    {
        Buffer[Head] = element;
        AdvanceHead();
    }
    …
};

Note how all the functions you had in your C version are there, just without any macros and almost no pointers, resulting in much cleaner code. You would use it like so:

Queue<int, 10> gQueue;

for (int i = 0; i < 10; i++)
{
    gQueue.Push(i);
}
…