aboutsummaryrefslogtreecommitdiffstats
path: root/lib/rbtree.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 19:30:50 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:22:34 -0400
commitd6ff1273928ebf15466a85b7e1810cd00e72998b (patch)
tree709cd0702c1ae1366994382bcd170c37ea857149 /lib/rbtree.c
parent5bc9188aa207dafd47eab57df7c4fe5b3d3f636a (diff)
rbtree: adjust node color in __rb_erase_color() only when necessary
In __rb_erase_color(), we were always setting a node to black after exiting the main loop. And in one case, after fixing up the tree to satisfy all rbtree invariants, we were setting the current node to root just to guarantee a loop exit, at which point the root would be set to black. However this is not necessary, as the root of an rbtree is already known to be black. The only case where the color flip is required is when we exit the loop due to the current node being red, and it's easiest to just do the flip at that point instead of doing it after the loop. [adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change] 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: Adrian Hunter <adrian.hunter@intel.com> Cc: Alexander Shishkin <alexander.shishkin@intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/rbtree.c')
-rw-r--r--lib/rbtree.c28
1 files changed, 17 insertions, 11 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 41cf19b2fe51..baf7c835c57c 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -259,10 +259,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
259{ 259{
260 struct rb_node *other; 260 struct rb_node *other;
261 261
262 while ((!node || rb_is_black(node)) && node != root->rb_node) 262 while (true) {
263 { 263 /*
264 if (parent->rb_left == node) 264 * Loop invariant: all leaf paths going through node have a
265 { 265 * black node count that is 1 lower than other leaf paths.
266 *
267 * If node is red, we can flip it to black to adjust.
268 * If node is the root, all leaf paths go through it.
269 * Otherwise, we need to adjust the tree through color flips
270 * and tree rotations as per one of the 4 cases below.
271 */
272 if (node && rb_is_red(node)) {
273 rb_set_black(node);
274 break;
275 } else if (!parent) {
276 break;
277 } else if (parent->rb_left == node) {
266 other = parent->rb_right; 278 other = parent->rb_right;
267 if (rb_is_red(other)) 279 if (rb_is_red(other))
268 { 280 {
@@ -291,12 +303,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
291 rb_set_black(parent); 303 rb_set_black(parent);
292 rb_set_black(other->rb_right); 304 rb_set_black(other->rb_right);
293 __rb_rotate_left(parent, root); 305 __rb_rotate_left(parent, root);
294 node = root->rb_node;
295 break; 306 break;
296 } 307 }
297 } 308 } else {
298 else
299 {
300 other = parent->rb_left; 309 other = parent->rb_left;
301 if (rb_is_red(other)) 310 if (rb_is_red(other))
302 { 311 {
@@ -325,13 +334,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
325 rb_set_black(parent); 334 rb_set_black(parent);
326 rb_set_black(other->rb_left); 335 rb_set_black(other->rb_left);
327 __rb_rotate_right(parent, root); 336 __rb_rotate_right(parent, root);
328 node = root->rb_node;
329 break; 337 break;
330 } 338 }
331 } 339 }
332 } 340 }
333 if (node)
334 rb_set_black(node);
335} 341}
336 342
337void rb_erase(struct rb_node *node, struct rb_root *root) 343void rb_erase(struct rb_node *node, struct rb_root *root)