4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
27 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
34 * lustre/ldlm/interval_tree.c
36 * Interval tree library used by ldlm extent lock code
38 * Author: Huang Wei <huangwei@clusterfs.com>
39 * Author: Jay Xiong <jinshan.xiong@sun.com>
41 # include <lustre_dlm.h>
42 #include <obd_support.h>
43 #include <interval_tree.h>
50 static inline int node_is_left_child(struct interval_node
*node
)
52 LASSERT(node
->in_parent
!= NULL
);
53 return node
== node
->in_parent
->in_left
;
56 static inline int node_is_right_child(struct interval_node
*node
)
58 LASSERT(node
->in_parent
!= NULL
);
59 return node
== node
->in_parent
->in_right
;
62 static inline int node_is_red(struct interval_node
*node
)
64 return node
->in_color
== INTERVAL_RED
;
67 static inline int node_is_black(struct interval_node
*node
)
69 return node
->in_color
== INTERVAL_BLACK
;
72 static inline int extent_compare(struct interval_node_extent
*e1
,
73 struct interval_node_extent
*e2
)
76 if (e1
->start
== e2
->start
) {
77 if (e1
->end
< e2
->end
)
79 else if (e1
->end
> e2
->end
)
84 if (e1
->start
< e2
->start
)
92 static inline int extent_equal(struct interval_node_extent
*e1
,
93 struct interval_node_extent
*e2
)
95 return (e1
->start
== e2
->start
) && (e1
->end
== e2
->end
);
98 static inline int extent_overlapped(struct interval_node_extent
*e1
,
99 struct interval_node_extent
*e2
)
101 return (e1
->start
<= e2
->end
) && (e2
->start
<= e1
->end
);
104 static inline int node_compare(struct interval_node
*n1
,
105 struct interval_node
*n2
)
107 return extent_compare(&n1
->in_extent
, &n2
->in_extent
);
110 static inline int node_equal(struct interval_node
*n1
,
111 struct interval_node
*n2
)
113 return extent_equal(&n1
->in_extent
, &n2
->in_extent
);
116 static inline __u64
max_u64(__u64 x
, __u64 y
)
118 return x
> y
? x
: y
;
121 static inline __u64
min_u64(__u64 x
, __u64 y
)
123 return x
< y
? x
: y
;
126 #define interval_for_each(node, root) \
127 for (node = interval_first(root); node != NULL; \
128 node = interval_next(node))
130 #define interval_for_each_reverse(node, root) \
131 for (node = interval_last(root); node != NULL; \
132 node = interval_prev(node))
134 static struct interval_node
*interval_first(struct interval_node
*node
)
138 while (node
->in_left
)
139 node
= node
->in_left
;
143 static struct interval_node
*interval_last(struct interval_node
*node
)
147 while (node
->in_right
)
148 node
= node
->in_right
;
152 static struct interval_node
*interval_next(struct interval_node
*node
)
157 return interval_first(node
->in_right
);
158 while (node
->in_parent
&& node_is_right_child(node
))
159 node
= node
->in_parent
;
160 return node
->in_parent
;
163 static struct interval_node
*interval_prev(struct interval_node
*node
)
169 return interval_last(node
->in_left
);
171 while (node
->in_parent
&& node_is_left_child(node
))
172 node
= node
->in_parent
;
174 return node
->in_parent
;
177 enum interval_iter
interval_iterate(struct interval_node
*root
,
178 interval_callback_t func
,
181 struct interval_node
*node
;
182 enum interval_iter rc
= INTERVAL_ITER_CONT
;
184 interval_for_each(node
, root
) {
185 rc
= func(node
, data
);
186 if (rc
== INTERVAL_ITER_STOP
)
192 EXPORT_SYMBOL(interval_iterate
);
194 enum interval_iter
interval_iterate_reverse(struct interval_node
*root
,
195 interval_callback_t func
,
198 struct interval_node
*node
;
199 enum interval_iter rc
= INTERVAL_ITER_CONT
;
201 interval_for_each_reverse(node
, root
) {
202 rc
= func(node
, data
);
203 if (rc
== INTERVAL_ITER_STOP
)
209 EXPORT_SYMBOL(interval_iterate_reverse
);
211 /* try to find a node with same interval in the tree,
212 * if found, return the pointer to the node, otherwise return NULL*/
213 struct interval_node
*interval_find(struct interval_node
*root
,
214 struct interval_node_extent
*ex
)
216 struct interval_node
*walk
= root
;
220 rc
= extent_compare(ex
, &walk
->in_extent
);
224 walk
= walk
->in_left
;
226 walk
= walk
->in_right
;
231 EXPORT_SYMBOL(interval_find
);
233 static void __rotate_change_maxhigh(struct interval_node
*node
,
234 struct interval_node
*rotate
)
236 __u64 left_max
, right_max
;
238 rotate
->in_max_high
= node
->in_max_high
;
239 left_max
= node
->in_left
? node
->in_left
->in_max_high
: 0;
240 right_max
= node
->in_right
? node
->in_right
->in_max_high
: 0;
241 node
->in_max_high
= max_u64(interval_high(node
),
242 max_u64(left_max
,right_max
));
245 /* The left rotation "pivots" around the link from node to node->right, and
246 * - node will be linked to node->right's left child, and
247 * - node->right's left child will be linked to node's right child. */
248 static void __rotate_left(struct interval_node
*node
,
249 struct interval_node
**root
)
251 struct interval_node
*right
= node
->in_right
;
252 struct interval_node
*parent
= node
->in_parent
;
254 node
->in_right
= right
->in_left
;
256 right
->in_left
->in_parent
= node
;
258 right
->in_left
= node
;
259 right
->in_parent
= parent
;
261 if (node_is_left_child(node
))
262 parent
->in_left
= right
;
264 parent
->in_right
= right
;
268 node
->in_parent
= right
;
270 /* update max_high for node and right */
271 __rotate_change_maxhigh(node
, right
);
274 /* The right rotation "pivots" around the link from node to node->left, and
275 * - node will be linked to node->left's right child, and
276 * - node->left's right child will be linked to node's left child. */
277 static void __rotate_right(struct interval_node
*node
,
278 struct interval_node
**root
)
280 struct interval_node
*left
= node
->in_left
;
281 struct interval_node
*parent
= node
->in_parent
;
283 node
->in_left
= left
->in_right
;
285 left
->in_right
->in_parent
= node
;
286 left
->in_right
= node
;
288 left
->in_parent
= parent
;
290 if (node_is_right_child(node
))
291 parent
->in_right
= left
;
293 parent
->in_left
= left
;
297 node
->in_parent
= left
;
299 /* update max_high for node and left */
300 __rotate_change_maxhigh(node
, left
);
303 #define interval_swap(a, b) do { \
304 struct interval_node *c = a; a = b; b = c; \
308 * Operations INSERT and DELETE, when run on a tree with n keys,
309 * take O(logN) time.Because they modify the tree, the result
310 * may violate the red-black properties.To restore these properties,
311 * we must change the colors of some of the nodes in the tree
312 * and also change the pointer structure.
314 static void interval_insert_color(struct interval_node
*node
,
315 struct interval_node
**root
)
317 struct interval_node
*parent
, *gparent
;
319 while ((parent
= node
->in_parent
) && node_is_red(parent
)) {
320 gparent
= parent
->in_parent
;
321 /* Parent is RED, so gparent must not be NULL */
322 if (node_is_left_child(parent
)) {
323 struct interval_node
*uncle
;
324 uncle
= gparent
->in_right
;
325 if (uncle
&& node_is_red(uncle
)) {
326 uncle
->in_color
= INTERVAL_BLACK
;
327 parent
->in_color
= INTERVAL_BLACK
;
328 gparent
->in_color
= INTERVAL_RED
;
333 if (parent
->in_right
== node
) {
334 __rotate_left(parent
, root
);
335 interval_swap(node
, parent
);
338 parent
->in_color
= INTERVAL_BLACK
;
339 gparent
->in_color
= INTERVAL_RED
;
340 __rotate_right(gparent
, root
);
342 struct interval_node
*uncle
;
343 uncle
= gparent
->in_left
;
344 if (uncle
&& node_is_red(uncle
)) {
345 uncle
->in_color
= INTERVAL_BLACK
;
346 parent
->in_color
= INTERVAL_BLACK
;
347 gparent
->in_color
= INTERVAL_RED
;
352 if (node_is_left_child(node
)) {
353 __rotate_right(parent
, root
);
354 interval_swap(node
, parent
);
357 parent
->in_color
= INTERVAL_BLACK
;
358 gparent
->in_color
= INTERVAL_RED
;
359 __rotate_left(gparent
, root
);
363 (*root
)->in_color
= INTERVAL_BLACK
;
366 struct interval_node
*interval_insert(struct interval_node
*node
,
367 struct interval_node
**root
)
370 struct interval_node
**p
, *parent
= NULL
;
372 LASSERT(!interval_is_intree(node
));
376 if (node_equal(parent
, node
))
379 /* max_high field must be updated after each iteration */
380 if (parent
->in_max_high
< interval_high(node
))
381 parent
->in_max_high
= interval_high(node
);
383 if (node_compare(node
, parent
) < 0)
384 p
= &parent
->in_left
;
386 p
= &parent
->in_right
;
389 /* link node into the tree */
390 node
->in_parent
= parent
;
391 node
->in_color
= INTERVAL_RED
;
392 node
->in_left
= node
->in_right
= NULL
;
395 interval_insert_color(node
, root
);
400 EXPORT_SYMBOL(interval_insert
);
402 static inline int node_is_black_or_0(struct interval_node
*node
)
404 return !node
|| node_is_black(node
);
407 static void interval_erase_color(struct interval_node
*node
,
408 struct interval_node
*parent
,
409 struct interval_node
**root
)
411 struct interval_node
*tmp
;
413 while (node_is_black_or_0(node
) && node
!= *root
) {
414 if (parent
->in_left
== node
) {
415 tmp
= parent
->in_right
;
416 if (node_is_red(tmp
)) {
417 tmp
->in_color
= INTERVAL_BLACK
;
418 parent
->in_color
= INTERVAL_RED
;
419 __rotate_left(parent
, root
);
420 tmp
= parent
->in_right
;
422 if (node_is_black_or_0(tmp
->in_left
) &&
423 node_is_black_or_0(tmp
->in_right
)) {
424 tmp
->in_color
= INTERVAL_RED
;
426 parent
= node
->in_parent
;
428 if (node_is_black_or_0(tmp
->in_right
)) {
429 struct interval_node
*o_left
;
430 if ((o_left
= tmp
->in_left
))
431 o_left
->in_color
= INTERVAL_BLACK
;
432 tmp
->in_color
= INTERVAL_RED
;
433 __rotate_right(tmp
, root
);
434 tmp
= parent
->in_right
;
436 tmp
->in_color
= parent
->in_color
;
437 parent
->in_color
= INTERVAL_BLACK
;
439 tmp
->in_right
->in_color
= INTERVAL_BLACK
;
440 __rotate_left(parent
, root
);
445 tmp
= parent
->in_left
;
446 if (node_is_red(tmp
)) {
447 tmp
->in_color
= INTERVAL_BLACK
;
448 parent
->in_color
= INTERVAL_RED
;
449 __rotate_right(parent
, root
);
450 tmp
= parent
->in_left
;
452 if (node_is_black_or_0(tmp
->in_left
) &&
453 node_is_black_or_0(tmp
->in_right
)) {
454 tmp
->in_color
= INTERVAL_RED
;
456 parent
= node
->in_parent
;
458 if (node_is_black_or_0(tmp
->in_left
)) {
459 struct interval_node
*o_right
;
460 if ((o_right
= tmp
->in_right
))
461 o_right
->in_color
= INTERVAL_BLACK
;
462 tmp
->in_color
= INTERVAL_RED
;
463 __rotate_left(tmp
, root
);
464 tmp
= parent
->in_left
;
466 tmp
->in_color
= parent
->in_color
;
467 parent
->in_color
= INTERVAL_BLACK
;
469 tmp
->in_left
->in_color
= INTERVAL_BLACK
;
470 __rotate_right(parent
, root
);
477 node
->in_color
= INTERVAL_BLACK
;
481 * if the @max_high value of @node is changed, this function traverse a path
482 * from node up to the root to update max_high for the whole tree.
484 static void update_maxhigh(struct interval_node
*node
,
487 __u64 left_max
, right_max
;
490 left_max
= node
->in_left
? node
->in_left
->in_max_high
: 0;
491 right_max
= node
->in_right
? node
->in_right
->in_max_high
: 0;
492 node
->in_max_high
= max_u64(interval_high(node
),
493 max_u64(left_max
, right_max
));
495 if (node
->in_max_high
>= old_maxhigh
)
497 node
= node
->in_parent
;
501 void interval_erase(struct interval_node
*node
,
502 struct interval_node
**root
)
504 struct interval_node
*child
, *parent
;
507 LASSERT(interval_is_intree(node
));
509 if (!node
->in_left
) {
510 child
= node
->in_right
;
511 } else if (!node
->in_right
) {
512 child
= node
->in_left
;
513 } else { /* Both left and right child are not NULL */
514 struct interval_node
*old
= node
;
516 node
= interval_next(node
);
517 child
= node
->in_right
;
518 parent
= node
->in_parent
;
519 color
= node
->in_color
;
522 child
->in_parent
= parent
;
524 parent
->in_right
= child
;
526 parent
->in_left
= child
;
528 node
->in_color
= old
->in_color
;
529 node
->in_right
= old
->in_right
;
530 node
->in_left
= old
->in_left
;
531 node
->in_parent
= old
->in_parent
;
533 if (old
->in_parent
) {
534 if (node_is_left_child(old
))
535 old
->in_parent
->in_left
= node
;
537 old
->in_parent
->in_right
= node
;
542 old
->in_left
->in_parent
= node
;
544 old
->in_right
->in_parent
= node
;
545 update_maxhigh(child
? : parent
, node
->in_max_high
);
546 update_maxhigh(node
, old
->in_max_high
);
551 parent
= node
->in_parent
;
552 color
= node
->in_color
;
555 child
->in_parent
= parent
;
557 if (node_is_left_child(node
))
558 parent
->in_left
= child
;
560 parent
->in_right
= child
;
565 update_maxhigh(child
? : parent
, node
->in_max_high
);
568 if (color
== INTERVAL_BLACK
)
569 interval_erase_color(child
, parent
, root
);
571 EXPORT_SYMBOL(interval_erase
);
573 static inline int interval_may_overlap(struct interval_node
*node
,
574 struct interval_node_extent
*ext
)
576 return (ext
->start
<= node
->in_max_high
&&
577 ext
->end
>= interval_low(node
));
581 * This function finds all intervals that overlap interval ext,
582 * and calls func to handle resulted intervals one by one.
583 * in lustre, this function will find all conflicting locks in
584 * the granted queue and add these locks to the ast work list.
589 * if (ext->end < interval_low(node)) {
590 * interval_search(node->in_left, ext, func, data);
591 * } else if (interval_may_overlap(node, ext)) {
592 * if (extent_overlapped(ext, &node->in_extent))
594 * interval_search(node->in_left, ext, func, data);
595 * interval_search(node->in_right, ext, func, data);
601 enum interval_iter
interval_search(struct interval_node
*node
,
602 struct interval_node_extent
*ext
,
603 interval_callback_t func
,
606 struct interval_node
*parent
;
607 enum interval_iter rc
= INTERVAL_ITER_CONT
;
609 LASSERT(ext
!= NULL
);
610 LASSERT(func
!= NULL
);
613 if (ext
->end
< interval_low(node
)) {
615 node
= node
->in_left
;
618 } else if (interval_may_overlap(node
, ext
)) {
619 if (extent_overlapped(ext
, &node
->in_extent
)) {
620 rc
= func(node
, data
);
621 if (rc
== INTERVAL_ITER_STOP
)
626 node
= node
->in_left
;
629 if (node
->in_right
) {
630 node
= node
->in_right
;
635 parent
= node
->in_parent
;
637 if (node_is_left_child(node
) &&
639 /* If we ever got the left, it means that the
640 * parent met ext->end<interval_low(parent), or
641 * may_overlap(parent). If the former is true,
642 * we needn't go back. So stop early and check
643 * may_overlap(parent) after this loop. */
644 node
= parent
->in_right
;
648 parent
= parent
->in_parent
;
650 if (parent
== NULL
|| !interval_may_overlap(parent
, ext
))
656 EXPORT_SYMBOL(interval_search
);
658 static enum interval_iter
interval_overlap_cb(struct interval_node
*n
,
662 return INTERVAL_ITER_STOP
;
665 int interval_is_overlapped(struct interval_node
*root
,
666 struct interval_node_extent
*ext
)
669 (void)interval_search(root
, ext
, interval_overlap_cb
, &has
);
672 EXPORT_SYMBOL(interval_is_overlapped
);
674 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
675 * some extents, because programs seldom do IO backward.
677 * The recursive algorithm of expanding low:
679 * struct interval_node *tmp;
680 * static __u64 res = 0;
684 * if (root->in_max_high < low) {
685 * res = max_u64(root->in_max_high + 1, res);
687 * } else if (low < interval_low(root)) {
688 * interval_expand_low(root->in_left, low);
692 * if (interval_high(root) < low)
693 * res = max_u64(interval_high(root) + 1, res);
694 * interval_expand_low(root->in_left, low);
695 * interval_expand_low(root->in_right, low);
700 * It's much easy to eliminate the recursion, see interval_search for
703 static inline __u64
interval_expand_low(struct interval_node
*root
, __u64 low
)
705 /* we only concern the empty tree right now. */
711 static inline __u64
interval_expand_high(struct interval_node
*node
, __u64 high
)
715 while (node
!= NULL
) {
716 if (node
->in_max_high
< high
)
719 if (interval_low(node
) > high
) {
720 result
= interval_low(node
) - 1;
721 node
= node
->in_left
;
723 node
= node
->in_right
;
730 /* expanding the extent based on @ext. */
731 void interval_expand(struct interval_node
*root
,
732 struct interval_node_extent
*ext
,
733 struct interval_node_extent
*limiter
)
735 /* The assertion of interval_is_overlapped is expensive because we may
736 * travel many nodes to find the overlapped node. */
737 LASSERT(interval_is_overlapped(root
, ext
) == 0);
738 if (!limiter
|| limiter
->start
< ext
->start
)
739 ext
->start
= interval_expand_low(root
, ext
->start
);
740 if (!limiter
|| limiter
->end
> ext
->end
)
741 ext
->end
= interval_expand_high(root
, ext
->end
);
742 LASSERT(interval_is_overlapped(root
, ext
) == 0);
744 EXPORT_SYMBOL(interval_expand
);
This page took 0.052209 seconds and 5 git commands to generate.