Weekly edition	Kernel	Security	Distributions	Contact Us	Search
Archives	Calendar	Subscribe	Write for LWN	LWN.net FAQ	Sponsors

Generic red-black trees

Posted Jun 14, 2012 3:19 UTC (Thu) by slashdot (guest, #22014)
Parent article: Generic red-black trees

C++ templates are obviously the best solution.

If not using C++, the best solution is to put the template body in an unguarded include file.

Then, to instantiate the template, you do something like this:

#define NAME foo
#define T foo_t
#define U bar_t
#include "template_body.h"

(with the header #undefining those macros)

This allows to implement the code without huge multiline macros and horrible trailing continuation backslashes.

(Log in to post comments)

Generic red-black trees

Posted Jun 14, 2012 13:49 UTC (Thu) by nix (subscriber, #2304) [Link]

What a coincidence. At the very instant you were typing that comment, I was replacing around a thousand lines of duplicated code using exactly that token-pasting technique (this was related to <elf.h> though, and its annoying mass of types with names differing only in 32-vs-64...)

Some of the hoary old C tricks are truly disgusting, but they do work. The preprocessor is horrible, but if you take it away you have to provide *something*, preferably something less horrible, to replace it (as C++ did, but Java notably did not).

Generic red-black trees

Posted Jun 14, 2012 14:08 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link]

People use dynamic bytecode generation and/or reflection in Java quite often as a replacement for things done with templates/preprocessor.

Generic red-black trees

Posted Jun 14, 2012 16:07 UTC (Thu) by etienne (subscriber, #25256) [Link]

Maybe the nice thing about templates/preprocessor is that the work is done once at compilation time, and not each times the software is started.
Also, preprocessor help you to initialise a lot of things which will then be loaded in memory already initialised, ready to use.
It is not unheard-of to generate a lot of variable/structure and sort them by the "sort" command in Makefile to have a sorted list ready to use, with pointer to next already set by the linker. That initialised memory will also have good cache locality.
Some people may also have tried to use the old "m4" macro language to replace the CPP processor, but it did not stick too nicely.

Generic red-black trees

Posted Jun 16, 2012 4:52 UTC (Sat) by daniel.santos (subscriber, #85158) [Link]

I actually considered this "supermacro" approach (as I've heard it called before). But with 17-ish parameters, it just really, really, really seemed verbose to me. One of my aims is reducing copy, paste & edit source code and while using this technique would likely reduce it, it wouldn't be to the degree that I had hoped. (It would improve backtraces and make #if directives available however.)

#define RB_PREFIX          my_objects
#define RB_CONT_TYPE       struct container
#define RB_CONT_ROOT       tree
#define RB_CONT_LEFT       leftmost
#define RB_CONT_RIGHT      /* none */
#define RB_CONT_COUNT      count
#define RB_OBJ_TYPE        struct object
#define RB_OBJ_NODE        node
#define RB_OBJ_KEY         id
#define RB_ALLOW_DUPES     1
#define RB_INSERT_REPLACES 1
#define RB_COMPARE_FUNC    compare_u32
#define RB_AUGMENTED_FUNC  /* none */
#define RB_INSERT_MOD      static __flatten noinline
#define RB_FIND_MOD        /* defaults */
#define RB_INSERT_NEAR_MOD /* defaults */
#define RB_FIND_NEAR_MOD   /* defaults */
#include <linux/grbtree.h>

vs

/* this is actually version 4's RB_DEFINE_INTERFACE, with 16 arguments */
RB_DEFINE_INTERFACE(
	my_objects,
	struct container, tree, leftmost, /* no right */, count,
	struct object, node, id,
	RB_UNIQUE_KEYS | RB_INSERT_REPLACES, compare_u32, /* no augment */,
	static __flatten noinline,,,)

What's your opinion?

As far as metaprogramming is concerned, if you examine it the code, I think you'll see that this is really as close you can get to "C metaprogramming" with current technologies & standards (minus any tricks I haven't learned yet). The "domain language" is basically what you pass to the RB_DEFINE_INTERFACE macro, weak as that may be. This is stored in a compile-time struct rb_relationship object (which shouldn't even appear in the data section of the object file) and tells the compiler how to instantiate the inline functions. Without leaving the C language completely, I don't see how else to create a better solution.

Generic red-black trees

Posted Jun 26, 2012 13:04 UTC (Tue) by juliank (subscriber, #45896) [Link]

You at least know what the first thing does, the latter one is not really understandable (do you want to remember 16 macro arguments or look them up all the time?)