X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lustre%2Fldlm%2Finterval_tree.c;h=1318562cf5ed4473228ad4242b9ce8768e645be4;hb=c8df02cbe6626201eba7744625fafa030b1b466d;hp=0b69afc4bcd38b1dd40e79a3e4f98e8f09a7507d;hpb=6ded7c96c486ebcb069e9125d4fe94c1efddbf60;p=fs%2Flustre-release.git diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c index 0b69afc..1318562 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. @@ -26,7 +24,7 @@ * 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. */ /* @@ -101,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); @@ -195,7 +193,7 @@ enum interval_iter interval_iterate(struct interval_node *root, 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) @@ -213,7 +211,7 @@ enum interval_iter interval_iterate_reverse(struct interval_node *root, 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) @@ -322,10 +320,10 @@ static void __rotate_right(struct interval_node *node, } 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, @@ -384,7 +382,7 @@ 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; @@ -402,7 +400,7 @@ struct interval_node *interval_insert(struct interval_node *node, if (node_compare(node, parent) < 0) p = &parent->in_left; - else + else p = &parent->in_right; } @@ -499,8 +497,8 @@ static void interval_erase_color(struct interval_node *node, 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, @@ -545,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; @@ -569,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; @@ -587,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) @@ -656,13 +654,13 @@ enum interval_iter interval_search(struct interval_node *node, 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->endend < 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) { @@ -777,7 +721,7 @@ EXPORT_SYMBOL(interval_is_overlapped); * 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) @@ -795,7 +739,7 @@ static inline __u64 interval_expand_high(struct interval_node *node, __u64 high) while (node != NULL) { if (node->in_max_high < high) break; - + if (interval_low(node) > high) { result = interval_low(node) - 1; node = node->in_left;