Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
-
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
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_color(r) ((r)->__rb_parent_color & 1)
-#define rb_is_red(r) (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-
-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)
+static inline void rb_set_black(struct rb_node *rb)
{
- rb->__rb_parent_color = (unsigned long)p | color;
+ rb->__rb_parent_color |= RB_BLACK;
}
static inline struct rb_node *rb_red_parent(struct rb_node *red)
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)
+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;
gparent = rb_red_parent(parent);
- if (parent == gparent->rb_left) {
- tmp = gparent->rb_right;
+ tmp = gparent->rb_right;
+ if (parent != tmp) { /* parent == gparent->rb_left */
if (tmp && rb_is_red(tmp)) {
/*
* Case 1 - color flips
continue;
}
- if (parent->rb_right == node) {
+ tmp = parent->rb_right;
+ if (node == tmp) {
/*
* Case 2 - left rotate at parent
*
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;
}
/*
* / \
* n U
*/
- gparent->rb_left = tmp = parent->rb_right;
+ gparent->rb_left = tmp; /* == parent->rb_right */
parent->rb_right = gparent;
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;
continue;
}
- if (parent->rb_left == node) {
+ tmp = parent->rb_left;
+ if (node == tmp) {
/* Case 2 - right rotate at parent */
parent->rb_left = tmp = node->rb_right;
node->rb_right = parent;
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;
}
/* Case 3 - left rotate at gparent */
- gparent->rb_right = tmp = parent->rb_left;
+ gparent->rb_right = tmp; /* == parent->rb_left */
parent->rb_left = gparent;
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 *node, 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 *sibling, *tmp1, *tmp2;
+ struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
while (true) {
/*
- * Loop invariant: all leaf paths going through node have a
- * black node count that is 1 lower than other leaf paths.
- *
- * If node is red, we can flip it to black to adjust.
- * If node is the root, all leaf paths go through it.
- * Otherwise, we need to adjust the tree through color flips
- * and tree rotations as per one of the 4 cases below.
+ * Loop invariants:
+ * - node is black (or NULL on first iteration)
+ * - node is not the root (parent is not NULL)
+ * - All leaf paths going through parent and node have a
+ * black node count that is 1 lower than other leaf paths.
*/
- if (node && rb_is_red(node)) {
- rb_set_parent_color(node, parent, RB_BLACK);
- break;
- } else if (!parent) {
- break;
- } else if (parent->rb_left == node) {
- sibling = parent->rb_right;
+ sibling = parent->rb_right;
+ if (node != sibling) { /* node == parent->rb_left */
if (rb_is_red(sibling)) {
/*
* Case 1 - left rotate at parent
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;
* / \ / \
* Sl Sr Sl Sr
*
- * This leaves us violating 5), so
- * recurse at p. If p is red, the
- * recursion will just flip it to black
- * and exit. If coming from Case 1,
- * p is known to be red.
+ * This leaves us violating 5) which
+ * can be fixed by flipping p to black
+ * if it was red, or by recursing at p.
+ * p is red when coming from Case 1.
*/
rb_set_parent_color(sibling, parent,
RB_RED);
- node = parent;
- parent = rb_parent(node);
- continue;
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
}
/*
* Case 3 - right rotate at sibling
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;
/* Case 2 - sibling color flip */
rb_set_parent_color(sibling, parent,
RB_RED);
- node = parent;
- parent = rb_parent(node);
- continue;
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
}
/* Case 3 - right rotate at sibling */
sibling->rb_right = tmp1 = tmp2->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, *parent;
- int color;
-
- if (!node->rb_left)
- child = node->rb_right;
- else if (!node->rb_right)
- child = node->rb_left;
- else
- {
- struct rb_node *old = node, *left;
-
- node = node->rb_right;
- 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;
-
- child = node->rb_right;
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (parent == old) {
- parent = node;
- } else {
- if (child)
- rb_set_parent(child, parent);
- parent->rb_left = child;
-
- node->rb_right = old->rb_right;
- rb_set_parent(old->rb_right, node);
- }
-
- node->__rb_parent_color = old->__rb_parent_color;
- node->rb_left = old->rb_left;
- rb_set_parent(old->rb_left, node);
-
- goto color;
- }
+/*
+ * 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.
+ */
- parent = rb_parent(node);
- color = rb_color(node);
-
- 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;
+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) {}
- color:
- if (color == RB_BLACK)
- __rb_erase_color(child, parent, 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.
if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a right-hand child, go down and then left as far
- as we can. */
+ /*
+ * If we have a right-hand child, go down and then left as far
+ * as we can.
+ */
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
return (struct rb_node *)node;
}
- /* No right-hand children. Everything down and left is
- smaller than us, so any 'next' node must be in the general
- direction of our parent. Go up the tree; any time the
- 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. */
+ /*
+ * No right-hand children. Everything down and left is smaller than us,
+ * so any 'next' node must be in the general direction of our parent.
+ * Go up the tree; any time the 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 ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a left-hand child, go down and then right as far
- as we can. */
+ /*
+ * If we have a left-hand child, go down and then right as far
+ * as we can.
+ */
if (node->rb_left) {
node = node->rb_left;
while (node->rb_right)
return (struct rb_node *)node;
}
- /* No left-hand children. Go up till we find an ancestor which
- is a right-hand child of its parent */
+ /*
+ * No left-hand children. Go up till we find an ancestor which
+ * is a right-hand child of its parent.
+ */
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
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)
projects / firefly-linux-kernel-4.4.55.git / blobdiff