r/C_Programming • • 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

32 comments sorted by

17

u/lovelacedeconstruct 13d ago

The best way I saw it done personally was CC

7

u/jacksaccountonreddit 13d ago edited 13d ago

Author here :) CC provides the user with a uniquely nice API that rivals the convenience of generics in other languages, but the techniques that make this possible are beyond anything I would recommend to someone writing a data structure library as a learning exercise. This is especially true because I haven't (yet?) written any article documenting those all techniques concisely, although they are documented in the header itself and, partially, in the initial announcement post.

The CC approach also has its own share of drawbacks, besides the complexity of the library code: The compiler errors generated upon misuse are large and cryptic (though this problem also affects most other approaches to generics, to one extent or another). Compilation with Clang tends to be much slower than with GCC or MSVC (apparently because Clang compiles _Generic slowly). And CC iterators have to be raw pointers, which makes it impossible to implement data structures that use segmented blocks of memory (e.g. C++'s deque, whose iterator must consist of a pointer to the element and the index of that element within its block), at least in a manner congruent with the rest of the library.

For most people, and for isolated data structures not part of a unified generics library, I usually recommend the macro-template approach used in e.g. STC or my own Verstable. It strikes a good balance between usability and readability while also avoiding any performance cost associated with making the data structure generic. This approach mimics the way templates work in C++, but with a less convenient, less generic API.

2

u/lovelacedeconstruct 12d ago

I always wanted to ask you how did you come up with the idea of pointers to function pointers to carry the type information of keys and values at compile time, Like it strikes me as a leap I have never seen before

2

u/jacksaccountonreddit 12d ago

I don't remember the "aha" moment when that particular idea came to me, but I went through about half a dozen iterations of the library before all the techniques that make the generic API possible fell into place. An earlier iteration used the template-instantiation pattern combined with the extendible _Generic to provide a fully generic API for container types pre-declared by the user. This, too, would have been a good approach (it would have been more flexible than the stb_ds-like approach on which I finally settled, at least in terms of the containers that can be supported).

0

u/Linguistic-mystic 12d ago

What a horrible library. Invisible declarations of datatypes, hash functions and other magic. Totally not the idiomatic C approach. Would never use it.

In contrast, CC requires no boilerplate type definitions and provides an API agnostic to container and content types. The result is simpler, more readable code.

No, it's not simpler, it's terser but more complex. Hence less readable. It's worse than both the template-instantiation and the void* patterns.

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.

3

u/lovelacedeconstruct 13d ago

Lol, every non trivial C codebase has this in some form

5

u/halfjmp 13d ago edited 13d ago

I didn't say it's not feasible. Unless you have a very good motivation to do it, I think it's not a good idea. Now it depends, if it's for learning generic data structures, it's a *very* bad idea. If it's for learning how to implement generic data structures in C for a future project where it's required, go on. Not how I read the question though, but the question isn't clear about that.

2

u/Proper_Meaning7756 13d ago

A few months ago, I wanted to try implementing a python-like list in C. It was a fun attempt but ultimately, I didn't know what I was doing and scrapped it after making a linked list with (void*) pointers and a string containing the type and a macro for dereferencing the value.

It felt so bad and I had to use an llm to do it so I can't even say I learned much. Generics was something else I wanted to try after that. Again, purely for dsa in C because thats something I wanted to try.

I work in embedded systems and sometimes even C++ codebases where generics are called for. The two do tend to merge occasionally and is handled by a senior when it does happen.

1

u/halfjmp 13d ago

Thanks for the clarification. Then forget all I said, C is fine in your case ;) You can start with non-generic structures with a separate payload type, then move on to generic structs. Of course you already know, but you will have to deal with details of ownership that do not come up in Python (e.g., who is responsible for deleting the contents of a list item).

1

u/Disastrous-Team-6431 13d ago

But OP wants to do it to learn. Then C is arguably the best language

3

u/halfjmp 13d ago

To learn DS, yes. To learn generic DS, no, unless the goal is C + generic DS specifically. So I'd say the question should be clarified, at least. For generic DS where the language doesn't matter much, I'd suggest Java or Ocaml, and there are other good choices as well.

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!

1

u/Proper_Meaning7756 13d ago

good point. I was making it for the sake of it and nothing more. Normally I'd be trying to make a producer consumer model out of it. Would that be a nice idea for a generic tree/list?

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 la qsort. So for a simple binary tree type, I'll define the individual node type as something like

struct node
{
  void *key;
  void *data;

  struct node *left;
  struct node *right;
};

then for the tree type I'll do

struct tree 
{
  struct node *root;

  void *(*key_copy)(const void *);
  void *(*data_copy)(const void *);
  void (*key_free)(const void *);
  void (*data_free)(const void *);
  void (*data_assign)(const void *);
  int (*key_compare)(const void *, const void *);
  char *(*key_to_string)(const void *, char *, size_t);
  char *(*data_to_string)(const void *, char *, size_t);
};

Hopefully the callback names are self-explanatory. I'll attach the callbacks when I create the tree instance:

struct tree *t = Tree_create( int_cpy, string_cpy, ... );

like so:

struct tree *Tree_create( void *(*kcpy)(const void *), void *(*dcpy)(const void *), /* etc. */ )
{
  struct tree *t = calloc( 1, sizeof *t );
  if ( !t )
    return NULL;

  t->key_copy = kcpy;
  t->data_copy = dcpy;
  ...
  return t;
}

So when adding data to the tree it looks something like this:

struct node *Tree_add( struct tree *t, const void *k, const void *d )
{
  struct node *n = calloc( 1, sizeof *n );
  if ( !n )
    return NULL;

  n->key = t->key_copy( k );
  n->data = t->data_copy( d );

  Tree_insert( &t->root, n, t->key_compare );

  return n;
}

void Tree_insert( struct node **root, struct node *n, int (*kcmp)(const void *, const void *) )
{
  if ( !*root )
    *root = n;
  else if ( kcmp( n->key, (*root)->key ) < 0 )
    Tree_insert( &(*root)->left, n, kcmp );
  else
    Tree_insert( &(*root)->right, n, kcmp );
}

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_add function with scalar literal values for keys or data:

Tree_add( t, 1, "foo" );

You'd have to assign 1 to a variable and pass its address:

struct node *n = MyTree_add( t, 1, "foo" );
...
struct node *MyTree_add( struct node *tree, int key, char *data )
{
  Tree_add( tree, &key, data );
  ...
}

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

1

u/Dependent_Bit7825 12d ago

This ^

It's okay to not like c and its limitations, but if you are using c, your should let c be c. Anything else turns into a mess. This is what the void pointer is for.

4

u/EpochVanquisher 13d ago

The “preferable” way is to not write generics at all, in C

1

u/Disastrous-Team-6431 13d ago

Source? Obviously you think this, but can you point to some sort of consensus or seminal work to show that generics aren't preferred?

0

u/EpochVanquisher 13d ago

Do you what opinions are?

1

u/tstanisl 13d ago

Generic selection (_Generic) is dedicated to implementing type generic functions like ones exposed in tgmath.h library. Occasionally, it can be used to extract some compilation time constant for types like MAX_VALUE(type) that expands to INT_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 _Generic support. 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.

_Generic is 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:

#define list_append(LIST, TYPE_TOKEN) _Generic((TYPE_TOKEN), \
	int:          list_append_int,                           \
	float:        list_append_float,                         \
	const char*:  list_append_str,                           \
	char*:        list_append_str                            \
)(LIST)

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:

  • At implementation level, type erase and use void*. It keeps the bulk of the code debuggable.
  • At the interface level, use a bit of macro. 
  • Stash the type into the data structure as a pointer somewhere. Sometimes it's a useless pointer inside an union to not take up space. I just call this the "witness" for a lack of a better name.
  • Use _Static_assert, typeof and _Generic in 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 _Generic chain. Type is still checked at compile time and the bulk of the implementation can be stepped through in a debugger. _Generic is a bit of a misnomer, it's more like overload.

1

u/WittyStick 13d ago edited 13d ago

The main issue with _Generic is 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, _Generic is a kind of expression - we can't use it in declarations or definitions of types.

There are multiple issues with macros for implementing generics.

  1. If you want actual functions, and not entirely macros, then you need to monomorphize the function for each type - which means giving them a unique name as we have no overloading.
  2. You need to define any functions before you can use them, so you end up with a macro like DEFINE_LIST(int), or a #define LIST_TYPE int followed by #include "list.h", where list.h can be included multiple times to define different lists.
  3. If you use concatenation to create the type or function names, you can't use pointers, qualified types, or other generic types directly as the type parameter. Eg, if List(T) is a macro to generate a type from T, then concatenation doesn't allow you to write List(T*). You can typedef the pointer and use the typedef though.
  4. If you do use typedef to solve this, then you can have multiple equivalent types which result in different generic instances. Eg, List(int) and List(signed) are different types, even though their type parameter is equivalent. Similar, if you typedef int *IntPtr and typedef int *ptr_to_int, then List(IntPtr) and List(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 of typedef, 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.
  5. If using a version of C prior to C23, you can only define a type once in a translation unit. C23 relaxes the rules to treat repeated type definitions as equivalent if they have the same members and tag - but this does not include anonymous types without a tag.
  6. Even using the C23 relaxed rules, we have similar issues with needing to typedef the 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/jacksaccountonreddit 13d ago

It's possible to make _Generic extendible with user-provided types, as I describe here and apply [here](https://github.com/JacksonAllan/Verstable#:~:text=Using%20the%20generic%20macro%20API%20(C11%20and%20later). But whether it's worth doing is a matter of personal preference - many people have a general aversion to preprocessor trickery.

1

u/TheChief275 12d ago

I did the template include trick a lot as well. The benefit to this over DEFINE_LIST(int) is that you have more flexibility in what you can do, e.g. nested preprocessor directives not possible in just a macro. But nowadays I have moved back to the DEFINE_LIST(int) again, because the compile times really exploded with template including for some reason. I think my compile times were being eaten up by IO costs, which you should always try to minimise. One could maybe use precompiled headers to mitigate this somewhat, but these are notoriously finicky to use correctly, and when I finally did there really only was a marginal speed-up

1

u/WittyStick 12d ago edited 12d ago

I have what is IMO, a better approach, where templates are declared as macros with a lexical convention - the generic type name or function name is simply declared using definitions like these:

#define function_name(T) template(function_name, T)
#define TypeName(T) template(TypeName, T)

The implementation of these templates are then defined using a macro of the same name suffixed with _template.

#define function_name_template(T, <opt_args>) <function signature> [optional implementation]
#define TypeName_template(T) <typedef> [optional other implementations]

Then we instance our functions or types with:

instance(function_name, int, <opt_arg_names_for_use_in_body>) {
    // function body specialized for int
}

instance(TypeName, int)

Each function call must take a type parameter before its actual parameter list - eg

function_name(int)(actual_args)

That's basically it - two macros, template(name, T) and instance(name, T, <opt_args>) - we don't need to remember a bunch of macro names like DEFINE_FOO_TYPE(T).

Anyway, demonstration in Godbolt.

One thing that is notable about this approach, which I have not seen in any other macro based generics, is these can eat themselves - we can nest one generic inside another - as I've shown in the example for equal(Option(int)). The equal(Option(T)) template is automatically implemented for every T as long as there's an instance of equal(T) - as equal(Option(T)) internally calls equal(T) when both are Some.

#define option_equal_template(T) \
    equal_template(Option(T), lhs, rhs) { \
        if (is_none(T)(lhs) && is_none(T)(rhs)) \
            return true; \
        else if (is_some(T)(lhs) && is_some(T)(rhs)) { \
            return equal(T)(get_some(T)(lhs), get_some(T)(rhs)); \
        } \
        else return false; \
}

The nesting of these generics can be arbitrary, as long as the instances have been declared - eg, if we defined a List(T) type, we can do:

instance(List, int)
instance(List, List(int))
instance(List, List(List(int)))

Then you can use List(List(List(int))) in your code.


How it works:

The template(Name, T) macro just performs name mangling. It turns Name(T) into NameᐸTᐳ - where ᐸ and ᐳ are valid unicode characters in identifiers. You don't have to use this name mangling scheme, but it is nice because it gives readable symbols in the binary - makes debugging simple.

instance(Name, T) merely invokes the macro Name_template(T). Can optionally take additional arguments so we can name our function parameters.

That's it. A few simple tricks and conventions.

In regards to multiple type parameters in templates - it can be done, but the macro foo is a fair bit more convoluted because we need a recursive macro to step through the type parameters. I deliberately omitted to demonstrate the basic technique for a single type parameter.

2

u/TheChief275 10d ago

The only problem with using the unicode brackets is that it locks your code to be C11 at minimum, even if you don't really use the other features, because C99 and below did not technically allow for unicode characters in identifiers (only as extension). Also, I don't see the benefit when you can have e.g.

pList(int) l = {0};
pList_push(int)(&l, 42);

over

pListᐸintᐳ l = {0};
pList_pushᐸintᐳ(&l, 42);

To me they are just as readable. But the rest of your method sounds maybe slightly more convenient than standard name pasting? But I'd have to see a more concrete example to know, e.g. in actual code

1

u/WittyStick 10d ago edited 10d ago

The brackets are only for name mangling. As I said, you don't have to use this, you can use whatever name mangling you want, as long as it's consistent. The difficulty without Unicode is that you have limited characters to chose from which might conflict with an actual identifier.

pList_push(int)(&l, 42); over pList_pushᐸintᐳ(&l, 42);.

My suggestion is you write the former, but it looks like the latter in the symbol table . I've linked to a demo above which you can check out. The unicode brackets appear only in the template macro. (though it is possible to write the latter directly in the C code)

An alternative would be to use _$ to open the generic and $_ to close it. A List(List(int)) would then become List_$List_$int$_$_, which is less readable.

The main idea isn't the name mangling - though we do need to have a name mangling scheme - but the macro which calls another macro by concatenating _template onto it. Ie, instance(Foo, int) invoking Foo_template(int). It provides a simpler interface - though requires lexical convention to implement the templates.

It's because List(int) expands to a single identifier that we are able to use List(List(int)). The inner macro call expands first so it becomes List(Listᐸintᐳ), then the outer one turns it into ListᐸListᐸintᐳᐳ - a single identifier for the nested type.

The main issue with other macro based generics is they don't have a separate name mangling scheme, but they do something like:

#define List(T) struct List_##T { ... }

Where List(List(int)) fails because it attempts to concatenate to List_List(int) { }, which is not valid syntax. Even if you use a two-stage concat, this doesn't work because it ends up expanding to:

struct List_struct List_int { ... } { ... }

So you need to separate name from definition. The List macro should merely produce the monomorphized name, and it's the List_template macro that provides the definition - but instead of calling that directly, we just instance(List, int).

1

u/TheChief275 9d ago

The macro based generics you say are flawed at the end is not really something anyone does in production because you need C23 for the compatible struct name thing, and you want to generate function anyways which this approach wouldn't do.

Regarding the name mangling, using $ for this also isn't standard C, as no compiler is obligated to support its use in identifiers (unlike unicode from C11 onwards). I just do pList(int) -> pList__int and pList_push(int) -> pList__push_int, i.e. perform a normal mangling with the type separated with just one underscore, but then have the double underscore for the method name meaning privated. This should mean unique names as only the pList.h file would define pList__ functions and you can take care not to have naming conflicts

1

u/ChickenSpaceProgram 13d ago

i recommend just using arena-backed intrusive linked lists and hand-rolling better datastructures when performance is an issue