On 13/07/12 03:31, Michel Lespinasse wrote:
> 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 <wal...@google.com>
> ---
> lib/rbtree.c | 19 +++++++++++++++----
> 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) {
This breaks tools/perf build in linux-next:
../../lib/rbtree.c: In function 'rb_insert_color':
../../lib/rbtree.c:95:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c:95:9: note: each undeclared identifier is reported only once
for each function it appears in
../../lib/rbtree.c: In function '__rb_erase_color':
../../lib/rbtree.c:216:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c: In function 'rb_erase':
../../lib/rbtree.c:368:2: error: unknown type name 'bool'
make: *** [util/rbtree.o] Error 1
How about:
From: Adrian Hunter <adrian.hun...@intel.com>
Date: Fri, 31 Aug 2012 10:49:27 +0300
Subject: [PATCH] perf tools: fix build for another rbtree.c change
Fixes:
../../lib/rbtree.c: In function 'rb_insert_color':
../../lib/rbtree.c:95:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c:95:9: note: each undeclared identifier is reported only once
for each function it appears in
../../lib/rbtree.c: In function '__rb_erase_color':
../../lib/rbtree.c:216:9: error: 'true' undeclared (first use in this function)
../../lib/rbtree.c: In function 'rb_erase':
../../lib/rbtree.c:368:2: error: unknown type name 'bool'
make: *** [util/rbtree.o] Error 1
Signed-off-by: Adrian Hunter <adrian.hun...@intel.com>
---
tools/perf/util/include/linux/rbtree.h | 1 +
1 file changed, 1 insertion(+)
diff --git a/tools/perf/util/include/linux/rbtree.h
b/tools/perf/util/include/linux/rbtree.h
index 7a243a1..2a030c5 100644
--- a/tools/perf/util/include/linux/rbtree.h
+++ b/tools/perf/util/include/linux/rbtree.h
@@ -1 +1,2 @@
+#include <stdbool.h>
#include "../../../../include/linux/rbtree.h"
--
1.7.11.4
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
