Generic red-black trees

Generic red-black trees

Posted Jun 16, 2012 2:57 UTC (Sat) by daniel.santos (subscriber, #85158)
Parent article: Generic red-black trees

First off, thank you Jonathan for this wonderful write-up! I haven't been getting much feedback in LKML and this is exactly the type of discussion I'm needing. I found it funny too that two implementations popped up at almost the exact same time. Unfortunately, we didn't find out about each other for a few months. To add to this, there's a generic interval tree implementation as well, that may eliminate the need for the augmented function in rbtree.

So I appreciate your explanation of my implementation, as you seem to understand my solution pretty well. However, the main thing I want to address (that wasn't in my last patch set posting) is that you don't actually have to use the ugly macro (and believe me, I truly hate ugly macros, but went this way when I exhausted all other options). My implementation actually consists of two layers written on top of the existing rbtree implementation. The first layer consists of an enum, struct rb_relationship and some inline functions.

enum rb_flags {
RB_HAS_LEFTMOST	   = 0x00000001, /* The container has a struct rb_node *leftmost
				    member that will receive a pointer to the
				    leftmost (smallest) object in the tree that
				    is updated during inserts & deletions */
RB_HAS_RIGHTMOST   = 0x00000002, /* same as above (for right side of tree) */
RB_HAS_COUNT	   = 0x00000004, /* The container has an unsigned 32-bit
				    integer field that will receive updates of
				    the object count in the tree. */
RB_UNIQUE_KEYS	   = 0x00000008, /* the tree contains only unique values. */
RB_INSERT_REPLACES = 0x00000010, /* when set, the rb_insert() will replace a
				    value if it matches the supplied one (valid
				    only when RB_UNIQUE_KEYS is set). */
RB_IS_AUGMENTED	   = 0x00000020, /* is an augmented tree */
};

struct rb_relationship {
	long root_offset;
	long left_offset;
	long right_offset;
	long count_offset;
	long node_offset;
	long key_offset;
	int flags;
	const rb_compare_f compare;
	const rb_augment_f augment;
};

As I described in my patch set, this struct can be thought of as both the DDL (Data Definition Language) of a database and the template parameters of a C++ templatized function since the values are used both to define the relationship between two entities as well as dictate how the inline function will expand. The generic inline functions themselves have very little dependency on the pre-processor, aside from build-time bug checks. Like Kent Overstreet's implementation, these functions accept pointers to rb_root & rb_node structs. As of version 4, which I hope to publish early next week, they are all defined static __always_inline __flatten (more on that later).

struct rb_node *rb_find(
		struct rb_root *root,
		const void *key,
		const struct rb_relationship *rel);
struct rb_node *rb_find_near(
		struct rb_node *from,
		const void *key,
		const struct rb_relationship *rel);
struct rb_node *rb_insert(
		struct rb_root *root,
		struct rb_node *node,
		const struct rb_relationship *rel);
struct rb_node *rb_insert_near(
		struct rb_root *root,
		struct rb_node *start,
		struct rb_node *node,
		const struct rb_relationship *rel);
void rb_remove(
		struct rb_root *root,
		struct rb_node *node,
		const struct rb_relationship *rel);

Finally, there is a smaller macro ("smaller" as in "expanding to far fewer characters") that can be used to create a struct rb_relationship initializer, still with a daunting number of parameters however.

#define RB_RELATIONSHIP(						\
		cont_type, root, left, right, count,			\
		obj_type, node, key,					\
		_flags, _compare, _augment) //...

As with RB_DEFINE_INTERFACE, you leave a parameter empty if you don't need the feature (I changed the _augment parameter to use this method as well for the sake of consistency). Thus, there are a total of three ways you can use this interface, which is left up to the programmer's preferences and needs.

1. Define your struct rb_relationship by hand and call the generic inline functions directly,
2. use RB_RELATIONSHIP to initialize your struct rb_relationship variable and call the generic inline functions directly, or
3. use RB_DEFINE_INTERFACE to define the entire interface (ugly macro, but you get type safety and brevity).

So here's what these first two methods would look like (using version 4):

Method 1:

const static struct rb_relationship my_rel = RB_RELATIONSHIP(
	struct cfs_rq, tasks_timeline, rb_leftmost, /* no rightmost or count */, ,
	struct sched_entity, run_node, vruntime,
	0, compare_vruntime, /* no augment */);

Note that, as with RB_DEFINE_INTERFACE, you don't need to supply the RB_HAS_LEFTMOST flag, since the macro does it for you if the leftmost parameter is non-empty.

Method 2:

const static struct rb_relationship my_rel = {
	.root_offset  = offsetof(struct cfs_rq, tasks_timeline),
	.left_offset  = offsetof(struct cfs_rq, rb_leftmost),
	.right_offset = 0,
	.count_offset = 0,
	.node_offset  = offsetof(struct sched_entity, run_node),
	.key_offset   = offsetof(struct sched_entity, vruntime),
	.flags        = RB_HAS_LEFTMOST,
	.compare      = (const rb_compare_f)compare_vruntime,
	.augment      = 0
};

On the topic of the __flatten function modifier, this expands to __attribute__((flatten)) for gcc 4.1 and later (excepting 4.6.0, which had a bug) and was necessary to solve an optimization problem in gcc 4.5. Overall, optimization is perfect in 4.6.3+, acceptable in 4.1.2 to 4.5.3 and not so very pretty in 3.4.6 (haven't tested 4.0 yet). I've just finished the find_near and insert_near (the later is still untested) and I'm working on a test module both to test for correctness and do performance profiling -- something that I see as crucial since the the implementation depends upon the compiler in a somewhat "bleeding edge" fashion. (As an example, an early iteration of this bombed so bad on 4.5 that it produced 3x larger and 2x slower function than on 4.6.2.)

---

(Log in to post comments)