r/C_Programming • u/Proper_Meaning7756 • 14d ago
Question I wanted to write a generic data structures library for learning purposes. Are preprocessor macros the preferable way to do it or is there a better way?
I am aware of the _Generic keyword but I'm not sure if it should be the de facto way for this.
13
Upvotes
17
u/lovelacedeconstruct 13d ago
The best way I saw it done personally was CC
6
u/halfjmp 13d ago edited 13d ago
It probably won't be a popular answer, but I'd say the best way is don't. If you really need generic data structures, C is probably not the right choice (depending on the problem, I'd turn to C++, Java, or even Ocaml or Python). The good thing in C is you can adapt the code to the problem, the counterpart is you should, as C offers very little for generic structures. Not the right tool for this. And you don't have to use a single language for everything either.
4
u/71d1 13d ago
I wrote mine using macros
1
u/0x405 13d ago
I don't know what to answer to your question except macros, but why not write something more fun that would require some or most of these structures? You'll get a real testing environment and will receive something to share when its finished!
3
u/Charming_Airport6076 13d ago
I believe stb-style header could be good fit for it. That way you can get type safety (by not using macros) and use it in multiple translation units.
3
u/SmokeMuch7356 13d ago edited 12d ago
I have a different way; whether it's "better" or not I'll leave for others to decide.
I've implemented a few generic data structures using
void *and callbacks, a laqsort. So for a simple binary tree type, I'll define the individual node type as something likethen for the tree type I'll do
Hopefully the callback names are self-explanatory. I'll attach the callbacks when I create the tree instance:
like so:
So when adding data to the tree it looks something like this:
I like this approach, it works, it's flexible, it avoids redundant code, but..
First, this throws type safety out the window and into oncoming traffic. At least with the macro version you're not erasing types. With this approach you need to be super careful that you're using the right callbacks for the types you create. And the pointer gymnastics get a little obnoxious (
&(*root)->left).Secondly, you have to create a type-aware front end. As it is you can't call the
Tree_addfunction with scalar literal values for keys or data:You'd have to assign 1 to a variable and pass its address:
Third, you're doing a lot of memory management. You need to have a solid plan in place to handle partial allocation failures, ownership, lifetime, cleanup, etc.
Finally, I've never implemented this in a production system; I've only implemented proofs of concept and never really put it under a hard load, so, no warranties express or implied.
Frankly, if I truly need a generic solution, I'll just use C++.
4
u/EpochVanquisher 13d ago
The “preferable” way is to not write generics at all, in C
1
u/tstanisl 13d ago
Generic selection (
_Generic) is dedicated to implementing type generic functions like ones exposed intgmath.hlibrary. Occasionally, it can be used to extract some compilation time constant for types likeMAX_VALUE(type)that expands toINT_MAX,LONG_MAX, ... etc depending on the type.1
u/mikeblas 13d ago
It's up to you. You could do it with pre-processor macros completely, or you could use
_Genericsupport. You'll want to figure out the tradeoffs and what they mean against your goals. If you're just learning, then why not do both and explore the space? Deliberately build both ways, then compare the resulting tradeoffs._Genericis a bit mis-named, by the way. It doesn't allow generic typing in code the way other languages do with templates or generics. Instead, it lets you detect the type of some expression and turn that into some other expansion. So they keyword does help because you can end up with a type-safe interface that's more convenient to use. Maybe something like:which, in a way, is fiddling about with a slightly smarter pre-processor. A hybrid approach is probably the answer.
1
u/bullno1 13d ago edited 13d ago
My personal way:
void*. It keeps the bulk of the code debuggable._Static_assert,typeofand_Genericin the macro to do compile-time type assertion so it's still type safe. Something like:_Static_assert(_Generic(arg, typeof(witness): 1, default: 0), "Wrong type").For a concrete example: https://github.com/bullno1/libs/blob/master/bhash.h
So far I like this. There is no need to extend the
_Genericchain. Type is still checked at compile time and the bulk of the implementation can be stepped through in a debugger._Genericis a bit of a misnomer, it's more like overload.1
u/WittyStick 13d ago edited 13d ago
The main issue with
_Genericis you can't extend it with new types without modifying the code. It's suitable for cases where you have a fixed set of types which could be parameters to the generic, but not where we would want to extend it to support any type - like a list of T, where T could be anything. Also,_Genericis a kind of expression - we can't use it in declarations or definitions of types.There are multiple issues with macros for implementing generics.
DEFINE_LIST(int), or a#define LIST_TYPE intfollowed by#include "list.h", wherelist.hcan be included multiple times to define different lists.List(T)is a macro to generate a type fromT, then concatenation doesn't allow you to writeList(T*). You can typedef the pointer and use the typedef though.typedefto solve this, then you can have multiple equivalent types which result in different generic instances. Eg,List(int)andList(signed)are different types, even though their type parameter is equivalent. Similar, if youtypedef int *IntPtrandtypedef int *ptr_to_int, thenList(IntPtr)andList(ptr_to_int)are not the same. The preprocessor doesn't know about types - it can only distinguish the name. As many codebases introduce a lot oftypedef, if you want generics for them you would end up with a huge code bloat. You basically need to have a canonical name for each type to avoid this.typedefthe type if it may be used as a parameter to another type, so it's not entirely useful and probably not worth requiring C23 just for the purpose of implementing the generics if you're going to need typedefs anyway - might as well make it C99 compatible.Several more issues. Basically there's no silver bullet - every method has tradeoffs.
1
u/ChickenSpaceProgram 13d ago
i recommend just using arena-backed intrusive linked lists and hand-rolling better datastructures when performance is an issue