1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#include <linux/rbtree_augmented.h>
25#include <linux/export.h>
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71static inline void rb_set_black(struct rb_node *rb)
72{
73 rb->__rb_parent_color |= RB_BLACK;
74}
75
76static inline struct rb_node *rb_red_parent(struct rb_node *red)
77{
78 return (struct rb_node *)red->__rb_parent_color;
79}
80
81
82
83
84
85
86static inline void
87__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
88 struct rb_root *root, int color)
89{
90 struct rb_node *parent = rb_parent(old);
91 new->__rb_parent_color = old->__rb_parent_color;
92 rb_set_parent_color(old, new, color);
93 __rb_change_child(old, new, parent, root);
94}
95
96static __always_inline void
97__rb_insert(struct rb_node *node, struct rb_root *root,
98 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
99{
100 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
101
102 while (true) {
103
104
105
106 if (unlikely(!parent)) {
107
108
109
110
111
112 rb_set_parent_color(node, NULL, RB_BLACK);
113 break;
114 }
115
116
117
118
119
120
121
122 if(rb_is_black(parent))
123 break;
124
125 gparent = rb_red_parent(parent);
126
127 tmp = gparent->rb_right;
128 if (parent != tmp) {
129 if (tmp && rb_is_red(tmp)) {
130
131
132
133
134
135
136
137
138
139
140
141
142
143 rb_set_parent_color(tmp, gparent, RB_BLACK);
144 rb_set_parent_color(parent, gparent, RB_BLACK);
145 node = gparent;
146 parent = rb_parent(node);
147 rb_set_parent_color(node, parent, RB_RED);
148 continue;
149 }
150
151 tmp = parent->rb_right;
152 if (node == tmp) {
153
154
155
156
157
158
159
160
161
162
163
164
165
166 tmp = node->rb_left;
167 WRITE_ONCE(parent->rb_right, tmp);
168 WRITE_ONCE(node->rb_left, parent);
169 if (tmp)
170 rb_set_parent_color(tmp, parent,
171 RB_BLACK);
172 rb_set_parent_color(parent, node, RB_RED);
173 augment_rotate(parent, node);
174 parent = node;
175 tmp = node->rb_right;
176 }
177
178
179
180
181
182
183
184
185
186
187
188 WRITE_ONCE(gparent->rb_left, tmp);
189 WRITE_ONCE(parent->rb_right, gparent);
190 if (tmp)
191 rb_set_parent_color(tmp, gparent, RB_BLACK);
192 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
193 augment_rotate(gparent, parent);
194 break;
195 } else {
196 tmp = gparent->rb_left;
197 if (tmp && rb_is_red(tmp)) {
198
199 rb_set_parent_color(tmp, gparent, RB_BLACK);
200 rb_set_parent_color(parent, gparent, RB_BLACK);
201 node = gparent;
202 parent = rb_parent(node);
203 rb_set_parent_color(node, parent, RB_RED);
204 continue;
205 }
206
207 tmp = parent->rb_left;
208 if (node == tmp) {
209
210 tmp = node->rb_right;
211 WRITE_ONCE(parent->rb_left, tmp);
212 WRITE_ONCE(node->rb_right, parent);
213 if (tmp)
214 rb_set_parent_color(tmp, parent,
215 RB_BLACK);
216 rb_set_parent_color(parent, node, RB_RED);
217 augment_rotate(parent, node);
218 parent = node;
219 tmp = node->rb_left;
220 }
221
222
223 WRITE_ONCE(gparent->rb_right, tmp);
224 WRITE_ONCE(parent->rb_left, gparent);
225 if (tmp)
226 rb_set_parent_color(tmp, gparent, RB_BLACK);
227 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
228 augment_rotate(gparent, parent);
229 break;
230 }
231 }
232}
233
234
235
236
237
238static __always_inline void
239____rb_erase_color(struct rb_node *parent, struct rb_root *root,
240 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
241{
242 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
243
244 while (true) {
245
246
247
248
249
250
251
252 sibling = parent->rb_right;
253 if (node != sibling) {
254 if (rb_is_red(sibling)) {
255
256
257
258
259
260
261
262
263
264 tmp1 = sibling->rb_left;
265 WRITE_ONCE(parent->rb_right, tmp1);
266 WRITE_ONCE(sibling->rb_left, parent);
267 rb_set_parent_color(tmp1, parent, RB_BLACK);
268 __rb_rotate_set_parents(parent, sibling, root,
269 RB_RED);
270 augment_rotate(parent, sibling);
271 sibling = tmp1;
272 }
273 tmp1 = sibling->rb_right;
274 if (!tmp1 || rb_is_black(tmp1)) {
275 tmp2 = sibling->rb_left;
276 if (!tmp2 || rb_is_black(tmp2)) {
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292 rb_set_parent_color(sibling, parent,
293 RB_RED);
294 if (rb_is_red(parent))
295 rb_set_black(parent);
296 else {
297 node = parent;
298 parent = rb_parent(node);
299 if (parent)
300 continue;
301 }
302 break;
303 }
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331 tmp1 = tmp2->rb_right;
332 WRITE_ONCE(sibling->rb_left, tmp1);
333 WRITE_ONCE(tmp2->rb_right, sibling);
334 WRITE_ONCE(parent->rb_right, tmp2);
335 if (tmp1)
336 rb_set_parent_color(tmp1, sibling,
337 RB_BLACK);
338 augment_rotate(sibling, tmp2);
339 tmp1 = sibling;
340 sibling = tmp2;
341 }
342
343
344
345
346
347
348
349
350
351
352
353
354 tmp2 = sibling->rb_left;
355 WRITE_ONCE(parent->rb_right, tmp2);
356 WRITE_ONCE(sibling->rb_left, parent);
357 rb_set_parent_color(tmp1, sibling, RB_BLACK);
358 if (tmp2)
359 rb_set_parent(tmp2, parent);
360 __rb_rotate_set_parents(parent, sibling, root,
361 RB_BLACK);
362 augment_rotate(parent, sibling);
363 break;
364 } else {
365 sibling = parent->rb_left;
366 if (rb_is_red(sibling)) {
367
368 tmp1 = sibling->rb_right;
369 WRITE_ONCE(parent->rb_left, tmp1);
370 WRITE_ONCE(sibling->rb_right, parent);
371 rb_set_parent_color(tmp1, parent, RB_BLACK);
372 __rb_rotate_set_parents(parent, sibling, root,
373 RB_RED);
374 augment_rotate(parent, sibling);
375 sibling = tmp1;
376 }
377 tmp1 = sibling->rb_left;
378 if (!tmp1 || rb_is_black(tmp1)) {
379 tmp2 = sibling->rb_right;
380 if (!tmp2 || rb_is_black(tmp2)) {
381
382 rb_set_parent_color(sibling, parent,
383 RB_RED);
384 if (rb_is_red(parent))
385 rb_set_black(parent);
386 else {
387 node = parent;
388 parent = rb_parent(node);
389 if (parent)
390 continue;
391 }
392 break;
393 }
394
395 tmp1 = tmp2->rb_left;
396 WRITE_ONCE(sibling->rb_right, tmp1);
397 WRITE_ONCE(tmp2->rb_left, sibling);
398 WRITE_ONCE(parent->rb_left, tmp2);
399 if (tmp1)
400 rb_set_parent_color(tmp1, sibling,
401 RB_BLACK);
402 augment_rotate(sibling, tmp2);
403 tmp1 = sibling;
404 sibling = tmp2;
405 }
406
407 tmp2 = sibling->rb_right;
408 WRITE_ONCE(parent->rb_left, tmp2);
409 WRITE_ONCE(sibling->rb_right, parent);
410 rb_set_parent_color(tmp1, sibling, RB_BLACK);
411 if (tmp2)
412 rb_set_parent(tmp2, parent);
413 __rb_rotate_set_parents(parent, sibling, root,
414 RB_BLACK);
415 augment_rotate(parent, sibling);
416 break;
417 }
418 }
419}
420
421
422void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
423 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
424{
425 ____rb_erase_color(parent, root, augment_rotate);
426}
427EXPORT_SYMBOL(__rb_erase_color);
428
429
430
431
432
433
434
435
436static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
437static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
438static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
439
440static const struct rb_augment_callbacks dummy_callbacks = {
441 .propagate = dummy_propagate,
442 .copy = dummy_copy,
443 .rotate = dummy_rotate
444};
445
446void rb_insert_color(struct rb_node *node, struct rb_root *root)
447{
448 __rb_insert(node, root, dummy_rotate);
449}
450EXPORT_SYMBOL(rb_insert_color);
451
452void rb_erase(struct rb_node *node, struct rb_root *root)
453{
454 struct rb_node *rebalance;
455 rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
456 if (rebalance)
457 ____rb_erase_color(rebalance, root, dummy_rotate);
458}
459EXPORT_SYMBOL(rb_erase);
460
461
462
463
464
465
466
467
468void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
469 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
470{
471 __rb_insert(node, root, augment_rotate);
472}
473EXPORT_SYMBOL(__rb_insert_augmented);
474
475
476
477
478struct rb_node *rb_first(const struct rb_root *root)
479{
480 struct rb_node *n;
481
482 n = root->rb_node;
483 if (!n)
484 return NULL;
485 while (n->rb_left)
486 n = n->rb_left;
487 return n;
488}
489EXPORT_SYMBOL(rb_first);
490
491struct rb_node *rb_last(const struct rb_root *root)
492{
493 struct rb_node *n;
494
495 n = root->rb_node;
496 if (!n)
497 return NULL;
498 while (n->rb_right)
499 n = n->rb_right;
500 return n;
501}
502EXPORT_SYMBOL(rb_last);
503
504struct rb_node *rb_next(const struct rb_node *node)
505{
506 struct rb_node *parent;
507
508 if (RB_EMPTY_NODE(node))
509 return NULL;
510
511
512
513
514
515 if (node->rb_right) {
516 node = node->rb_right;
517 while (node->rb_left)
518 node=node->rb_left;
519 return (struct rb_node *)node;
520 }
521
522
523
524
525
526
527
528
529 while ((parent = rb_parent(node)) && node == parent->rb_right)
530 node = parent;
531
532 return parent;
533}
534EXPORT_SYMBOL(rb_next);
535
536struct rb_node *rb_prev(const struct rb_node *node)
537{
538 struct rb_node *parent;
539
540 if (RB_EMPTY_NODE(node))
541 return NULL;
542
543
544
545
546
547 if (node->rb_left) {
548 node = node->rb_left;
549 while (node->rb_right)
550 node=node->rb_right;
551 return (struct rb_node *)node;
552 }
553
554
555
556
557
558 while ((parent = rb_parent(node)) && node == parent->rb_left)
559 node = parent;
560
561 return parent;
562}
563EXPORT_SYMBOL(rb_prev);
564
565void rb_replace_node(struct rb_node *victim, struct rb_node *new,
566 struct rb_root *root)
567{
568 struct rb_node *parent = rb_parent(victim);
569
570
571 *new = *victim;
572
573
574 if (victim->rb_left)
575 rb_set_parent(victim->rb_left, new);
576 if (victim->rb_right)
577 rb_set_parent(victim->rb_right, new);
578 __rb_change_child(victim, new, parent, root);
579}
580EXPORT_SYMBOL(rb_replace_node);
581
582void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
583 struct rb_root *root)
584{
585 struct rb_node *parent = rb_parent(victim);
586
587
588 *new = *victim;
589
590
591 if (victim->rb_left)
592 rb_set_parent(victim->rb_left, new);
593 if (victim->rb_right)
594 rb_set_parent(victim->rb_right, new);
595
596
597
598
599
600 __rb_change_child_rcu(victim, new, parent, root);
601}
602EXPORT_SYMBOL(rb_replace_node_rcu);
603
604static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
605{
606 for (;;) {
607 if (node->rb_left)
608 node = node->rb_left;
609 else if (node->rb_right)
610 node = node->rb_right;
611 else
612 return (struct rb_node *)node;
613 }
614}
615
616struct rb_node *rb_next_postorder(const struct rb_node *node)
617{
618 const struct rb_node *parent;
619 if (!node)
620 return NULL;
621 parent = rb_parent(node);
622
623
624 if (parent && node == parent->rb_left && parent->rb_right) {
625
626
627 return rb_left_deepest_node(parent->rb_right);
628 } else
629
630
631 return (struct rb_node *)parent;
632}
633EXPORT_SYMBOL(rb_next_postorder);
634
635struct rb_node *rb_first_postorder(const struct rb_root *root)
636{
637 if (!root->rb_node)
638 return NULL;
639
640 return rb_left_deepest_node(root->rb_node);
641}
642EXPORT_SYMBOL(rb_first_postorder);
643