From: "Michal Nazarewicz" <mina86@mina86.com>
To: aarcange@redhat.com, dwmw2@infradead.org, riel@redhat.com,
peterz@infradead.org, daniel.santos@pobox.com, axboe@kernel.dk,
ebiederm@xmission.com, Michel Lespinasse <walken@google.com>
Cc: linux-mm@kvack.org, akpm@linux-foundation.org,
linux-kernel@vger.kernel.org, torvalds@linux-foundation.org
Subject: Re: [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c
Date: Tue, 10 Jul 2012 14:19:20 +0200 [thread overview]
Message-ID: <op.wg8ciikk3l0zgt@mpn-glaptop> (raw)
In-Reply-To: <1341876923-12469-5-git-send-email-walken@google.com>
On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse <walken@google.com> wrote:
> rbtree users must use the documented APIs to manipulate the tree
> structure. Low-level helpers to manipulate node colors and parenthood
> are not part of that API, so move them to lib/rbtree.c
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
> ---
> include/linux/rbtree.h | 16 ----------------
> lib/rbtree.c | 18 ++++++++++++++++++
> 2 files changed, 18 insertions(+), 16 deletions(-)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 2049087..a06c044 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -35,8 +35,6 @@
> struct rb_node
> {
> unsigned long rb_parent_color;
> -#define RB_RED 0
> -#define RB_BLACK 1
> struct rb_node *rb_right;
> struct rb_node *rb_left;
> } __attribute__((aligned(sizeof(long))));
> @@ -49,20 +47,6 @@ struct rb_root
> #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
> -#define rb_color(r) ((r)->rb_parent_color & 1)
> -#define rb_is_red(r) (!rb_color(r))
> -#define rb_is_black(r) rb_color(r)
> -#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
> -#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
> -
> -static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> -{
> - rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> -}
> -static inline void rb_set_color(struct rb_node *rb, int color)
> -{
> - rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> -}
> #define RB_ROOT (struct rb_root) { NULL, }
> #define rb_entry(ptr, type, member) container_of(ptr, type, member)
> diff --git a/lib/rbtree.c b/lib/rbtree.c
> index fe43c8c..d0ec339 100644
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -23,6 +23,24 @@
> #include <linux/rbtree.h>
> #include <linux/export.h>
>+#define RB_RED 0
> +#define RB_BLACK 1
Interestingly, those are almost never used. RB_BLACK is used only once.
Should we get rid of those instead? Or change the code (like rb_is_red())
to use them?
> +
> +#define rb_color(r) ((r)->rb_parent_color & 1)
> +#define rb_is_red(r) (!rb_color(r))
> +#define rb_is_black(r) rb_color(r)
> +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
> +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
> +
> +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> +{
> + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> +}
> +static inline void rb_set_color(struct rb_node *rb, int color)
> +{
> + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> +}
> +
> static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
> {
> struct rb_node *right = node->rb_right;
--
Best regards, _ _
.o. | Liege of Serenely Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michał “mina86” Nazarewicz (o o)
ooo +----<email/xmpp: mpn@google.com>--------------ooO--(_)--Ooo--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2012-07-10 12:19 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-07-09 23:35 [PATCH 00/13] rbtree updates Michel Lespinasse
2012-07-09 23:35 ` [PATCH 01/13] rbtree: reference Documentation/rbtree.txt for usage instructions Michel Lespinasse
2012-07-10 1:45 ` Rik van Riel
2012-07-09 23:35 ` [PATCH 02/13] rbtree: empty nodes have no color Michel Lespinasse
2012-07-10 10:59 ` Daniel Santos
2012-07-10 23:10 ` Michel Lespinasse
2012-07-09 23:35 ` [PATCH 03/13] rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c Michel Lespinasse
2012-07-09 23:35 ` [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c Michel Lespinasse
2012-07-10 12:19 ` Michal Nazarewicz [this message]
2012-07-10 23:12 ` Michel Lespinasse
2012-07-11 15:48 ` Michal Nazarewicz
2012-07-09 23:35 ` [PATCH 05/13] rbtree: performance and correctness test Michel Lespinasse
2012-07-10 12:27 ` Michal Nazarewicz
2012-07-10 23:18 ` Michel Lespinasse
2012-07-11 6:14 ` Michel Lespinasse
2012-07-11 19:30 ` Daniel Santos
2012-07-09 23:35 ` [PATCH 06/13] rbtree: break out of rb_insert_color loop after tree rotation Michel Lespinasse
2012-07-09 23:35 ` [PATCH 07/13] rbtree: adjust root color in rb_insert_color() only when necessary Michel Lespinasse
2012-07-09 23:35 ` [PATCH 08/13] rbtree: optimize tree rotations in rb_insert_color() Michel Lespinasse
2012-07-09 23:35 ` [PATCH 09/13] rbtree: optimize color flips and parent fetching " Michel Lespinasse
2012-07-09 23:35 ` [PATCH 10/13] rbtree: adjust node color in __rb_erase_color() only when necessary Michel Lespinasse
2012-07-09 23:35 ` [PATCH 11/13] rbtree: optimize case selection logic in __rb_erase_color() Michel Lespinasse
2012-07-09 23:35 ` [PATCH 12/13] rbtree: optimize tree rotations " Michel Lespinasse
2012-07-09 23:35 ` [PATCH 13/13] rbtree: optimize color flips " Michel Lespinasse
2012-07-11 13:23 ` [PATCH 00/13] rbtree updates Peter Zijlstra
2012-07-12 1:12 ` Michel Lespinasse
2012-07-12 14:09 ` Peter Zijlstra
2012-07-12 14:12 ` Peter Zijlstra
2012-07-13 0:39 ` 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=op.wg8ciikk3l0zgt@mpn-glaptop \
--to=mina86@mina86.com \
--cc=aarcange@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=axboe@kernel.dk \
--cc=daniel.santos@pobox.com \
--cc=dwmw2@infradead.org \
--cc=ebiederm@xmission.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=peterz@infradead.org \
--cc=riel@redhat.com \
--cc=torvalds@linux-foundation.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