[sheepdog] [PATCH stable-0.7] rbtree: add rb_destroy helper

[Hitoshi Mitake]

From: Liu Yuan <namei.unix at gmail.com>

Signed-off-by: Liu Yuan <namei.unix at gmail.com>
Reviewed-by: Hitoshi Mitake <mitake.hitoshi at lab.ntt.co.jp>
Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>

Conflicts:
	dog/vdi.c
	include/rbtree.h
	sheep/group.c

Conflicts were resolved by Hitoshi Mitake.
Signed-off-by: Hitoshi Mitake <mitake.hitoshi at lab.ntt.co.jp>
---
 include/rbtree.h |  113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)

diff --git a/include/rbtree.h b/include/rbtree.h
index 642d151..aa16be3 100644
--- a/include/rbtree.h
+++ b/include/rbtree.h
@@ -80,4 +80,117 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
 	*rb_link = node;
 }
 
+/*
+ * Search for a value in the rbtree.  This returns NULL when the key is not
+ * found in the rbtree.
+ */
+#define rb_search(root, key, member, compar)				\
+({									\
+	struct rb_node *__n = (root)->rb_node;				\
+	typeof(key) __ret = NULL, __data;				\
+									\
+	while (__n) {							\
+		__data = rb_entry(__n, typeof(*key), member);		\
+		int __cmp = compar(key, __data);			\
+									\
+		if (__cmp < 0)						\
+			__n = __n->rb_left;				\
+		else if (__cmp > 0)					\
+			__n = __n->rb_right;				\
+		else {							\
+			__ret = __data;					\
+			break;						\
+		}							\
+	}								\
+	__ret;								\
+})
+
+/*
+ * Insert a new node into the rbtree.  This returns NULL on success, or the
+ * existing node on error.
+ */
+#define rb_insert(root, new, member, compar)				\
+({									\
+	struct rb_node **__n = &(root)->rb_node, *__parent = NULL;	\
+	typeof(new) __old = NULL, __data;				\
+									\
+	while (*__n) {							\
+		__data = rb_entry(*__n, typeof(*new), member);		\
+		int __cmp = compar(new, __data);			\
+									\
+		__parent = *__n;					\
+		if (__cmp < 0)						\
+			__n = &((*__n)->rb_left);			\
+		else if (__cmp > 0)					\
+			__n = &((*__n)->rb_right);			\
+		else {							\
+			__old = __data;					\
+			break;						\
+		}							\
+	}								\
+									\
+	if (__old == NULL) {						\
+		/* Add new node and rebalance tree. */			\
+		rb_link_node(&((new)->member), __parent, __n);		\
+		rb_insert_color(&((new)->member), root);		\
+	}								\
+									\
+	__old;							\
+})
+
+/*
+ * Search for a value in the rbtree.  When the key is not found in the rbtree,
+ * this returns the next greater node. Note, if key > greatest node, we'll
+ * return first node.
+ *
+ * For an empty tree, we return NULL.
+ */
+#define rb_nsearch(root, key, member, compar)                           \
+({                                                                      \
+        struct rb_node *__n = (root)->rb_node;                          \
+        typeof(key) __ret = NULL, __data;                               \
+                                                                        \
+        while (__n) {                                                   \
+                __data = rb_entry(__n, typeof(*key), member);           \
+                int __cmp = compar(key, __data);                        \
+                                                                        \
+                if (__cmp < 0) {                                        \
+                        __ret = __data;                                 \
+                        __n = __n->rb_left;                             \
+                } else if (__cmp > 0)                                   \
+                        __n = __n->rb_right;                            \
+                else {                                                  \
+                        __ret = __data;                                 \
+                        break;                                          \
+                }                                                       \
+        }                                                               \
+        if (!__ret && !RB_EMPTY_ROOT(root))                             \
+                __ret = rb_entry(rb_first(root), typeof(*key), member); \
+        __ret;                                                          \
+})
+
+/* Iterate over a rbtree safe against removal of rbnode */
+#define rb_for_each(pos, root)					\
+	pos = rb_first(root);					\
+	for (struct rb_node *__n = rb_next(pos);		\
+	     pos && ({ __n = rb_next(pos); 1; });		\
+	     pos = __n)
+
+/* Iterate over a rbtree of given type safe against removal of rbnode */
+#define rb_for_each_entry(pos, root, member)				\
+	for (struct rb_node *__pos = rb_first(root), *__n;		\
+	     __pos && ({ __n = rb_next(__pos); 1; }) &&			\
+		     ({ pos =  rb_entry(__pos, typeof(*pos), member); 1; }); \
+	     __pos = __n)
+
+/* Destroy the tree and free the memory */
+#define rb_destroy(root, type, member)                                  \
+{                                                                       \
+        type *__dummy;                                                  \
+        rb_for_each_entry(__dummy, root, member) {                      \
+                rb_erase(&__dummy->member, root);                       \
+                free(__dummy);                                          \
+        }                                                               \
+}
+
 #endif /* __RBTREE_H_ */
-- 
1.7.10.4