June 25, 2025・7 minute read
I write type safe generic data structures in C using a technique that I haven’t seen elsewhere. It involves unions and typeof , 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
" , 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.
Click to see the Code list.h #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 main.c 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
... continue reading