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.
27 * This file is part of Lustre, http://www.lustre.org/
28 * Lustre is a trademark of Sun Microsystems, Inc.
30 * lustre/ldlm/interval_tree.c
32 * Interval tree library used by ldlm extent lock code
34 * Author: Huang Wei <huangwei@clusterfs.com>
35 * Author: Jay Xiong <jinshan.xiong@sun.com>
37 #include "../include/lustre_dlm.h"
38 #include "../include/obd_support.h"
39 #include "../include/interval_tree.h"
46 static inline int node_is_left_child(struct interval_node *node)
48 return node == node->in_parent->in_left;
51 static inline int node_is_right_child(struct interval_node *node)
53 return node == node->in_parent->in_right;
56 static inline int node_is_red(struct interval_node *node)
58 return node->in_color == INTERVAL_RED;
61 static inline int node_is_black(struct interval_node *node)
63 return node->in_color == INTERVAL_BLACK;
66 static inline int extent_compare(struct interval_node_extent *e1,
67 struct interval_node_extent *e2)
71 if (e1->start == e2->start) {
72 if (e1->end < e2->end)
74 else if (e1->end > e2->end)
79 if (e1->start < e2->start)
87 static inline int extent_equal(struct interval_node_extent *e1,
88 struct interval_node_extent *e2)
90 return (e1->start == e2->start) && (e1->end == e2->end);
93 static inline int extent_overlapped(struct interval_node_extent *e1,
94 struct interval_node_extent *e2)
96 return (e1->start <= e2->end) && (e2->start <= e1->end);
99 static inline int node_equal(struct interval_node *n1, struct interval_node *n2)
101 return extent_equal(&n1->in_extent, &n2->in_extent);
104 static inline __u64 max_u64(__u64 x, __u64 y)
106 return x > y ? x : y;
109 static struct interval_node *interval_first(struct interval_node *node)
113 while (node->in_left)
114 node = node->in_left;
118 static struct interval_node *interval_next(struct interval_node *node)
123 return interval_first(node->in_right);
124 while (node->in_parent && node_is_right_child(node))
125 node = node->in_parent;
126 return node->in_parent;
129 static void __rotate_change_maxhigh(struct interval_node *node,
130 struct interval_node *rotate)
132 __u64 left_max, right_max;
134 rotate->in_max_high = node->in_max_high;
135 left_max = node->in_left ? node->in_left->in_max_high : 0;
136 right_max = node->in_right ? node->in_right->in_max_high : 0;
137 node->in_max_high = max_u64(interval_high(node),
138 max_u64(left_max, right_max));
141 /* The left rotation "pivots" around the link from node to node->right, and
142 * - node will be linked to node->right's left child, and
143 * - node->right's left child will be linked to node's right child.
145 static void __rotate_left(struct interval_node *node,
146 struct interval_node **root)
148 struct interval_node *right = node->in_right;
149 struct interval_node *parent = node->in_parent;
151 node->in_right = right->in_left;
153 right->in_left->in_parent = node;
155 right->in_left = node;
156 right->in_parent = parent;
158 if (node_is_left_child(node))
159 parent->in_left = right;
161 parent->in_right = right;
165 node->in_parent = right;
167 /* update max_high for node and right */
168 __rotate_change_maxhigh(node, right);
171 /* The right rotation "pivots" around the link from node to node->left, and
172 * - node will be linked to node->left's right child, and
173 * - node->left's right child will be linked to node's left child.
175 static void __rotate_right(struct interval_node *node,
176 struct interval_node **root)
178 struct interval_node *left = node->in_left;
179 struct interval_node *parent = node->in_parent;
181 node->in_left = left->in_right;
183 left->in_right->in_parent = node;
184 left->in_right = node;
186 left->in_parent = parent;
188 if (node_is_right_child(node))
189 parent->in_right = left;
191 parent->in_left = left;
195 node->in_parent = left;
197 /* update max_high for node and left */
198 __rotate_change_maxhigh(node, left);
201 #define interval_swap(a, b) do { \
202 struct interval_node *c = a; a = b; b = c; \
206 * Operations INSERT and DELETE, when run on a tree with n keys,
207 * take O(logN) time.Because they modify the tree, the result
208 * may violate the red-black properties.To restore these properties,
209 * we must change the colors of some of the nodes in the tree
210 * and also change the pointer structure.
212 static void interval_insert_color(struct interval_node *node,
213 struct interval_node **root)
215 struct interval_node *parent, *gparent;
217 while ((parent = node->in_parent) && node_is_red(parent)) {
218 gparent = parent->in_parent;
219 /* Parent is RED, so gparent must not be NULL */
220 if (node_is_left_child(parent)) {
221 struct interval_node *uncle;
223 uncle = gparent->in_right;
224 if (uncle && node_is_red(uncle)) {
225 uncle->in_color = INTERVAL_BLACK;
226 parent->in_color = INTERVAL_BLACK;
227 gparent->in_color = INTERVAL_RED;
232 if (parent->in_right == node) {
233 __rotate_left(parent, root);
234 interval_swap(node, parent);
237 parent->in_color = INTERVAL_BLACK;
238 gparent->in_color = INTERVAL_RED;
239 __rotate_right(gparent, root);
241 struct interval_node *uncle;
243 uncle = gparent->in_left;
244 if (uncle && node_is_red(uncle)) {
245 uncle->in_color = INTERVAL_BLACK;
246 parent->in_color = INTERVAL_BLACK;
247 gparent->in_color = INTERVAL_RED;
252 if (node_is_left_child(node)) {
253 __rotate_right(parent, root);
254 interval_swap(node, parent);
257 parent->in_color = INTERVAL_BLACK;
258 gparent->in_color = INTERVAL_RED;
259 __rotate_left(gparent, root);
263 (*root)->in_color = INTERVAL_BLACK;
266 struct interval_node *interval_insert(struct interval_node *node,
267 struct interval_node **root)
270 struct interval_node **p, *parent = NULL;
272 LASSERT(!interval_is_intree(node));
276 if (node_equal(parent, node))
279 /* max_high field must be updated after each iteration */
280 if (parent->in_max_high < interval_high(node))
281 parent->in_max_high = interval_high(node);
283 if (extent_compare(&node->in_extent, &parent->in_extent) < 0)
284 p = &parent->in_left;
286 p = &parent->in_right;
289 /* link node into the tree */
290 node->in_parent = parent;
291 node->in_color = INTERVAL_RED;
292 node->in_left = NULL;
293 node->in_right = NULL;
296 interval_insert_color(node, root);
301 EXPORT_SYMBOL(interval_insert);
303 static inline int node_is_black_or_0(struct interval_node *node)
305 return !node || node_is_black(node);
308 static void interval_erase_color(struct interval_node *node,
309 struct interval_node *parent,
310 struct interval_node **root)
312 struct interval_node *tmp;
314 while (node_is_black_or_0(node) && node != *root) {
315 if (parent->in_left == node) {
316 tmp = parent->in_right;
317 if (node_is_red(tmp)) {
318 tmp->in_color = INTERVAL_BLACK;
319 parent->in_color = INTERVAL_RED;
320 __rotate_left(parent, root);
321 tmp = parent->in_right;
323 if (node_is_black_or_0(tmp->in_left) &&
324 node_is_black_or_0(tmp->in_right)) {
325 tmp->in_color = INTERVAL_RED;
327 parent = node->in_parent;
329 if (node_is_black_or_0(tmp->in_right)) {
330 struct interval_node *o_left;
332 o_left = tmp->in_left;
334 o_left->in_color = INTERVAL_BLACK;
335 tmp->in_color = INTERVAL_RED;
336 __rotate_right(tmp, root);
337 tmp = parent->in_right;
339 tmp->in_color = parent->in_color;
340 parent->in_color = INTERVAL_BLACK;
342 tmp->in_right->in_color = INTERVAL_BLACK;
343 __rotate_left(parent, root);
348 tmp = parent->in_left;
349 if (node_is_red(tmp)) {
350 tmp->in_color = INTERVAL_BLACK;
351 parent->in_color = INTERVAL_RED;
352 __rotate_right(parent, root);
353 tmp = parent->in_left;
355 if (node_is_black_or_0(tmp->in_left) &&
356 node_is_black_or_0(tmp->in_right)) {
357 tmp->in_color = INTERVAL_RED;
359 parent = node->in_parent;
361 if (node_is_black_or_0(tmp->in_left)) {
362 struct interval_node *o_right;
364 o_right = tmp->in_right;
366 o_right->in_color = INTERVAL_BLACK;
367 tmp->in_color = INTERVAL_RED;
368 __rotate_left(tmp, root);
369 tmp = parent->in_left;
371 tmp->in_color = parent->in_color;
372 parent->in_color = INTERVAL_BLACK;
374 tmp->in_left->in_color = INTERVAL_BLACK;
375 __rotate_right(parent, root);
382 node->in_color = INTERVAL_BLACK;
386 * if the @max_high value of @node is changed, this function traverse a path
387 * from node up to the root to update max_high for the whole tree.
389 static void update_maxhigh(struct interval_node *node,
392 __u64 left_max, right_max;
395 left_max = node->in_left ? node->in_left->in_max_high : 0;
396 right_max = node->in_right ? node->in_right->in_max_high : 0;
397 node->in_max_high = max_u64(interval_high(node),
398 max_u64(left_max, right_max));
400 if (node->in_max_high >= old_maxhigh)
402 node = node->in_parent;
406 void interval_erase(struct interval_node *node,
407 struct interval_node **root)
409 struct interval_node *child, *parent;
412 LASSERT(interval_is_intree(node));
414 if (!node->in_left) {
415 child = node->in_right;
416 } else if (!node->in_right) {
417 child = node->in_left;
418 } else { /* Both left and right child are not NULL */
419 struct interval_node *old = node;
421 node = interval_next(node);
422 child = node->in_right;
423 parent = node->in_parent;
424 color = node->in_color;
427 child->in_parent = parent;
429 parent->in_right = child;
431 parent->in_left = child;
433 node->in_color = old->in_color;
434 node->in_right = old->in_right;
435 node->in_left = old->in_left;
436 node->in_parent = old->in_parent;
438 if (old->in_parent) {
439 if (node_is_left_child(old))
440 old->in_parent->in_left = node;
442 old->in_parent->in_right = node;
447 old->in_left->in_parent = node;
449 old->in_right->in_parent = node;
450 update_maxhigh(child ? : parent, node->in_max_high);
451 update_maxhigh(node, old->in_max_high);
456 parent = node->in_parent;
457 color = node->in_color;
460 child->in_parent = parent;
462 if (node_is_left_child(node))
463 parent->in_left = child;
465 parent->in_right = child;
470 update_maxhigh(child ? : parent, node->in_max_high);
473 if (color == INTERVAL_BLACK)
474 interval_erase_color(child, parent, root);
476 EXPORT_SYMBOL(interval_erase);
478 static inline int interval_may_overlap(struct interval_node *node,
479 struct interval_node_extent *ext)
481 return (ext->start <= node->in_max_high &&
482 ext->end >= interval_low(node));
486 * This function finds all intervals that overlap interval ext,
487 * and calls func to handle resulted intervals one by one.
488 * in lustre, this function will find all conflicting locks in
489 * the granted queue and add these locks to the ast work list.
494 * if (ext->end < interval_low(node)) {
495 * interval_search(node->in_left, ext, func, data);
496 * } else if (interval_may_overlap(node, ext)) {
497 * if (extent_overlapped(ext, &node->in_extent))
499 * interval_search(node->in_left, ext, func, data);
500 * interval_search(node->in_right, ext, func, data);
506 enum interval_iter interval_search(struct interval_node *node,
507 struct interval_node_extent *ext,
508 interval_callback_t func,
511 enum interval_iter rc = INTERVAL_ITER_CONT;
512 struct interval_node *parent;
518 if (ext->end < interval_low(node)) {
520 node = node->in_left;
523 } else if (interval_may_overlap(node, ext)) {
524 if (extent_overlapped(ext, &node->in_extent)) {
525 rc = func(node, data);
526 if (rc == INTERVAL_ITER_STOP)
531 node = node->in_left;
534 if (node->in_right) {
535 node = node->in_right;
540 parent = node->in_parent;
542 if (node_is_left_child(node) &&
545 * If we ever got the left, it means that the
546 * parent met ext->end<interval_low(parent), or
547 * may_overlap(parent). If the former is true,
548 * we needn't go back. So stop early and check
549 * may_overlap(parent) after this loop.
551 node = parent->in_right;
555 parent = parent->in_parent;
557 if (!parent || !interval_may_overlap(parent, ext))
563 EXPORT_SYMBOL(interval_search);