Armin Ronacher: Collections in C

Armin seems to have reinvented the BSD queue macros.<p>Having once had the pleasure of inheriting a codebase animated by CPP-macro collections, allow me to be a voice in favor of running, not walking, from programmers who embrace them. They're tricky, they blow up, they're extremely noisy in the code, and (worst of all) they don't encapsulate, offering new devs a myriad of ways to write tangly hard-to-understand subtly broken code that works directly with the collection structure.<p>Type safety is entirely overrated. C requires so much deliberation to deploy even the simplest collection that the likelihood of you picking up a <i>foo</i> where a <i>bar</i> was what was provided is minimal, and easily diagnosed. Just use voidstar.<p>One of the first things I did at that job was to port STLport's Red-Black tree (from &#60;map&#62;) to C code, specialized on voidstar. It worked beautifully. If there are times when you don't want to use a void* collection (or a gossamer-thin wrapper around one), those are also times when you don't want a generic collection library to begin with.

Why not just pick and choose what you need from C++? For all the hate that C++ gets, one nice thing is it doesn't force anything down your throat. Between simple not using features, and compile time options (disabling exceptions for example), you NEVER have to pay for a feature that you don't want or need.<p>He could have literally written C-style code except used C++ just to create a few generic data stores instead of using all of this preprocessor magic which I guarantee is more fragile/harder to debug than basic C++ templates.

If you really want to learn how to do this, and do it really really well, check out sglib:<p><a href="http://sglib.sourceforge.net/" rel="nofollow">http://sglib.sourceforge.net/</a><p>It's got nearly every data structure you can imagine, all implemented as CPP meta hackery. Brilliant.

I don't agree with one of his premises:<p>"I normally like to avoid tools that generate new C files for the very simple reason that these usually generate ugly looking code I then have to look at which is annoying or at least require yet another tool in my toolchain which causes headaches when compiling code on more than on operating system. A simple Python script that generates a C file sounds simple, but it stops being simple if you also want that thing to be part of your windows installation where Python is usually not available or works differently."<p>I have moved most of my macro code generation to using another language, with a proper template engine, to generate code (in my case C++ but the same holds for C). If he doesn't trust Python across platforms, he can take a fixed version with known properties and code around it, or take another language (which presumably will have the same issues). I use PHP, I'm a bit careful in cross-platform features and it works great.<p>Apart from this, he can still write his code generator in C, so that on a new platforms it can be bootstrapped with a regular C compiler, then process his templates, then compile his actual code. It's painful to do string processing in C, but this generator only needs to be written once anyway, and it's not much work. Plus if he uses a small template engine, that'll take most of the pain away (most of the work will be in modifying the templates, not the code generation engine).

A good C library implementing common data structures (lists, trees, hash tables, etc) is GLib:<p><a href="http://library.gnome.org/devel/glib/" rel="nofollow">http://library.gnome.org/devel/glib/</a><p>It does many other things, provides abstractions for threads, files, etc. It is a general-purpose utility library originally written for GTK+. I never really understood why GLib is not more often used.

"This worked really well up to the point where I needed two kinds of lists. One that accepted floats and another one that works with arbitrary pointers."<p>Had he never heard of unions?<p>Even without knowledge of unions, you could treat a pointer as a, depending on the architecture, sequence of 32 bits. That sequence can be cast to whatever you want. So long as you have a clear way of describing what you've stored in that 32 bit sequence, you should never get confused.

Another way is probably to use a Linux Kernel-like list: <a href="http://isis.poly.edu/kulesh/stuff/src/klist/" rel="nofollow">http://isis.poly.edu/kulesh/stuff/src/klist/</a>

There is something to be said for not taking DRY to extremes. This appears to be one of those extremes.

Oh man, with that kind of macro "metaprogramming" (if it can be called that), you're bringing on a world of error message pain. It's almost not worth it.

I find myself reminded of the famous Dr. Sagan quote for some reason: “If you want to make an apple pie from scratch, you must first create the universe.” (From "cloning Minecraft" to "implementing a list" in only five sentences!)

This is both awesome and very terrible at the same time.<p>This proves that you can do magic in C but it also proves that C is really a low level assembler :-)<p>For me, stuff like this has been one of the prime reasons to prefer C++ over C. You can totally get the same performance and compiled code when using templates. But you gain compile-time checking and much more robust code.<p>(These preprocessor tricks are also popular in the BSD kernel)

`#define _CAT(A,B) A##B` is going to invoke undefined behaviour, I think:<p>""" None of these macro names, nor the identifier `defined`, shall be the subject of a #define or a #undef preprocessing directive. Any other predefined macro names shall begin with a leading underscore followed by an uppercase letter or a second underscore. """ (s6.10.8)

I give thanks every day that there are people like the author and others who can write and understand code like that so that I don't have to. I'll be damned if that doesn't look like trying to build a boat using a chainsaw and popsicle sticks with instructions written in Farsi.

this kind of stuff has always scared me. Its seems like it would be really easy to get confused just trying to use this stuff. Generally if i need a list i either use the void* interface and cast as neccesary, or if i want to do something like store a list of floats, or anything where i want to store the value of the item in the list (not just a pointer) then i use a 'fat' datastructure like this<p><a href="https://github.com/lukesandberg/Regex/blob/master/src/util/fat_stack.h" rel="nofollow">https://github.com/lukesandberg/Regex/blob/master/src/util/f...</a><p>when you construct it you just tell it how big each item is then it copies the value into the stack element for storage.<p>Sometimes it a few extra copy/cast statements but at least its very clear what you are doing.

<a href="http://uthash.sourceforge.net/utarray.html" rel="nofollow">http://uthash.sourceforge.net/utarray.html</a><p><a href="http://www.openbsd.org/cgi-bin/man.cgi?query=queue" rel="nofollow">http://www.openbsd.org/cgi-bin/man.cgi?query=queue</a>

For those who are curious, this solution has a name:<p>Variable Queue