Merge tag 'rpmsg-v4.14' of git://github.com/andersson/remoteproc

[sfrench/cifs-2.6.git] / lib / rbtree.c

diff --git a/lib/rbtree.c b/lib/rbtree.c
index d102d9d2ffaa640f4406dc59a576fa79e7e396b1..ba4a9d165f1bed3c39651387def0008fc793fbd6 100644 (file)
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -105,16 +105,25 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
 
        while (true) {
                /*
-                * Loop invariant: node is red
-                *
-                * If there is a black parent, we are done.
-                * Otherwise, take some corrective action as we don't
-                * want a red root or two consecutive red nodes.
+                * Loop invariant: node is red.
                 */
-               if (!parent) {
+               if (unlikely(!parent)) {
+                       /*
+                        * The inserted node is root. Either this is the
+                        * first node, or we recursed at Case 1 below and
+                        * are no longer violating 4).
+                        */
                        rb_set_parent_color(node, NULL, RB_BLACK);
                        break;
-               } else if (rb_is_black(parent))
+               }
+
+               /*
+                * If there is a black parent, we are done.
+                * Otherwise, take some corrective action as,
+                * per 4), we don't want a red root or two
+                * consecutive red nodes.
+                */
+               if(rb_is_black(parent))
                        break;
 
                gparent = rb_red_parent(parent);
@@ -123,7 +132,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                if (parent != tmp) {    /* parent == gparent->rb_left */
                        if (tmp && rb_is_red(tmp)) {
                                /*
-                                * Case 1 - color flips
+                                * Case 1 - node's uncle is red (color flips).
                                 *
                                 *       G            g
                                 *      / \          / \
@@ -146,7 +155,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                        tmp = parent->rb_right;
                        if (node == tmp) {
                                /*
-                                * Case 2 - left rotate at parent
+                                * Case 2 - node's uncle is black and node is
+                                * the parent's right child (left rotate at parent).
                                 *
                                 *      G             G
                                 *     / \           / \
@@ -170,7 +180,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                        }
 
                        /*
-                        * Case 3 - right rotate at gparent
+                        * Case 3 - node's uncle is black and node is
+                        * the parent's left child (right rotate at gparent).
                         *
                         *        G           P
                         *       / \         / \