summaryrefslogtreecommitdiffstats
path: root/lib/rbtree.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:31:07 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:36 +0900
commit7abc704ae399fcb9c51ca200b0456f8a975a8011 (patch)
tree3180bbf50ef3d25f0647362ecc7e7925f884d738 /lib/rbtree.c
parent28d7530928d01638678f63c3c70113540b0e6abe (diff)
downloadlinux-7abc704ae399fcb9c51ca200b0456f8a975a8011.tar.gz
linux-7abc704ae399fcb9c51ca200b0456f8a975a8011.tar.bz2
linux-7abc704ae399fcb9c51ca200b0456f8a975a8011.zip
rbtree: add __rb_change_child() helper function
Add __rb_change_child() as an inline helper function to replace code that would otherwise be duplicated 4 times in the source. No changes to binary size or speed. Signed-off-by: Michel Lespinasse <walken@google.com> Reviewed-by: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/rbtree.c')
-rw-r--r--lib/rbtree.c46
1 files changed, 17 insertions, 29 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 61cdd0e3e538..de89a614b1ba 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -66,6 +66,19 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
return (struct rb_node *)red->__rb_parent_color;
}
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+ struct rb_node *parent, struct rb_root *root)
+{
+ if (parent) {
+ if (parent->rb_left == old)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else
+ root->rb_node = new;
+}
+
/*
* Helper function for rotations:
* - old's parent and color get assigned to new
@@ -78,13 +91,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
struct rb_node *parent = rb_parent(old);
new->__rb_parent_color = old->__rb_parent_color;
rb_set_parent_color(old, new, color);
- if (parent) {
- if (parent->rb_left == old)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else
- root->rb_node = new;
+ __rb_change_child(old, new, parent, root);
}
void rb_insert_color(struct rb_node *node, struct rb_root *root)
@@ -375,13 +382,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
while ((left = node->rb_left) != NULL)
node = left;
- if (rb_parent(old)) {
- if (rb_parent(old)->rb_left == old)
- rb_parent(old)->rb_left = node;
- else
- rb_parent(old)->rb_right = node;
- } else
- root->rb_node = node;
+ __rb_change_child(old, node, rb_parent(old), root);
child = node->rb_right;
parent = rb_parent(node);
@@ -410,13 +411,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
if (child)
rb_set_parent(child, parent);
- if (parent) {
- if (parent->rb_left == node)
- parent->rb_left = child;
- else
- parent->rb_right = child;
- } else
- root->rb_node = child;
+ __rb_change_child(node, child, parent, root);
color:
if (color == RB_BLACK)
@@ -591,14 +586,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_node *parent = rb_parent(victim);
/* Set the surrounding nodes to point to the replacement */
- if (parent) {
- if (victim == parent->rb_left)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else {
- root->rb_node = new;
- }
+ __rb_change_child(victim, new, parent, root);
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)