I Write Type Safe Generic Data Structures in C

I write type safe generic data structures in C using a technique that I haven’t seen elsewhere¹. It uses unions to associate type information with a generic data structure, but we’ll get to that. My approach works for any type of data structure: maps, arrays, binary trees… but for this article I illustrate the ideas by implementing a basic linked list. Since many people aren’t aware you can do C generics at all, I figured I’d start simple and build up to this:

typedef struct {
    int value;
} Foo;
    
List(int) int_list = {0};
list_prepend(&int_list, 3);

List(Foo) foo_list = {0};
list_prepend(&foo_list, (Foo){ 5 });
list_prepend(&foo_list, (Foo){ 3 });

// this won't compile, which is good!
// list_prepend(&foo_list, 7); 

list_for(item, &foo_list) {
    // `item` is of type `Foo *`
    printf("%i\n", item->value);
}

Generics level 0: Generic Headers

I hesitate to even mention this, because I do not like it², but its worth comparing to the technique at the end of this article. It works like this: you write your data structure in a header, using macros for your types, and then #include the header multiple times; once for each type the data structure will be used with.

#ifndef T
#error "T must be defined before including this header"
#endif

#define _CONCAT(a, b) a##b
#define CONCAT(a, b) _CONCAT(a, b)

#define NODE_TYPE CONCAT(T, ListNode)
#define PREPEND_FUNC CONCAT(T, _list_prepend)

typedef struct NODE_TYPE NODE_TYPE;
struct NODE_TYPE {
    NODE_TYPE *next;
    T data;
};

void PREPEND_FUNC(NODE_TYPE **head, T data) {
    NODE_TYPE *node = malloc(sizeof(*node));
    node->data = data;
    node->next = *head;
    *head = node;
}

#undef T
#undef _CONCAT
#undef CONCAT
#undef NODE_TYPE
#undef PREPEND_FUNC

typedef struct {
    int a;
} Foo;

typedef struct {
    char *str;
    double num;
} Bar;

#define T Foo
#include "list.h"

#define T Bar
#include "list.h"

FooListNode *foo_head = NULL;
Foo_list_prepend(&foo_head, (Foo){1})

BarListNode *bar_head = NULL;
Bar_list_prepend(&bar_head, (Bar){"hello", 5.4})

While it is generic and type safe, it has downsides:

• makes it hard to find where types and functions are defined (because they’re constructed by macros)
• code completion may not handle them well
• bloats your binary size and build times with copies of the same functions
• requires using type-prefixed functions: Foo_list_prepend() and int_list_prepend() vs just list_prepend()

Generics level 1: void *

Another way to make a data structure generic is to use void *. It’s not type safe but we’ll get to that.

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    void *data;
};

void list_prepend(ListNode **head, void *data) {
    ListNode *node = malloc(sizeof(*node));
    node->data = data;
    node->next = *head;
    *head = node;
}

Note: malloc is used for familiarity, but I highly recommend Arenas instead. You can watch or read about them.

Having ListNode and its data as separate allocations isn’t ideal from a memory and performance perspective. It requires 2 allocations per node when one would do, the data pointer uses memory unnecessarily, and you will likely get two cache misses per node when traversing the list: once getting the next node, and once getting its data. We can fix these issues with…

Generics level 2: Inline storage

Instead of storing a pointer to the node’s data, we can use a Flexible Array Member to store the data inside the node. To do so, we make a single allocation large enough for both the node and the type it stores³:

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    char data[]; // glossing over some padding/alignment details here
};

void list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size) 
{
    ListNode *node = malloc(sizeof(*node) + data_size);
    memcpy(node->data, data, data_size);
    node->next = *head;
    *head = node;
}

void main() {
    ListNode *foo_list = NULL;
    Foo foo = {5};
    list_prepend(&foo_list, &foo, sizeof(foo));
}

Now next and the actual contents of data are beside each other in memory, solving the issues of the void * approach. Unfortunately we now have to pass the size, but we’ll fix that in the next section

If you wanted to avoid the memcpy, and initialize the node’s memory directly, you could do so with a list_alloc_front function:

void *list_alloc_front(ListNode **head, size_t data_size)  {
    ListNode *node = malloc(sizeof(*node) + data_size);
    node->next = *head;
    *head = node;
    return node->data;
}

Foo *new_foo = list_alloc_front(&foo_list, sizeof(*new_foo));
new_foo->value = 5;

Generics level 3: Type Checking

The part you’ve all been waiting for: how to get the compiler to error when we try to add the wrong type to a list. The way I found to do this is to use a union with a payload member that has a parameterized type:

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}

List(Foo) foo_list = {0};
List(int) int_list = {0};

How does that help us? Well, we can use the ternary operator to enforce that the item parameter is the same type as the list’s payload:

// Note: leading underscore add to the 
// function name since only the macro should call it
void _list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size);

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload)) 
               
List(Foo) *foo_list = NULL;
Bar bar = {5, 6};
list_prepend(&foo_list, &bar); // error!

The macro also handles passing the item size for us! This is the error Clang produces when adding the wrong type to the list:

error: pointer type mismatch ('Foo *' and 'Bar *') [-Werror,-Wpointer-type-mismatch]
   38 |     list_prepend(&foo_list, &bar);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: expanded from macro 'list_prepend'
   15 |     _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload))
      |    

Macros get a bad rep, but I think this is fairly understandable. Some things to note: payload is never used at runtime, it exists just for type information at compile time. Using a union makes payload not consume any memory.

If you’re writing a generic function that needs to return a pointer to contained data, you can use __typeof__() to cast the return type from void * to the data structure’s payload type. __typeof__() is supported in all three big C compilers (clang, gcc, and msvc since version 19.39).

#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))
    
void *_list_alloc_front(ListNode **head) {...}

If for some reason you don’t like using the ternary operator to ensure two types are the same, a previous version of this article used a different technique:

// Note: I added a leading underscore to the 
// function name since only the macro should call it
void _list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size);

#define list_prepend(list, item) \
    /* cast function type */ \
    ((void (*)(ListNode **, \
               __typeof__((list)->payload), \
               size_t))_list_prepend)  \
               /* call function */ \
               (&((list)->head), item, sizeof(*(list)->payload)) 
               
List(Foo) *foo_list = NULL;
Bar bar = {5};
list_prepend(&foo_list, &bar); // error!

#define List(type) struct { \
    ListNode *head; \
    type *payload; \
}

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload)) 

Passing a Parameter

One annoying thing about C compilers released prior to late 2025⁴ is that they do not consider these two variables to have the same type:

List(Foo) a;
List(Foo) b = a; // error

void my_function(List(Foo) list);
my_function(a); // error: incompatible type

Even though the variables have identical type definitions, the compiler still errors because they are two distinct definitions. A typedef avoids the issue:

typedef List(Foo) ListFoo; // this makes it all work

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok

List(Foo) local_foo_list; // still works 

Conclusion

You can use this for any type of data structure, even ones with multiple associated types, like a hash map:

typedef struct {
    ...
} MapInternal;

#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

For more detail, like how the list_for macro is implemented, see the code here

Thanks to Martin Fouilleul for the encouragement to finish this post, which I’ve been sitting on for months, and the feedback on early drafts.