1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41# include <lustre_dlm.h>
42#include <obd_support.h>
43#include <interval_tree.h>
44
45enum {
46 INTERVAL_RED = 0,
47 INTERVAL_BLACK = 1
48};
49
50static 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
56static 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
62static inline int node_is_red(struct interval_node *node)
63{
64 return node->in_color == INTERVAL_RED;
65}
66
67static inline int node_is_black(struct interval_node *node)
68{
69 return node->in_color == INTERVAL_BLACK;
70}
71
72static inline int extent_compare(struct interval_node_extent *e1,
73 struct interval_node_extent *e2)
74{
75 int rc;
76 if (e1->start == e2->start) {
77 if (e1->end < e2->end)
78 rc = -1;
79 else if (e1->end > e2->end)
80 rc = 1;
81 else
82 rc = 0;
83 } else {
84 if (e1->start < e2->start)
85 rc = -1;
86 else
87 rc = 1;
88 }
89 return rc;
90}
91
92static inline int extent_equal(struct interval_node_extent *e1,
93 struct interval_node_extent *e2)
94{
95 return (e1->start == e2->start) && (e1->end == e2->end);
96}
97
98static inline int extent_overlapped(struct interval_node_extent *e1,
99 struct interval_node_extent *e2)
100{
101 return (e1->start <= e2->end) && (e2->start <= e1->end);
102}
103
104static inline int node_compare(struct interval_node *n1,
105 struct interval_node *n2)
106{
107 return extent_compare(&n1->in_extent, &n2->in_extent);
108}
109
110static inline int node_equal(struct interval_node *n1,
111 struct interval_node *n2)
112{
113 return extent_equal(&n1->in_extent, &n2->in_extent);
114}
115
116static inline __u64 max_u64(__u64 x, __u64 y)
117{
118 return x > y ? x : y;
119}
120
121static inline __u64 min_u64(__u64 x, __u64 y)
122{
123 return x < y ? x : y;
124}
125
126#define interval_for_each(node, root) \
127for (node = interval_first(root); node != NULL; \
128 node = interval_next(node))
129
130#define interval_for_each_reverse(node, root) \
131for (node = interval_last(root); node != NULL; \
132 node = interval_prev(node))
133
134static struct interval_node *interval_first(struct interval_node *node)
135{
136 ENTRY;
137
138 if (!node)
139 RETURN(NULL);
140 while (node->in_left)
141 node = node->in_left;
142 RETURN(node);
143}
144
145static struct interval_node *interval_last(struct interval_node *node)
146{
147 ENTRY;
148
149 if (!node)
150 RETURN(NULL);
151 while (node->in_right)
152 node = node->in_right;
153 RETURN(node);
154}
155
156static struct interval_node *interval_next(struct interval_node *node)
157{
158 ENTRY;
159
160 if (!node)
161 RETURN(NULL);
162 if (node->in_right)
163 RETURN(interval_first(node->in_right));
164 while (node->in_parent && node_is_right_child(node))
165 node = node->in_parent;
166 RETURN(node->in_parent);
167}
168
169static struct interval_node *interval_prev(struct interval_node *node)
170{
171 ENTRY;
172
173 if (!node)
174 RETURN(NULL);
175
176 if (node->in_left)
177 RETURN(interval_last(node->in_left));
178
179 while (node->in_parent && node_is_left_child(node))
180 node = node->in_parent;
181
182 RETURN(node->in_parent);
183}
184
185enum interval_iter interval_iterate(struct interval_node *root,
186 interval_callback_t func,
187 void *data)
188{
189 struct interval_node *node;
190 enum interval_iter rc = INTERVAL_ITER_CONT;
191 ENTRY;
192
193 interval_for_each(node, root) {
194 rc = func(node, data);
195 if (rc == INTERVAL_ITER_STOP)
196 break;
197 }
198
199 RETURN(rc);
200}
201EXPORT_SYMBOL(interval_iterate);
202
203enum interval_iter interval_iterate_reverse(struct interval_node *root,
204 interval_callback_t func,
205 void *data)
206{
207 struct interval_node *node;
208 enum interval_iter rc = INTERVAL_ITER_CONT;
209 ENTRY;
210
211 interval_for_each_reverse(node, root) {
212 rc = func(node, data);
213 if (rc == INTERVAL_ITER_STOP)
214 break;
215 }
216
217 RETURN(rc);
218}
219EXPORT_SYMBOL(interval_iterate_reverse);
220
221
222
223struct interval_node *interval_find(struct interval_node *root,
224 struct interval_node_extent *ex)
225{
226 struct interval_node *walk = root;
227 int rc;
228 ENTRY;
229
230 while (walk) {
231 rc = extent_compare(ex, &walk->in_extent);
232 if (rc == 0)
233 break;
234 else if (rc < 0)
235 walk = walk->in_left;
236 else
237 walk = walk->in_right;
238 }
239
240 RETURN(walk);
241}
242EXPORT_SYMBOL(interval_find);
243
244static void __rotate_change_maxhigh(struct interval_node *node,
245 struct interval_node *rotate)
246{
247 __u64 left_max, right_max;
248
249 rotate->in_max_high = node->in_max_high;
250 left_max = node->in_left ? node->in_left->in_max_high : 0;
251 right_max = node->in_right ? node->in_right->in_max_high : 0;
252 node->in_max_high = max_u64(interval_high(node),
253 max_u64(left_max,right_max));
254}
255
256
257
258
259static void __rotate_left(struct interval_node *node,
260 struct interval_node **root)
261{
262 struct interval_node *right = node->in_right;
263 struct interval_node *parent = node->in_parent;
264
265 node->in_right = right->in_left;
266 if (node->in_right)
267 right->in_left->in_parent = node;
268
269 right->in_left = node;
270 right->in_parent = parent;
271 if (parent) {
272 if (node_is_left_child(node))
273 parent->in_left = right;
274 else
275 parent->in_right = right;
276 } else {
277 *root = right;
278 }
279 node->in_parent = right;
280
281
282 __rotate_change_maxhigh(node, right);
283}
284
285
286
287
288static void __rotate_right(struct interval_node *node,
289 struct interval_node **root)
290{
291 struct interval_node *left = node->in_left;
292 struct interval_node *parent = node->in_parent;
293
294 node->in_left = left->in_right;
295 if (node->in_left)
296 left->in_right->in_parent = node;
297 left->in_right = node;
298
299 left->in_parent = parent;
300 if (parent) {
301 if (node_is_right_child(node))
302 parent->in_right = left;
303 else
304 parent->in_left = left;
305 } else {
306 *root = left;
307 }
308 node->in_parent = left;
309
310
311 __rotate_change_maxhigh(node, left);
312}
313
314#define interval_swap(a, b) do { \
315 struct interval_node *c = a; a = b; b = c; \
316} while (0)
317
318
319
320
321
322
323
324
325static void interval_insert_color(struct interval_node *node,
326 struct interval_node **root)
327{
328 struct interval_node *parent, *gparent;
329 ENTRY;
330
331 while ((parent = node->in_parent) && node_is_red(parent)) {
332 gparent = parent->in_parent;
333
334 if (node_is_left_child(parent)) {
335 struct interval_node *uncle;
336 uncle = gparent->in_right;
337 if (uncle && node_is_red(uncle)) {
338 uncle->in_color = INTERVAL_BLACK;
339 parent->in_color = INTERVAL_BLACK;
340 gparent->in_color = INTERVAL_RED;
341 node = gparent;
342 continue;
343 }
344
345 if (parent->in_right == node) {
346 __rotate_left(parent, root);
347 interval_swap(node, parent);
348 }
349
350 parent->in_color = INTERVAL_BLACK;
351 gparent->in_color = INTERVAL_RED;
352 __rotate_right(gparent, root);
353 } else {
354 struct interval_node *uncle;
355 uncle = gparent->in_left;
356 if (uncle && node_is_red(uncle)) {
357 uncle->in_color = INTERVAL_BLACK;
358 parent->in_color = INTERVAL_BLACK;
359 gparent->in_color = INTERVAL_RED;
360 node = gparent;
361 continue;
362 }
363
364 if (node_is_left_child(node)) {
365 __rotate_right(parent, root);
366 interval_swap(node, parent);
367 }
368
369 parent->in_color = INTERVAL_BLACK;
370 gparent->in_color = INTERVAL_RED;
371 __rotate_left(gparent, root);
372 }
373 }
374
375 (*root)->in_color = INTERVAL_BLACK;
376 EXIT;
377}
378
379struct interval_node *interval_insert(struct interval_node *node,
380 struct interval_node **root)
381
382{
383 struct interval_node **p, *parent = NULL;
384 ENTRY;
385
386 LASSERT(!interval_is_intree(node));
387 p = root;
388 while (*p) {
389 parent = *p;
390 if (node_equal(parent, node))
391 RETURN(parent);
392
393
394 if (parent->in_max_high < interval_high(node))
395 parent->in_max_high = interval_high(node);
396
397 if (node_compare(node, parent) < 0)
398 p = &parent->in_left;
399 else
400 p = &parent->in_right;
401 }
402
403
404 node->in_parent = parent;
405 node->in_color = INTERVAL_RED;
406 node->in_left = node->in_right = NULL;
407 *p = node;
408
409 interval_insert_color(node, root);
410 node->in_intree = 1;
411
412 RETURN(NULL);
413}
414EXPORT_SYMBOL(interval_insert);
415
416static inline int node_is_black_or_0(struct interval_node *node)
417{
418 return !node || node_is_black(node);
419}
420
421static void interval_erase_color(struct interval_node *node,
422 struct interval_node *parent,
423 struct interval_node **root)
424{
425 struct interval_node *tmp;
426 ENTRY;
427
428 while (node_is_black_or_0(node) && node != *root) {
429 if (parent->in_left == node) {
430 tmp = parent->in_right;
431 if (node_is_red(tmp)) {
432 tmp->in_color = INTERVAL_BLACK;
433 parent->in_color = INTERVAL_RED;
434 __rotate_left(parent, root);
435 tmp = parent->in_right;
436 }
437 if (node_is_black_or_0(tmp->in_left) &&
438 node_is_black_or_0(tmp->in_right)) {
439 tmp->in_color = INTERVAL_RED;
440 node = parent;
441 parent = node->in_parent;
442 } else {
443 if (node_is_black_or_0(tmp->in_right)) {
444 struct interval_node *o_left;
445 if ((o_left = tmp->in_left))
446 o_left->in_color = INTERVAL_BLACK;
447 tmp->in_color = INTERVAL_RED;
448 __rotate_right(tmp, root);
449 tmp = parent->in_right;
450 }
451 tmp->in_color = parent->in_color;
452 parent->in_color = INTERVAL_BLACK;
453 if (tmp->in_right)
454 tmp->in_right->in_color = INTERVAL_BLACK;
455 __rotate_left(parent, root);
456 node = *root;
457 break;
458 }
459 } else {
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;
466 }
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;
470 node = parent;
471 parent = node->in_parent;
472 } else {
473 if (node_is_black_or_0(tmp->in_left)) {
474 struct interval_node *o_right;
475 if ((o_right = tmp->in_right))
476 o_right->in_color = INTERVAL_BLACK;
477 tmp->in_color = INTERVAL_RED;
478 __rotate_left(tmp, root);
479 tmp = parent->in_left;
480 }
481 tmp->in_color = parent->in_color;
482 parent->in_color = INTERVAL_BLACK;
483 if (tmp->in_left)
484 tmp->in_left->in_color = INTERVAL_BLACK;
485 __rotate_right(parent, root);
486 node = *root;
487 break;
488 }
489 }
490 }
491 if (node)
492 node->in_color = INTERVAL_BLACK;
493 EXIT;
494}
495
496
497
498
499
500static void update_maxhigh(struct interval_node *node,
501 __u64 old_maxhigh)
502{
503 __u64 left_max, right_max;
504 ENTRY;
505
506 while (node) {
507 left_max = node->in_left ? node->in_left->in_max_high : 0;
508 right_max = node->in_right ? node->in_right->in_max_high : 0;
509 node->in_max_high = max_u64(interval_high(node),
510 max_u64(left_max, right_max));
511
512 if (node->in_max_high >= old_maxhigh)
513 break;
514 node = node->in_parent;
515 }
516 EXIT;
517}
518
519void interval_erase(struct interval_node *node,
520 struct interval_node **root)
521{
522 struct interval_node *child, *parent;
523 int color;
524 ENTRY;
525
526 LASSERT(interval_is_intree(node));
527 node->in_intree = 0;
528 if (!node->in_left) {
529 child = node->in_right;
530 } else if (!node->in_right) {
531 child = node->in_left;
532 } else {
533 struct interval_node *old = node;
534
535 node = interval_next(node);
536 child = node->in_right;
537 parent = node->in_parent;
538 color = node->in_color;
539
540 if (child)
541 child->in_parent = parent;
542 if (parent == old)
543 parent->in_right = child;
544 else
545 parent->in_left = child;
546
547 node->in_color = old->in_color;
548 node->in_right = old->in_right;
549 node->in_left = old->in_left;
550 node->in_parent = old->in_parent;
551
552 if (old->in_parent) {
553 if (node_is_left_child(old))
554 old->in_parent->in_left = node;
555 else
556 old->in_parent->in_right = node;
557 } else {
558 *root = node;
559 }
560
561 old->in_left->in_parent = node;
562 if (old->in_right)
563 old->in_right->in_parent = node;
564 update_maxhigh(child ? : parent, node->in_max_high);
565 update_maxhigh(node, old->in_max_high);
566 if (parent == old)
567 parent = node;
568 goto color;
569 }
570 parent = node->in_parent;
571 color = node->in_color;
572
573 if (child)
574 child->in_parent = parent;
575 if (parent) {
576 if (node_is_left_child(node))
577 parent->in_left = child;
578 else
579 parent->in_right = child;
580 } else {
581 *root = child;
582 }
583
584 update_maxhigh(child ? : parent, node->in_max_high);
585
586color:
587 if (color == INTERVAL_BLACK)
588 interval_erase_color(child, parent, root);
589 EXIT;
590}
591EXPORT_SYMBOL(interval_erase);
592
593static inline int interval_may_overlap(struct interval_node *node,
594 struct interval_node_extent *ext)
595{
596 return (ext->start <= node->in_max_high &&
597 ext->end >= interval_low(node));
598}
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621enum interval_iter interval_search(struct interval_node *node,
622 struct interval_node_extent *ext,
623 interval_callback_t func,
624 void *data)
625{
626 struct interval_node *parent;
627 enum interval_iter rc = INTERVAL_ITER_CONT;
628
629 LASSERT(ext != NULL);
630 LASSERT(func != NULL);
631
632 while (node) {
633 if (ext->end < interval_low(node)) {
634 if (node->in_left) {
635 node = node->in_left;
636 continue;
637 }
638 } else if (interval_may_overlap(node, ext)) {
639 if (extent_overlapped(ext, &node->in_extent)) {
640 rc = func(node, data);
641 if (rc == INTERVAL_ITER_STOP)
642 break;
643 }
644
645 if (node->in_left) {
646 node = node->in_left;
647 continue;
648 }
649 if (node->in_right) {
650 node = node->in_right;
651 continue;
652 }
653 }
654
655 parent = node->in_parent;
656 while (parent) {
657 if (node_is_left_child(node) &&
658 parent->in_right) {
659
660
661
662
663
664 node = parent->in_right;
665 break;
666 }
667 node = parent;
668 parent = parent->in_parent;
669 }
670 if (parent == NULL || !interval_may_overlap(parent, ext))
671 break;
672 }
673
674 return rc;
675}
676EXPORT_SYMBOL(interval_search);
677
678static enum interval_iter interval_overlap_cb(struct interval_node *n,
679 void *args)
680{
681 *(int *)args = 1;
682 return INTERVAL_ITER_STOP;
683}
684
685int interval_is_overlapped(struct interval_node *root,
686 struct interval_node_extent *ext)
687{
688 int has = 0;
689 (void)interval_search(root, ext, interval_overlap_cb, &has);
690 return has;
691}
692EXPORT_SYMBOL(interval_is_overlapped);
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723static inline __u64 interval_expand_low(struct interval_node *root, __u64 low)
724{
725
726 if (root == NULL)
727 return 0;
728 return low;
729}
730
731static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
732{
733 __u64 result = ~0;
734
735 while (node != NULL) {
736 if (node->in_max_high < high)
737 break;
738
739 if (interval_low(node) > high) {
740 result = interval_low(node) - 1;
741 node = node->in_left;
742 } else {
743 node = node->in_right;
744 }
745 }
746
747 return result;
748}
749
750
751void interval_expand(struct interval_node *root,
752 struct interval_node_extent *ext,
753 struct interval_node_extent *limiter)
754{
755
756
757 LASSERT(interval_is_overlapped(root, ext) == 0);
758 if (!limiter || limiter->start < ext->start)
759 ext->start = interval_expand_low(root, ext->start);
760 if (!limiter || limiter->end > ext->end)
761 ext->end = interval_expand_high(root, ext->end);
762 LASSERT(interval_is_overlapped(root, ext) == 0);
763}
764EXPORT_SYMBOL(interval_expand);
765