summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--lib/rbtree.c19
1 files changed, 15 insertions, 4 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 12abb8a..d0be5fc 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -91,8 +91,21 @@ 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)
@@ -142,8 +155,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
break;
}
}
-
- rb_set_black(root->rb_node);
}
EXPORT_SYMBOL(rb_insert_color);
OpenPOWER on IntegriCloud