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.3-59-g8ed1b 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 +++++---- lib/rbtree.c | 178 +++++++++++++++++++++++++------------------------ 2 files changed, 109 insertions(+), 101 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; diff --git a/lib/rbtree.c b/lib/rbtree.c index 63473e04f18a..4a7173cad149 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -26,60 +26,66 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { struct rb_node *right = node->rb_right; + struct rb_node *parent = rb_parent(node); if ((node->rb_right = right->rb_left)) - right->rb_left->rb_parent = node; + rb_set_parent(right->rb_left, node); right->rb_left = node; - if ((right->rb_parent = node->rb_parent)) + rb_set_parent(right, parent); + + if (parent) { - if (node == node->rb_parent->rb_left) - node->rb_parent->rb_left = right; + if (node == parent->rb_left) + parent->rb_left = right; else - node->rb_parent->rb_right = right; + parent->rb_right = right; } else root->rb_node = right; - node->rb_parent = right; + rb_set_parent(node, right); } static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) { struct rb_node *left = node->rb_left; + struct rb_node *parent = rb_parent(node); if ((node->rb_left = left->rb_right)) - left->rb_right->rb_parent = node; + rb_set_parent(left->rb_right, node); left->rb_right = node; - if ((left->rb_parent = node->rb_parent)) + rb_set_parent(left, parent); + + if (parent) { - if (node == node->rb_parent->rb_right) - node->rb_parent->rb_right = left; + if (node == parent->rb_right) + parent->rb_right = left; else - node->rb_parent->rb_left = left; + parent->rb_left = left; } else root->rb_node = left; - node->rb_parent = left; + rb_set_parent(node, left); } void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent, *gparent; - while ((parent = node->rb_parent) && parent->rb_color == RB_RED) + while ((parent = rb_parent(node)) && rb_is_red(parent)) { - gparent = parent->rb_parent; + gparent = rb_parent(parent); if (parent == gparent->rb_left) { { register struct rb_node *uncle = gparent->rb_right; - if (uncle && uncle->rb_color == RB_RED) + if (uncle && rb_is_red(uncle)) { - uncle->rb_color = RB_BLACK; - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); node = gparent; continue; } @@ -94,17 +100,17 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) node = tmp; } - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(parent); + rb_set_red(gparent); __rb_rotate_right(gparent, root); } else { { register struct rb_node *uncle = gparent->rb_left; - if (uncle && uncle->rb_color == RB_RED) + if (uncle && rb_is_red(uncle)) { - uncle->rb_color = RB_BLACK; - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); node = gparent; continue; } @@ -119,13 +125,13 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) node = tmp; } - parent->rb_color = RB_BLACK; - gparent->rb_color = RB_RED; + rb_set_black(parent); + rb_set_red(gparent); __rb_rotate_left(gparent, root); } } - root->rb_node->rb_color = RB_BLACK; + rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color); @@ -134,43 +140,40 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, { struct rb_node *other; - while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) + while ((!node || rb_is_black(node)) && node != root->rb_node) { if (parent->rb_left == node) { other = parent->rb_right; - if (other->rb_color == RB_RED) + if (rb_is_red(other)) { - other->rb_color = RB_BLACK; - parent->rb_color = RB_RED; + rb_set_black(other); + rb_set_red(parent); __rb_rotate_left(parent, root); other = parent->rb_right; } - if ((!other->rb_left || - other->rb_left->rb_color == RB_BLACK) - && (!other->rb_right || - other->rb_right->rb_color == RB_BLACK)) + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) { - other->rb_color = RB_RED; + rb_set_red(other); node = parent; - parent = node->rb_parent; + parent = rb_parent(node); } else { - if (!other->rb_right || - other->rb_right->rb_color == RB_BLACK) + if (!other->rb_right || rb_is_black(other->rb_right)) { - register struct rb_node *o_left; + struct rb_node *o_left; if ((o_left = other->rb_left)) - o_left->rb_color = RB_BLACK; - other->rb_color = RB_RED; + rb_set_black(o_left); + rb_set_red(other); __rb_rotate_right(other, root); other = parent->rb_right; } - other->rb_color = parent->rb_color; - parent->rb_color = RB_BLACK; + rb_set_colour(other, rb_colour(parent)); + rb_set_black(parent); if (other->rb_right) - other->rb_right->rb_color = RB_BLACK; + rb_set_black(other->rb_right); __rb_rotate_left(parent, root); node = root->rb_node; break; @@ -179,38 +182,35 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, else { other = parent->rb_left; - if (other->rb_color == RB_RED) + if (rb_is_red(other)) { - other->rb_color = RB_BLACK; - parent->rb_color = RB_RED; + rb_set_black(other); + rb_set_red(parent); __rb_rotate_right(parent, root); other = parent->rb_left; } - if ((!other->rb_left || - other->rb_left->rb_color == RB_BLACK) - && (!other->rb_right || - other->rb_right->rb_color == RB_BLACK)) + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) { - other->rb_color = RB_RED; + rb_set_red(other); node = parent; - parent = node->rb_parent; + parent = rb_parent(node); } else { - if (!other->rb_left || - other->rb_left->rb_color == RB_BLACK) + if (!other->rb_left || rb_is_black(other->rb_left)) { register struct rb_node *o_right; if ((o_right = other->rb_right)) - o_right->rb_color = RB_BLACK; - other->rb_color = RB_RED; + rb_set_black(o_right); + rb_set_red(other); __rb_rotate_left(other, root); other = parent->rb_left; } - other->rb_color = parent->rb_color; - parent->rb_color = RB_BLACK; + rb_set_colour(other, rb_colour(parent)); + rb_set_black(parent); if (other->rb_left) - other->rb_left->rb_color = RB_BLACK; + rb_set_black(other->rb_left); __rb_rotate_right(parent, root); node = root->rb_node; break; @@ -218,7 +218,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, } } if (node) - node->rb_color = RB_BLACK; + rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root) @@ -238,43 +238,41 @@ void rb_erase(struct rb_node *node, struct rb_root *root) while ((left = node->rb_left) != NULL) node = left; child = node->rb_right; - parent = node->rb_parent; - color = node->rb_color; + parent = rb_parent(node); + color = rb_colour(node); if (child) - child->rb_parent = parent; - - if (node->rb_parent == old) { + rb_set_parent(child, parent); + if (parent == old) { parent->rb_right = child; parent = node; - } else + } else parent->rb_left = child; - node->rb_parent = old->rb_parent; - node->rb_color = old->rb_color; + node->rb_parent_colour = old->rb_parent_colour; node->rb_right = old->rb_right; node->rb_left = old->rb_left; - if (old->rb_parent) + if (rb_parent(old)) { - if (old->rb_parent->rb_left == old) - old->rb_parent->rb_left = node; + if (rb_parent(old)->rb_left == old) + rb_parent(old)->rb_left = node; else - old->rb_parent->rb_right = node; + rb_parent(old)->rb_right = node; } else root->rb_node = node; - old->rb_left->rb_parent = node; + rb_set_parent(old->rb_left, node); if (old->rb_right) - old->rb_right->rb_parent = node; + rb_set_parent(old->rb_right, node); goto color; } - parent = node->rb_parent; - color = node->rb_color; + parent = rb_parent(node); + color = rb_colour(node); if (child) - child->rb_parent = parent; + rb_set_parent(child, parent); if (parent) { if (parent->rb_left == node) @@ -322,6 +320,8 @@ EXPORT_SYMBOL(rb_last); struct rb_node *rb_next(struct rb_node *node) { + struct rb_node *parent; + /* If we have a right-hand child, go down and then left as far as we can. */ if (node->rb_right) { @@ -337,15 +337,17 @@ struct rb_node *rb_next(struct rb_node *node) ancestor is a right-hand child of its parent, keep going up. First time it's a left-hand child of its parent, said parent is our 'next' node. */ - while (node->rb_parent && node == node->rb_parent->rb_right) - node = node->rb_parent; + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; - return node->rb_parent; + return parent; } EXPORT_SYMBOL(rb_next); struct rb_node *rb_prev(struct rb_node *node) { + struct rb_node *parent; + /* If we have a left-hand child, go down and then right as far as we can. */ if (node->rb_left) { @@ -357,17 +359,17 @@ struct rb_node *rb_prev(struct rb_node *node) /* No left-hand children. Go up till we find an ancestor which is a right-hand child of its parent */ - while (node->rb_parent && node == node->rb_parent->rb_left) - node = node->rb_parent; + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; - return node->rb_parent; + return parent; } EXPORT_SYMBOL(rb_prev); void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { - struct rb_node *parent = victim->rb_parent; + struct rb_node *parent = rb_parent(victim); /* Set the surrounding nodes to point to the replacement */ if (parent) { @@ -379,9 +381,9 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, root->rb_node = new; } if (victim->rb_left) - victim->rb_left->rb_parent = new; + rb_set_parent(victim->rb_left, new); if (victim->rb_right) - victim->rb_right->rb_parent = new; + rb_set_parent(victim->rb_right, new); /* Copy the pointers/colour from the victim to the replacement */ *new = *victim; -- cgit v1.2.3-59-g8ed1b 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.3-59-g8ed1b 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 +- kernel/hrtimer.c | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (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: */ diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c index d2a7296c8251..04ab27ddfd90 100644 --- a/kernel/hrtimer.c +++ b/kernel/hrtimer.c @@ -393,7 +393,7 @@ static void __remove_hrtimer(struct hrtimer *timer, struct hrtimer_base *base) if (base->first == &timer->node) base->first = rb_next(&timer->node); rb_erase(&timer->node, &base->active); - timer->node.rb_parent = HRTIMER_INACTIVE; + rb_set_parent(&timer->node, &timer->node); } /* @@ -578,7 +578,7 @@ void hrtimer_init(struct hrtimer *timer, clockid_t clock_id, clock_id = CLOCK_MONOTONIC; timer->base = &bases[clock_id]; - timer->node.rb_parent = HRTIMER_INACTIVE; + rb_set_parent(&timer->node, &timer->node); } /** -- cgit v1.2.3-59-g8ed1b 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 +++++++++++----------- lib/rbtree.c | 10 +++++----- 2 files changed, 16 insertions(+), 16 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; diff --git a/lib/rbtree.c b/lib/rbtree.c index 4a7173cad149..1e55ba1c2edf 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -170,7 +170,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, __rb_rotate_right(other, root); other = parent->rb_right; } - rb_set_colour(other, rb_colour(parent)); + rb_set_color(other, rb_color(parent)); rb_set_black(parent); if (other->rb_right) rb_set_black(other->rb_right); @@ -207,7 +207,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, __rb_rotate_left(other, root); other = parent->rb_left; } - rb_set_colour(other, rb_colour(parent)); + rb_set_color(other, rb_color(parent)); rb_set_black(parent); if (other->rb_left) rb_set_black(other->rb_left); @@ -239,7 +239,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node = left; child = node->rb_right; parent = rb_parent(node); - color = rb_colour(node); + color = rb_color(node); if (child) rb_set_parent(child, parent); @@ -249,7 +249,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) } else parent->rb_left = child; - node->rb_parent_colour = old->rb_parent_colour; + node->rb_parent_color = old->rb_parent_color; node->rb_right = old->rb_right; node->rb_left = old->rb_left; @@ -269,7 +269,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) } parent = rb_parent(node); - color = rb_colour(node); + color = rb_color(node); if (child) rb_set_parent(child, parent); -- cgit v1.2.3-59-g8ed1b