The patch titled Subject: rbtree: adjust node color in __rb_erase_color() only when necessary has been removed from the -mm tree. Its filename was rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary.patch This patch was dropped because it was merged into mainline or a subsystem tree ------------------------------------------------------ From: Michel Lespinasse <walken@xxxxxxxxxx> Subject: 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@xxxxxxxxx: perf tools: fix build for another rbtree.c change] Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx> Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx> Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx> Cc: Rik van Riel <riel@xxxxxxxxxx> Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx> Cc: Daniel Santos <daniel.santos@xxxxxxxxx> Cc: Jens Axboe <axboe@xxxxxxxxx> Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx> Signed-off-by: Adrian Hunter <adrian.hunter@xxxxxxxxx> Cc: Alexander Shishkin <alexander.shishkin@xxxxxxxxx> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx> --- lib/rbtree.c | 28 +++++++++++++---------- tools/perf/util/include/linux/rbtree.h | 1 2 files changed, 18 insertions(+), 11 deletions(-) diff -puN lib/rbtree.c~rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary lib/rbtree.c --- a/lib/rbtree.c~rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary +++ a/lib/rbtree.c @@ -259,10 +259,22 @@ static void __rb_erase_color(struct rb_n { struct rb_node *other; - while ((!node || rb_is_black(node)) && node != root->rb_node) - { - if (parent->rb_left == node) - { + while (true) { + /* + * Loop invariant: all leaf paths going through node have a + * black node count that is 1 lower than other leaf paths. + * + * If node is red, we can flip it to black to adjust. + * If node is the root, all leaf paths go through it. + * Otherwise, we need to adjust the tree through color flips + * and tree rotations as per one of the 4 cases below. + */ + if (node && rb_is_red(node)) { + rb_set_black(node); + break; + } else if (!parent) { + break; + } else if (parent->rb_left == node) { other = parent->rb_right; if (rb_is_red(other)) { @@ -291,12 +303,9 @@ static void __rb_erase_color(struct rb_n rb_set_black(parent); rb_set_black(other->rb_right); __rb_rotate_left(parent, root); - node = root->rb_node; break; } - } - else - { + } else { other = parent->rb_left; if (rb_is_red(other)) { @@ -325,13 +334,10 @@ static void __rb_erase_color(struct rb_n rb_set_black(parent); rb_set_black(other->rb_left); __rb_rotate_right(parent, root); - node = root->rb_node; break; } } } - if (node) - rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root) diff -puN tools/perf/util/include/linux/rbtree.h~rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary tools/perf/util/include/linux/rbtree.h --- a/tools/perf/util/include/linux/rbtree.h~rbtree-adjust-node-color-in-__rb_erase_color-only-when-necessary +++ a/tools/perf/util/include/linux/rbtree.h @@ -1,2 +1,3 @@ #include <stdbool.h> +#include <stdbool.h> #include "../../../../include/linux/rbtree.h" _ Patches currently in -mm which might be from walken@xxxxxxxxxx are origin.patch prio_tree-remove-fix.patch -- To unsubscribe from this list: send the line "unsubscribe mm-commits" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html