summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:30:44 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:33 +0900
commit6d58452dc066db61acdff7b84671db1b11a3de1c (patch)
tree36df08157d975398c5416d068f83cd31b79ae2c7
parent1f0528653e41ec230c60f5738820e8a544731399 (diff)
downloadop-kernel-dev-6d58452dc066db61acdff7b84671db1b11a3de1c.zip
op-kernel-dev-6d58452dc066db61acdff7b84671db1b11a3de1c.tar.gz
rbtree: adjust root color in rb_insert_color() only when necessary
The root node of an rbtree must always be black. However, rb_insert_color() only needs to maintain this invariant when it has been broken - that is, when it exits the loop due to the current (red) node being the root. In all other cases (exiting after tree rotations, or exiting due to an existing black parent) the invariant is already satisfied, so there is no need to adjust the root node color. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Acked-by: David Woodhouse <David.Woodhouse@intel.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Daniel Santos <daniel.santos@pobox.com> Cc: Jens Axboe <axboe@kernel.dk> Cc: "Eric W. Biederman" <ebiederm@xmission.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-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