HN

Comments (123)

• Menu

  o11c
  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).
• Menu

  gritzko
  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.
• Menu

  layer8
  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
• Menu

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

  teo_zero
  > Structurally identical types will be considered the same type in GCC 15 and Clang later in 2025 thanks to a rule changeBeware 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) {...}
• germandiago
  If I have to do that I'd rather use C++ templates directly.
• Menu

  uecker
  It is cool trick. I already use in my experimental library though ;-) https://github.com/uecker/noplate/blob/main/src/list.h
• SuperV1234
  Level 4: switching to C++
• Menu

  mfuzzey
  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
• eqvinox
  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...)
• Menu

  HexDecOctBin
  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 typeC23 solves that too: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdfSupported by latest GCC and Clang, but not by MSVC.
• anon
  undefined
• anon
  undefined
• tehnub
  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?
• Menu

  monkeyelite
  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.
• Menu

  david2ndaccount
  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)`?
• pjmlp
  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.
• Menu

  hgs3
  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.
• anon
  undefined
• b0a04gl
  what happens if two types have same size and alignment but different semantics : like `int` vs `float` or `struct { int a; }` vs `int`? does the type tag system catch accidental reuse . aka defending against structual collisions
• asplake
  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.
• ryao
  uint64_t data[] in level 2 violates the strict aliasing rule. Use the char type instead to avoid the violation.
• Menu

  ape4
  Or write in CFront and have it translated to C
• Menu

  WalterBright
  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.
• JacksonAllan
  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
• Menu

  notnmeyer
  pretty sure C is the new Go.
• kahlonel
  [dead]
• ValveFan6969
  [dead]
• luppy47474
  [flagged]
• luppy47474
  [flagged]
• Menu

  adamnemecek
  Dude the ship has sailed.