HN Reader

For your level 2 code, `uint64_t data[];` is wrong for types whose alignment is greater than `uint64_t`, and also wasteful for types whose alignment is smaller (for example, under an ilp32 ABI on 64-bit architectures).

For your level 3 code, it should be `int main() { List(Foo) foo_list = {NULL};`

Note that working around a lack of `typeof` means you can't return anything. Also, your particular workaround allows `const`ness errors since `==` is symmetrical.

You can't safely omit `payload` since you need it to know the correct size. Consider a `List(int64_t)` and you try to add an `int32_t` to it - this should be fine, but you can't `sizeof` the `int32_t`. Your code is actually lacking quite a bit to make this work.

=====

There are 2 major limitations to generics in C right now:

* Delegating to a vtable (internal or external) is limited in functionality, since structs cannot contain macros, only functions.

* Delegating to an external vtable (mandatory to avoid overhead) means that you have to forward-declare all of the types you'll ever use a vtable with. So far the best approach I've found is to declare (but not define) static functions in the same forwarding header I declare the typedefs in; note that GCC and Clang differ in what phase the "undefined static" warning appears in for the case where you don't actually include that particular type's header in a given TU.

(think about writing a function that accepts either `struct SizedBuffer {void *p; size_t len;};` or `struct BoundedBuffer {void *begin; void *end;};`, and also const versions thereof - all from different headers).

Why would you jump through all these hoops instead of just writing C++ if you want "C with generics"

It is cool trick. I already use in my experimental library though ;-) https://github.com/uecker/noplate/blob/main/src/list.h

I believe "type witness" is the generic (hah) term for "member that doesn't do anything but hold the type". Lot less literature out there about type witnesses than I had thought though...

Here's how to do it in D:

    struct ListNode(T) {
        ListNode* next;
        T data;
    }

    T!int node;

Why suffer the C preprocessor? Using preprocessor macros is like using a hammer for finish carpentry, rather than a nail gun. A nail gun is 10x faster, drives the nail perfectly every time, and no half moon dents in your work.

Interesting but too complicated for me.

For my own hashmap implementation I followed a wasteful aproach since I’m. It targeting embedded.

I created a structure called a hashmap object. It has two elements: a void pointer and a char pointer. The first one is the data and the second one is the metadata. The metadata is basically a string were the user can put anything, the type of the data, more data, whatever.

Then I preallocate 10s of thousands of hashmap objects. That way users of my hashmap don’t have to think about aollocating and de allocating hashmap nodes, they just insert, delete and search freely. They still have to care about allocating and de allocating they’re own data though.

The “typeof on old compilers” section contains the code:

         (list)->payload = (item); /* just for type checking */\

That is not a no-op. That is overwriting the list head with your (item). Did you mean to wrap it in an `if(0)`?

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.

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

Hi. I object.

The trick#0 you mention is how I made an entire C dialect. Here is a generic binary heap, for example https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h The syntax is a bit heavyweight, but a huge huge advantage is: you get regular C structs in the end, very plain, very predictable, very optimizable. Compiler would eat them like donuts.

In the other cases, it is void* and runtime memory sizing and you have to define macros anyway.

The casting of the function type assumes that the item pointer type (e.g. Foo*) has the same representation as void*, which the C standard doesn’t guarantee (in standardese: the two types aren’t “compatible”). Calling the function with the converted type therefore constitutes undefined behavior. It also impacts aliasing analysis by compilers (see [0], incidentally), even if the pointer representation happens to be the same.

This casting of the functions to different argument types constitutes the core of the type safety of the generic invocations; I’m not sure it can be fixed.

[0] https://news.ycombinator.com/item?id=44421185

> Structurally identical types will be considered the same type in GCC 15 and Clang later in 2025 thanks to a rule change

Beware that only tagged unions are considered the same type under the new rule, provided they have the same structrure and the same tag.

The List(T) macro should be changed to generate a different tag for each different T. Which is trivial (with ##) for simple one-word types, but impossible for even mildly complex ones like pointers to char (strings).

Of course you can force yourself to typedef any type before using it in a List, but it looses much of its versatility. Example:

  typedef char *str;
  List(str) my_list_of_str;
  List(str) tokenize(str input) {...}

If I have to do that I'd rather use C++ templates directly.

There's also the method used in the Linux kernel to embed the list information (struct list_head) within the type specific struct. https://kernelnewbies.org/FAQ/LinkedLists

Interesting idea with the union and using typeof(). We (I) went with large macros defining wrappers instead, which, I believe, is a necessity with intrusive data structures, or at least I don't immediately see how to do that with unions & typeof. Maybe it's possible...?

e.g. hash table wrapper: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#...

(cf. https://docs.frrouting.org/projects/dev-guide/en/latest/list...)

The key idea here seems to be to use function pointer's type to enforce type safety rather than using the data "handle" type (that is often found in implementations inspired by Sean Barrett's strechy_buffers).

> One annoying thing about C is that it does not consider these two variables to have the same type

C23 solves that too: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

Supported by latest GCC and Clang, but not by MSVC.

I'm curious what a hashmap looks like with this approach. It's one thing to pass through or hold onto a generic value, but another to perform operations on it. Think computing the hash value or comparing equality of generic keys in a generic hashmap.

Good share, thanks. My approach so far has been to define macros that generate the container type for a given underlying type, as well as all of the relevant type-safe functions, which end up calling into functions that take void*. But the union trick plus the structural identity does seem to simplify things a bit.

When I saw the title I assumed it was originally "Why I" or "How I" and was trimmed automatically by HN, but this is the original. Could it be that the author was influenced by HN's title guidelines and titled it thus?

This is all well and good but, for my mileage, nothing can ever beat C++ generics and the RAII pattern when there is a choice between plain old C and C++ . One second while I get my fire-retardant suit on...

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.

"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.

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

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.

Or write in CFront and have it translated to C

pretty sure C is the new Go.

Another way is to not try to write generic data structures. When you tailor them to the use case you can simplify.

The #1 data structure in any program is array.

Level 4: switching to C++

Dude the ship has sailed.