[Xen-devel] [PATCH 04/17] rbtree: empty nodes have no color

[Praveen Kumar <kpraveen.lkml@xxxxxxxxx>]

Empty nodes have no color.  We can make use of this property to simplify the
code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros.

commit 4c199a93a2d36b277a9fd209a0f2793f8460a215 from linux tree.

Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
Cc: Rik van Riel <riel@xxxxxxxxxx>
Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Cc: Daniel Santos <daniel.santos@xxxxxxxxx>
Cc: Jens Axboe <axboe@xxxxxxxxx>
Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
Cc: John Stultz <john.stultz@xxxxxxxxxx>
Signed-off-by: Stephen Rothwell <sfr@xxxxxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
---
 xen/common/rbtree.c      | 4 ++--
 xen/include/xen/rbtree.h | 9 ++++++---
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 0695edd9f9..81fb746b35 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -323,7 +323,7 @@ struct rb_node *rb_next(struct rb_node *node)
 {
     struct rb_node *parent;
 
-    if (rb_parent(node) == node)
+    if (RB_EMPTY_NODE(node))
         return NULL;
 
     /* If we have a right-hand child, go down and then left as far
@@ -352,7 +352,7 @@ struct rb_node *rb_prev(struct rb_node *node)
 {
     struct rb_node *parent;
 
-    if (rb_parent(node) == node)
+    if (RB_EMPTY_NODE(node))
         return NULL;
 
     /* If we have a left-hand child, go down and then right as far
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index f93c4d5823..29071a7e4a 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -52,9 +52,12 @@ static inline void rb_set_color(struct rb_node *rb, int 
color)
 #define RB_ROOT (struct rb_root) { NULL, }
 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
 
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
-#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
+#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbree */
+#define RB_EMPTY_NODE(node)  ((node)->rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node)  ((node)->rb_parent_color = (unsigned long)(node))
+
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
-- 
2.12.0


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel