From 1975e59375756da4ff4e6e7d12f67485e813ace0 Mon Sep 17 00:00:00 2001 From: David Woodhouse Date: Fri, 21 Apr 2006 13:30:36 +0100 Subject: [RBTREE] Remove dead code in rb_erase() Observe rb_erase(), when the victim node 'old' has two children so neither of the simple cases at the beginning are taken. Observe that it effectively does an 'rb_next()' operation to find the next (by value) node in the tree. That is; we go to the victim's right-hand child and then follow left-hand pointers all the way down the tree as far as we can until we find the next node 'node'. We end up with 'node' being either the same immediate right-hand child of 'old', or one of its descendants on the far left-hand side. For a start, we _know_ that 'node' has a parent. We can drop that check. We also know that if 'node's parent is 'old', then 'node' is the right-hand child of its parent. And that if 'node's parent is _not_ 'old', then 'node' is the left-hand child of its parent. So instead of checking for 'node->rb_parent == old' in one place and also checking 'node's heritage separately when we're trying to change its link from its parent, we can shuffle things around a bit and do it like this... Signed-off-by: David Woodhouse --- lib/rbtree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 14b791ac5089..63473e04f18a 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -243,18 +243,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root) if (child) child->rb_parent = parent; - if (parent) - { - if (parent->rb_left == node) - parent->rb_left = child; - else - parent->rb_right = child; - } - else - root->rb_node = child; - if (node->rb_parent == old) + if (node->rb_parent == old) { + parent->rb_right = child; parent = node; + } else + parent->rb_left = child; + node->rb_parent = old->rb_parent; node->rb_color = old->rb_color; node->rb_right = old->rb_right; -- cgit v1.2.3 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 'lib') 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 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 'lib') 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