1 files changed, 173 insertions, 36 deletions

diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 8d32d85a5234..61b6c48871a0 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -193,24 +193,55 @@ Example:
 Support for Augmented rbtrees
 -----------------------------
 
-Augmented rbtree is an rbtree with "some" additional data stored in each node.
-This data can be used to augment some new functionality to rbtree.
-Augmented rbtree is an optional feature built on top of basic rbtree
-infrastructure. An rbtree user who wants this feature will have to call the
-augmentation functions with the user provided augmentation callback
-when inserting and erasing nodes.
-
-On insertion, the user must call rb_augment_insert() once the new node is in
-place. This will cause the augmentation function callback to be called for
-each node between the new node and the root which has been affected by the
-insertion.
-
-When erasing a node, the user must call rb_augment_erase_begin() first to
-retrieve the deepest node on the rebalance path. Then, after erasing the
-original node, the user must call rb_augment_erase_end() with the deepest
-node found earlier. This will cause the augmentation function to be called
-for each affected node between the deepest node and the root.
-
+Augmented rbtree is an rbtree with "some" additional data stored in
+each node, where the additional data for node N must be a function of
+the contents of all nodes in the subtree rooted at N. This data can
+be used to augment some new functionality to rbtree. Augmented rbtree
+is an optional feature built on top of basic rbtree infrastructure.
+An rbtree user who wants this feature will have to call the augmentation
+functions with the user provided augmentation callback when inserting
+and erasing nodes.
+
+C files implementing augmented rbtree manipulation must include
+<linux/rbtree_augmented.h> instead of <linus/rbtree.h>. Note that
+linux/rbtree_augmented.h exposes some rbtree implementations details
+you are not expected to rely on; please stick to the documented APIs
+there and do not include <linux/rbtree_augmented.h> from header files
+either so as to minimize chances of your users accidentally relying on
+such implementation details.
+
+On insertion, the user must update the augmented information on the path
+leading to the inserted node, then call rb_link_node() as usual and
+rb_augment_inserted() instead of the usual rb_insert_color() call.
+If rb_augment_inserted() rebalances the rbtree, it will callback into
+a user provided function to update the augmented information on the
+affected subtrees.
+
+When erasing a node, the user must call rb_erase_augmented() instead of
+rb_erase(). rb_erase_augmented() calls back into user provided functions
+to updated the augmented information on affected subtrees.
+
+In both cases, the callbacks are provided through struct rb_augment_callbacks.
+3 callbacks must be defined:
+
+- A propagation callback, which updates the augmented value for a given
+  node and its ancestors, up to a given stop point (or NULL to update
+  all the way to the root).
+
+- A copy callback, which copies the augmented value for a given subtree
+  to a newly assigned subtree root.
+
+- A tree rotation callback, which copies the augmented value for a given
+  subtree to a newly assigned subtree root AND recomputes the augmented
+  information for the former subtree root.
+
+The compiled code for rb_erase_augmented() may inline the propagation and
+copy callbacks, which results in a large function, so each augmented rbtree
+user should have a single rb_erase_augmented() call site in order to limit
+compiled code size.
+
+
+Sample usage:
 
 Interval tree is an example of augmented rb tree. Reference -
 "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein.
@@ -230,26 +261,132 @@ and its immediate children. And this will be used in O(log n) lookup
 for lowest match (lowest start address among all possible matches)
 with something like:
 
-find_lowest_match(lo, hi, node)
+struct interval_tree_node *
+interval_tree_first_match(struct rb_root *root,
+                          unsigned long start, unsigned long last)
 {
-        lowest_match = NULL;
-        while (node) {
-                if (max_hi(node->left) > lo) {
-                        // Lowest overlap if any must be on left side
-                        node = node->left;
-                } else if (overlap(lo, hi, node)) {
-                        lowest_match = node;
-                        break;
-                } else if (lo > node->lo) {
-                        // Lowest overlap if any must be on right side
-                        node = node->right;
-                } else {
-                        break;
+        struct interval_tree_node *node;
+
+        if (!root->rb_node)
+                return NULL;
+        node = rb_entry(root->rb_node, struct interval_tree_node, rb);
+
+        while (true) {
+                if (node->rb.rb_left) {
+                        struct interval_tree_node *left =
+                                rb_entry(node->rb.rb_left,
+                                         struct interval_tree_node, rb);
+                        if (left->__subtree_last >= start) {
+                                /*
+                                 * Some nodes in left subtree satisfy Cond2.
+                                 * Iterate to find the leftmost such node N.
+                                 * If it also satisfies Cond1, that's the match
+                                 * we are looking for. Otherwise, there is no
+                                 * matching interval as nodes to the right of N
+                                 * can't satisfy Cond1 either.
+                                 */
+                                node = left;
+                                continue;
+                        }
                 }
+                if (node->start <= last) {              /* Cond1 */
+                        if (node->last >= start)        /* Cond2 */
+                                return node;    /* node is leftmost match */
+                        if (node->rb.rb_right) {
+                                node = rb_entry(node->rb.rb_right,
+                                        struct interval_tree_node, rb);
+                                if (node->__subtree_last >= start)
+                                        continue;
+                        }
+                }
+                return NULL;    /* No match */
+        }
+}
+
+Insertion/removal are defined using the following augmented callbacks:
+
+static inline unsigned long
+compute_subtree_last(struct interval_tree_node *node)
+{
+        unsigned long max = node->last, subtree_last;
+        if (node->rb.rb_left) {
+                subtree_last = rb_entry(node->rb.rb_left,
+                        struct interval_tree_node, rb)->__subtree_last;
+                if (max < subtree_last)
+                        max = subtree_last;
+        }
+        if (node->rb.rb_right) {
+                subtree_last = rb_entry(node->rb.rb_right,
+                        struct interval_tree_node, rb)->__subtree_last;
+                if (max < subtree_last)
+                        max = subtree_last;
+        }
+        return max;
+}
+
+static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
+{
+        while (rb != stop) {
+                struct interval_tree_node *node =
+                        rb_entry(rb, struct interval_tree_node, rb);
+                unsigned long subtree_last = compute_subtree_last(node);
+                if (node->__subtree_last == subtree_last)
+                        break;
+                node->__subtree_last = subtree_last;
+                rb = rb_parent(&node->rb);
         }
-        return lowest_match;
 }
 
-Finding exact match will be to first find lowest match and then to follow
-successor nodes looking for exact match, until the start of a node is beyond
-the hi value we are looking for.
+static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+        struct interval_tree_node *old =
+                rb_entry(rb_old, struct interval_tree_node, rb);
+        struct interval_tree_node *new =
+                rb_entry(rb_new, struct interval_tree_node, rb);
+
+        new->__subtree_last = old->__subtree_last;
+}
+
+static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+        struct interval_tree_node *old =
+                rb_entry(rb_old, struct interval_tree_node, rb);
+        struct interval_tree_node *new =
+                rb_entry(rb_new, struct interval_tree_node, rb);
+
+        new->__subtree_last = old->__subtree_last;
+        old->__subtree_last = compute_subtree_last(old);
+}
+
+static const struct rb_augment_callbacks augment_callbacks = {
+        augment_propagate, augment_copy, augment_rotate
+};
+
+void interval_tree_insert(struct interval_tree_node *node,
+                          struct rb_root *root)
+{
+        struct rb_node **link = &root->rb_node, *rb_parent = NULL;
+        unsigned long start = node->start, last = node->last;
+        struct interval_tree_node *parent;
+
+        while (*link) {
+                rb_parent = *link;
+                parent = rb_entry(rb_parent, struct interval_tree_node, rb);
+                if (parent->__subtree_last < last)
+                        parent->__subtree_last = last;
+                if (start < parent->start)
+                        link = &parent->rb.rb_left;
+                else
+                        link = &parent->rb.rb_right;
+        }
+
+        node->__subtree_last = last;
+        rb_link_node(&node->rb, rb_parent, link);
+        rb_insert_augmented(&node->rb, root, &augment_callbacks);
+}
+
+void interval_tree_remove(struct interval_tree_node *node,
+                          struct rb_root *root)
+{
+        rb_erase_augmented(&node->rb, root, &augment_callbacks);
+}