I Write Type Safe Generic Data Structures in C

Summary

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\n", item->value); } 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 Codelist.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.ctypedef 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 ...