linux/lib/rbtree.c
*/
-#include <linux/rbtree.h>
+#include <linux/rbtree_augmented.h>
#include <linux/export.h>
/*
* parentheses and have some accompanying text comment.
*/
-#define RB_RED 0
-#define RB_BLACK 1
-
-#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
-
-#define __rb_color(pc) ((pc) & 1)
-#define __rb_is_black(pc) __rb_color(pc)
-#define __rb_is_red(pc) (!__rb_color(pc))
-#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
-#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
-#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
-
static inline void rb_set_black(struct rb_node *rb)
{
rb->__rb_parent_color |= RB_BLACK;
}
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
- rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
-}
-
-static inline void rb_set_parent_color(struct rb_node *rb,
- struct rb_node *p, int color)
-{
- rb->__rb_parent_color = (unsigned long)p | color;
-}
-
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
__rb_change_child(old, new, parent, root);
}
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+static __always_inline void
+__rb_insert(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
rb_set_parent_color(tmp, parent,
RB_BLACK);
rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
parent = node;
tmp = node->rb_right;
}
if (tmp)
rb_set_parent_color(tmp, gparent, RB_BLACK);
__rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
break;
} else {
tmp = gparent->rb_left;
rb_set_parent_color(tmp, parent,
RB_BLACK);
rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
parent = node;
tmp = node->rb_left;
}
if (tmp)
rb_set_parent_color(tmp, gparent, RB_BLACK);
__rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
break;
}
}
}
-EXPORT_SYMBOL(rb_insert_color);
-static void __rb_erase_color(struct rb_node *parent, struct rb_root *root)
+__always_inline void
+__rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
+ augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_right;
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
+ augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
+ augment_rotate(parent, sibling);
break;
} else {
sibling = parent->rb_left;
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
+ augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_left;
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
+ augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
+ augment_rotate(parent, sibling);
break;
}
}
}
+EXPORT_SYMBOL(__rb_erase_color);
-void rb_erase(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *child = node->rb_right, *tmp = node->rb_left;
- struct rb_node *parent, *rebalance;
- unsigned long pc;
-
- if (!tmp) {
- /*
- * Case 1: node to erase has no more than 1 child (easy!)
- *
- * Note that if there is one child it must be red due to 5)
- * and node must be black due to 4). We adjust colors locally
- * so as to bypass __rb_erase_color() later on.
- */
- pc = node->__rb_parent_color;
- parent = __rb_parent(pc);
- __rb_change_child(node, child, parent, root);
- if (child) {
- child->__rb_parent_color = pc;
- rebalance = NULL;
- } else
- rebalance = __rb_is_black(pc) ? parent : NULL;
- } else if (!child) {
- /* Still case 1, but this time the child is node->rb_left */
- tmp->__rb_parent_color = pc = node->__rb_parent_color;
- parent = __rb_parent(pc);
- __rb_change_child(node, tmp, parent, root);
- rebalance = NULL;
- } else {
- struct rb_node *successor = child, *child2;
- tmp = child->rb_left;
- if (!tmp) {
- /*
- * Case 2: node's successor is its right child
- *
- * (n) (s)
- * / \ / \
- * (x) (s) -> (x) (c)
- * \
- * (c)
- */
- parent = child;
- child2 = child->rb_right;
- } else {
- /*
- * Case 3: node's successor is leftmost under
- * node's right child subtree
- *
- * (n) (s)
- * / \ / \
- * (x) (y) -> (x) (y)
- * / /
- * (p) (p)
- * / /
- * (s) (c)
- * \
- * (c)
- */
- do {
- parent = successor;
- successor = tmp;
- tmp = tmp->rb_left;
- } while (tmp);
- parent->rb_left = child2 = successor->rb_right;
- successor->rb_right = child;
- rb_set_parent(child, successor);
- }
-
- successor->rb_left = tmp = node->rb_left;
- rb_set_parent(tmp, successor);
+/*
+ * Non-augmented rbtree manipulation functions.
+ *
+ * We use dummy augmented callbacks here, and have the compiler optimize them
+ * out of the rb_insert_color() and rb_erase() function definitions.
+ */
- pc = node->__rb_parent_color;
- tmp = __rb_parent(pc);
- __rb_change_child(node, successor, tmp, root);
- if (child2) {
- successor->__rb_parent_color = pc;
- rb_set_parent_color(child2, parent, RB_BLACK);
- rebalance = NULL;
- } else {
- unsigned long pc2 = successor->__rb_parent_color;
- successor->__rb_parent_color = pc;
- rebalance = __rb_is_black(pc2) ? parent : NULL;
- }
- }
+static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
+static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
+static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
- if (rebalance)
- __rb_erase_color(rebalance, root);
-}
-EXPORT_SYMBOL(rb_erase);
+static const struct rb_augment_callbacks dummy_callbacks = {
+ dummy_propagate, dummy_copy, dummy_rotate
+};
-static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
- struct rb_node *parent;
-
-up:
- func(node, data);
- parent = rb_parent(node);
- if (!parent)
- return;
-
- if (node == parent->rb_left && parent->rb_right)
- func(parent->rb_right, data);
- else if (parent->rb_left)
- func(parent->rb_left, data);
-
- node = parent;
- goto up;
+ __rb_insert(node, root, dummy_rotate);
}
+EXPORT_SYMBOL(rb_insert_color);
-/*
- * after inserting @node into the tree, update the tree to account for
- * both the new entry and any damage done by rebalance
- */
-void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
+void rb_erase(struct rb_node *node, struct rb_root *root)
{
- if (node->rb_left)
- node = node->rb_left;
- else if (node->rb_right)
- node = node->rb_right;
-
- rb_augment_path(node, func, data);
+ rb_erase_augmented(node, root, &dummy_callbacks);
}
-EXPORT_SYMBOL(rb_augment_insert);
+EXPORT_SYMBOL(rb_erase);
/*
- * before removing the node, find the deepest node on the rebalance path
- * that will still be there after @node gets removed
+ * Augmented rbtree manipulation functions.
+ *
+ * This instantiates the same __always_inline functions as in the non-augmented
+ * case, but this time with user-defined callbacks.
*/
-struct rb_node *rb_augment_erase_begin(struct rb_node *node)
-{
- struct rb_node *deepest;
-
- if (!node->rb_right && !node->rb_left)
- deepest = rb_parent(node);
- else if (!node->rb_right)
- deepest = node->rb_left;
- else if (!node->rb_left)
- deepest = node->rb_right;
- else {
- deepest = rb_next(node);
- if (deepest->rb_right)
- deepest = deepest->rb_right;
- else if (rb_parent(deepest) != node)
- deepest = rb_parent(deepest);
- }
- return deepest;
-}
-EXPORT_SYMBOL(rb_augment_erase_begin);
-
-/*
- * after removal, update the tree to account for the removed entry
- * and any rebalance damage.
- */
-void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
+void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- if (node)
- rb_augment_path(node, func, data);
+ __rb_insert(node, root, augment_rotate);
}
-EXPORT_SYMBOL(rb_augment_erase_end);
+EXPORT_SYMBOL(__rb_insert_augmented);
/*
* This function returns the first node (in sort order) of the tree.
projects / firefly-linux-kernel-4.4.55.git / blobdiff