b=22181 interval_erase() fix

[fs/lustre-release.git] / lustre / ldlm / interval_tree.c

diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c
index 60dcbeb..0e2cac1 100644 (file)
--- a/lustre/ldlm/interval_tree.c
+++ b/lustre/ldlm/interval_tree.c
@@ -44,6 +44,7 @@
 # include <lustre_dlm.h>
 #else
 # include <liblustre.h>
+# include <libcfs/kp30.h>
 #endif
 #include <obd_support.h>
 #include <interval_tree.h>
@@ -101,7 +102,7 @@ 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, 
+static inline int extent_overlapped(struct interval_node_extent *e1,
                                     struct interval_node_extent *e2)
 {
         return (e1->start <= e2->end) && (e2->start <= e1->end);
@@ -195,7 +196,7 @@ enum interval_iter interval_iterate(struct interval_node *root,
         struct interval_node *node;
         enum interval_iter rc = INTERVAL_ITER_CONT;
         ENTRY;
-        
+
         interval_for_each(node, root) {
                 rc = func(node, data);
                 if (rc == INTERVAL_ITER_STOP)
@@ -213,7 +214,7 @@ enum interval_iter interval_iterate_reverse(struct interval_node *root,
         struct interval_node *node;
         enum interval_iter rc = INTERVAL_ITER_CONT;
         ENTRY;
-        
+
         interval_for_each_reverse(node, root) {
                 rc = func(node, data);
                 if (rc == INTERVAL_ITER_STOP)
@@ -322,10 +323,10 @@ static void __rotate_right(struct interval_node *node,
 } while (0)
 
 /*
- * Operations INSERT and DELETE, when run on a tree with n keys, 
- * take O(logN) time.Because they modify the tree, the result 
- * may violate the red-black properties.To restore these properties, 
- * we must change the colors of some of the nodes in the tree 
+ * Operations INSERT and DELETE, when run on a tree with n keys,
+ * take O(logN) time.Because they modify the tree, the result
+ * may violate the red-black properties.To restore these properties,
+ * we must change the colors of some of the nodes in the tree
  * and also change the pointer structure.
  */
 static void interval_insert_color(struct interval_node *node,
@@ -384,7 +385,6 @@ static void interval_insert_color(struct interval_node *node,
 
 struct interval_node *interval_insert(struct interval_node *node,
                                       struct interval_node **root)
-                     
 {
         struct interval_node **p, *parent = NULL;
         ENTRY;
@@ -402,7 +402,7 @@ struct interval_node *interval_insert(struct interval_node *node,
 
                 if (node_compare(node, parent) < 0)
                         p = &parent->in_left;
-                else 
+                else
                         p = &parent->in_right;
         }
 
@@ -499,8 +499,8 @@ static void interval_erase_color(struct interval_node *node,
         EXIT;
 }
 
-/* 
- * if the @max_high value of @node is changed, this function traverse  a path 
+/*
+ * if the @max_high value of @node is changed, this function traverse  a path
  * from node  up to the root to update max_high for the whole tree.
  */
 static void update_maxhigh(struct interval_node *node,
@@ -545,12 +545,10 @@ void interval_erase(struct interval_node *node,
 
                 if (child)
                         child->in_parent = parent;
-                if (parent == old) {
+                if (parent == old)
                         parent->in_right = child;
-                        parent = node;
-                } else {
+                else
                         parent->in_left = child;
-                }
 
                 node->in_color = old->in_color;
                 node->in_right = old->in_right;
@@ -569,8 +567,10 @@ void interval_erase(struct interval_node *node,
                 old->in_left->in_parent = node;
                 if (old->in_right)
                         old->in_right->in_parent = node;
-                update_maxhigh(child, node->in_max_high);
+                update_maxhigh(child ? : parent, node->in_max_high);
                 update_maxhigh(node, old->in_max_high);
+                if (parent == old)
+                         parent = node;
                 goto color;
         }
         parent = node->in_parent;
@@ -587,7 +587,7 @@ void interval_erase(struct interval_node *node,
                 *root = child;
         }
 
-        update_maxhigh(child, node->in_max_high);
+        update_maxhigh(child ? : parent, node->in_max_high);
 
 color:
         if (color == INTERVAL_BLACK)
@@ -656,13 +656,13 @@ enum interval_iter interval_search(struct interval_node *node,
                                 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 
+                                /* 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
@@ -701,7 +701,7 @@ EXPORT_SYMBOL(interval_is_overlapped);
  * some extents, because programs seldom do IO backward.
  *
  * The recursive algorithm of expanding low:
- * expand_low {
+ * interval_expand_low {
  *        struct interval_node *tmp;
  *        static __u64 res = 0;
  *
@@ -723,7 +723,7 @@ EXPORT_SYMBOL(interval_is_overlapped);
  *        return res;
  * }
  *
- * It's much easy to eliminate the recursion, see interval_search for 
+ * It's much easy to eliminate the recursion, see interval_search for
  * an example. -jay
  */
 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
@@ -741,7 +741,7 @@ static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
         while (node != NULL) {
                 if (node->in_max_high < high)
                         break;
-                        
+
                 if (interval_low(node) > high) {
                         result = interval_low(node) - 1;
                         node = node->in_left;