Templates in C

If the data you are working with can be coerced to a void pointer, you can side step the problem by writing a single implementation that only works with void pointers or only with raw bytes. When the user actually uses it they have to cast back to the original type and to be careful not to get confused about which data structure is which.

This is easy to implement, but is error-prone and type-unsafe to use. If you require all data to be pointers the user is encouraged to heap allocate a large number of individual items, which is bad for performance.

You write your library or algorithm to work with opaque types and when you need type-specific functionality, you call a function pointer given by the user.

A good example of this in the standard C library is the qsort function. For moving things it just memcpy's a void pointer, but for the actual comparison it calls the comparison function given by the user.

The advantage of this approach is that it takes up very little code space - there is just one qsort.

The disadvantages are that it is type unsafe — there is no way to check that the user's function pointer is the right one and it is annoying to use. The user has to define a (probably trivial) global function just to sort some data.

Another approach is to not define a function at all and just do the work in a macro. The classic K&R definition of max is an example of this:

#define max(a, b) ((a) > (b)? (a) : (b))

Ignoring the multiple evaluation problem (a or b is evaluated twice, which can be expensive or surprising if it involves side-effects), this is not adequate for more advanced operations. Sans extensions, you can't really define or use local variables, you can't use recursion, you can't get the normal compiler errors when you pass the wrong type to the "function" and this forcibly inlines the code at every usage site.

It is very easy to use though (it looks like a function).

Another approach is to actually generate a function with the actual types and call that generated function. To avoid having to actually copy-paste, you generate the function via a macro.

#define COMBINE(a, b) a##b
#define MAKE_MAX(T, prefix) \
  static inline \
  T COMBINE(prefix, max)(T a, T b){ \
      if(a > b) return a; \
      return b; \
  }
MAKE_MAX(int, int_)

#include <assert.h>
int main(void){
    int x = int_max(1, 2);
    assert(x == 2);
    return 0;
}

This is type safe and you get the benefits of functions (separating implementation details from usage, local variables, early returns, etc.), but it becomes impossible to debug if you need to step through the generated code — the nature of C macros is everything will be on a single line. Checking the result of the macro expansion is also more difficult.

Additionally, customizing the expanded code is difficult: you either need a large number of arguments to the macro or just forgo customization of things like prefixes to function names.

Finally, just writing it is annoying. You need a \ on every line, most editors give up on syntax highlighting it properly, etc.

Another alternative is to generate extra source files that then are compiled into your program. The issue with this is that it greatly complicates the building and compiling of your code. Suddenly you need a build system that is aware of the need to generate the code instead of just leveraging the C compiler that you already have. You step farther away from the ideal of just compiling with cc *.c -o program.

The manual version of source code generation is copy-pasting the data structure and functions every time you need a new one. This is a nightmare for maintainability — a bug copy-pasted 100 times might never get fixed, especially if that code is then altered and diverges.

This approach is very similar to Code Generating Macros, but with the benefit of it being easy to check the expanded code, it is possible to debug and customization is much more straightforward thanks to #ifdef. The rest of this article will explain how they work.