@@ -90,8 +90,23 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
- while ((parent = rb_parent(node)) && rb_is_red(parent))
+ 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.
+ */
+ parent = rb_parent(node);
+ if (!parent)
+ {
+ rb_set_black(node);
+ break;
+ } else if (rb_is_black(parent))
+ break;
+
gparent = rb_parent(parent);
if (parent == gparent->rb_left)
@@ -141,8 +156,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
__rb_rotate_left(gparent, root);
}
}
-
- rb_set_black(root->rb_node);
}
EXPORT_SYMBOL(rb_insert_color);