-/* -*- 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.
*
* You should have received a copy of the GNU General Public License
* version 2 along with this program; If not, see
- * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
- *
- * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
- * CA 95054 USA or visit www.sun.com if you need additional information or
- * have any questions.
+ * http://www.gnu.org/licenses/gpl-2.0.html
*
* 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.
+ *
+ * Copyright (c) 2014, Intel Corporation.
*/
/*
* This file is part of Lustre, http://www.lustre.org/
* Author: Huang Wei <huangwei@clusterfs.com>
* Author: Jay Xiong <jinshan.xiong@sun.com>
*/
-#ifdef __KERNEL__
-# include <lustre_dlm.h>
-#else
-# include <liblustre.h>
-#endif
-#include <obd_support.h>
+
+#include <lustre_dlm.h>
#include <interval_tree.h>
enum {
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);
}
static inline __u64 max_u64(__u64 x, __u64 y)
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)
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)
} 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,
struct interval_node *interval_insert(struct interval_node *node,
struct interval_node **root)
-
+
{
struct interval_node **p, *parent = NULL;
ENTRY;
if (node_compare(node, parent) < 0)
p = &parent->in_left;
- else
+ else
p = &parent->in_right;
}
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,
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;
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;
*root = child;
}
- update_maxhigh(child, node->in_max_high);
+ update_maxhigh(child ? : parent, node->in_max_high);
color:
if (color == INTERVAL_BLACK)
*
*/
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)
{
* 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)
while (node != NULL) {
if (node->in_max_high < high)
break;
-
+
if (interval_low(node) > high) {
result = interval_low(node) - 1;
node = node->in_left;
ext->end = interval_expand_high(root, ext->end);
LASSERT(interval_is_overlapped(root, ext) == 0);
}
-EXPORT_SYMBOL(interval_expand);