I write type-safe generic data structures in C

Posted by todsacerdoti 6/30/2025

I write type-safe generic data structures in C(danielchasehooper.com)

412 points | 182 commentspage 2

eqvinox 6/30/2025|

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

hgs3 6/30/2025||

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.

lhearachel 6/30/2025|

I first would question what a user wants to do with a hashmap that uses polymorphic key-values of unknowable type at compile-time.

As a thought experiment, you could certainly have users define their own hash and equality functions and attach them to the table-entries themselves. On first thought, that sounds like it would be rife with memory safety issues.

At the end of the day, it is all just bytes. You could simply say that you will only key based on raw memory sequences.

KerrAvon 7/1/2025||

> I first would question what a user wants to do with a hashmap that uses polymorphic key-values of unknowable type at compile-time.

All of Apple's modern platforms use this concept pervasively, because the Objective-C Foundation framework has a common primitive data structure for it (NSDictionary).

makz 7/1/2025||

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.

HexDecOctBin 6/30/2025||

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.

dhooper 6/30/2025|

Author here. Not quite. The key idea is about using a union to associate type information with a generic data type. Type casting a function is not the only way to use that type information. I discuss that as well as the C23 changes in the footnotes and the "typeof on old compilers" section.

wahern 6/30/2025||

FWIW, as far back as 2015 my feature check library documents Visual Studio as supporting "__typeof".[1] Note the leading but not trailing underscores. Perhaps I was mistaken, but I usually tested that sort of thing. It's also possible __typeof had slightly different semantics.

[1] See https://github.com/wahern/autoguess/blob/b44556e4/config.h.g... (that's the 2015 revision, but HEAD has the same code).

dhooper 6/30/2025||

msvc 19.39 is the first to support it, which I mention in the article. You can confirm it didn't work up through 19.38 in godbolt [1]. I don't use Visual Studio, so I don't know what version of that first started using msvc 19.39

[1] https://godbolt.org/z/M7zPYdssP

rucikir 7/8/2025|||

Playing with MSVC's typeof, I've just discovered that its docs [1] have an example that has never worked with any released version of MSVC... MSVC doesn't support `typeof` applied on function types and function pointers! (bug report [2] [3]). Is there anyone from the compiler team around here? :)

[1]: https://learn.microsoft.com/en-us/cpp/c-language/typeof-c?vi... [2]: https://developercommunity.visualstudio.com/t/Support-for-ty... [3]: https://gcc.godbolt.org/z/Kn51qrj99

wahern 7/1/2025|||

This is gonna haunt me.

Digging through some old code of mine (circa 2009) I found this bit:

  #elif _MSC_VER >= 1310
  #define typeof(type)    __typeof(type)

So somehow I had the impression Visual Studio .NET 2003 (7.1)[1] added __typeof. I'm still holding out hope someone will come to my rescue and reply that once upon a time MSVC had __typeof, but removed it. But for now it seems past me is gaslighting present me.

[1] See https://learn.microsoft.com/en-us/cpp/overview/compiler-vers... for mapping between Visual Studio versions and _MSC_VER.

EDIT: Ah ha! It seems Microsoft did support __typeof, but perhaps only for "managed" C++ (aka C++ .NET)?

> One thing to watch out for when using the __typeof operator in managed C++ is that __typeof(wchar_t) can return different values depending on the compilation options.

Source: https://learn.microsoft.com/en-us/archive/msdn-magazine/2002... (See also https://learn.microsoft.com/en-us/archive/msdn-magazine/2005...)

canyp 7/2/2025||

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.

david2ndaccount 6/30/2025||

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)`?

josephg 6/30/2025|

In that example they also had replace the union with a struct - presumably to work around this issue. But that seems wasteful to me too. Doing it within an if(0) seems strictly better.

tehnub 7/1/2025||

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?

jayde2767 7/1/2025|

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

More comments...