From 7fe1e133bf45b0fe70491ed3d4c5b491feff7aa8 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Fri, 21 Apr 2006 13:12:44 +0100 Subject: [RBTREE] Add accessor macros for colour and parent fields of rb_node This is in preparation for merging those fields into a single 'unsigned long', because using a whole machine-word for a single bit of colour information is wasteful. Signed-off-by: David Woodhouse --- include/linux/rbtree.h | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'include') diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 4b7cc4fe366d..ffee81ce7b6f 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -107,6 +107,15 @@ struct rb_node struct rb_node *rb_left; }; +#define rb_parent(r) ((r)->rb_parent) +#define rb_set_parent(r,p) do { (r)->rb_parent = p; } while (0) +#define rb_colour(r) ((r)->rb_colour) +#define rb_is_red(r) ((r)->colour == RB_RED) +#define rb_is_black(r) ((r)->colour == RB_BLACK) +#define rb_set_red(r) do { (r)->colour = RB_RED; } while (0) +#define rb_set_black(r) do { (r)->colour = RB_BLACK; } while (0) +#define rb_set_colour(r,c) do { (r)->colour = (c); } while (0) + struct rb_root { struct rb_node *rb_node; -- cgit v1.2.2 From 55a981027fc393c86de2c4e7836c9515088a9a58 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Fri, 21 Apr 2006 13:35:51 +0100 Subject: [RBTREE] Merge colour and parent fields of struct rb_node. We only used a single bit for colour information, so having a whole machine word of space allocated for it was a bit wasteful. Instead, store it in the lowest bit of the 'parent' pointer, since that was always going to be aligned anyway. Signed-off-by: David Woodhouse --- include/linux/rbtree.h | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) (limited to 'include') diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index ffee81ce7b6f..748be50329d8 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -99,28 +99,35 @@ static inline struct page * rb_insert_page_cache(struct inode * inode, struct rb_node { - struct rb_node *rb_parent; - int rb_color; + unsigned long rb_parent_colour; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; }; -#define rb_parent(r) ((r)->rb_parent) -#define rb_set_parent(r,p) do { (r)->rb_parent = p; } while (0) -#define rb_colour(r) ((r)->rb_colour) -#define rb_is_red(r) ((r)->colour == RB_RED) -#define rb_is_black(r) ((r)->colour == RB_BLACK) -#define rb_set_red(r) do { (r)->colour = RB_RED; } while (0) -#define rb_set_black(r) do { (r)->colour = RB_BLACK; } while (0) -#define rb_set_colour(r,c) do { (r)->colour = (c); } while (0) - struct rb_root { struct rb_node *rb_node; }; + +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_colour & ~3)) +#define rb_colour(r) ((r)->rb_parent_colour & 1) +#define rb_is_red(r) (!rb_colour(r)) +#define rb_is_black(r) rb_colour(r) +#define rb_set_red(r) do { (r)->rb_parent_colour &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_colour |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p; +} +static inline void rb_set_colour(struct rb_node *rb, int colour) +{ + rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour; +} + #define RB_ROOT (struct rb_root) { NULL, } #define rb_entry(ptr, type, member) container_of(ptr, type, member) @@ -140,8 +147,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) { - node->rb_parent = parent; - node->rb_color = RB_RED; + node->rb_parent_colour = (unsigned long )parent; node->rb_left = node->rb_right = NULL; *rb_link = node; -- cgit v1.2.2 From e977145aeaad23d443686f2a2d5b32800d1607c5 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Fri, 21 Apr 2006 23:15:39 +0100 Subject: [RBTREE] Add explicit alignment to sizeof(long) for struct rb_node. Seems like a strange requirement, but allegedly it was necessary for struct address_space on CRIS, because it otherwise ended up being only byte-aligned. It's harmless enough, and easier to just do it than to prove it isn't necessary... although I really ought to dig out my etrax board and test it some time. Signed-off-by: David Woodhouse --- include/linux/rbtree.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'include') diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 748be50329d8..3cc30b0ab828 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -104,7 +104,8 @@ struct rb_node #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; -}; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ struct rb_root { -- cgit v1.2.2 From ed198cb49750fd9ec564e9f1df66c10efea605f1 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Sat, 22 Apr 2006 02:38:50 +0100 Subject: [RBTREE] Update hrtimers to use rb_parent() accessor macro. Also switch it to use the same method of using off-tree nodes as everyone else now does -- set them to point to themselves. Signed-off-by: David Woodhouse --- include/linux/hrtimer.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include') diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h index 306acf1dc6d5..7d2a1b974c5e 100644 --- a/include/linux/hrtimer.h +++ b/include/linux/hrtimer.h @@ -127,7 +127,7 @@ extern ktime_t hrtimer_get_next_event(void); static inline int hrtimer_active(const struct hrtimer *timer) { - return timer->node.rb_parent != HRTIMER_INACTIVE; + return rb_parent(&timer->node) != &timer->node; } /* Forward a hrtimer so it expires after now: */ -- cgit v1.2.2 From 2f3243aebd8df4d9eecaeca04bbff6c7dbfb2142 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Mon, 5 Jun 2006 20:19:05 +0100 Subject: [RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistency Since rb_insert_color() is part of the _public_ API, while the others are purely internal, switch to be consistent with that. Signed-off-by: David Woodhouse --- include/linux/rbtree.h | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'include') diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 3cc30b0ab828..f37006f21664 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -99,7 +99,7 @@ static inline struct page * rb_insert_page_cache(struct inode * inode, struct rb_node { - unsigned long rb_parent_colour; + unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; @@ -113,20 +113,20 @@ struct rb_root }; -#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_colour & ~3)) -#define rb_colour(r) ((r)->rb_parent_colour & 1) -#define rb_is_red(r) (!rb_colour(r)) -#define rb_is_black(r) rb_colour(r) -#define rb_set_red(r) do { (r)->rb_parent_colour &= ~1; } while (0) -#define rb_set_black(r) do { (r)->rb_parent_colour |= 1; } while (0) +#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_colour = (rb->rb_parent_colour & 3) | (unsigned long)p; + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; } -static inline void rb_set_colour(struct rb_node *rb, int colour) +static inline void rb_set_color(struct rb_node *rb, int color) { - rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour; + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; } #define RB_ROOT (struct rb_root) { NULL, } @@ -148,7 +148,7 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) { - node->rb_parent_colour = (unsigned long )parent; + node->rb_parent_color = (unsigned long )parent; node->rb_left = node->rb_right = NULL; *rb_link = node; -- cgit v1.2.2