X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lustre%2Fldlm%2Finterval_tree.c;h=53c23d5c44086e2e8aaa226be9612b4881030451;hb=1d889090f2e2902d861d1fab0227c4343127cc42;hp=bedf5b3a45ab520270a984ecb2e7216827149b1a;hpb=022b102258cd85314f4fa1fb8322638cc79f4634;p=fs%2Flustre-release.git diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c index bedf5b3..53c23d5 100644 --- a/lustre/ldlm/interval_tree.c +++ b/lustre/ldlm/interval_tree.c @@ -1,35 +1,47 @@ -/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*- - * vim:expandtab:shiftwidth=8:tabstop=8: +/* + * GPL HEADER START * - * Interval tree library used by ldlm extent lock code + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * - * Copyright (c) 2007 Cluster File Systems, Inc. - * Author: Huang Wei - * Author: Jay Xiong + * 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. * - * 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 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). * - * 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. + * 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 * - * 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. + * 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. * - * 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. + * GPL HEADER END + */ +/* + * Copyright (c) 2008, 2010, Oracle and/or its affiliates. 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 + * Author: Jay Xiong */ #ifdef __KERNEL__ # include #else -# include -# include +# include #endif #include #include @@ -87,7 +99,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); @@ -99,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) { @@ -375,6 +387,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; @@ -398,6 +411,7 @@ struct interval_node *interval_insert(struct interval_node *node, *p = node; interval_insert_color(node, root); + node->in_intree = 1; RETURN(NULL); } @@ -513,6 +527,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) { @@ -527,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; @@ -551,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; @@ -569,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) @@ -607,59 +623,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);