1 /*
2 * GPL HEADER START
3 *
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
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.
9 *
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).
15 *
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
19 *
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
22 * have any questions.
23 *
24 * GPL HEADER END
25 */
26 /*
27 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
29 */
30 /*
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
33 *
34 * lustre/ldlm/interval_tree.c
35 *
36 * Interval tree library used by ldlm extent lock code
37 *
38 * Author: Huang Wei <huangwei@clusterfs.com>
39 * Author: Jay Xiong <jinshan.xiong@sun.com>
40 */
41 #include "../include/lustre_dlm.h"
42 #include "../include/obd_support.h"
43 #include "../include/interval_tree.h"
44
45 enum {
46 INTERVAL_RED = 0,
47 INTERVAL_BLACK = 1
48 };
49
node_is_left_child(struct interval_node * node)50 static inline int node_is_left_child(struct interval_node *node)
51 {
52 LASSERT(node->in_parent != NULL);
53 return node == node->in_parent->in_left;
54 }
55
node_is_right_child(struct interval_node * node)56 static inline int node_is_right_child(struct interval_node *node)
57 {
58 LASSERT(node->in_parent != NULL);
59 return node == node->in_parent->in_right;
60 }
61
node_is_red(struct interval_node * node)62 static inline int node_is_red(struct interval_node *node)
63 {
64 return node->in_color == INTERVAL_RED;
65 }
66
node_is_black(struct interval_node * node)67 static inline int node_is_black(struct interval_node *node)
68 {
69 return node->in_color == INTERVAL_BLACK;
70 }
71
extent_compare(struct interval_node_extent * e1,struct interval_node_extent * e2)72 static inline int extent_compare(struct interval_node_extent *e1,
73 struct interval_node_extent *e2)
74 {
75 int rc;
76
77 if (e1->start == e2->start) {
78 if (e1->end < e2->end)
79 rc = -1;
80 else if (e1->end > e2->end)
81 rc = 1;
82 else
83 rc = 0;
84 } else {
85 if (e1->start < e2->start)
86 rc = -1;
87 else
88 rc = 1;
89 }
90 return rc;
91 }
92
extent_equal(struct interval_node_extent * e1,struct interval_node_extent * e2)93 static inline int extent_equal(struct interval_node_extent *e1,
94 struct interval_node_extent *e2)
95 {
96 return (e1->start == e2->start) && (e1->end == e2->end);
97 }
98
node_compare(struct interval_node * n1,struct interval_node * n2)99 static inline int node_compare(struct interval_node *n1,
100 struct interval_node *n2)
101 {
102 return extent_compare(&n1->in_extent, &n2->in_extent);
103 }
104
node_equal(struct interval_node * n1,struct interval_node * n2)105 static inline int node_equal(struct interval_node *n1,
106 struct interval_node *n2)
107 {
108 return extent_equal(&n1->in_extent, &n2->in_extent);
109 }
110
max_u64(__u64 x,__u64 y)111 static inline __u64 max_u64(__u64 x, __u64 y)
112 {
113 return x > y ? x : y;
114 }
115
interval_first(struct interval_node * node)116 static struct interval_node *interval_first(struct interval_node *node)
117 {
118 if (!node)
119 return NULL;
120 while (node->in_left)
121 node = node->in_left;
122 return node;
123 }
124
interval_next(struct interval_node * node)125 static struct interval_node *interval_next(struct interval_node *node)
126 {
127 if (!node)
128 return NULL;
129 if (node->in_right)
130 return interval_first(node->in_right);
131 while (node->in_parent && node_is_right_child(node))
132 node = node->in_parent;
133 return node->in_parent;
134 }
135
__rotate_change_maxhigh(struct interval_node * node,struct interval_node * rotate)136 static void __rotate_change_maxhigh(struct interval_node *node,
137 struct interval_node *rotate)
138 {
139 __u64 left_max, right_max;
140
141 rotate->in_max_high = node->in_max_high;
142 left_max = node->in_left ? node->in_left->in_max_high : 0;
143 right_max = node->in_right ? node->in_right->in_max_high : 0;
144 node->in_max_high = max_u64(interval_high(node),
145 max_u64(left_max, right_max));
146 }
147
148 /* The left rotation "pivots" around the link from node to node->right, and
149 * - node will be linked to node->right's left child, and
150 * - node->right's left child will be linked to node's right child. */
__rotate_left(struct interval_node * node,struct interval_node ** root)151 static void __rotate_left(struct interval_node *node,
152 struct interval_node **root)
153 {
154 struct interval_node *right = node->in_right;
155 struct interval_node *parent = node->in_parent;
156
157 node->in_right = right->in_left;
158 if (node->in_right)
159 right->in_left->in_parent = node;
160
161 right->in_left = node;
162 right->in_parent = parent;
163 if (parent) {
164 if (node_is_left_child(node))
165 parent->in_left = right;
166 else
167 parent->in_right = right;
168 } else {
169 *root = right;
170 }
171 node->in_parent = right;
172
173 /* update max_high for node and right */
174 __rotate_change_maxhigh(node, right);
175 }
176
177 /* The right rotation "pivots" around the link from node to node->left, and
178 * - node will be linked to node->left's right child, and
179 * - node->left's right child will be linked to node's left child. */
__rotate_right(struct interval_node * node,struct interval_node ** root)180 static void __rotate_right(struct interval_node *node,
181 struct interval_node **root)
182 {
183 struct interval_node *left = node->in_left;
184 struct interval_node *parent = node->in_parent;
185
186 node->in_left = left->in_right;
187 if (node->in_left)
188 left->in_right->in_parent = node;
189 left->in_right = node;
190
191 left->in_parent = parent;
192 if (parent) {
193 if (node_is_right_child(node))
194 parent->in_right = left;
195 else
196 parent->in_left = left;
197 } else {
198 *root = left;
199 }
200 node->in_parent = left;
201
202 /* update max_high for node and left */
203 __rotate_change_maxhigh(node, left);
204 }
205
206 #define interval_swap(a, b) do { \
207 struct interval_node *c = a; a = b; b = c; \
208 } while (0)
209
210 /*
211 * Operations INSERT and DELETE, when run on a tree with n keys,
212 * take O(logN) time.Because they modify the tree, the result
213 * may violate the red-black properties.To restore these properties,
214 * we must change the colors of some of the nodes in the tree
215 * and also change the pointer structure.
216 */
interval_insert_color(struct interval_node * node,struct interval_node ** root)217 static void interval_insert_color(struct interval_node *node,
218 struct interval_node **root)
219 {
220 struct interval_node *parent, *gparent;
221
222 while ((parent = node->in_parent) && node_is_red(parent)) {
223 gparent = parent->in_parent;
224 /* Parent is RED, so gparent must not be NULL */
225 if (node_is_left_child(parent)) {
226 struct interval_node *uncle;
227
228 uncle = gparent->in_right;
229 if (uncle && node_is_red(uncle)) {
230 uncle->in_color = INTERVAL_BLACK;
231 parent->in_color = INTERVAL_BLACK;
232 gparent->in_color = INTERVAL_RED;
233 node = gparent;
234 continue;
235 }
236
237 if (parent->in_right == node) {
238 __rotate_left(parent, root);
239 interval_swap(node, parent);
240 }
241
242 parent->in_color = INTERVAL_BLACK;
243 gparent->in_color = INTERVAL_RED;
244 __rotate_right(gparent, root);
245 } else {
246 struct interval_node *uncle;
247
248 uncle = gparent->in_left;
249 if (uncle && node_is_red(uncle)) {
250 uncle->in_color = INTERVAL_BLACK;
251 parent->in_color = INTERVAL_BLACK;
252 gparent->in_color = INTERVAL_RED;
253 node = gparent;
254 continue;
255 }
256
257 if (node_is_left_child(node)) {
258 __rotate_right(parent, root);
259 interval_swap(node, parent);
260 }
261
262 parent->in_color = INTERVAL_BLACK;
263 gparent->in_color = INTERVAL_RED;
264 __rotate_left(gparent, root);
265 }
266 }
267
268 (*root)->in_color = INTERVAL_BLACK;
269 }
270
interval_insert(struct interval_node * node,struct interval_node ** root)271 struct interval_node *interval_insert(struct interval_node *node,
272 struct interval_node **root)
273
274 {
275 struct interval_node **p, *parent = NULL;
276
277 LASSERT(!interval_is_intree(node));
278 p = root;
279 while (*p) {
280 parent = *p;
281 if (node_equal(parent, node))
282 return parent;
283
284 /* max_high field must be updated after each iteration */
285 if (parent->in_max_high < interval_high(node))
286 parent->in_max_high = interval_high(node);
287
288 if (node_compare(node, parent) < 0)
289 p = &parent->in_left;
290 else
291 p = &parent->in_right;
292 }
293
294 /* link node into the tree */
295 node->in_parent = parent;
296 node->in_color = INTERVAL_RED;
297 node->in_left = NULL;
298 node->in_right = NULL;
299 *p = node;
300
301 interval_insert_color(node, root);
302 node->in_intree = 1;
303
304 return NULL;
305 }
306 EXPORT_SYMBOL(interval_insert);
307
node_is_black_or_0(struct interval_node * node)308 static inline int node_is_black_or_0(struct interval_node *node)
309 {
310 return !node || node_is_black(node);
311 }
312
interval_erase_color(struct interval_node * node,struct interval_node * parent,struct interval_node ** root)313 static void interval_erase_color(struct interval_node *node,
314 struct interval_node *parent,
315 struct interval_node **root)
316 {
317 struct interval_node *tmp;
318
319 while (node_is_black_or_0(node) && node != *root) {
320 if (parent->in_left == node) {
321 tmp = parent->in_right;
322 if (node_is_red(tmp)) {
323 tmp->in_color = INTERVAL_BLACK;
324 parent->in_color = INTERVAL_RED;
325 __rotate_left(parent, root);
326 tmp = parent->in_right;
327 }
328 if (node_is_black_or_0(tmp->in_left) &&
329 node_is_black_or_0(tmp->in_right)) {
330 tmp->in_color = INTERVAL_RED;
331 node = parent;
332 parent = node->in_parent;
333 } else {
334 if (node_is_black_or_0(tmp->in_right)) {
335 struct interval_node *o_left;
336
337 o_left = tmp->in_left;
338 if (o_left)
339 o_left->in_color = INTERVAL_BLACK;
340 tmp->in_color = INTERVAL_RED;
341 __rotate_right(tmp, root);
342 tmp = parent->in_right;
343 }
344 tmp->in_color = parent->in_color;
345 parent->in_color = INTERVAL_BLACK;
346 if (tmp->in_right)
347 tmp->in_right->in_color = INTERVAL_BLACK;
348 __rotate_left(parent, root);
349 node = *root;
350 break;
351 }
352 } else {
353 tmp = parent->in_left;
354 if (node_is_red(tmp)) {
355 tmp->in_color = INTERVAL_BLACK;
356 parent->in_color = INTERVAL_RED;
357 __rotate_right(parent, root);
358 tmp = parent->in_left;
359 }
360 if (node_is_black_or_0(tmp->in_left) &&
361 node_is_black_or_0(tmp->in_right)) {
362 tmp->in_color = INTERVAL_RED;
363 node = parent;
364 parent = node->in_parent;
365 } else {
366 if (node_is_black_or_0(tmp->in_left)) {
367 struct interval_node *o_right;
368
369 o_right = tmp->in_right;
370 if (o_right)
371 o_right->in_color = INTERVAL_BLACK;
372 tmp->in_color = INTERVAL_RED;
373 __rotate_left(tmp, root);
374 tmp = parent->in_left;
375 }
376 tmp->in_color = parent->in_color;
377 parent->in_color = INTERVAL_BLACK;
378 if (tmp->in_left)
379 tmp->in_left->in_color = INTERVAL_BLACK;
380 __rotate_right(parent, root);
381 node = *root;
382 break;
383 }
384 }
385 }
386 if (node)
387 node->in_color = INTERVAL_BLACK;
388 }
389
390 /*
391 * if the @max_high value of @node is changed, this function traverse a path
392 * from node up to the root to update max_high for the whole tree.
393 */
update_maxhigh(struct interval_node * node,__u64 old_maxhigh)394 static void update_maxhigh(struct interval_node *node,
395 __u64 old_maxhigh)
396 {
397 __u64 left_max, right_max;
398
399 while (node) {
400 left_max = node->in_left ? node->in_left->in_max_high : 0;
401 right_max = node->in_right ? node->in_right->in_max_high : 0;
402 node->in_max_high = max_u64(interval_high(node),
403 max_u64(left_max, right_max));
404
405 if (node->in_max_high >= old_maxhigh)
406 break;
407 node = node->in_parent;
408 }
409 }
410
interval_erase(struct interval_node * node,struct interval_node ** root)411 void interval_erase(struct interval_node *node,
412 struct interval_node **root)
413 {
414 struct interval_node *child, *parent;
415 int color;
416
417 LASSERT(interval_is_intree(node));
418 node->in_intree = 0;
419 if (!node->in_left) {
420 child = node->in_right;
421 } else if (!node->in_right) {
422 child = node->in_left;
423 } else { /* Both left and right child are not NULL */
424 struct interval_node *old = node;
425
426 node = interval_next(node);
427 child = node->in_right;
428 parent = node->in_parent;
429 color = node->in_color;
430
431 if (child)
432 child->in_parent = parent;
433 if (parent == old)
434 parent->in_right = child;
435 else
436 parent->in_left = child;
437
438 node->in_color = old->in_color;
439 node->in_right = old->in_right;
440 node->in_left = old->in_left;
441 node->in_parent = old->in_parent;
442
443 if (old->in_parent) {
444 if (node_is_left_child(old))
445 old->in_parent->in_left = node;
446 else
447 old->in_parent->in_right = node;
448 } else {
449 *root = node;
450 }
451
452 old->in_left->in_parent = node;
453 if (old->in_right)
454 old->in_right->in_parent = node;
455 update_maxhigh(child ? : parent, node->in_max_high);
456 update_maxhigh(node, old->in_max_high);
457 if (parent == old)
458 parent = node;
459 goto color;
460 }
461 parent = node->in_parent;
462 color = node->in_color;
463
464 if (child)
465 child->in_parent = parent;
466 if (parent) {
467 if (node_is_left_child(node))
468 parent->in_left = child;
469 else
470 parent->in_right = child;
471 } else {
472 *root = child;
473 }
474
475 update_maxhigh(child ? : parent, node->in_max_high);
476
477 color:
478 if (color == INTERVAL_BLACK)
479 interval_erase_color(child, parent, root);
480 }
481 EXPORT_SYMBOL(interval_erase);
482