linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Adrian Hunter <adrian.hunter@intel.com>
To: akpm@linux-foundation.org
Cc: Michel Lespinasse <walken@google.com>,
	linux-mm@kvack.org, linux-kernel@vger.kernel.org,
	acme@redhat.com
Subject: Re: [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary
Date: Fri, 31 Aug 2012 11:01:36 +0300	[thread overview]
Message-ID: <50406F60.5040707@intel.com> (raw)
In-Reply-To: <1342139517-3451-8-git-send-email-walken@google.com>

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 <walken@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.hunter@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.hunter@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


  reply	other threads:[~2012-08-31  8:00 UTC|newest]

Thread overview: 27+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-07-13  0:31 [PATCH v2 00/12] rbtree updates Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 01/12] rbtree: reference Documentation/rbtree.txt for usage instructions Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 02/12] rbtree: empty nodes have no color Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 03/12] rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 04/12] rbtree: move some implementation details from rbtree.h to rbtree.c Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 05/12] rbtree: performance and correctness test Michel Lespinasse
2012-07-13 20:15   ` Andrew Morton
2012-07-13 22:33     ` Michel Lespinasse
2012-07-13 22:45       ` Andrew Morton
2012-07-13 23:09         ` Michel Lespinasse
2012-07-13 23:11           ` Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 06/12] rbtree: break out of rb_insert_color loop after tree rotation Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 07/12] rbtree: adjust root color in rb_insert_color() only when necessary Michel Lespinasse
2012-08-31  8:01   ` Adrian Hunter [this message]
2012-08-31  8:07     ` Michel Lespinasse
2012-08-31  8:15       ` Andrew Morton
2012-08-31  8:35         ` Adrian Hunter
2012-08-31  8:39           ` Michel Lespinasse
2012-09-06 20:47             ` Olof Johansson
2012-08-31  9:25           ` Alexander Shishkin
2012-09-08  1:26           ` Arnaldo Carvalho de Melo
2012-09-08 11:49     ` [tip:perf/core] perf tools: Fix build for another rbtree.c change tip-bot for Adrian Hunter
2012-07-13  0:31 ` [PATCH v2 08/12] rbtree: low level optimizations in rb_insert_color() Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 09/12] rbtree: adjust node color in __rb_erase_color() only when necessary Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 10/12] rbtree: optimize case selection logic in __rb_erase_color() Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 11/12] rbtree: low level optimizations " Michel Lespinasse
2012-07-13  0:31 ` [PATCH v2 12/12] rbtree: coding style adjustments Michel Lespinasse

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=50406F60.5040707@intel.com \
    --to=adrian.hunter@intel.com \
    --cc=acme@redhat.com \
    --cc=akpm@linux-foundation.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=walken@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).