Template in C++ is the single reason that I still keep using it. Previously, I thought generic programming in C is nothing but ugly and painful. Now I have changed my mind a bit, in the light of tree.h written by Niels Provos. Generic programming in C can be done without much pain and with just slightly less elegance in comparison to C++ implementations. How can this be done? Macros, of course. But in what form macros are used is where all the tricks come in.
The first way to achieve generic programming is to pass a type to macros. Jason Evans‘ rb.h is an example. Each operation on an RB tree is a macro. Users have to provide the type of the data in the tree and a comparison function with each macro. It is not hard to think of this way, but we can do better.
In tree.h, Niels gives a better solution: to use token concatenation. The key macro is SPLAY_PROTOTYPE(name, type, field, cmp). It is a huge macro that defines several operations, in the form of “static inline” functions, on the splay tree. These functions will be inserted to the C source code which uses the macro. Using SPLAY_PROTOTYPE() with different “name”s will insert different functions. For example, when “SPLAY_PROTOTYPE(int32, int, data, intcmp)” is invoked, the insertion function will be “int32_SPLAY_INSERT()”. Splay trees with different “name”s can coexist in one C source code because their operations have different names. At the end of tree.h, Niels further defines “#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)”. Then In the C source code, we can call insertion with “RB_INSERT(int32, x, y)”. In comparison to a C++ template implementation, the only line you need to add is SPLAY_PROTOTYPE(). Calling operations is as easy.
I will further explain this idea when I present my khash implementation in C.