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
The naming of LIST_HEAD_INIT and INIT_LIST_HEAD is confusing to me.
I write type-safe generic data structures in C
61–70 of 196 posts
Re: I write type-safe generic data structures in C
#62Hi. 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 an…
Author here. Binary heaps and linked lists are different use cases. A binary heap must read the data you put in it to store it correctly, but a linked list doesn't. If I were writing a generic binary heap, maybe I would weigh my options differently. I mentioned this in the footnotes.
And that's why I like C++ templates
Re: I write type-safe generic data structures in C
#63Earlier quoted context omitted.
Do you have a couple of real world examples?
Any established C codebase, for example the kernel or Postgres? Traditionally microcontroller firmwares as well, though those are increasingly friendly to C++, you just have to be careful about allocations as C++ makes it way easier to accidentally allocate than C does.
I'm not sure about other compilers, but compiling C code as C++ with MSVC ends up with pretty much the exact same code, instruction by instruction. C++ is a bit more strict though especially with casting, so a lot of code won't compile out of the box.
Re: I write type-safe generic data structures in C
#64There'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
The naming of LIST_HEAD_INIT and INIT_LIST_HEAD is confusing to me.
The way I remember it is:
INIT_LIST_HEAD is of form VERB_NOUN so is called from within a function to programatically initialise the list.
LIST_HEAD_INIT is NOUN_VERB and is used within a structure initialiser not from a function.
But my main point was to show the "embed the list in the data" approach rather than "embed the data in the list" or "point to the data from the list" and not to discuss the naming details in the kernel implementation of the concept.
Re: I write type-safe generic data structures in C
#65Earlier quoted context omitted.
This is incorrect. In a function definition, an empty list means it takes no parameters. 6.7.5.3 Function declarators > 14. An empty list in a function declarator that is part of a definition of that function specifies that the function has no parameters.
As you surely know if you're quoting the standard, it depends on which standard!
I believe that since C23 foo() is now a nullary function. As this is the last approved standard and it supersedes all previous standards, it is technically correct to say that de-jure this is what the (unqualified) C standard mandates.
Of course de-facto things are more nunanced.
Re: I write type-safe generic data structures in C
#66Earlier quoted context omitted.
This is incorrect. In a function definition, an empty list means it takes no parameters. 6.7.5.3 Function declarators > 14. An empty list in a function declarator that is part of a definition of that function specifies that the function has no parameters.
As you surely know if you're quoting the standard, it depends on which standard!
Quote a different standard.
Re: I write type-safe generic data structures in C
#67pretty sure C is the new Go.
pretty sure C has to go
Re: I write type-safe generic data structures in C
#68Earlier quoted context omitted.
Mhm. Putting the dummy member into the embedded node doesn't give a path from the proper object to find the embedded node "mid-struct". run-time checks are the "easy way out". We/I'll stick to macro soup probably, so we have compile-time checks. btw. For ISO C WG14… has anyone suggested adding _Include to the preprocessor, along the lines of _Pragma? It'd really help with doing this kind of really long macros, hiding…
I don't think anybody has proposed this, at least not recently. There is a proposal for multi-line macros: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3531.txt
That one might actually be better, nice to know & thanks for the pointer! (I hope it actually goes somewhere…)
Re: I write type-safe generic data structures in C
#69For 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 `con…
> it should be `int main() { List(Foo) foo_list = {NULL};` In C `int main()` means the function takes an unknown number of arguments. You need `int main(void)` to mean it doesn't take any arguments. This is a fact frequently forgotten by those who write C++.
That had been harmonized with C++ in C23 (e.g. func() is equivalent with func(void) now).
It's not really relevant for main() though, even in older C versions main() works fine and simply means "I don't need argc and argv".
Re: I write type-safe generic data structures in C
#70uint64_t data[] in level 2 violates the strict aliasing rule. Use the char type instead to avoid the violation.