-/* -*- 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.
* 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.
*/
/*
#ifdef __KERNEL__
# include <lustre_dlm.h>
#else
-# include <liblustre.h>
+# include <libcfs/libcfs.h>
#endif
#include <obd_support.h>
#include <interval_tree.h>
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);
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)
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
}
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;
git://git.whamcloud.com / fs / lustre-release.git / blobdiff