X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lustre%2Fldlm%2Finterval_tree.c;h=e69d13f7227b4a70a9b503a38e59dd97a5a0d117;hb=ad1810a2dbea1eed5e8b5feb55bdf915a545feb3;hp=680d2387c893aa6458d1e6f48ad8894633c1d253;hpb=70e80ade90af09300396706b8910e196a7928520;p=fs%2Flustre-release.git diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c index 680d238..e69d13f 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. @@ -16,8 +14,8 @@ * in the LICENSE file that accompanied this code). * * You should have received a copy of the GNU General Public License - * version 2 along with this program; If not, see [sun.com URL with a - * copy of GPLv2]. + * 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 @@ -26,8 +24,10 @@ * 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/ @@ -43,9 +43,8 @@ #ifdef __KERNEL__ # include #else -# include +# include #endif -#include #include enum { @@ -101,7 +100,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); @@ -113,11 +112,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) { @@ -389,6 +388,7 @@ struct interval_node *interval_insert(struct interval_node *node, struct interval_node **p, *parent = NULL; ENTRY; + LASSERT(!interval_is_intree(node)); p = root; while (*p) { parent = *p; @@ -412,6 +412,7 @@ struct interval_node *interval_insert(struct interval_node *node, *p = node; interval_insert_color(node, root); + node->in_intree = 1; RETURN(NULL); } @@ -527,6 +528,8 @@ void interval_erase(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) { @@ -541,12 +544,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; @@ -565,8 +566,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; @@ -583,7 +586,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) @@ -621,59 +624,61 @@ 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->endin_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->endin_right; + break; + } + node = parent; + parent = parent->in_parent; + } + if (parent == NULL || !interval_may_overlap(parent, ext)) + break; + } + + RETURN(rc); } EXPORT_SYMBOL(interval_search);