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 #define interval_for_each(node, root) \
109 for (node = interval_first(root); node != NULL; \
110 node = interval_next(node))
112 #define interval_for_each_reverse(node, root) \
113 for (node = interval_last(root); node != NULL; \
114 node = interval_prev(node))
116 static struct interval_node *interval_first(struct interval_node *node)
122 while (node->in_left)
123 node = node->in_left;
127 static struct interval_node *interval_last(struct interval_node *node)
133 while (node->in_right)
134 node = node->in_right;
138 static struct interval_node *interval_next(struct interval_node *node)
145 RETURN(interval_first(node->in_right));
146 while (node->in_parent && node_is_right_child(node))
147 node = node->in_parent;
148 RETURN(node->in_parent);
151 static struct interval_node *interval_prev(struct interval_node *node)
159 RETURN(interval_last(node->in_left));
161 while (node->in_parent && node_is_left_child(node))
162 node = node->in_parent;
164 RETURN(node->in_parent);
167 enum interval_iter interval_iterate(struct interval_node *root,
168 interval_callback_t func,
171 struct interval_node *node;
172 enum interval_iter rc = INTERVAL_ITER_CONT;
176 interval_for_each(node, root) {
177 rc = func(node, data);
178 if (rc == INTERVAL_ITER_STOP)
184 EXPORT_SYMBOL(interval_iterate);
186 enum interval_iter interval_iterate_reverse(struct interval_node *root,
187 interval_callback_t func,
190 struct interval_node *node;
191 enum interval_iter rc = INTERVAL_ITER_CONT;
195 interval_for_each_reverse(node, root) {
196 rc = func(node, data);
197 if (rc == INTERVAL_ITER_STOP)
203 EXPORT_SYMBOL(interval_iterate_reverse);
205 /* try to find a node with same interval in the tree,
206 * if found, return the pointer to the node, otherwise return NULL
208 struct interval_node *interval_find(struct interval_node *root,
209 struct interval_node_extent *ex)
211 struct interval_node *walk = root;
217 rc = extent_compare(ex, &walk->in_extent);
221 walk = walk->in_left;
223 walk = walk->in_right;
228 EXPORT_SYMBOL(interval_find);
230 static void __rotate_change_maxhigh(struct interval_node *node,
231 struct interval_node *rotate)
233 __u64 left_max, right_max;
235 rotate->in_max_high = node->in_max_high;
236 left_max = node->in_left ? node->in_left->in_max_high : 0;
237 right_max = node->in_right ? node->in_right->in_max_high : 0;
238 node->in_max_high = max3(interval_high(node),
239 left_max, right_max);
242 /* The left rotation "pivots" around the link from node to node->right, and
243 * - node will be linked to node->right's left child, and
244 * - node->right's left child will be linked to node's right child.
246 static void __rotate_left(struct interval_node *node,
247 struct interval_node **root)
249 struct interval_node *right = node->in_right;
250 struct interval_node *parent = node->in_parent;
252 node->in_right = right->in_left;
254 right->in_left->in_parent = node;
256 right->in_left = node;
257 right->in_parent = parent;
259 if (node_is_left_child(node))
260 parent->in_left = right;
262 parent->in_right = right;
266 node->in_parent = right;
268 /* update max_high for node and right */
269 __rotate_change_maxhigh(node, right);
272 /* The right rotation "pivots" around the link from node to node->left, and
273 * - node will be linked to node->left's right child, and
274 * - node->left's right child will be linked to node's left child.
276 static void __rotate_right(struct interval_node *node,
277 struct interval_node **root)
279 struct interval_node *left = node->in_left;
280 struct interval_node *parent = node->in_parent;
282 node->in_left = left->in_right;
284 left->in_right->in_parent = node;
285 left->in_right = node;
287 left->in_parent = parent;
289 if (node_is_right_child(node))
290 parent->in_right = left;
292 parent->in_left = left;
296 node->in_parent = left;
298 /* update max_high for node and left */
299 __rotate_change_maxhigh(node, left);
302 #define interval_swap(a, b) do { \
303 struct interval_node *c = a; a = b; b = c; \
307 * Operations INSERT and DELETE, when run on a tree with n keys,
308 * take O(logN) time.Because they modify the tree, the result
309 * may violate the red-black properties.To restore these properties,
310 * we must change the colors of some of the nodes in the tree
311 * and also change the pointer structure.
313 static void interval_insert_color(struct interval_node *node,
314 struct interval_node **root)
316 struct interval_node *parent, *gparent;
320 while ((parent = node->in_parent) && node_is_red(parent)) {
321 gparent = parent->in_parent;
322 /* Parent is RED, so gparent must not be NULL */
323 if (node_is_left_child(parent)) {
324 struct interval_node *uncle;
326 uncle = gparent->in_right;
327 if (uncle && node_is_red(uncle)) {
328 uncle->in_color = INTERVAL_BLACK;
329 parent->in_color = INTERVAL_BLACK;
330 gparent->in_color = INTERVAL_RED;
335 if (parent->in_right == node) {
336 __rotate_left(parent, root);
337 interval_swap(node, parent);
340 parent->in_color = INTERVAL_BLACK;
341 gparent->in_color = INTERVAL_RED;
342 __rotate_right(gparent, root);
344 struct interval_node *uncle;
346 uncle = gparent->in_left;
347 if (uncle && node_is_red(uncle)) {
348 uncle->in_color = INTERVAL_BLACK;
349 parent->in_color = INTERVAL_BLACK;
350 gparent->in_color = INTERVAL_RED;
355 if (node_is_left_child(node)) {
356 __rotate_right(parent, root);
357 interval_swap(node, parent);
360 parent->in_color = INTERVAL_BLACK;
361 gparent->in_color = INTERVAL_RED;
362 __rotate_left(gparent, root);
366 (*root)->in_color = INTERVAL_BLACK;
370 struct interval_node *interval_insert(struct interval_node *node,
371 struct interval_node **root)
373 struct interval_node **p, *parent = NULL;
377 LASSERT(!interval_is_intree(node));
382 /* max_high field must be updated after each iteration */
383 if (parent->in_max_high < interval_high(node))
384 parent->in_max_high = interval_high(node);
386 if (node_compare(node, parent) < 0)
387 p = &parent->in_left;
389 p = &parent->in_right;
392 /* link node into the tree */
393 node->in_parent = parent;
394 node->in_color = INTERVAL_RED;
395 node->in_left = node->in_right = NULL;
398 interval_insert_color(node, root);
403 EXPORT_SYMBOL(interval_insert);
405 static inline int node_is_black_or_0(struct interval_node *node)
407 return !node || node_is_black(node);
410 static void interval_erase_color(struct interval_node *node,
411 struct interval_node *parent,
412 struct interval_node **root)
414 struct interval_node *tmp;
418 while (node_is_black_or_0(node) && node != *root) {
419 if (parent->in_left == node) {
420 tmp = parent->in_right;
421 if (node_is_red(tmp)) {
422 tmp->in_color = INTERVAL_BLACK;
423 parent->in_color = INTERVAL_RED;
424 __rotate_left(parent, root);
425 tmp = parent->in_right;
427 if (node_is_black_or_0(tmp->in_left) &&
428 node_is_black_or_0(tmp->in_right)) {
429 tmp->in_color = INTERVAL_RED;
431 parent = node->in_parent;
433 if (node_is_black_or_0(tmp->in_right)) {
434 struct interval_node *o_left;
436 if ((o_left = tmp->in_left))
439 tmp->in_color = INTERVAL_RED;
440 __rotate_right(tmp, root);
441 tmp = parent->in_right;
443 tmp->in_color = parent->in_color;
444 parent->in_color = INTERVAL_BLACK;
446 tmp->in_right->in_color =
448 __rotate_left(parent, root);
453 tmp = parent->in_left;
454 if (node_is_red(tmp)) {
455 tmp->in_color = INTERVAL_BLACK;
456 parent->in_color = INTERVAL_RED;
457 __rotate_right(parent, root);
458 tmp = parent->in_left;
460 if (node_is_black_or_0(tmp->in_left) &&
461 node_is_black_or_0(tmp->in_right)) {
462 tmp->in_color = INTERVAL_RED;
464 parent = node->in_parent;
466 if (node_is_black_or_0(tmp->in_left)) {
467 struct interval_node *o_right;
469 if ((o_right = tmp->in_right))
472 tmp->in_color = INTERVAL_RED;
473 __rotate_left(tmp, root);
474 tmp = parent->in_left;
476 tmp->in_color = parent->in_color;
477 parent->in_color = INTERVAL_BLACK;
479 tmp->in_left->in_color = INTERVAL_BLACK;
480 __rotate_right(parent, root);
487 node->in_color = INTERVAL_BLACK;
492 * if the @max_high value of @node is changed, this function traverse a path
493 * from node up to the root to update max_high for the whole tree.
495 static void update_maxhigh(struct interval_node *node,
498 __u64 left_max, right_max;
503 left_max = node->in_left ? node->in_left->in_max_high : 0;
504 right_max = node->in_right ? node->in_right->in_max_high : 0;
505 node->in_max_high = max3(interval_high(node),
506 left_max, right_max);
508 if (node->in_max_high >= old_maxhigh)
510 node = node->in_parent;
515 void interval_erase(struct interval_node *node,
516 struct interval_node **root)
518 struct interval_node *child, *parent;
523 LASSERT(interval_is_intree(node));
525 if (!node->in_left) {
526 child = node->in_right;
527 } else if (!node->in_right) {
528 child = node->in_left;
529 } else { /* Both left and right child are not NULL */
530 struct interval_node *old = node;
532 node = interval_next(node);
533 child = node->in_right;
534 parent = node->in_parent;
535 color = node->in_color;
538 child->in_parent = parent;
540 parent->in_right = child;
542 parent->in_left = child;
544 node->in_color = old->in_color;
545 node->in_right = old->in_right;
546 node->in_left = old->in_left;
547 node->in_parent = old->in_parent;
549 if (old->in_parent) {
550 if (node_is_left_child(old))
551 old->in_parent->in_left = node;
553 old->in_parent->in_right = node;
558 old->in_left->in_parent = node;
560 old->in_right->in_parent = node;
561 update_maxhigh(child ? : parent, node->in_max_high);
562 update_maxhigh(node, old->in_max_high);
567 parent = node->in_parent;
568 color = node->in_color;
571 child->in_parent = parent;
573 if (node_is_left_child(node))
574 parent->in_left = child;
576 parent->in_right = child;
581 update_maxhigh(child ? : parent, node->in_max_high);
584 if (color == INTERVAL_BLACK)
585 interval_erase_color(child, parent, root);
588 EXPORT_SYMBOL(interval_erase);
590 static inline int interval_may_overlap(struct interval_node *node,
591 struct interval_node_extent *ext)
593 return (ext->start <= node->in_max_high &&
594 ext->end >= interval_low(node));
598 * This function finds all intervals that overlap interval ext,
599 * and calls func to handle resulted intervals one by one.
600 * in lustre, this function will find all conflicting locks in
601 * the granted queue and add these locks to the ast work list.
606 * if (ext->end < interval_low(node)) {
607 * interval_search(node->in_left, ext, func, data);
608 * } else if (interval_may_overlap(node, ext)) {
609 * if (extent_overlapped(ext, &node->in_extent))
611 * interval_search(node->in_left, ext, func, data);
612 * interval_search(node->in_right, ext, func, data);
618 enum interval_iter interval_search(struct interval_node *node,
619 struct interval_node_extent *ext,
620 interval_callback_t func,
623 struct interval_node *parent;
624 enum interval_iter rc = INTERVAL_ITER_CONT;
628 LASSERT(ext != NULL);
629 LASSERT(func != NULL);
632 if (ext->end < interval_low(node)) {
634 node = node->in_left;
637 } else if (interval_may_overlap(node, ext)) {
638 if (extent_overlapped(ext, &node->in_extent)) {
639 rc = func(node, data);
640 if (rc == INTERVAL_ITER_STOP)
645 node = node->in_left;
648 if (node->in_right) {
649 node = node->in_right;
654 parent = node->in_parent;
656 if (node_is_left_child(node) &&
658 /* If we ever got the left, it means that the
659 * parent met ext->end<interval_low(parent), or
660 * may_overlap(parent). If the former is true,
661 * we needn't go back. So stop early and check
662 * may_overlap(parent) after this loop.
664 node = parent->in_right;
668 parent = parent->in_parent;
670 if (parent == NULL || !interval_may_overlap(parent, ext))
676 EXPORT_SYMBOL(interval_search);
678 static enum interval_iter interval_overlap_cb(struct interval_node *n,
682 return INTERVAL_ITER_STOP;
685 int interval_is_overlapped(struct interval_node *root,
686 struct interval_node_extent *ext)
689 (void)interval_search(root, ext, interval_overlap_cb, &has);
692 EXPORT_SYMBOL(interval_is_overlapped);
694 /* Don't expand to low. Expanding downwards is expensive, and meaningless to
695 * some extents, because programs seldom do IO backward.
697 * The recursive algorithm of expanding low:
699 * struct interval_node *tmp;
700 * static __u64 res = 0;
704 * if (root->in_max_high < low) {
705 * res = max(root->in_max_high + 1, res);
707 * } else if (low < interval_low(root)) {
708 * interval_expand_low(root->in_left, low);
712 * if (interval_high(root) < low)
713 * res = max(interval_high(root) + 1, res);
714 * interval_expand_low(root->in_left, low);
715 * interval_expand_low(root->in_right, low);
720 * It's much easy to eliminate the recursion, see interval_search for
723 static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
725 /* we only concern the empty tree right now. */
731 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
735 while (node != NULL) {
736 if (node->in_max_high < high)
739 if (interval_low(node) > high) {
740 result = interval_low(node) - 1;
741 node = node->in_left;
743 node = node->in_right;
750 /* expanding the extent based on @ext. */
751 void interval_expand(struct interval_node *root,
752 struct interval_node_extent *ext,
753 struct interval_node_extent *limiter)
755 /* The assertion of interval_is_overlapped is expensive because we may
756 * travel many nodes to find the overlapped node.
758 LASSERT(interval_is_overlapped(root, ext) == 0);
759 if (!limiter || limiter->start < ext->start)
760 ext->start = interval_expand_low(root, ext->start);
761 if (!limiter || limiter->end > ext->end)
762 ext->end = interval_expand_high(root, ext->end);
763 LASSERT(interval_is_overlapped(root, ext) == 0);
765 EXPORT_SYMBOL(interval_expand);