X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lustre%2Fldlm%2Finterval_tree.c;h=53c23d5c44086e2e8aaa226be9612b4881030451;hb=1d889090f2e2902d861d1fab0227c4343127cc42;hp=0b69afc4bcd38b1dd40e79a3e4f98e8f09a7507d;hpb=6ded7c96c486ebcb069e9125d4fe94c1efddbf60;p=fs%2Flustre-release.git

diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c
index 0b69afc..53c23d5 100644
--- a/lustre/ldlm/interval_tree.c
+++ b/lustre/ldlm/interval_tree.c
@@ -1,6 +1,4 @@
-/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
- * vim:expandtab:shiftwidth=8:tabstop=8:
- *
+/*
  * GPL HEADER START
  *
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
@@ -26,7 +24,7 @@
  * GPL HEADER END
  */
 /*
- * Copyright  2008 Sun Microsystems, Inc. All rights reserved
+ * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
  * Use is subject to license terms.
  */
 /*
@@ -43,7 +41,7 @@
 #ifdef __KERNEL__
 # include <lustre_dlm.h>
 #else
-# include <liblustre.h>
+# include <libcfs/libcfs.h>
 #endif
 #include <obd_support.h>
 #include <interval_tree.h>
@@ -113,11 +111,11 @@ static inline int node_compare(struct interval_node *n1,
         return extent_compare(&n1->in_extent, &n2->in_extent);
 }
 
-static inline int node_equal(struct interval_node *n1,
-                             struct interval_node *n2)
+int node_equal(struct interval_node *n1, struct interval_node *n2)
 {
-        return extent_equal(&n1->in_extent, &n2->in_extent);
+	return extent_equal(&n1->in_extent, &n2->in_extent);
 }
+EXPORT_SYMBOL(node_equal);
 
 static inline __u64 max_u64(__u64 x, __u64 y)
 {
@@ -195,7 +193,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 +211,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 +320,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 +382,7 @@ 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 +400,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 +497,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 +543,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 +565,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 +585,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)
@@ -625,116 +623,64 @@ static inline int interval_may_overlap(struct interval_node *node,
  *
  */
 enum interval_iter interval_search(struct interval_node *node,
-                                   struct interval_node_extent *ext,
-                                   interval_callback_t func,
-                                   void *data)
-{
-        struct interval_node *parent;
-        enum interval_iter rc = INTERVAL_ITER_CONT;
-
-        LASSERT(ext != NULL);
-        LASSERT(func != NULL);
-
-        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 == NULL || !interval_may_overlap(parent, ext))
-                        break;
-        }
-
-        return rc;
+				   struct interval_node_extent *ext,
+				   interval_callback_t func,
+				   void *data)
+{
+	struct interval_node *parent;
+	enum interval_iter rc = INTERVAL_ITER_CONT;
+
+	ENTRY;
+
+	LASSERT(ext != NULL);
+	LASSERT(func != NULL);
+
+	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 == NULL || !interval_may_overlap(parent, ext))
+			break;
+	}
+
+	RETURN(rc);
 }
 EXPORT_SYMBOL(interval_search);
 
-enum interval_iter interval_search_expand_extent( struct interval_node *node,
-                                       struct interval_node_extent *ext,
-                                       struct interval_node_extent *result_ext,
-                                       interval_callback_t func, void *data)
-{
-        struct interval_node *parent;
-        enum interval_iter rc = INTERVAL_ITER_CONT;
-
-        LASSERT(ext != NULL);
-        LASSERT(func != NULL);
-
-        while (node) {
-                if (ext->end < interval_low(node)) {
-                        if (result_ext->end > interval_low(node) - 1)
-                                result_ext->end = interval_low(node) - 1;
-                        if (node->in_left) {
-                                node = node->in_left;
-                                continue;
-                        }
-                } else if (ext->start > node->in_max_high) {
-                        if (result_ext->start < node->in_max_high + 1)
-                                result_ext->start = node->in_max_high + 1;
-                } else {
-                        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) {
-                                node = parent->in_right;
-                                break;
-                        }
-                        node = parent;
-                        parent = node->in_parent;
-                }
-                if (parent == NULL)
-                        break;
-        }
-        return rc;
-}
-
 static enum interval_iter interval_overlap_cb(struct interval_node *n,
                                               void *args)
 {
@@ -777,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)
@@ -795,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;