See my follow-up article: “A Fast, Growable Array With Stable Pointers in C”
\nI write type safe generic data structures in C using a technique that I haven’t seen elsewhere<sup>1</sup>. 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:
\ntypedef struct {\n int value;\n} Foo;\n \nList(int) int_list = {0};\nlist_prepend(&int_list, 3);\nList(Foo) foo_list = {0};\nlist_prepend(&foo_list, (Foo){ 5 });\nlist_prepend(&foo_list, (Foo){ 3 });\n// this won't compile, which is good!\n// list_prepend(&foo_list, 7); \nlist_for(item, &foo_list) {\n // `item` is of type `Foo *`\n printf("%i\\n", item->value);\n}I hesitate to even mention this, because I do not like it<sup>2</sup>, 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.
list.h
#ifndef T\n#error "T must be defined before including this header"\n#endif\n#define _CONCAT(a, b) a##b\n#define CONCAT(a, b) _CONCAT(a, b)\n#define NODE_TYPE CONCAT(T, ListNode)\n#define PREPEND_FUNC CONCAT(T, _list_prepend)\ntypedef struct NODE_TYPE NODE_TYPE;\nstruct NODE_TYPE {\n NODE_TYPE *next;\n T data;\n};\nvoid PREPEND_FUNC(NODE_TYPE **head, T data) {\n NODE_TYPE *node = malloc(sizeof(*node));\n node->data = data;\n node->next = *head;\n *head = node;\n}\n#undef T\n#undef _CONCAT\n#undef CONCAT\n#undef NODE_TYPE\n#undef PREPEND_FUNCmain.c
typedef struct {\n int a;\n} Foo;\ntypedef struct {\n char *str;\n double num;\n} Bar;\n#define T Foo\n#include "list.h"\n#define T Bar\n#include "list.h"\nFooListNode *foo_head = NULL;\nFoo_list_prepend(&foo_head, (Foo){1})\nBarListNode *bar_head = NULL;\nBar_list_prepend(&bar_head, (Bar){"hello", 5.4})While it is generic and type safe, it has downsides:
\nFoo_list_prepend() and int_list_prepend() vs justlist_prepend()void *\nAnother 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;\nstruct ListNode {\n ListNode *next;\n void *data;\n};\nvoid list_prepend(ListNode **head, void *data) {\n ListNode *node = malloc(sizeof(*node));\n node->data = data;\n node->next = *head;\n *head = node;\n}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…
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<sup>3</sup>:
\ntypedef struct ListNode ListNode;\nstruct ListNode {\n ListNode *next;\n char data[]; // glossing over some padding/alignment details here\n};\nvoid list_prepend(ListNode **head, \n void *data, \n size_t data_size) \n{\n ListNode *node = malloc(sizeof(*node) + data_size);\n memcpy(node->data, data, data_size);\n node->next = *head;\n *head = node;\n}\nvoid main() {\n ListNode *foo_list = NULL;\n Foo foo = {5};\n list_prepend(&foo_list, &foo, sizeof(foo));\n}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) {\n ListNode *node = malloc(sizeof(*node) + data_size);\n node->next = *head;\n *head = node;\n return node->data;\n}\nFoo *new_foo = list_alloc_front(&foo_list, sizeof(*new_foo));\nnew_foo->value = 5;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 { \\\n ListNode *head; \\\n type *payload; \\\n}\nList(Foo) foo_list = {0};\nList(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 \n// function name since only the macro should call it\nvoid _list_prepend(ListNode **head, \n void *data, \n size_t data_size);\n#define list_prepend(list, item) \\\n _list_prepend(&((list)->head), \\\n (1 ? (item) : (list)->payload), \\\n sizeof(*(list)->payload)) \n \nList(Foo) *foo_list = NULL;\nBar bar = {5, 6};\nlist_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:
\nerror: pointer type mismatch ('Foo *' and 'Bar *') [-Werror,-Wpointer-type-mismatch]\n 38 | list_prepend(&foo_list, &bar);\n | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~\nnote: expanded from macro 'list_prepend'\n 15 | _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload))\n | 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) \\\n (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))\n \nvoid *_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: We can use Calling a typecast function pointer is technically undefined behavior, but in practice it’s fine when compiled by modern compilers targeting modern platforms. It’s possible to do type safe returns as well, by assigning through ## Read the old technique
\n__typeof__(foo_list.payload) to get the type the list contains. We’ll write a list_prepend macro, which will call _list_prepend with a cast function type so that the void * parameter is the list’s payload type```\n// Note: I added a leading underscore to the \n// function name since only the macro should call it\nvoid _list_prepend(ListNode **head, \n void *data, \n size_t data_size);\n#define list_prepend(list, item)
\n /* cast function type */
\n ((void ()(ListNode *,
\n typeof((list)->payload),
\n size_t))_list_prepend)
\n /* call function */
\n (&((list)->head), item, sizeof(*(list)->payload))
List(Foo) *foo_list = NULL;\nBar bar = {5};\nlist_prepend(&foo_list, &bar); // error!
\n`typeof` on old compilers`__typeof__()` was an optional extension until C23, which made it part of the C standard. While Clang and gcc have supported it for a *long* time, some compilers haven’t (like msvc versions prior to 19.39). To make this technique work on those compilers, you can use the terenary operator instead of typeof```\n#define List(type) struct { \\\n ListNode *head; \\\n type *payload; \\\n}\n#define list_prepend(list, item) \\\n _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload)) payload, but I’ll leave the details as an exercise for the reader. #
One annoying thing about C compilers<sup>4</sup> is that they do not consider these two variables to have the same type:
\nList(Foo) a;\nList(Foo) b = a; // error\nvoid my_function(List(Foo) list);\nmy_function(a); // error: incompatible typeEven 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\nListFoo a;\nListFoo b = a; // ok\nvoid my_function(ListFoo list);\nmy_function(a); // ok\nList(Foo) local_foo_list; // still works You can use this for any type of data structure, even ones with multiple associated types, like a hash map:
\ntypedef struct {\n ...\n} MapInternal;\n#define Map(key_type, value_type) union { \\\n MapInternal map; \\\n key_type *key; \\\n value_type *value; \\\n}The example source code, which includes the list_for macro, can be downloaded by joining my newsletter at the bottom of this page.
struct {int a; int b;} baz; STBDS_ADDRESSOF(baz, 5) compiles successfully, when you really want a type error.↩︎add_int andadd_double from the same source), this option has more merit. You can get creative with c features in other ways to get type-specific behavior, like for hashing functions, for example.↩︎data member, but that’s a whole other topic that you should read up on elsewhere if you’re unfamiliar.↩︎