I actually debated whether to write this article at all - as this isn't exactly anything new that I'm showcasing here. Every technique listed in this article is an established pattern.

That being said, I very rarely see the primary pattern I want to discuss being recommended, when I believe it is just unequivocably the best in many cases. And rather, I keep seeing what I believe to be bad techniques recommended as the go-to method for handling this problem. So my hope is that this article is one you or I can easily link to as a reference.

Anyways, the solution is template headers!

Template Headers

The concept of a template header is very simple, and is similar to how you would write generic code in any other language, except because it's C we do it using the preprocessor.

Say I want to define my own custom array type that looks like the following:

0123struct ArrayStruct {
    ArrayElemType* elements;
    int length;
};

This general pattern can be repeated throughout the codebase, but each time there are two things that need to be changed. Mainly, ArrayStruct and ArrayElemType.

All the C preprocessor really is at the end of the day is a very fancy find+replace tool, so if we #define something, it will replace the leftmost identifier from then on with anything to the right. If you think about it, a generic is really just taking in a type parameter and pasting it to where it needs to go. We can absolutely do the same in C! All we have to do is require the user to #define types to put into our relevant fields.

012345678910111213/* ArrayStruct and ArrayElemType will be replaced by what the user
passes in for ARRAY_STRUCT_TYPE and ARRAY_ELEM_TYPE respectively */
#define ArrayStruct ARRAY_STRUCT_TYPE
#define ArrayElemType ARRAY_ELEM_TYPE

struct ArrayStruct {
    ArrayElemType* elements;
    int length;
};

#undef ARRAY_STRUCT_TYPE
#undef ARRAY_ELEM_TYPE
#undef ArrayStruct
#undef ArrayElemType

The user could of course forget to define everything they need to, which is why we can add in some #ifdef statements to make sure everything looks good before proceeding. If not, we can toss them an error message with the #error directive

0123#ifndef ARRAY_ELEMENT_TYPE
    #error No type defined for generic array element type \
    above the #include, please #define ARRAY_ELEMENT_TYPE to the array element type
#endif

That's really all there is to it! I added in some extra boilerplate for adding the ability to typedef the resulting struct (I typedef by default but I know some others don't like that) but in principle that's all there is.

Then you save this to a separate file (something like "generic_array.h"), and then can use it around your program like so:

0123#define ARRAY_ELEMENT_TYPE int
#define ARRAY_STRUCT_TYPE IntArray
/* Creates an IntArray struct that can be used around the program */
#include "generic_array.h"

For those not familiar, the #include directive is just secretly copy and paste. In C, everything is just treated as one enormous file, and #include directly pastes the content of another file in its place. Thus the #include copies our genericized code into its place, that then gets modified according to the #define's the user provides.

You may be wondering what possible effort this saves - and for a simple case like this it doesn't really. However, doing it this way even for an array of this simplicity has its benefits. For one, it guarantees a consistent convention across the codebase, which is incredibly helpful. The amount of elements is always array.length, the elements can always be accessed with array.elements. In addition, it's simply modifiable (for instance, migrating from 32-bit to 64-bit you could change int to a larger type)

But the real benefits of this technique start to show itself when you consider more complex generic structures, as well as the other half of the equation: functions.

C doesn't have function overloading, so we run into an obvious problem - if we need a function associated with our generic datastructure (the *algorithms* in data structures and algorithms ;)), how do we do that? This is where my favorite niche feature of C comes in.

The token paste operator ## is a rarely used but extremely versatile feature. For some parameter A, ##A will be replaced with whatever is passed as A. In our case, it's capable of handling automatic name mangling according to a pattern.

012345/* Defines the "xar_get" symbol to be replaced with XAR_GET_(XAR_FN_POSTFIX) */
#define xar_get         XAR_GET_(XAR_FN_POSTFIX)
/* XAR_FN_POSTFIX needs to be expanded to its definition, so we need a second here */
#define XAR_GET_(type)  XAR_GET__(type)
/* Now we can directly paste its expansion onto the end of the xar_get_ signature.*/
#define XAR_GET__(type) xar_get_##type

If you don't know what a xar is, don't worry you won't need to for this post. (I will explain in a future post because they're cool though!)

What the above code does is replace any instance of "xar_get" with xar_get_(whatever we pass as XAR_FN_POSTFIX). So #define'ing XAR_FN_POSTFIX as string will replace all instances of xar_get with xar_get_string

For the implementation of the actual function then, it becomes extremely simple and readable. You can pretty much just read/write it like any other function.

012XarType xar_get(XarStruct xar_struct, int index) {
    /* You can just use xar_struct here like any variable */
}

And usage code just looks like this:

0123456789#define XAR_ELEMENT_TYPE int
#define XAR_STRUCT_TYPE IntXar
#define XAR_FN_POSTFIX int
#include "generic_xar.h"

int main(void) {
    IntXar xar;
    /* ... */
    int value = xar_get_int(xar, 0);
}

Everything just kinda works! That's really all there is to it.

If you wanted to get really fancy with it, you could use the _Generic keyword introduced in C17 to achieve function overloading. Instead of calling xar_get_int, you could call xar_get and it will dispatch to the correct function definition at compile time! However, I don't use this because I program in C99 (C17 still has compatibility issues for me)

Another thing I like to do is separate implementation from header usage in the STB style by having an, e.g., extra #define XAR_IMPLEMENTATION above the header that generates the actual function definitions. This avoids the issue of multiple definitions if you want to use this across modules.

Why Template Headers are AWESOME

I believe this is the best technique for writing generic C code for non-pointer datastructures (we'll get to those later) for several reasons.

The first reason they're great is that this is entirely legal C with no extra compiler extensions or outside scripts, that works as far back as C89 (unless you use _Generic). So this is an extremely portable setup with minimal changes. It also frees you from external build systems and is agnostic to how you generally set up your project.

The next reason, building off of the first, is that it is an extremely friendly technique to external tooling. Any old C LSP can read a template header definition and give you full autocomplete, goto definition, syntax highlighting, and more. It also works fantastically with debuggers! It'll show you the genericized code when stepping through, which is still readable enough to be reasonably debuggable.

It is a very flexible technique, and depending on how crazy you want to get with writing preprocessor code, you can give people very thorough control over how things get setup while not needing to worry about implementation details.

The last reason, and my number one reason I use this technique, is it offers type safety. If you pass the wrong type to a generated function or expect the wrong output, it throws an error at compile time. This catches bugs for me very regularly.

GingerBill cited the lack of the ability to create a type-safe hashmap as one of his reasons for making a new language with proper generic support. I agree that this is important, and while it wasn't the easiest, I did manage to create a template header for a 100% type safe hash map implementation that I regularly use across projects. The productivity boost from this cannot be understated, and along with my other generic data structures, lets me write C projects at a speed comparable to any other high level language.

What Datastructures Should You NOT Use Template Headers For?

I do not use Template Headers for pointer based data structures: (double or singly linked) lists, trees, etc. Instead, for these I follow the intrusive pattern in pretty much the same way that the Linux Kernel does.

I won't be going in-depth on how the intrusive data structure pattern works here, though you can find a good explanation here: https://www.data-structures-in-practice.com/intrusive-linked-lists/

In doing this, you definitely lose type safety and could potentially run into some nasty bugs. However, when I tried applying the template-header pattern to this, I found it to be far more cumbersome and was more of a detriment to my productivity. In addition, the intrusive data structure pattern offers an incredible amount of flexibility, in that a single blob of data can be a part of multiple data structures at once, which has come in handy a few times.

Intrusive data structures also prevent you from needing to allocate the data structure separately from the instances of data. This is especially nice if you're working with allocating/deallocating specific elements, but is still nice in a batch allocation context because you don't need to consider the sizes separately. You just have one structure.

So my rule of thumb is the following: If you can only think of it in terms of the data structure containing your data (arrays, dynamic arrays, hash maps, etc) - then template headers are a great fit. If it's better to think of your data containing a node in a tree, then the intrusive pattern is better.