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.gnu.org/licenses/gpl-2.0.html
23 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Use is subject to license terms.
26 * Copyright (c) 2014, Intel Corporation.
29 * This file is part of Lustre, http://www.lustre.org/
31 * lustre/ldlm/interval_tree.c
33 * Interval tree library used by ldlm extent lock code
35 * Author: Huang Wei <huangwei@clusterfs.com>
36 * Author: Jay Xiong <jinshan.xiong@sun.com>
39 #include <lustre_dlm.h>
40 #include <interval_tree.h>
47 static inline int node_is_left_child(struct interval_node *node)
49 LASSERT(node->in_parent != NULL);
50 return node == node->in_parent->in_left;
53 static inline int node_is_right_child(struct interval_node *node)
55 LASSERT(node->in_parent != NULL);
56 return node == node->in_parent->in_right;
59 static inline int node_is_red(struct interval_node *node)
61 return node->in_color == INTERVAL_RED;
64 static inline int node_is_black(struct interval_node *node)
66 return node->in_color == INTERVAL_BLACK;
69 static inline int extent_compare(struct interval_node_extent *e1,
70 struct interval_node_extent *e2)
74 if (e1->start == e2->start) {
75 if (e1->end < e2->end)
77 else if (e1->end > e2->end)
82 if (e1->start < e2->start)
90 static inline int extent_equal(struct interval_node_extent *e1,
91 struct interval_node_extent *e2)
93 return (e1->start == e2->start) && (e1->end == e2->end);
96 static inline int extent_overlapped(struct interval_node_extent *e1,
97 struct interval_node_extent *e2)
99 return (e1->start <= e2->end) && (e2->start <= e1->end);
102 static inline int node_compare(struct interval_node *n1,
103 struct interval_node *n2)
105 return extent_compare(&n1->in_extent, &n2->in_extent);
108 int node_equal(struct interval_node *n1, struct interval_node *n2)
110 return extent_equal(&n1->in_extent, &n2->in_extent);
113 #define interval_for_each(node, root) \
114 for (node = interval_first(root); node != NULL; \
115 node = interval_next(node))
117 #define interval_for_each_reverse(node, root) \
118 for (node = interval_last(root); node != NULL; \
119 node = interval_prev(node))
121 static struct interval_node *interval_first(struct interval_node *node)
127 while (node->in_left)
128 node = node->in_left;
132 static struct interval_node *interval_last(struct interval_node *node)
138 while (node->in_right)
139 node = node->in_right;
143 static struct interval_node *interval_next(struct interval_node *node)
150 RETURN(interval_first(node->in_right));
151 while (node->in_parent && node_is_right_child(node))
152 node = node->in_parent;
153 RETURN(node->in_parent);
156 static struct interval_node *interval_prev(struct interval_node *node)
164 RETURN(interval_last(node->in_left));
166 while (node->in_parent && node_is_left_child(node))
167 node = node->in_parent;
169 RETURN(node->in_parent);
172 enum interval_iter interval_iterate(struct interval_node *root,
173 interval_callback_t func,
176 struct interval_node *node;
177 enum interval_iter rc = INTERVAL_ITER_CONT;
181 interval_for_each(node, root) {
182 rc = func(node, data);
183 if (rc == INTERVAL_ITER_STOP)
189 EXPORT_SYMBOL(interval_iterate);
191 enum interval_iter interval_iterate_reverse(struct interval_node *root,
192 interval_callback_t func,
195 struct interval_node *node;
196 enum interval_iter rc = INTERVAL_ITER_CONT;
200 interval_for_each_reverse(node, root) {
201 rc = func(node, data);
202 if (rc == INTERVAL_ITER_STOP)
208 EXPORT_SYMBOL(interval_iterate_reverse);
210 /* try to find a node with same interval in the tree,
211 * 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;
222 rc = extent_compare(ex, &walk->in_extent);
226 walk = walk->in_left;
228 walk = walk->in_right;
233 EXPORT_SYMBOL(interval_find);
235 static void __rotate_change_maxhigh(struct interval_node *node,
236 struct interval_node *rotate)
238 __u64 left_max, right_max;
240 rotate->in_max_high = node->in_max_high;
241 left_max = node->in_left ? node->in_left->in_max_high : 0;
242 right_max = node->in_right ? node->in_right->in_max_high : 0;
243 node->in_max_high = max3(interval_high(node),
244 left_max, right_max);
247 /* The left rotation "pivots" around the link from node to node->right, and
248 * - node will be linked to node->right's left child, and
249 * - node->right's left child will be linked to node's right child.
251 static void __rotate_left(struct interval_node *node,
252 struct interval_node **root)
254 struct interval_node *right = node->in_right;
255 struct interval_node *parent = node->in_parent;
257 node->in_right = right->in_left;
259 right->in_left->in_parent = node;
261 right->in_left = node;
262 right->in_parent = parent;
264 if (node_is_left_child(node))
265 parent->in_left = right;
267 parent->in_right = right;
271 node->in_parent = right;
273 /* update max_high for node and right */
274 __rotate_change_maxhigh(node, right);
277 /* The right rotation "pivots" around the link from node to node->left, and
278 * - node will be linked to node->left's right child, and
279 * - node->left's right child will be linked to node's left child.
281 static void __rotate_right(struct interval_node *node,
282 struct interval_node **root)
284 struct interval_node *left = node->in_left;
285 struct interval_node *parent = node->in_parent;
287 node->in_left = left->in_right;
289 left->in_right->in_parent = node;
290 left->in_right = node;
292 left->in_parent = parent;
294 if (node_is_right_child(node))
295 parent->in_right = left;
297 parent->in_left = left;
301 node->in_parent = left;
303 /* update max_high for node and left */
304 __rotate_change_maxhigh(node, left);
307 #define interval_swap(a, b) do { \
308 struct interval_node *c = a; a = b; b = c; \
312 * Operations INSERT and DELETE, when run on a tree with n keys,
313 * take O(logN) time.Because they modify the tree, the result
314 * may violate the red-black properties.To restore these properties,
315 * we must change the colors of some of the nodes in the tree
316 * and also change the pointer structure.
318 static void interval_insert_color(struct interval_node *node,
319 struct interval_node **root)
321 struct interval_node *parent, *gparent;
325 while ((parent = node->in_parent) && node_is_red(parent)) {
326 gparent = parent->in_parent;
327 /* Parent is RED, so gparent must not be NULL */
328 if (node_is_left_child(parent)) {
329 struct interval_node *uncle;
331 uncle = gparent->in_right;
332 if (uncle && node_is_red(uncle)) {
333 uncle->in_color = INTERVAL_BLACK;
334 parent->in_color = INTERVAL_BLACK;
335 gparent->in_color = INTERVAL_RED;
340 if (parent->in_right == node) {
341 __rotate_left(parent, root);
342 interval_swap(node, parent);
345 parent->in_color = INTERVAL_BLACK;
346 gparent->in_color = INTERVAL_RED;
347 __rotate_right(gparent, root);
349 struct interval_node *uncle;
351 uncle = gparent->in_left;
352 if (uncle && node_is_red(uncle)) {
353 uncle->in_color = INTERVAL_BLACK;
354 parent->in_color = INTERVAL_BLACK;
355 gparent->in_color = INTERVAL_RED;
360 if (node_is_left_child(node)) {
361 __rotate_right(parent, root);
362 interval_swap(node, parent);
365 parent->in_color = INTERVAL_BLACK;
366 gparent->in_color = INTERVAL_RED;
367 __rotate_left(gparent, root);
371 (*root)->in_color = INTERVAL_BLACK;
375 struct interval_node *interval_insert(struct interval_node *node,
376 struct interval_node **root)
378 struct interval_node **p, *parent = NULL;
382 LASSERT(!interval_is_intree(node));
386 if (node_equal(parent, node))
389 /* max_high field must be updated after each iteration */
390 if (parent->in_max_high < interval_high(node))
391 parent->in_max_high = interval_high(node);
393 if (node_compare(node, parent) < 0)
394 p = &parent->in_left;
396 p = &parent->in_right;
399 /* link node into the tree */
400 node->in_parent = parent;
401 node->in_color = INTERVAL_RED;
402 node->in_left = node->in_right = NULL;
405 interval_insert_color(node, root);
410 EXPORT_SYMBOL(interval_insert);
412 static inline int node_is_black_or_0(struct interval_node *node)
414 return !node || node_is_black(node);
417 static void interval_erase_color(struct interval_node *node,
418 struct interval_node *parent,
419 struct interval_node **root)
421 struct interval_node *tmp;
425 while (node_is_black_or_0(node) && node != *root) {
426 if (parent->in_left == node) {
427 tmp = parent->in_right;
428 if (node_is_red(tmp)) {
429 tmp->in_color = INTERVAL_BLACK;
430 parent->in_color = INTERVAL_RED;
431 __rotate_left(parent, root);
432 tmp = parent->in_right;
434 if (node_is_black_or_0(tmp->in_left) &&
435 node_is_black_or_0(tmp->in_right)) {
436 tmp->in_color = INTERVAL_RED;
438 parent = node->in_parent;
440 if (node_is_black_or_0(tmp->in_right)) {
441 struct interval_node *o_left;
443 if ((o_left = tmp->in_left))
446 tmp->in_color = INTERVAL_RED;
447 __rotate_right(tmp, root);
448 tmp = parent->in_right;
450 tmp->in_color = parent->in_color;
451 parent->in_color = INTERVAL_BLACK;
453 tmp->in_right->in_color =
455 __rotate_left(parent, root);
460 tmp = parent->in_left;
461 if (node_is_red(tmp)) {
462 tmp->in_color = INTERVAL_BLACK;
463 parent->in_color = INTERVAL_RED;
464 __rotate_right(parent, root);
465 tmp = parent->in_left;
467 if (node_is_black_or_0(tmp->in_left) &&
468 node_is_black_or_0(tmp->in_right)) {
469 tmp->in_color = INTERVAL_RED;
471 parent = node->in_parent;
473 if (node_is_black_or_0(tmp->in_left)) {
474 struct interval_node *o_right;
476 if ((o_right = tmp->in_right))
479 tmp->in_color = INTERVAL_RED;
480 __rotate_left(tmp, root);
481 tmp = parent->in_left;
483 tmp->in_color = parent->in_color;
484 parent->in_color = INTERVAL_BLACK;
486 tmp->in_left->in_color = INTERVAL_BLACK;
487 __rotate_right(parent, root);
494 node->in_color = INTERVAL_BLACK;
499 * if the @max_high value of @node is changed, this function traverse a path
500 * from node up to the root to update max_high for the whole tree.
502 static void update_maxhigh(struct interval_node *node,
505 __u64 left_max, right_max;
510 left_max = node->in_left ? node->in_left->in_max_high : 0;
511 right_max = node->in_right ? node->in_right->in_max_high : 0;
512 node->in_max_high = max3(interval_high(node),
513 left_max, right_max);
515 if (node->in_max_high >= old_maxhigh)
517 node = node->in_parent;
522 void interval_erase(struct interval_node *node,
523 struct interval_node **root)
525 struct interval_node *child, *parent;
530 LASSERT(interval_is_intree(node));
532 if (!node->in_left) {
533 child = node->in_right;
534 } else if (!node->in_right) {
535 child = node->in_left;
536 } else { /* Both left and right child are not NULL */
537 struct interval_node *old = node;
539 node = interval_next(node);
540 child = node->in_right;
541 parent = node->in_parent;
542 color = node->in_color;
545 child->in_parent = parent;
547 parent->in_right = child;
549 parent->in_left = child;
551 node->in_color = old->in_color;
552 node->in_right = old->in_right;
553 node->in_left = old->in_left;
554 node->in_parent = old->in_parent;
556 if (old->in_parent) {
557 if (node_is_left_child(old))
558 old->in_parent->in_left = node;
560 old->in_parent->in_right = node;
565 old->in_left->in_parent = node;
567 old->in_right->in_parent = node;
568 update_maxhigh(child ? : parent, node->in_max_high);
569 update_maxhigh(node, old->in_max_high);
574 parent = node->in_parent;
575 color = node->in_color;
578 child->in_parent = parent;
580 if (node_is_left_child(node))
581 parent->in_left = child;
583 parent->in_right = child;
588 update_maxhigh(child ? : parent, node->in_max_high);
591 if (color == INTERVAL_BLACK)
592 interval_erase_color(child, parent, root);
595 EXPORT_SYMBOL(interval_erase);
597 static inline int interval_may_overlap(struct interval_node *node,
598 struct interval_node_extent *ext)
600 return (ext->start <= node->in_max_high &&
601 ext->end >= interval_low(node));
605 * This function finds all intervals that overlap interval ext,
606 * and calls func to handle resulted intervals one by one.
607 * in lustre, this function will find all conflicting locks in
608 * the granted queue and add these locks to the ast work list.
613 * if (ext->end < interval_low(node)) {
614 * interval_search(node->in_left, ext, func, data);
615 * } else if (interval_may_overlap(node, ext)) {
616 * if (extent_overlapped(ext, &node->in_extent))
618 * interval_search(node->in_left, ext, func, data);
619 * interval_search(node->in_right, ext, func, data);
625 enum interval_iter interval_search(struct interval_node *node,
626 struct interval_node_extent *ext,
627 interval_callback_t func,
630 struct interval_node *parent;
631 enum interval_iter rc = INTERVAL_ITER_CONT;
635 LASSERT(ext != NULL);
636 LASSERT(func != NULL);
639 if (ext->end < interval_low(node)) {
641 node = node->in_left;
644 } else if (interval_may_overlap(node, ext)) {
645 if (extent_overlapped(ext, &node->in_extent)) {
646 rc = func(node, data);
647 if (rc == INTERVAL_ITER_STOP)
652 node = node->in_left;
655 if (node->in_right) {
656 node = node->in_right;
661 parent = node->in_parent;
663 if (node_is_left_child(node) &&
665 /* If we ever got the left, it means that the
666 * parent met ext->end<interval_low(parent), or
667 * may_overlap(parent). If the former is true,
668 * we needn't go back. So stop early and check
669 * may_overlap(parent) after this loop.
671 node = parent->in_right;
675 parent = parent->in_parent;
677 if (parent == NULL || !interval_may_overlap(parent, ext))
683 EXPORT_SYMBOL(interval_search);
685 static enum interval_iter interval_overlap_cb(struct interval_node *n,
689 return INTERVAL_ITER_STOP;
692 int interval_is_overlapped(struct interval_node *root,
693 struct interval_node_extent *ext)
696 (void)interval_search(root, ext, interval_overlap_cb, &has);
699 EXPORT_SYMBOL(interval_is_overlapped);
701 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
702 * some extents, because programs seldom do IO backward.
704 * The recursive algorithm of expanding low:
706 * struct interval_node *tmp;
707 * static __u64 res = 0;
711 * if (root->in_max_high < low) {
712 * res = max(root->in_max_high + 1, res);
714 * } else if (low < interval_low(root)) {
715 * interval_expand_low(root->in_left, low);
719 * if (interval_high(root) < low)
720 * res = max(interval_high(root) + 1, res);
721 * interval_expand_low(root->in_left, low);
722 * interval_expand_low(root->in_right, low);
727 * It's much easy to eliminate the recursion, see interval_search for
730 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
732 /* we only concern the empty tree right now. */
738 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
742 while (node != NULL) {
743 if (node->in_max_high < high)
746 if (interval_low(node) > high) {
747 result = interval_low(node) - 1;
748 node = node->in_left;
750 node = node->in_right;
757 /* expanding the extent based on @ext. */
758 void interval_expand(struct interval_node *root,
759 struct interval_node_extent *ext,
760 struct interval_node_extent *limiter)
762 /* The assertion of interval_is_overlapped is expensive because we may
763 * travel many nodes to find the overlapped node.
765 LASSERT(interval_is_overlapped(root, ext) == 0);
766 if (!limiter || limiter->start < ext->start)
767 ext->start = interval_expand_low(root, ext->start);
768 if (!limiter || limiter->end > ext->end)
769 ext->end = interval_expand_high(root, ext->end);
770 LASSERT(interval_is_overlapped(root, ext) == 0);
772 EXPORT_SYMBOL(interval_expand);