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.
Attractive Chaos 
Hey man
It’s great that you used macros to make your hash generic!!!
I’ve been doing this for years to the dismay of my colleagues ) :
Here’s a little demo I threw together showing some other macro tricks I often use.
I’d be interested to talk!!!
Cheers
Thanks a lot for the example. It looks very interesting to me. I just began to use such macros two weeks ago and more and more believe this is the best way to achieve generic programming in C. Most of other C libraries, such as Glib and GHThash, use “void*” as generic type, but this is usually ugly (we have to take care of the memory pointed by void* even if we know it is just an integer) and adds a lot of overhead (void* itself costs sizeof(size_t) bytes and it makes the compiler unable to optimize the codes; in addition, we usually need function calls to evaluate void*).
Hey man
I haven’t seen anyone use the basic idea in the example (apart from the guys who have adopted it at my work) and I sort of want to get the credit for it when the overall meta-programming approach comes out.
I’m half considering writing a book/paper/webpage about it.
Would I be too rude if I asked that you take the example code off the post?? ( :
Also, would I be too presumptuous to ask if you wanted to collaborate on publishing the approach??
I live in England and I’m guessing you do too.
Cheers
Dave
Hey there
I’m emailing you a modified version of your hash code that uses some more macro stuff.
I’m not sure if you’re receiving my emails due to spam filtering?
Let me know what you think.
Cheers
Dave
There’s another example from 2003 (with a paper from 2006) implementing a few more containers, at http://sglib.sourceforge.net/ . The code itself is at http://likwid.googlecode.com/hg-history/65ce1fcedc201b59f14b2b01f69f973732d5ed4a/src/includes/sglib.h .
The documentation explains that
“…the invocation:
SGLIB_DEFINE_SORTED_LIST_FUNCTIONS(ilist, ilist_comparator, next)
is expanded into definitions of functions, such as sglib_ilist_len, sglib_ilist_sort, sglib_ilist_add, sglib_ilist_delete, etc. ”
So it is using the same method used above to have macros generate type-specific functions.
Though my favorite line from the documentation is:
“Everyone knows that the C preprocessor can be used to imitate genericity of other languages and everyone consider[s] this idea dangerous and ugly. I don’t.”
Personally, I also think it’s kind of ugly, but if the worst complaint we have about a method is that it requires too many backslashes, then it’s doing pretty well.