Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
Em Fri, Aug 31, 2012 at 11:35:40AM +0300, Adrian Hunter escreveu: > AFAICS tools/perf/util/include/linux is for fixing up the > differences between kernel headers and exported kernel headers. > Hence my change: > > 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 > #include "../../../../include/linux/rbtree.h" I applied this one now, thanks, - Arnaldo -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
Em Fri, Aug 31, 2012 at 11:35:40AM +0300, Adrian Hunter escreveu: AFAICS tools/perf/util/include/linux is for fixing up the differences between kernel headers and exported kernel headers. Hence my change: 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 I applied this one now, thanks, - Arnaldo -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, Aug 31, 2012 at 1:39 AM, Michel Lespinasse wrote: > On Fri, Aug 31, 2012 at 1:35 AM, Adrian Hunter > wrote: >> On 31/08/12 11:15, Andrew Morton wrote: >>> On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse >>> wrote: I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? >>> >>> Yup. But it's unclear why we should include the header via the cc >>> command line? >> >> Dunno >> >> AFAICS tools/perf/util/include/linux is for fixing up the >> differences between kernel headers and exported kernel headers. >> Hence my change: >> >> 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 >> #include "../../../../include/linux/rbtree.h" >> >> Alex? > > Ah, makes sense to me. I wasn't previously aware of the > tools/perf/util/include/linux directory. I think your fix is fine. > (I don't understand how you hit the issue given the previous Makefile > fix, but I think your fix looks nicer) Looks like the Makefile change either never landed, or has since been dropped. Can we please get this one picked up? Without it, perf is unbuildable on linux-next. -Olof -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, Aug 31, 2012 at 1:39 AM, Michel Lespinasse wal...@google.com wrote: On Fri, Aug 31, 2012 at 1:35 AM, Adrian Hunter adrian.hun...@intel.com wrote: On 31/08/12 11:15, Andrew Morton wrote: On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse wal...@google.com wrote: I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? Yup. But it's unclear why we should include the header via the cc command line? Dunno AFAICS tools/perf/util/include/linux is for fixing up the differences between kernel headers and exported kernel headers. Hence my change: 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 Alex? Ah, makes sense to me. I wasn't previously aware of the tools/perf/util/include/linux directory. I think your fix is fine. (I don't understand how you hit the issue given the previous Makefile fix, but I think your fix looks nicer) Looks like the Makefile change either never landed, or has since been dropped. Can we please get this one picked up? Without it, perf is unbuildable on linux-next. -Olof -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
Adrian Hunter writes: > On 31/08/12 11:15, Andrew Morton wrote: >> On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse >> wrote: >> >>> On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter >>> wrote: 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 >>> >>> I thought Andrew had a patch >>> rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation >>> that fixed this though a Makefile change ? >> >> Yup. But it's unclear why we should include the header via the cc >> command line? > > Dunno > > AFAICS tools/perf/util/include/linux is for fixing up the > differences between kernel headers and exported kernel headers. > Hence my change: > > 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 > #include "../../../../include/linux/rbtree.h" > > Alex? Whichever color like best. :) Consider my initial patch a bugreport. Regards, -- Alex -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, Aug 31, 2012 at 1:35 AM, Adrian Hunter wrote: > On 31/08/12 11:15, Andrew Morton wrote: >> On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse >> wrote: >>> I thought Andrew had a patch >>> rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation >>> that fixed this though a Makefile change ? >> >> Yup. But it's unclear why we should include the header via the cc >> command line? > > Dunno > > AFAICS tools/perf/util/include/linux is for fixing up the > differences between kernel headers and exported kernel headers. > Hence my change: > > 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 > #include "../../../../include/linux/rbtree.h" > > Alex? Ah, makes sense to me. I wasn't previously aware of the tools/perf/util/include/linux directory. I think your fix is fine. (I don't understand how you hit the issue given the previous Makefile fix, but I think your fix looks nicer) -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On 31/08/12 11:15, Andrew Morton wrote: > On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse > wrote: > >> On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter >> wrote: >>> 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 >> >> I thought Andrew had a patch >> rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation >> that fixed this though a Makefile change ? > > Yup. But it's unclear why we should include the header via the cc > command line? Dunno AFAICS tools/perf/util/include/linux is for fixing up the differences between kernel headers and exported kernel headers. Hence my change: 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 #include "../../../../include/linux/rbtree.h" Alex? > > > From: Alexander Shishkin > Subject: > rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation > > Commit 2cfaf9cc68190c24fdd05e4d104099b3f27c7a44 (rbtree: adjust root color > in rb_insert_color() only when necessary) introduces bool type and constants > to the rbtree.c, and breaks compilation of tools/perf: > > ../../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 > or 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 > > This patch is the easiest solution I can think of. > > Signed-off-by: Alexander Shishkin > Acked-by: Michel Lespinasse > Signed-off-by: Andrew Morton > --- > > tools/perf/Makefile |2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff -puN > tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation > tools/perf/Makefile > --- > a/tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation > +++ a/tools/perf/Makefile > @@ -806,7 +806,7 @@ $(OUTPUT)ui/browsers/map.o: ui/browsers/ > $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DENABLE_SLFUTURE_CONST $< > > $(OUTPUT)util/rbtree.o: ../../lib/rbtree.c $(OUTPUT)PERF-CFLAGS > - $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) > -DETC_PERFCONFIG='"$(ETC_PERFCONFIG_SQ)"' $< > + $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) > -DETC_PERFCONFIG='"$(ETC_PERFCONFIG_SQ)"' -include stdbool.h $< > > $(OUTPUT)util/parse-events.o: util/parse-events.c $(OUTPUT)PERF-CFLAGS > $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -Wno-redundant-decls $< > _ > > > -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse wrote: > On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter > wrote: > > 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 > > I thought Andrew had a patch > rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation > that fixed this though a Makefile change ? Yup. But it's unclear why we should include the header via the cc command line? From: Alexander Shishkin Subject: rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation Commit 2cfaf9cc68190c24fdd05e4d104099b3f27c7a44 (rbtree: adjust root color in rb_insert_color() only when necessary) introduces bool type and constants to the rbtree.c, and breaks compilation of tools/perf: ../../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 or 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 This patch is the easiest solution I can think of. Signed-off-by: Alexander Shishkin Acked-by: Michel Lespinasse Signed-off-by: Andrew Morton --- tools/perf/Makefile |2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff -puN tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation tools/perf/Makefile --- a/tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation +++ a/tools/perf/Makefile @@ -806,7 +806,7 @@ $(OUTPUT)ui/browsers/map.o: ui/browsers/ $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DENABLE_SLFUTURE_CONST $< $(OUTPUT)util/rbtree.o: ../../lib/rbtree.c $(OUTPUT)PERF-CFLAGS - $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DETC_PERFCONFIG='"$(ETC_PERFCONFIG_SQ)"' $< + $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DETC_PERFCONFIG='"$(ETC_PERFCONFIG_SQ)"' -include stdbool.h $< $(OUTPUT)util/parse-events.o: util/parse-events.c $(OUTPUT)PERF-CFLAGS $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -Wno-redundant-decls $< _ -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter wrote: > 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 I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
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
> ---
> 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
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
---
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
#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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter adrian.hun...@intel.com wrote: 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 I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? -- Michel Walken Lespinasse A program is never fully debugged until the last user dies. -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse wal...@google.com wrote: On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter adrian.hun...@intel.com wrote: 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 I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? Yup. But it's unclear why we should include the header via the cc command line? From: Alexander Shishkin alexander.shish...@linux.intel.com Subject: rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation Commit 2cfaf9cc68190c24fdd05e4d104099b3f27c7a44 (rbtree: adjust root color in rb_insert_color() only when necessary) introduces bool type and constants to the rbtree.c, and breaks compilation of tools/perf: ../../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 or 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 This patch is the easiest solution I can think of. Signed-off-by: Alexander Shishkin alexander.shish...@linux.intel.com Acked-by: Michel Lespinasse wal...@google.com Signed-off-by: Andrew Morton a...@linux-foundation.org --- tools/perf/Makefile |2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff -puN tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation tools/perf/Makefile --- a/tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation +++ a/tools/perf/Makefile @@ -806,7 +806,7 @@ $(OUTPUT)ui/browsers/map.o: ui/browsers/ $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DENABLE_SLFUTURE_CONST $ $(OUTPUT)util/rbtree.o: ../../lib/rbtree.c $(OUTPUT)PERF-CFLAGS - $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DETC_PERFCONFIG='$(ETC_PERFCONFIG_SQ)' $ + $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DETC_PERFCONFIG='$(ETC_PERFCONFIG_SQ)' -include stdbool.h $ $(OUTPUT)util/parse-events.o: util/parse-events.c $(OUTPUT)PERF-CFLAGS $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -Wno-redundant-decls $ _ -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On 31/08/12 11:15, Andrew Morton wrote: On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse wal...@google.com wrote: On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter adrian.hun...@intel.com wrote: 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 I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? Yup. But it's unclear why we should include the header via the cc command line? Dunno AFAICS tools/perf/util/include/linux is for fixing up the differences between kernel headers and exported kernel headers. Hence my change: 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 Alex? From: Alexander Shishkin alexander.shish...@linux.intel.com Subject: rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation Commit 2cfaf9cc68190c24fdd05e4d104099b3f27c7a44 (rbtree: adjust root color in rb_insert_color() only when necessary) introduces bool type and constants to the rbtree.c, and breaks compilation of tools/perf: ../../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 or 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 This patch is the easiest solution I can think of. Signed-off-by: Alexander Shishkin alexander.shish...@linux.intel.com Acked-by: Michel Lespinasse wal...@google.com Signed-off-by: Andrew Morton a...@linux-foundation.org --- tools/perf/Makefile |2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff -puN tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation tools/perf/Makefile --- a/tools/perf/Makefile~rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation +++ a/tools/perf/Makefile @@ -806,7 +806,7 @@ $(OUTPUT)ui/browsers/map.o: ui/browsers/ $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DENABLE_SLFUTURE_CONST $ $(OUTPUT)util/rbtree.o: ../../lib/rbtree.c $(OUTPUT)PERF-CFLAGS - $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DETC_PERFCONFIG='$(ETC_PERFCONFIG_SQ)' $ + $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -DETC_PERFCONFIG='$(ETC_PERFCONFIG_SQ)' -include stdbool.h $ $(OUTPUT)util/parse-events.o: util/parse-events.c $(OUTPUT)PERF-CFLAGS $(QUIET_CC)$(CC) -o $@ -c $(ALL_CFLAGS) -Wno-redundant-decls $ _ -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
On Fri, Aug 31, 2012 at 1:35 AM, Adrian Hunter adrian.hun...@intel.com wrote: On 31/08/12 11:15, Andrew Morton wrote: On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse wal...@google.com wrote: I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? Yup. But it's unclear why we should include the header via the cc command line? Dunno AFAICS tools/perf/util/include/linux is for fixing up the differences between kernel headers and exported kernel headers. Hence my change: 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 Alex? Ah, makes sense to me. I wasn't previously aware of the tools/perf/util/include/linux directory. I think your fix is fine. (I don't understand how you hit the issue given the previous Makefile fix, but I think your fix looks nicer) -- Michel Walken Lespinasse A program is never fully debugged until the last user dies. -- 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/
Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
Adrian Hunter adrian.hun...@intel.com writes: On 31/08/12 11:15, Andrew Morton wrote: On Fri, 31 Aug 2012 01:07:24 -0700 Michel Lespinasse wal...@google.com wrote: On Fri, Aug 31, 2012 at 1:01 AM, Adrian Hunter adrian.hun...@intel.com wrote: 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 I thought Andrew had a patch rbtree-adjust-root-color-in-rb_insert_color-only-when-necessary-fix-perf-compilation that fixed this though a Makefile change ? Yup. But it's unclear why we should include the header via the cc command line? Dunno AFAICS tools/perf/util/include/linux is for fixing up the differences between kernel headers and exported kernel headers. Hence my change: 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 Alex? Whichever color like best. :) Consider my initial patch a bugreport. Regards, -- Alex -- 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/
[PATCH v2 07/12] 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
---
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) {
+ /*
+* 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);
--
1.7.7.3
--
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/
[PATCH v2 07/12] 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 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) {
+ /*
+* 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);
--
1.7.7.3
--
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/
