diff options
Diffstat (limited to 'lib/rbtree.c')
-rw-r--r-- | lib/rbtree.c | 48 |
1 files changed, 7 insertions, 41 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index 1ef6e25d031c..5114eda6309c 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -13,7 +13,7 @@ #include <linux/export.h> /* - * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree + * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree * * 1) A node is either red or black * 2) The root is black @@ -58,7 +58,7 @@ static inline void rb_set_black(struct rb_node *rb) { - rb->__rb_parent_color |= RB_BLACK; + rb->__rb_parent_color += RB_BLACK; } static inline struct rb_node *rb_red_parent(struct rb_node *red) @@ -83,14 +83,10 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, static __always_inline void __rb_insert(struct rb_node *node, struct rb_root *root, - bool newleft, struct rb_node **leftmost, void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; - if (newleft) - *leftmost = node; - while (true) { /* * Loop invariant: node is red. @@ -437,38 +433,19 @@ static const struct rb_augment_callbacks dummy_callbacks = { void rb_insert_color(struct rb_node *node, struct rb_root *root) { - __rb_insert(node, root, false, NULL, dummy_rotate); + __rb_insert(node, root, dummy_rotate); } EXPORT_SYMBOL(rb_insert_color); void rb_erase(struct rb_node *node, struct rb_root *root) { struct rb_node *rebalance; - rebalance = __rb_erase_augmented(node, root, - NULL, &dummy_callbacks); + rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); if (rebalance) ____rb_erase_color(rebalance, root, dummy_rotate); } EXPORT_SYMBOL(rb_erase); -void rb_insert_color_cached(struct rb_node *node, - struct rb_root_cached *root, bool leftmost) -{ - __rb_insert(node, &root->rb_root, leftmost, - &root->rb_leftmost, dummy_rotate); -} -EXPORT_SYMBOL(rb_insert_color_cached); - -void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) -{ - struct rb_node *rebalance; - rebalance = __rb_erase_augmented(node, &root->rb_root, - &root->rb_leftmost, &dummy_callbacks); - if (rebalance) - ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate); -} -EXPORT_SYMBOL(rb_erase_cached); - /* * Augmented rbtree manipulation functions. * @@ -477,10 +454,9 @@ EXPORT_SYMBOL(rb_erase_cached); */ void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, - bool newleft, struct rb_node **leftmost, void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { - __rb_insert(node, root, newleft, leftmost, augment_rotate); + __rb_insert(node, root, augment_rotate); } EXPORT_SYMBOL(__rb_insert_augmented); @@ -527,7 +503,7 @@ struct rb_node *rb_next(const struct rb_node *node) if (node->rb_right) { node = node->rb_right; while (node->rb_left) - node=node->rb_left; + node = node->rb_left; return (struct rb_node *)node; } @@ -559,7 +535,7 @@ struct rb_node *rb_prev(const struct rb_node *node) if (node->rb_left) { node = node->rb_left; while (node->rb_right) - node=node->rb_right; + node = node->rb_right; return (struct rb_node *)node; } @@ -591,16 +567,6 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, } EXPORT_SYMBOL(rb_replace_node); -void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, - struct rb_root_cached *root) -{ - rb_replace_node(victim, new, &root->rb_root); - - if (root->rb_leftmost == victim) - root->rb_leftmost = new; -} -EXPORT_SYMBOL(rb_replace_node_cached); - void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { |