Merge branches 'gemini' and 'misc' into devel

1 files changed, 68 insertions, 0 deletions

diff --git a/lib/rbtree.c b/lib/rbtree.c
index e2aa3be29858..4693f79195d3 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -283,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.
  */