Merge tag 'v4.9-rc1' into patchwork

[karo-tx-linux.git] / drivers / staging / lustre / lustre / ldlm / interval_tree.c

diff --git a/drivers/staging/lustre/lustre/ldlm/interval_tree.c b/drivers/staging/lustre/lustre/ldlm/interval_tree.c
index f4a70ebddeaf689d9fdf5aabca64bc9d652fb81e..e134ecd21bb210ef181bed573589131c1865e267 100644 (file)
--- a/drivers/staging/lustre/lustre/ldlm/interval_tree.c
+++ b/drivers/staging/lustre/lustre/ldlm/interval_tree.c
@@ -90,6 +90,17 @@ static inline int extent_equal(struct interval_node_extent *e1,
        return (e1->start == e2->start) && (e1->end == e2->end);
 }
 
+static inline int extent_overlapped(struct interval_node_extent *e1,
+                                   struct interval_node_extent *e2)
+{
+       return (e1->start <= e2->end) && (e2->start <= e1->end);
+}
+
+static inline int node_equal(struct interval_node *n1, struct interval_node *n2)
+{
+       return extent_equal(&n1->in_extent, &n2->in_extent);
+}
+
 static inline __u64 max_u64(__u64 x, __u64 y)
 {
        return x > y ? x : y;
@@ -262,7 +273,7 @@ struct interval_node *interval_insert(struct interval_node *node,
        p = root;
        while (*p) {
                parent = *p;
-               if (extent_equal(&parent->in_extent, &node->in_extent))
+               if (node_equal(parent, node))
                        return parent;
 
                /* max_high field must be updated after each iteration */
@@ -463,3 +474,90 @@ color:
                interval_erase_color(child, parent, root);
 }
 EXPORT_SYMBOL(interval_erase);
+
+static inline int interval_may_overlap(struct interval_node *node,
+                                      struct interval_node_extent *ext)
+{
+       return (ext->start <= node->in_max_high &&
+               ext->end >= interval_low(node));
+}
+
+/*
+ * This function finds all intervals that overlap interval ext,
+ * and calls func to handle resulted intervals one by one.
+ * in lustre, this function will find all conflicting locks in
+ * the granted queue and add these locks to the ast work list.
+ *
+ * {
+ *     if (!node)
+ *             return 0;
+ *     if (ext->end < interval_low(node)) {
+ *             interval_search(node->in_left, ext, func, data);
+ *     } else if (interval_may_overlap(node, ext)) {
+ *             if (extent_overlapped(ext, &node->in_extent))
+ *                     func(node, data);
+ *             interval_search(node->in_left, ext, func, data);
+ *             interval_search(node->in_right, ext, func, data);
+ *     }
+ *     return 0;
+ * }
+ *
+ */
+enum interval_iter interval_search(struct interval_node *node,
+                                  struct interval_node_extent *ext,
+                                  interval_callback_t func,
+                                  void *data)
+{
+       enum interval_iter rc = INTERVAL_ITER_CONT;
+       struct interval_node *parent;
+
+       LASSERT(ext);
+       LASSERT(func);
+
+       while (node) {
+               if (ext->end < interval_low(node)) {
+                       if (node->in_left) {
+                               node = node->in_left;
+                               continue;
+                       }
+               } else if (interval_may_overlap(node, ext)) {
+                       if (extent_overlapped(ext, &node->in_extent)) {
+                               rc = func(node, data);
+                               if (rc == INTERVAL_ITER_STOP)
+                                       break;
+                       }
+
+                       if (node->in_left) {
+                               node = node->in_left;
+                               continue;
+                       }
+                       if (node->in_right) {
+                               node = node->in_right;
+                               continue;
+                       }
+               }
+
+               parent = node->in_parent;
+               while (parent) {
+                       if (node_is_left_child(node) &&
+                           parent->in_right) {
+                               /*
+                                * If we ever got the left, it means that the
+                                * parent met ext->end<interval_low(parent), or
+                                * may_overlap(parent). If the former is true,
+                                * we needn't go back. So stop early and check
+                                * may_overlap(parent) after this loop.
+                                */
+                               node = parent->in_right;
+                               break;
+                       }
+                       node = parent;
+                       parent = parent->in_parent;
+               }
+               if (!parent || !interval_may_overlap(parent, ext))
+                       break;
+       }
+
+       return rc;
+}
+EXPORT_SYMBOL(interval_search);