[PATCH v2 2/3] [RFC] Generic Red-Black Trees

[Daniel Santos <danielfsantos@att.net>]

[-- Attachment #1: Type: text/plain, Size: 1 bytes --]



[-- Attachment #2: 0007-Generic-search-insert-for-Red-Black-Trees.patch --]
[-- Type: text/x-patch, Size: 19958 bytes --]

>From 5d71e7b4bc2b43f40568e0493b65332218dce0ba Mon Sep 17 00:00:00 2001
From: Daniel Santos <daniel.santos@pobox.com>
Date: Thu, 31 May 2012 17:43:24 -0500
Subject: Generic search & insert for Red-Black Trees

---
 include/linux/rbtree.h |  623 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 623 insertions(+), 0 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..1133682 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -96,6 +96,8 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
 
 #include <linux/kernel.h>
 #include <linux/stddef.h>
+#include <linux/typecheck.h>
+#include <linux/bug.h>
 
 struct rb_node
 {
@@ -148,6 +150,7 @@ extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
 
 typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+typedef long (*rb_compare_f)(const void *a, const void *b);
 
 extern void rb_augment_insert(struct rb_node *node,
 			      rb_augment_f func, void *data);
@@ -174,4 +177,624 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 	*rb_link = node;
 }
 
+
+#define __JUNK junk,
+#define _iff_empty(test_or_junk, t, f) __iff_empty(test_or_junk, t, f)
+#define __iff_empty(__ignored1, __ignored2, result, ...) result
+
+/**
+ * IFF_EMPTY() - Expands to the second argument when the first is empty, the
+ *               third if non-empty.
+ * @test:        An argument to test for emptiness.
+ * @t:           A value to expand to if test is empty.
+ * @f:           A value to expand to if test is non-empty.
+ *
+ * Caveats:
+ * IFF_EMPTY isn't perfect.  The test parmater must either be empty or a valid
+ * pre-processor token as well as result in a valid token when pasted to the
+ * end of a word.
+ *
+ * Valid Examples:
+ * IFF_EMPTY(a, b, c) = c
+ * IFF_EMPTY( , b, c) = b
+ * IFF_EMPTY( ,  , c) = (nothing)
+ *
+ * Invalid Examples:
+ * IFF_EMPTY(.,  b, c)
+ * IFF_EMPTY(+,  b, c)
+ */
+#define IFF_EMPTY(test, t, f) _iff_empty(__JUNK##test, t, f)
+
+/**
+ * IS_EMPTY() - test if a pre-processor argument is empty.
+ * @arg:        An argument (empty or non-empty)
+ *
+ * If empty, expands to 1, 0 otherwise.  See IFF_EMPTY() for caveats &
+ * limitations.
+ */
+#define IS_EMPTY(arg)	IFF_EMPTY(arg, 1, 0)
+
+/**
+ * OPT_OFFSETOF() - return the offsetof for the supplied expression, or zero
+ *                  if m is an empty argument.
+ * @type:           struct/union type
+ * @m:              (optional) struct member name
+ *
+ * Since any offsetof can return zero if the specified member is the first in
+ * the struct/union, you should also check if the argument is empty separately
+ * with IS_EMPTY(m).
+ */
+#define OPT_OFFSETOF(type, m) ((size_t) &((*((type *)0)) IFF_EMPTY(m, , .m)))
+
+
+enum rb_flags {
+	RB_HAS_LEFTMOST	   = 0x00000001,
+	RB_HAS_RIGHTMOST   = 0x00000002,
+	RB_UNIQUE_KEYS	   = 0x00000004,
+	RB_INSERT_REPLACES = 0x00000008,
+	RB_ALL_FLAGS	   = RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST
+			   | RB_UNIQUE_KEYS | RB_INSERT_REPLACES,
+};
+
+/**
+ * struct rb_relationship - Defines relationship between a container and
+ *                      the objects it contains.
+ * @root_offset:        Offset of container's struct rb_root member.
+ * @left_offset:        (Used only if has_left.) Offset of the container's
+ *                      struct rb_node *leftmost member for storing a pointer
+ *                      to the leftmost node in the tree, which is kept
+ *                      updated as inserts and deletions are made.
+ * @right_offset:       Same as left_offset, except for right side of tree.
+ * @node_offset:        Offset of object's struct rb_node member.
+ * @key_offset:         Offset of object's key member.
+ * @flags:              TODO
+ *
+ * Instances of struct rb_relationship should be compile-time constants (or
+ * rather, the value of its members).
+ */
+struct rb_relationship {
+	long root_offset;
+	long left_offset;
+	long right_offset;
+	long node_offset;
+	long key_offset;
+	int flags;
+};
+
+static __always_inline
+struct rb_root *__rb_to_root(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+	return (struct rb_root *)((char *)ptr + rel->root_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_left(void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON(!(rel->flags & RB_HAS_LEFTMOST));
+	BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST2(rel->left_offset);
+	return (struct rb_node **)((char *)ptr - rel->root_offset
+					       + rel->left_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_right(void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON(!(rel->flags & RB_HAS_RIGHTMOST));
+	BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST2(rel->right_offset);
+	return (struct rb_node **)((char *)ptr - rel->root_offset
+					       + rel->right_offset);
+}
+
+static __always_inline
+const void *__rb_node_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+	BUILD_BUG_ON_NON_CONST2(rel->key_offset);
+	return (const void *)((const char *)ptr - rel->node_offset
+						+ rel->key_offset);
+}
+
+static __always_inline
+char *__rb_node_to_obj(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+	return (char *)ptr - rel->node_offset;
+}
+
+/* not used anymore */
+#if 0
+static __always_inline
+struct rb_node *__rb_to_node(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+	return (struct rb_node *)((char *)ptr + rel->node_offset);
+}
+
+static __always_inline
+const void *__rb_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->key_offset);
+	return (const void *)((const char *)ptr + rel->key_offset);
+}
+
+#endif
+
+/** __rb_find -
+ *
+ */
+static __always_inline
+struct rb_node *__rb_find(
+		struct rb_node *node,
+		const void *key,
+		const struct rb_relationship *rel,
+		const rb_compare_f compare)
+{
+	while (node) {
+		long diff = compare(key, __rb_node_to_key(node, rel));
+
+		if (diff > 0)
+			node = node->rb_right;
+		else if (diff < 0)
+			node = node->rb_left;
+		else
+			return node;
+	}
+
+	return 0;
+}
+
+
+static __always_inline
+struct rb_node *rb_find(
+	struct rb_root *root,
+	const void *key,
+	const struct rb_relationship *rel,
+	const rb_compare_f compare)
+{
+	return __rb_find(root->rb_node, key, rel, compare);
+}
+
+enum rb_find_subtree_match {
+	RB_MATCH_NONE		= 0,
+	RB_MATCH_IMMEDIATE	= 2,
+	RB_MATCH_LEFT		= -1,
+	RB_MATCH_RIGHT		= 1,
+};
+
+
+/**
+ * rb_find_subtree - Locate the subtree that contains the specified key (if it
+ * 		     exists) starting from a specific node traversing upwards.
+ *
+ */
+static __always_inline
+struct rb_node *__rb_find_subtree(
+		struct rb_node *from,
+		const void *key,
+		int *matched,
+		const struct rb_relationship *rel,
+		const rb_compare_f compare)
+{
+	struct rb_node *prev = from;
+	struct rb_node *node = rb_parent(from);
+	long diff;
+
+	if (!node) {
+		*matched = RB_MATCH_NONE;
+		return prev;
+	}
+
+	diff = compare(key, __rb_node_to_key(node, rel));
+
+	if (diff > 0) {
+		while (1) {
+			prev = node;
+			node = rb_parent(prev);
+			if (!node)
+				break;
+
+			diff = compare(key, __rb_node_to_key(node, rel));
+			if (diff < 0)
+				break;
+			else if (!diff) {
+				*matched = RB_MATCH_LEFT;
+				return node;
+			}
+		}
+		*matched = RB_MATCH_NONE;
+		return prev->rb_left;
+	} else if (diff < 0) {
+		while (1) {
+			prev = node;
+			node = rb_parent(prev);
+			if (!node)
+				break;
+
+			diff = compare(key, __rb_node_to_key(node, rel));
+			if (diff > 0)
+				break;
+			else if (!diff) {
+				*matched = RB_MATCH_RIGHT;
+				return node;
+			}
+		}
+		*matched = RB_MATCH_NONE;
+		return prev->rb_right;
+	}
+
+	*matched = RB_MATCH_IMMEDIATE;
+	return node;
+}
+
+static __always_inline
+struct rb_node *rb_find_near(
+	struct rb_node *from,
+	const void *key,
+	const struct rb_relationship *rel,
+	const rb_compare_f compare)
+{
+	int matched;
+	struct rb_node *subtree;
+
+	subtree = __rb_find_subtree(from, key, &matched, rel, compare);
+
+	if (matched) {
+		return subtree;
+	}
+
+	return __rb_find(subtree, key, rel, compare);
+}
+
+static __always_inline
+struct rb_node *__rb_insert_epilogue(
+	struct rb_root *root,
+	struct rb_node *parent,
+	struct rb_node *node,
+	struct rb_node *found,
+	struct rb_node **rb_link,
+	const struct rb_relationship *rel,
+	const rb_augment_f augmented) {
+
+	if ((rel->flags & RB_UNIQUE_KEYS) && found) {
+		/* if replacing, we will still need to call do augmented */
+		if (rel->flags & RB_INSERT_REPLACES)
+			rb_replace_node(found, node, root);
+		/* otherwise, we can bail */
+		else
+			goto exit;
+	} else {
+		rb_link_node(node, parent, rb_link);
+		rb_insert_color(node, root);
+	}
+
+	if (augmented)	/* TODO: check verify which versions of gcc compile this out */
+		rb_augment_insert(node, augmented, NULL);
+
+exit:
+	return found;
+}
+
+
+/**
+ * rb_insert() - Inserts an object into a container.
+ * @container:  Pointer to the container.
+ * @obj:        Pointer to the new object to insert.
+ * @rel:        Pointer to the compile-time constant relationship definition.
+ *
+ * If an object with the same key already exists and rel->ins_replace is non-zero,
+ * then it is replaced with obj; if rel->ins_replace is zero, then no change is made.
+ * In either case, a pointer to the existing object is returned. Note that
+ * return values are pointers to the objects themselves, not to the struct
+ * rb_node.
+ *
+ * If no object with the same key exists, then obj is inserted and NULL is
+ * returned.
+ *
+ * See rb_find for example.
+ */
+static __always_inline
+struct rb_node *rb_insert(
+	struct rb_root *root,
+	struct rb_node *node,
+	const struct rb_relationship *rel,
+	const rb_compare_f compare,
+	const rb_augment_f augmented)
+{
+	struct rb_node **p     = &root->rb_node;
+	struct rb_node *parent = NULL;
+	const void *key        = __rb_node_to_key(node, rel);
+	int leftmost           = 1;
+	int rightmost          = 1;
+
+	BUILD_BUG_ON_NON_CONST2(rel->flags);
+	BUG_ON((rel->flags & RB_INSERT_REPLACES)
+		 && !(rel->flags & RB_UNIQUE_KEYS));
+
+	while (*p) {
+		long diff = compare(key, __rb_node_to_key(*p, rel));
+		parent    = *p;
+
+		if (diff > 0) {
+			p = &(*p)->rb_right;
+			if (rel->flags & RB_HAS_LEFTMOST)
+				leftmost = 0;
+		} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
+			p = &(*p)->rb_left;
+			if (rel->flags & RB_HAS_RIGHTMOST)
+				rightmost = 0;
+		} else
+			break;
+	}
+
+	if ((rel->flags & RB_HAS_LEFTMOST) && leftmost) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+
+		if (!(rel->flags & RB_INSERT_REPLACES) || !(*p) || *left == *p)
+			*left = node;
+	}
+	if ((rel->flags & RB_HAS_RIGHTMOST) && rightmost) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+
+		if (!(rel->flags & RB_INSERT_REPLACES) || !(*p) || *right == *p)
+			*right = node;
+	}
+
+	return __rb_insert_epilogue(root, parent, node, *p, p, rel, augmented);
+}
+
+static __always_inline
+struct rb_node *rb_insert_near(
+		struct rb_root *root,
+		struct rb_node *start,
+		struct rb_node *node,
+		const struct rb_relationship *rel,
+		const rb_compare_f compare,
+		const rb_augment_f augmented)
+{
+
+	return 0;
+/* TODO: not yet finished */
+#if 0
+	const void *key        = __rb_node_to_key(node, rel);
+	struct rb_node **p     = &start;
+	struct rb_node *parent = NULL;
+	struct rb_node *ret;
+	int matched;
+	long diff;
+
+	BUILD_BUG_ON_NON_CONST2(rel->flags);
+
+	ret = __rb_find_subtree(start, key, &matched, rel, compare);
+
+	if (!matched) {
+		while (*p) {
+			diff   = compare(__rb_node_to_key(*p, rel), key);
+			parent = *p;
+
+			if (diff > 0) {
+				p = &(*p)->rb_right;
+			} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
+				p = &(*p)->rb_left;
+			} else
+				break;
+		}
+		ret = *p;
+	} else {
+		/* FIXME: p will not be correctly set to point to the parent's
+		 * rb_left or rb_right member here when it's passed as
+		 * __rb_insert_epilogue()'s rb_link parameter.
+		 */
+		if (rel->flags & (RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST)) {
+			if ((rel->flags & RB_HAS_LEFTMOST)) {
+				struct rb_node **left = __rb_root_to_left(root, rel);
+				if (*left == ret) {
+					*left = node;
+				}
+			}
+
+			if ((rel->flags & RB_HAS_RIGHTMOST)) {
+				struct rb_node **right = __rb_root_to_right(root, rel);
+				if (*right == ret) {
+					*right = node;
+				}
+			}
+		}
+	}
+
+	if (rel->flags & RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST) {
+
+	}
+
+	if ((rel->flags & RB_HAS_LEFTMOST)) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+		if (!*left || (*left == parent && diff < 0)) {
+			*left = node;
+		}
+	}
+
+	if ((rel->flags & RB_HAS_RIGHTMOST)) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+		if ((*right == parent && diff > 0) || !*right) {
+			*right = node;
+		}
+	}
+
+	return __rb_insert_epilogue(root, parent, node, ret, p, rel, augmented);
+#endif
+}
+
+static __always_inline
+void rb_remove(
+	struct rb_root *root,
+	struct rb_node *node,
+	const struct rb_relationship *rel,
+	const rb_augment_f augmented)
+{
+	struct rb_node *deepest = NULL;
+
+	BUILD_BUG_ON_NON_CONST2(rel->flags);
+
+	if (augmented)
+		deepest = rb_augment_erase_begin(node);
+
+	if (rel->flags & RB_HAS_LEFTMOST) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+
+		if (*left == node)
+			*left = rb_next(node);
+	}
+
+	if (rel->flags & RB_HAS_RIGHTMOST) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+
+		if (*right == node)
+			*right = rb_prev(node);
+	}
+
+	rb_erase(node, root);
+
+	if (augmented)
+		rb_augment_erase_end(deepest, augmented, NULL);
+}
+
+
+/**
+ * RB_RELATIONHIP - Define the relationship bewteen a container with a
+ *                  struct rb_root member, and the objects it contains.
+ * @cont_type: container type
+ * @root:      container's struct rb_root member name
+ * @left:      (optional) if the container needs a pointer to the tree's
+ *             leftmost (smallest) object, then specify the container's struct
+ *             rb_node *leftmost member.  Otherwise, leave this parameter
+ *             empty.
+ * @right:     (optional) same as left, but for the rightmost (largest)
+ * @obj_type:  the type of object stored in container
+ * @node:      the struct rb_node memeber of the object
+ * @key:       the key member of the object
+ * @flags      see rb_flags.  Note: you do not have to specify RB_HAS_LEFTMOST
+ *             or RB_HAS_RIGHTMOST as these will be added automatically if the
+ *             left or right parameter (respectively) is non-empty
+ */
+#define RB_RELATIONHIP(							\
+		cont_type, root, left, right,				\
+		obj_type, node, key,					\
+		_flags) {						\
+	.root_offset     = offsetof(cont_type, root),			\
+	.left_offset     = OPT_OFFSETOF(cont_type, left),		\
+	.right_offset    = OPT_OFFSETOF(cont_type, right),		\
+	.node_offset     = offsetof(obj_type, node),			\
+	.key_offset      = offsetof(obj_type, key),			\
+	.flags           = (_flags)					\
+			 | IFF_EMPTY(left , 0, RB_HAS_LEFTMOST)		\
+			 | IFF_EMPTY(right, 0, RB_HAS_RIGHTMOST),	\
+}
+
+/**
+ * RB_DEFINE_INTERFACE - Defines a complete interface for a relationship
+ *                       between container and object including a struct
+ *                       rb_relationship and an interface of type-safe wrapper
+ *                       functions.
+ * @prefix:    name for the relationship (see explanation below)
+ * @cont_type: container type
+ * @root:      container's struct rb_root member name
+ * @left:      (optional) if the container needs a pointer to the tree's
+ *             leftmost (smallest) object, then specify the container's struct
+ *             rb_node *leftmost member.  Otherwise, leave this parameter
+ *             empty.
+ * @right:     (optional) same as left, but for the rightmost (largest)
+ * @obj_type:  the type of object stored in container
+ * @node:      the struct rb_node memeber of the object
+ * @key:       the key member of the object
+ * @flags      see rb_flags.  Note: you do not have to specify RB_HAS_LEFTMOST
+ *             or RB_HAS_RIGHTMOST as these will be added automatically if the
+ *             left or right parameter (respectively) is non-empty
+ * @compare:   pointer to key rb_compare_f function to compare keys.  Function
+ *             will be cast to and called as type long (*)(const void *a, const
+ *             void *b), hence type-safety is lost (FIXME: can this be improved
+ *             at all?).
+ * @augmented: pointer to the rb_augment_f or zero if tree is not augmented.
+ *
+ * This macro can be delcared in the global scope of either a source or header
+ * file and will generate a static const struct rb_relationship variable named
+ * prefix##_rel as well as similarly named (i.e., prefix##_##func_name)
+ * type-safe wrapper functions for find, find_near, insert, insert_near and
+ * remove.  If these function names are not sufficient, you can use the
+ * __RB_DEFINE_INTERFACE macro to specify them explicitly.
+ *
+ * The compare function will be passed pointers to the key members of two
+ * objects.  If your compare function needs access to other members of your
+ * struct (e.g., compound keys, etc.) , you can use the rb_entry macro to
+ * access other members.  However, if you use this mechanism, your find
+ * function must always pass it's key parameter as a pointer to the key member
+ * of an object of type obj_type, since the compare function is used for both
+ * inserts and lookups.
+ */
+#define RB_DEFINE_INTERFACE(prefix, ...)\
+__RB_DEFINE_INTERFACE(			\
+	prefix ## _rel,			\
+	prefix ## _insert,		\
+	prefix ## _insert_near,		\
+	prefix ## _find,		\
+	prefix ## _find_near,		\
+	prefix ## _remove,		\
+	__VA_ARGS__)
+
+
+#define __RB_DEFINE_INTERFACE(						\
+	rel_var, insert, insert_near, find, find_near, remove,		\
+	cont_type, root, left, right,					\
+	obj_type, node, key,						\
+	flags, compare, augmented)					\
+static const struct rb_relationship rel_var = RB_RELATIONHIP(		\
+	cont_type, root, left, right,					\
+	obj_type, node, key,						\
+	flags);								\
+									\
+static __always_inline							\
+obj_type *insert(cont_type *cont, obj_type *obj)			\
+{									\
+	struct rb_node *ret = rb_insert(				\
+			&cont->root, &obj->node, &rel_var,		\
+			(const rb_compare_f)compare, augmented);	\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *insert_near(cont_type *cont, obj_type *near, obj_type *obj)	\
+{									\
+	struct rb_node *ret = rb_insert_near(				\
+			&cont->root, &near->node, &obj->node, &rel_var,	\
+			(const rb_compare_f)compare, augmented);	\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *find(cont_type *cont,						\
+	       const typeof(((obj_type *)0)->key) *_key)		\
+{									\
+	struct rb_node *ret = rb_find(					\
+			&cont->root, _key, &rel_var,			\
+			(const rb_compare_f)compare);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *find_near(obj_type *near,					\
+		    const typeof(((obj_type *)0)->key) *_key)		\
+{									\
+	struct rb_node *ret = rb_find_near(				\
+			&near->node, _key, &rel_var,			\
+			(const rb_compare_f)compare);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+void remove(cont_type *cont, obj_type *obj)				\
+{									\
+	rb_remove(&cont->root, &obj->node, &rel_var, augmented);	\
+}									\
+
 #endif	/* _LINUX_RBTREE_H */
-- 
1.7.3.4