[Xen-changelog] [xen master] rbtree: empty nodes have no color

[patchbot@xxxxxxx]

commit 5c94f9163fe1b62765d885db35ed92e786902c97
Author:     Michel Lespinasse <walken@xxxxxxxxxx>
AuthorDate: Wed Dec 20 18:01:26 2017 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Wed Dec 20 18:01:26 2017 +0100

    rbtree: empty nodes have no color
    
    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.  Also,
    we can get rid of the rb_init_node function which had been introduced by
    commit 88d19cf37952 ("timers: Add rb_init_node() to allow for stack
    allocated rb nodes") to avoid some issue with the empty node's color not
    being initialized.
    
    I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are
    doing there, though.  axboe introduced them in commit 10fd48f2376d
    ("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev").  The way I
    see it, the 'empty node' abstraction is only used by rbtree users to
    flag nodes that they haven't inserted in any rbtree, so asking the
    predecessor or successor of such nodes doesn't make any sense.
    
    One final rb_init_node() caller was recently added in sysctl code to
    implement faster sysctl name lookups.  This code doesn't make use of
    RB_EMPTY_NODE at all, and from what I could see it only called
    rb_init_node() under the mistaken assumption that such initialization was
    required before node insertion.
    
    [sfr@xxxxxxxxxxxxxxxx: fix net/ceph/osd_client.c build]
    Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
    Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
    Signed-off-by: Stephen Rothwell <sfr@xxxxxxxxxxxxxxxx>
    Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
    Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
    [Linux commit 4c199a93a2d36b277a9fd209a0f2793f8460a215]
    
    Ported rbtree.h and rbtree.c changes which are relevant to Xen.
    
    Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>
    Acked-by: Jan Beulich <jbeulich@xxxxxxxx>
---
 xen/common/rbtree.c      | 4 ++--
 xen/include/xen/rbtree.h | 8 +++++---
 2 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 62e6387..76f009f 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -316,7 +316,7 @@ struct rb_node *rb_next(const 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
@@ -345,7 +345,7 @@ struct rb_node *rb_prev(const 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 9496f09..e947e38 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -128,9 +128,11 @@ 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 *);
--
generated by git-patchbot for /home/xen/git/xen.git#master

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/xen-changelog