/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
* vim:expandtab:shiftwidth=8:tabstop=8:
*
- * Interval tree library used by ldlm extent lock code
+ * GPL HEADER START
*
- * Copyright (c) 2007 Cluster File Systems, Inc.
- * Author: Huang Wei <huangwei@clusterfs.com>
- * Author: Jay Xiong <jinshan.xiong@sun.com>
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
- * This file is part of the Lustre file system, http://www.lustre.org
- * Lustre is a trademark of Cluster File Systems, Inc.
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 only,
+ * as published by the Free Software Foundation.
*
- * You may have signed or agreed to another license before downloading
- * this software. If so, you are bound by the terms and conditions
- * of that agreement, and the following does not apply to you. See the
- * LICENSE file included with this distribution for more information.
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License version 2 for more details (a copy is included
+ * in the LICENSE file that accompanied this code).
*
- * If you did not agree to a different license, then this copy of Lustre
- * is open source software; you can redistribute it and/or modify it
- * under the terms of version 2 of the GNU General Public License as
- * published by the Free Software Foundation.
+ * 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
*
- * In either case, Lustre is distributed in the hope that it will be
- * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * license text for more details.
+ * 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.
+ *
+ * GPL HEADER END
+ */
+/*
+ * Copyright 2008 Sun Microsystems, Inc. All rights reserved
+ * Use is subject to license terms.
+ */
+/*
+ * This file is part of Lustre, http://www.lustre.org/
+ * Lustre is a trademark of Sun Microsystems, Inc.
+ *
+ * lustre/ldlm/interval_tree.c
+ *
+ * Interval tree library used by ldlm extent lock code
+ *
+ * Author: Huang Wei <huangwei@clusterfs.com>
+ * Author: Jay Xiong <jinshan.xiong@sun.com>
*/
#ifdef __KERNEL__
# include <lustre_dlm.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;
+ LASSERT(!interval_is_intree(node));
p = root;
while (*p) {
parent = *p;
if (node_compare(node, parent) < 0)
p = &parent->in_left;
- else
+ else
p = &parent->in_right;
}
*p = node;
interval_insert_color(node, root);
+ node->in_intree = 1;
RETURN(NULL);
}
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,
int color;
ENTRY;
+ LASSERT(interval_is_intree(node));
+ node->in_intree = 0;
if (!node->in_left) {
child = node->in_right;
} else 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
+ /* 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