Merge branch 'fix/asoc' into for-linus

[pandora-kernel.git] / lib / rbtree.c

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 15e10b1..4693f79 100644 (file)
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -44,11 +44,6 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
        else
                root->rb_node = right;
        rb_set_parent(node, right);
-
-       if (root->augment_cb) {
-               root->augment_cb(node);
-               root->augment_cb(right);
-       }
 }
 
 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
@@ -72,20 +67,12 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
        else
                root->rb_node = left;
        rb_set_parent(node, left);
-
-       if (root->augment_cb) {
-               root->augment_cb(node);
-               root->augment_cb(left);
-       }
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *parent, *gparent;
 
-       if (root->augment_cb)
-               root->augment_cb(node);
-
        while ((parent = rb_parent(node)) && rb_is_red(parent))
        {
                gparent = rb_parent(parent);
@@ -240,15 +227,12 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
        else
        {
                struct rb_node *old = node, *left;
-               int old_parent_cb = 0;
-               int successor_parent_cb = 0;
 
                node = node->rb_right;
                while ((left = node->rb_left) != NULL)
                        node = left;
 
                if (rb_parent(old)) {
-                       old_parent_cb = 1;
                        if (rb_parent(old)->rb_left == old)
                                rb_parent(old)->rb_left = node;
                        else
@@ -263,10 +247,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                if (parent == old) {
                        parent = node;
                } else {
-                       successor_parent_cb = 1;
                        if (child)
                                rb_set_parent(child, parent);
-
                        parent->rb_left = child;
 
                        node->rb_right = old->rb_right;
@@ -277,24 +259,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                node->rb_left = old->rb_left;
                rb_set_parent(old->rb_left, node);
 
-               if (root->augment_cb) {
-                       /*
-                        * Here, three different nodes can have new children.
-                        * The parent of the successor node that was selected
-                        * to replace the node to be erased.
-                        * The node that is getting erased and is now replaced
-                        * by its successor.
-                        * The parent of the node getting erased-replaced.
-                        */
-                       if (successor_parent_cb)
-                               root->augment_cb(parent);
-
-                       root->augment_cb(node);
-
-                       if (old_parent_cb)
-                               root->augment_cb(rb_parent(old));
-               }
-
                goto color;
        }
 
@@ -303,19 +267,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
        if (child)
                rb_set_parent(child, parent);
-
-       if (parent) {
+       if (parent)
+       {
                if (parent->rb_left == node)
                        parent->rb_left = child;
                else
                        parent->rb_right = child;
-
-               if (root->augment_cb)
-                       root->augment_cb(parent);
-
-       } else {
-               root->rb_node = child;
        }
+       else
+               root->rb_node = child;
 
  color:
        if (color == RB_BLACK)
@@ -323,6 +283,74 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 }
 EXPORT_SYMBOL(rb_erase);
 
+static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
+{
+       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;
+}
+
+/*
+ * 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)
+{
+       if (node->rb_left)
+               node = node->rb_left;
+       else if (node->rb_right)
+               node = node->rb_right;
+
+       rb_augment_path(node, func, data);
+}
+
+/*
+ * before removing the node, find the deepest node on the rebalance path
+ * that will still be there after @node gets removed
+ */
+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;
+}
+
+/*
+ * 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)
+{
+       if (node)
+               rb_augment_path(node, func, data);
+}
+
 /*
  * This function returns the first node (in sort order) of the tree.
  */