Interesting! I’m working on toy/educational generator of ML-style tagged variants and associated functions in C (for a compiler) and when I’m a bit further along I will see if they’re compatible.

"I write type-safe generic data structures in C"

sounds like

"I build life-size houses out of toothpicks"

I can do that to, but I have no desire to. It's so much easier to just switch to Rust.

Welcome to around 1992, when Borland published BIDS 1.0 using similar tricks, as C++ templates were yet to be made part of the language.

With similar articles in The C/C++ Users Journal and Dr Dobbs, throught their existence.

While the effort is commendable, maybe pick a safer language that actually has all the features for type safe generic code.

Or write in CFront and have it translated to C

uint64_t data[] in level 2 violates the strict aliasing rule. Use the char type instead to avoid the violation.

Level 4: switching to C++

I think the idea of using a union to store the element type without any extra run-time memory cost might have some use, specifically in cases where the container struct wouldn't typically store a variable of the element type (or, more likely, a pointer to the element's type) but we want to slip that type information into the struct anyway.

However, the problem that I have with this idea as a general solution for generics is that it doesn't seem to solve any of the problems posed by the most similar alternative: just having a macro that defines a struct. The example shown in the article:

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

could just as easily be:

    #define List(type) struct { \
        type *head; \
        /* Other data, such as node/element count... */ \
    }

(As long as our nodes are maximally aligned - which they will be if they're dynamically allocated - it doesn't matter whether the pointer we store to the list head is ListNode *, type *, void *, or any other regular pointer type.)

The union approach has the same drawback as the struct approach: untagged unions are not compatible with each other, so we have to typedef the container in advance in order to pass in and out of functions (as noted in the article). This is broadly similar to the drawback from which the "generic headers" approach (which I usually call the "pseudo-template" approach) suffers, namely the need for boilerplate from the user. However, the generic-headers/pseudo-template approach is guaranteed to generate the most optimized code thanks to function specialization[1], and it can be combined with another technique to provide a non-type-prefixed API, as I discuss here[2] and demonstrate in practice here[3].

I'd also like to point to my own approach to generics[4] that is similar to the one described here in that it hides extra type information in the container handle's type - information that is later extracted by the API macros and passed into the relevant functions. My approach is different in that rather than exploiting unions, it exploits functions pointers' ability to hold multiple types (i.e. the return type and argument types) in one pointer. Because function pointers are "normal" C types, this approach doesn't suffer from the aforementioned typedef/boilerplate problem (and it allows for API macros that are agnostic to both element type/s and container type). However, the cost is that the code inside the library becomes rather complex, so I usually recommend the generic-headers/pseudo-template approach as the one that most people ought to take when implementing their own generic containers.

[1] https://gist.github.com/attractivechaos/6815764c213f38802227...

[2] https://github.com/JacksonAllan/CC/blob/main/articles/Better...

[3] https://github.com/JacksonAllan/Verstable

[4] https://github.com/JacksonAllan/CC

pretty sure C is the new Go.

Awesome write up! Please don’t mind the hostile crowd here. They don’t like anything other than their favorite language on the front page. There’s a much bigger silent majority that still loves C and the things you can do with it.