Generic red-black trees

Generic red-black trees

Posted Jun 16, 2012 4:52 UTC (Sat) by daniel.santos (subscriber, #85158)
In reply to: Generic red-black trees by slashdot
Parent article: Generic red-black trees

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.

---

(Log in to post comments)