Artikelen

Type-safe generieke datastructuren in C

05-10-2026 16:34 • Linux & open source • Daniel Hooper • https://danielchasehooper.com/posts/typechecked…

Auteur: Daniel Hooper

Type-safe generieke datastructuren in C

Ik schrijf type-safe generieke datastructuren in C met behulp van een techniek die ik elders niet ben tegengekomen¹. Het maakt gebruik van unions om type-informatie te koppelen aan een generieke datastructuur, maar daar komen we later op terug. Mijn aanpak werkt voor elk type datastructuur: maps, arrays, binaire bomen... maar voor dit artikel illustreer ik de ideeën door een basis-gelinkte lijst (linked list) te implementeren.

Omdat veel mensen niet weten dat generics in C überhaupt mogelijk zijn, begin ik simpel om op te bouwen naar dit resultaat:

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 });

// Dit zal niet compileren, wat juist is!
// list_prepend(&foo_list, 7);

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

Generieken niveau 0: Generieke headers

Ik aarzel om dit zelfs maar te noemen, omdat ik er niet van houd², maar het is waardevol om het te vergelijken met de techniek aan het einde van dit artikel. Het werkt als volgt: je schrijft je datastructuur in een header, gebruikmakend van macro's voor je types, en vervolgens #include je de header meerdere keren; één keer voor elk type waarmee de datastructuur gebruikt zal worden.

list.h

#ifndef T
#error "T moet worden gedefinieerd voordat deze header wordt geïncludeerd"
#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});

Hoewel dit generiek en type-safe is, kleven er nadelen aan:

Het is moeilijk te vinden waar types en functies zijn gedefinieerd (omdat ze door macro's worden geconstrueerd).
Code-completion (autofill) in editors werkt er mogelijk niet goed mee.
Het vergroot de binary-omvang en de build-tijden door kopieën van dezelfde functies.
Het vereist het gebruik van functies met een type-prefix: Foolistprepend() en intlistprepend() in plaats van gewoon list_prepend().

Generieken niveau 1: void *

Een andere manier om een datastructuur generiek te maken is door void * te gebruiken. Dit is niet type-safe, maar daar komen we later op terug.

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;
}

Noot: malloc wordt hier gebruikt voor de herkenbaarheid, maar ik raad Arenas sterk aan.

Het hebben van ListNode en de bijbehorende data als aparte allocaties is niet ideaal vanuit een geheugen- en prestatieperspectief. Het vereist twee allocaties per node terwijl één voldoende zou zijn, de datapointers gebruiken onnodig geheugen, en je zult waarschijnlijk twee cache-misses per node krijgen bij het doorlopen van de lijst: één keer voor de volgende node, en één keer voor de data. We kunnen deze problemen oplossen met...

Generieken niveau 2: Inline opslag

In plaats van een pointer naar de data van de node op te slaan, kunnen we een Flexible Array Member gebruiken om de data direct in de node op te slaan. Hiervoor maken we één allocatie die groot genoeg is voor zowel de node als het type dat deze opslaat³:

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    char data[]; // Hierbij worden details over padding/alignment weggelaten
};

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));
}

Nu staan next en de eigenlijke inhoud van data naast elkaar in het geheugen, wat de problemen van de void * aanpak oplost. Helaas moeten we nu de grootte (size) meegeven, maar dat lossen we op in de volgende sectie.

Als je de memcpy wilt vermijden en het geheugen van de node direct wilt initialiseren, kun je dat doen met een listallocfront functie:

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;

Generieken niveau 3: Typecontrole

Het deel waar jullie allemaal op hebben gewacht: hoe zorgen we dat de compiler een foutmelding geeft wanneer we proberen het verkeerde type aan een lijst toe te voegen? De manier die ik heb gevonden is door een union te gebruiken met een payload-lid dat een geparametriseerd type heeft:

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

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

Hoe helpt dit ons? We kunnen de ternaire operator gebruiken om af te dwingen dat de parameter item hetzelfde type heeft als de payload van de lijst:

// Noot: een underscore wordt toegevoegd aan de functienaam
// omdat alleen de macro deze mag aanroepen
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); // Fout!

De macro regelt ook het doorgeven van de grootte van het item voor ons! Dit is de fout die Clang produceert bij het toevoegen van het verkeerde type aan de lijst:

error: pointer type mismatch ('Foo ' and 'Bar ') [-Werror,-Wpointer-type-mismatch]

Macro's hebben een slechte naam, maar ik vind dit vrij begrijpelijk. Een paar dingen om op te merken: payload wordt nooit tijdens runtime gebruikt; het bestaat puur voor type-informatie tijdens het compileren. Door een union te gebruiken, verbruikt payload geen extra geheugen.

Als je een generieke functie schrijft die een pointer moet teruggeven naar de opgeslagen data, kun je typeof() gebruiken om het returntype te casten van void * naar het payload-type van de datastructuur. typeof() wordt ondersteund door de drie grote C-compilers (Clang, GCC, en MSVC sinds versie 19.39).

#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))

void *_list_alloc_front(ListNode **head) { ... }

Mocht je om wat voor reden dan ook de ternaire operator niet willen gebruiken om te controleren of twee types gelijk zijn, dan is er een alternatieve techniek. We kunnen typeof(foolist.payload) gebruiken om het type te verkrijgen dat de lijst bevat. We schrijven een listprepend macro, die listprepend aanroept met een cast-functietype, zodat de void * parameter het payload-type van de lijst wordt:

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); // Fout!

Het aanroepen van een typecast function pointer is technisch gezien undefined behavior, maar in de praktijk werkt het prima bij moderne compilers die gericht zijn op moderne platforms.

typeof op oudere compilers

typeof() was een optionele extensie tot C23, waarna het onderdeel werd van de C-standaard. Hoewel Clang en GCC dit al lang ondersteunen, doen sommige andere compilers dat niet (zoals MSVC-versies vóór 19.39). Om deze techniek op die compilers te laten werken, kun je de ternaire operator gebruiken in plaats van typeof:

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

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

Het is ook mogelijk om type-safe returns te implementeren door via de payload toe te wijzen, maar ik laat de details daarvan als oefening voor de lezer.

Het doorgeven van een parameter

Eén vervelend aspect van C-compilers⁴ is dat ze deze twee variabelen niet als hetzelfde type beschouwen:

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

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

Hoewel de variabelen identieke typedefinities hebben, geeft de compiler een fout omdat het twee verschillende definities zijn. Een typedef voorkomt dit probleem:

typedef List(Foo) ListFoo; // Dit lost het probleem op

ListFoo a;
ListFoo b = a; // OK

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

List(Foo) local_foo_list; // Werkt nog steeds

Conclusie

Je kunt deze methode gebruiken voor elk type datastructuur, zelfs voor structuren met meerdere bijbehorende types, zoals een hash map:

typedef struct {
    ...
} MapInternal;

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

***

Voetnoten:

¹ stbds.h is een voorbeeld van een type-safe generieke datastructuur, maar de technieken die daar worden gebruikt zijn niet zo algemeen als wat ik hier presenteer — het werkt alleen omdat de array en map zijn geïmplementeerd met behulp van een C-array. De compiler vangt sommige typefouten op bij toewijzing aan die C-array, niet op het moment dat waarden als parameters aan generieke functies worden doorgegeven. Bijvoorbeeld: struct {int a; int b;} baz; STBDSADDRESSOF(baz, 5) compileert succesvol, terwijl je eigenlijk een typefout zou willen zien.

² Als je een generieke functie wilt schrijven die type-specifieke code-generatie vereist (zoals het genereren van addint en adddouble uit dezelfde bron), heeft deze optie meer waarde. Je kunt creatief zijn met C-functies om type-specifiek gedrag te krijgen, bijvoorbeeld voor hashing-functies.

³ Ik laat hier wat informatie weg over alignment, padding en grootteberekeningen die meespelen bij het data-lid, maar dat is een geheel ander onderwerp waar je je elders in moet verdiepen als je hiermee onbekend bent.

⁴ Structureel identieke types met dezelfde tag-naam zullen als hetzelfde type worden beschouwd in GCC 15 en Clang eind 2025 dankzij een regelwijziging.

article_shortcut	Samenvatting laten zien
receipt_long	Volledige tekst laten zien
favorite	Artikel opslaan als favoriet
keep	Artikel vastzetten in linker kantlijn
settings	Categorie-instellingen beheren

Tech-update