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 __u64 max_u64(__u64 x, __u64 y)
98 static struct interval_node *interval_first(struct interval_node *node)
102 while (node->in_left)
103 node = node->in_left;
107 static struct interval_node *interval_next(struct interval_node *node)
112 return interval_first(node->in_right);
113 while (node->in_parent && node_is_right_child(node))
114 node = node->in_parent;
115 return node->in_parent;
118 static void __rotate_change_maxhigh(struct interval_node *node,
119 struct interval_node *rotate)
121 __u64 left_max, right_max;
123 rotate->in_max_high = node->in_max_high;
124 left_max = node->in_left ? node->in_left->in_max_high : 0;
125 right_max = node->in_right ? node->in_right->in_max_high : 0;
126 node->in_max_high = max_u64(interval_high(node),
127 max_u64(left_max, right_max));
130 /* The left rotation "pivots" around the link from node to node->right, and
131 * - node will be linked to node->right's left child, and
132 * - node->right's left child will be linked to node's right child.
134 static void __rotate_left(struct interval_node *node,
135 struct interval_node **root)
137 struct interval_node *right = node->in_right;
138 struct interval_node *parent = node->in_parent;
140 node->in_right = right->in_left;
142 right->in_left->in_parent = node;
144 right->in_left = node;
145 right->in_parent = parent;
147 if (node_is_left_child(node))
148 parent->in_left = right;
150 parent->in_right = right;
154 node->in_parent = right;
156 /* update max_high for node and right */
157 __rotate_change_maxhigh(node, right);
160 /* The right rotation "pivots" around the link from node to node->left, and
161 * - node will be linked to node->left's right child, and
162 * - node->left's right child will be linked to node's left child.
164 static void __rotate_right(struct interval_node *node,
165 struct interval_node **root)
167 struct interval_node *left = node->in_left;
168 struct interval_node *parent = node->in_parent;
170 node->in_left = left->in_right;
172 left->in_right->in_parent = node;
173 left->in_right = node;
175 left->in_parent = parent;
177 if (node_is_right_child(node))
178 parent->in_right = left;
180 parent->in_left = left;
184 node->in_parent = left;
186 /* update max_high for node and left */
187 __rotate_change_maxhigh(node, left);
190 #define interval_swap(a, b) do { \
191 struct interval_node *c = a; a = b; b = c; \
195 * Operations INSERT and DELETE, when run on a tree with n keys,
196 * take O(logN) time.Because they modify the tree, the result
197 * may violate the red-black properties.To restore these properties,
198 * we must change the colors of some of the nodes in the tree
199 * and also change the pointer structure.
201 static void interval_insert_color(struct interval_node *node,
202 struct interval_node **root)
204 struct interval_node *parent, *gparent;
206 while ((parent = node->in_parent) && node_is_red(parent)) {
207 gparent = parent->in_parent;
208 /* Parent is RED, so gparent must not be NULL */
209 if (node_is_left_child(parent)) {
210 struct interval_node *uncle;
212 uncle = gparent->in_right;
213 if (uncle && node_is_red(uncle)) {
214 uncle->in_color = INTERVAL_BLACK;
215 parent->in_color = INTERVAL_BLACK;
216 gparent->in_color = INTERVAL_RED;
221 if (parent->in_right == node) {
222 __rotate_left(parent, root);
223 interval_swap(node, parent);
226 parent->in_color = INTERVAL_BLACK;
227 gparent->in_color = INTERVAL_RED;
228 __rotate_right(gparent, root);
230 struct interval_node *uncle;
232 uncle = gparent->in_left;
233 if (uncle && node_is_red(uncle)) {
234 uncle->in_color = INTERVAL_BLACK;
235 parent->in_color = INTERVAL_BLACK;
236 gparent->in_color = INTERVAL_RED;
241 if (node_is_left_child(node)) {
242 __rotate_right(parent, root);
243 interval_swap(node, parent);
246 parent->in_color = INTERVAL_BLACK;
247 gparent->in_color = INTERVAL_RED;
248 __rotate_left(gparent, root);
252 (*root)->in_color = INTERVAL_BLACK;
255 struct interval_node *interval_insert(struct interval_node *node,
256 struct interval_node **root)
259 struct interval_node **p, *parent = NULL;
261 LASSERT(!interval_is_intree(node));
265 if (extent_equal(&parent->in_extent, &node->in_extent))
268 /* max_high field must be updated after each iteration */
269 if (parent->in_max_high < interval_high(node))
270 parent->in_max_high = interval_high(node);
272 if (extent_compare(&node->in_extent, &parent->in_extent) < 0)
273 p = &parent->in_left;
275 p = &parent->in_right;
278 /* link node into the tree */
279 node->in_parent = parent;
280 node->in_color = INTERVAL_RED;
281 node->in_left = NULL;
282 node->in_right = NULL;
285 interval_insert_color(node, root);
290 EXPORT_SYMBOL(interval_insert);
292 static inline int node_is_black_or_0(struct interval_node *node)
294 return !node || node_is_black(node);
297 static void interval_erase_color(struct interval_node *node,
298 struct interval_node *parent,
299 struct interval_node **root)
301 struct interval_node *tmp;
303 while (node_is_black_or_0(node) && node != *root) {
304 if (parent->in_left == node) {
305 tmp = parent->in_right;
306 if (node_is_red(tmp)) {
307 tmp->in_color = INTERVAL_BLACK;
308 parent->in_color = INTERVAL_RED;
309 __rotate_left(parent, root);
310 tmp = parent->in_right;
312 if (node_is_black_or_0(tmp->in_left) &&
313 node_is_black_or_0(tmp->in_right)) {
314 tmp->in_color = INTERVAL_RED;
316 parent = node->in_parent;
318 if (node_is_black_or_0(tmp->in_right)) {
319 struct interval_node *o_left;
321 o_left = tmp->in_left;
323 o_left->in_color = INTERVAL_BLACK;
324 tmp->in_color = INTERVAL_RED;
325 __rotate_right(tmp, root);
326 tmp = parent->in_right;
328 tmp->in_color = parent->in_color;
329 parent->in_color = INTERVAL_BLACK;
331 tmp->in_right->in_color = INTERVAL_BLACK;
332 __rotate_left(parent, root);
337 tmp = parent->in_left;
338 if (node_is_red(tmp)) {
339 tmp->in_color = INTERVAL_BLACK;
340 parent->in_color = INTERVAL_RED;
341 __rotate_right(parent, root);
342 tmp = parent->in_left;
344 if (node_is_black_or_0(tmp->in_left) &&
345 node_is_black_or_0(tmp->in_right)) {
346 tmp->in_color = INTERVAL_RED;
348 parent = node->in_parent;
350 if (node_is_black_or_0(tmp->in_left)) {
351 struct interval_node *o_right;
353 o_right = tmp->in_right;
355 o_right->in_color = INTERVAL_BLACK;
356 tmp->in_color = INTERVAL_RED;
357 __rotate_left(tmp, root);
358 tmp = parent->in_left;
360 tmp->in_color = parent->in_color;
361 parent->in_color = INTERVAL_BLACK;
363 tmp->in_left->in_color = INTERVAL_BLACK;
364 __rotate_right(parent, root);
371 node->in_color = INTERVAL_BLACK;
375 * if the @max_high value of @node is changed, this function traverse a path
376 * from node up to the root to update max_high for the whole tree.
378 static void update_maxhigh(struct interval_node *node,
381 __u64 left_max, right_max;
384 left_max = node->in_left ? node->in_left->in_max_high : 0;
385 right_max = node->in_right ? node->in_right->in_max_high : 0;
386 node->in_max_high = max_u64(interval_high(node),
387 max_u64(left_max, right_max));
389 if (node->in_max_high >= old_maxhigh)
391 node = node->in_parent;
395 void interval_erase(struct interval_node *node,
396 struct interval_node **root)
398 struct interval_node *child, *parent;
401 LASSERT(interval_is_intree(node));
403 if (!node->in_left) {
404 child = node->in_right;
405 } else if (!node->in_right) {
406 child = node->in_left;
407 } else { /* Both left and right child are not NULL */
408 struct interval_node *old = node;
410 node = interval_next(node);
411 child = node->in_right;
412 parent = node->in_parent;
413 color = node->in_color;
416 child->in_parent = parent;
418 parent->in_right = child;
420 parent->in_left = child;
422 node->in_color = old->in_color;
423 node->in_right = old->in_right;
424 node->in_left = old->in_left;
425 node->in_parent = old->in_parent;
427 if (old->in_parent) {
428 if (node_is_left_child(old))
429 old->in_parent->in_left = node;
431 old->in_parent->in_right = node;
436 old->in_left->in_parent = node;
438 old->in_right->in_parent = node;
439 update_maxhigh(child ? : parent, node->in_max_high);
440 update_maxhigh(node, old->in_max_high);
445 parent = node->in_parent;
446 color = node->in_color;
449 child->in_parent = parent;
451 if (node_is_left_child(node))
452 parent->in_left = child;
454 parent->in_right = child;
459 update_maxhigh(child ? : parent, node->in_max_high);
462 if (color == INTERVAL_BLACK)
463 interval_erase_color(child, parent, root);
465 EXPORT_SYMBOL(interval_erase);