]> git.ipfire.org Git - people/ms/u-boot.git/blob - lib/rbtree.c
projects / people / ms / u-boot.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
imx: hab: Check if CSF contains deprecated commands
[people/ms/u-boot.git] / lib / rbtree.c
1 /*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 (C) 2012 Michel Lespinasse <walken@google.com>
6
7 * SPDX-License-Identifier: GPL-2.0+
8
9 linux/lib/rbtree.c
10 */
11
12 #include <linux/rbtree_augmented.h>
13 #ifndef __UBOOT__
14 #include <linux/export.h>
15 #else
16 #include <ubi_uboot.h>
17 #endif
18 /*
19 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
20 *
21 * 1) A node is either red or black
22 * 2) The root is black
23 * 3) All leaves (NULL) are black
24 * 4) Both children of every red node are black
25 * 5) Every simple path from root to leaves contains the same number
26 * of black nodes.
27 *
28 * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
29 * consecutive red nodes in a path and every red node is therefore followed by
30 * a black. So if B is the number of black nodes on every simple path (as per
31 * 5), then the longest possible path due to 4 is 2B.
32 *
33 * We shall indicate color with case, where black nodes are uppercase and red
34 * nodes will be lowercase. Unknown color nodes shall be drawn as red within
35 * parentheses and have some accompanying text comment.
36 */
37
38 static inline void rb_set_black(struct rb_node *rb)
39 {
40 rb->__rb_parent_color |= RB_BLACK;
41 }
42
43 static inline struct rb_node *rb_red_parent(struct rb_node *red)
44 {
45 return (struct rb_node *)red->__rb_parent_color;
46 }
47
48 /*
49 * Helper function for rotations:
50 * - old's parent and color get assigned to new
51 * - old gets assigned new as a parent and 'color' as a color.
52 */
53 static inline void
54 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
55 struct rb_root *root, int color)
56 {
57 struct rb_node *parent = rb_parent(old);
58 new->__rb_parent_color = old->__rb_parent_color;
59 rb_set_parent_color(old, new, color);
60 __rb_change_child(old, new, parent, root);
61 }
62
63 static __always_inline void
64 __rb_insert(struct rb_node *node, struct rb_root *root,
65 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
66 {
67 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
68
69 while (true) {
70 /*
71 * Loop invariant: node is red
72 *
73 * If there is a black parent, we are done.
74 * Otherwise, take some corrective action as we don't
75 * want a red root or two consecutive red nodes.
76 */
77 if (!parent) {
78 rb_set_parent_color(node, NULL, RB_BLACK);
79 break;
80 } else if (rb_is_black(parent))
81 break;
82
83 gparent = rb_red_parent(parent);
84
85 tmp = gparent->rb_right;
86 if (parent != tmp) { /* parent == gparent->rb_left */
87 if (tmp && rb_is_red(tmp)) {
88 /*
89 * Case 1 - color flips
90 *
91 * G g
92 * / \ / \
93 * p u --> P U
94 * / /
95 * n N
96 *
97 * However, since g's parent might be red, and
98 * 4) does not allow this, we need to recurse
99 * at g.
100 */
101 rb_set_parent_color(tmp, gparent, RB_BLACK);
102 rb_set_parent_color(parent, gparent, RB_BLACK);
103 node = gparent;
104 parent = rb_parent(node);
105 rb_set_parent_color(node, parent, RB_RED);
106 continue;
107 }
108
109 tmp = parent->rb_right;
110 if (node == tmp) {
111 /*
112 * Case 2 - left rotate at parent
113 *
114 * G G
115 * / \ / \
116 * p U --> n U
117 * \ /
118 * n p
119 *
120 * This still leaves us in violation of 4), the
121 * continuation into Case 3 will fix that.
122 */
123 parent->rb_right = tmp = node->rb_left;
124 node->rb_left = parent;
125 if (tmp)
126 rb_set_parent_color(tmp, parent,
127 RB_BLACK);
128 rb_set_parent_color(parent, node, RB_RED);
129 augment_rotate(parent, node);
130 parent = node;
131 tmp = node->rb_right;
132 }
133
134 /*
135 * Case 3 - right rotate at gparent
136 *
137 * G P
138 * / \ / \
139 * p U --> n g
140 * / \
141 * n U
142 */
143 gparent->rb_left = tmp; /* == parent->rb_right */
144 parent->rb_right = gparent;
145 if (tmp)
146 rb_set_parent_color(tmp, gparent, RB_BLACK);
147 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
148 augment_rotate(gparent, parent);
149 break;
150 } else {
151 tmp = gparent->rb_left;
152 if (tmp && rb_is_red(tmp)) {
153 /* Case 1 - color flips */
154 rb_set_parent_color(tmp, gparent, RB_BLACK);
155 rb_set_parent_color(parent, gparent, RB_BLACK);
156 node = gparent;
157 parent = rb_parent(node);
158 rb_set_parent_color(node, parent, RB_RED);
159 continue;
160 }
161
162 tmp = parent->rb_left;
163 if (node == tmp) {
164 /* Case 2 - right rotate at parent */
165 parent->rb_left = tmp = node->rb_right;
166 node->rb_right = parent;
167 if (tmp)
168 rb_set_parent_color(tmp, parent,
169 RB_BLACK);
170 rb_set_parent_color(parent, node, RB_RED);
171 augment_rotate(parent, node);
172 parent = node;
173 tmp = node->rb_left;
174 }
175
176 /* Case 3 - left rotate at gparent */
177 gparent->rb_right = tmp; /* == parent->rb_left */
178 parent->rb_left = gparent;
179 if (tmp)
180 rb_set_parent_color(tmp, gparent, RB_BLACK);
181 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
182 augment_rotate(gparent, parent);
183 break;
184 }
185 }
186 }
187
188 /*
189 * Inline version for rb_erase() use - we want to be able to inline
190 * and eliminate the dummy_rotate callback there
191 */
192 static __always_inline void
193 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
194 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
195 {
196 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
197
198 while (true) {
199 /*
200 * Loop invariants:
201 * - node is black (or NULL on first iteration)
202 * - node is not the root (parent is not NULL)
203 * - All leaf paths going through parent and node have a
204 * black node count that is 1 lower than other leaf paths.
205 */
206 sibling = parent->rb_right;
207 if (node != sibling) { /* node == parent->rb_left */
208 if (rb_is_red(sibling)) {
209 /*
210 * Case 1 - left rotate at parent
211 *
212 * P S
213 * / \ / \
214 * N s --> p Sr
215 * / \ / \
216 * Sl Sr N Sl
217 */
218 parent->rb_right = tmp1 = sibling->rb_left;
219 sibling->rb_left = parent;
220 rb_set_parent_color(tmp1, parent, RB_BLACK);
221 __rb_rotate_set_parents(parent, sibling, root,
222 RB_RED);
223 augment_rotate(parent, sibling);
224 sibling = tmp1;
225 }
226 tmp1 = sibling->rb_right;
227 if (!tmp1 || rb_is_black(tmp1)) {
228 tmp2 = sibling->rb_left;
229 if (!tmp2 || rb_is_black(tmp2)) {
230 /*
231 * Case 2 - sibling color flip
232 * (p could be either color here)
233 *
234 * (p) (p)
235 * / \ / \
236 * N S --> N s
237 * / \ / \
238 * Sl Sr Sl Sr
239 *
240 * This leaves us violating 5) which
241 * can be fixed by flipping p to black
242 * if it was red, or by recursing at p.
243 * p is red when coming from Case 1.
244 */
245 rb_set_parent_color(sibling, parent,
246 RB_RED);
247 if (rb_is_red(parent))
248 rb_set_black(parent);
249 else {
250 node = parent;
251 parent = rb_parent(node);
252 if (parent)
253 continue;
254 }
255 break;
256 }
257 /*
258 * Case 3 - right rotate at sibling
259 * (p could be either color here)
260 *
261 * (p) (p)
262 * / \ / \
263 * N S --> N Sl
264 * / \ \
265 * sl Sr s
266 * \
267 * Sr
268 */
269 sibling->rb_left = tmp1 = tmp2->rb_right;
270 tmp2->rb_right = sibling;
271 parent->rb_right = tmp2;
272 if (tmp1)
273 rb_set_parent_color(tmp1, sibling,
274 RB_BLACK);
275 augment_rotate(sibling, tmp2);
276 tmp1 = sibling;
277 sibling = tmp2;
278 }
279 /*
280 * Case 4 - left rotate at parent + color flips
281 * (p and sl could be either color here.
282 * After rotation, p becomes black, s acquires
283 * p's color, and sl keeps its color)
284 *
285 * (p) (s)
286 * / \ / \
287 * N S --> P Sr
288 * / \ / \
289 * (sl) sr N (sl)
290 */
291 parent->rb_right = tmp2 = sibling->rb_left;
292 sibling->rb_left = parent;
293 rb_set_parent_color(tmp1, sibling, RB_BLACK);
294 if (tmp2)
295 rb_set_parent(tmp2, parent);
296 __rb_rotate_set_parents(parent, sibling, root,
297 RB_BLACK);
298 augment_rotate(parent, sibling);
299 break;
300 } else {
301 sibling = parent->rb_left;
302 if (rb_is_red(sibling)) {
303 /* Case 1 - right rotate at parent */
304 parent->rb_left = tmp1 = sibling->rb_right;
305 sibling->rb_right = parent;
306 rb_set_parent_color(tmp1, parent, RB_BLACK);
307 __rb_rotate_set_parents(parent, sibling, root,
308 RB_RED);
309 augment_rotate(parent, sibling);
310 sibling = tmp1;
311 }
312 tmp1 = sibling->rb_left;
313 if (!tmp1 || rb_is_black(tmp1)) {
314 tmp2 = sibling->rb_right;
315 if (!tmp2 || rb_is_black(tmp2)) {
316 /* Case 2 - sibling color flip */
317 rb_set_parent_color(sibling, parent,
318 RB_RED);
319 if (rb_is_red(parent))
320 rb_set_black(parent);
321 else {
322 node = parent;
323 parent = rb_parent(node);
324 if (parent)
325 continue;
326 }
327 break;
328 }
329 /* Case 3 - right rotate at sibling */
330 sibling->rb_right = tmp1 = tmp2->rb_left;
331 tmp2->rb_left = sibling;
332 parent->rb_left = tmp2;
333 if (tmp1)
334 rb_set_parent_color(tmp1, sibling,
335 RB_BLACK);
336 augment_rotate(sibling, tmp2);
337 tmp1 = sibling;
338 sibling = tmp2;
339 }
340 /* Case 4 - left rotate at parent + color flips */
341 parent->rb_left = tmp2 = sibling->rb_right;
342 sibling->rb_right = parent;
343 rb_set_parent_color(tmp1, sibling, RB_BLACK);
344 if (tmp2)
345 rb_set_parent(tmp2, parent);
346 __rb_rotate_set_parents(parent, sibling, root,
347 RB_BLACK);
348 augment_rotate(parent, sibling);
349 break;
350 }
351 }
352 }
353
354 /* Non-inline version for rb_erase_augmented() use */
355 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
356 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
357 {
358 ____rb_erase_color(parent, root, augment_rotate);
359 }
360 EXPORT_SYMBOL(__rb_erase_color);
361
362 /*
363 * Non-augmented rbtree manipulation functions.
364 *
365 * We use dummy augmented callbacks here, and have the compiler optimize them
366 * out of the rb_insert_color() and rb_erase() function definitions.
367 */
368
369 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
370 static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
371 static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
372
373 static const struct rb_augment_callbacks dummy_callbacks = {
374 dummy_propagate, dummy_copy, dummy_rotate
375 };
376
377 void rb_insert_color(struct rb_node *node, struct rb_root *root)
378 {
379 __rb_insert(node, root, dummy_rotate);
380 }
381 EXPORT_SYMBOL(rb_insert_color);
382
383 void rb_erase(struct rb_node *node, struct rb_root *root)
384 {
385 struct rb_node *rebalance;
386 rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
387 if (rebalance)
388 ____rb_erase_color(rebalance, root, dummy_rotate);
389 }
390 EXPORT_SYMBOL(rb_erase);
391
392 /*
393 * Augmented rbtree manipulation functions.
394 *
395 * This instantiates the same __always_inline functions as in the non-augmented
396 * case, but this time with user-defined callbacks.
397 */
398
399 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
400 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
401 {
402 __rb_insert(node, root, augment_rotate);
403 }
404 EXPORT_SYMBOL(__rb_insert_augmented);
405
406 /*
407 * This function returns the first node (in sort order) of the tree.
408 */
409 struct rb_node *rb_first(const struct rb_root *root)
410 {
411 struct rb_node *n;
412
413 n = root->rb_node;
414 if (!n)
415 return NULL;
416 while (n->rb_left)
417 n = n->rb_left;
418 return n;
419 }
420 EXPORT_SYMBOL(rb_first);
421
422 struct rb_node *rb_last(const struct rb_root *root)
423 {
424 struct rb_node *n;
425
426 n = root->rb_node;
427 if (!n)
428 return NULL;
429 while (n->rb_right)
430 n = n->rb_right;
431 return n;
432 }
433 EXPORT_SYMBOL(rb_last);
434
435 struct rb_node *rb_next(const struct rb_node *node)
436 {
437 struct rb_node *parent;
438
439 if (RB_EMPTY_NODE(node))
440 return NULL;
441
442 /*
443 * If we have a right-hand child, go down and then left as far
444 * as we can.
445 */
446 if (node->rb_right) {
447 node = node->rb_right;
448 while (node->rb_left)
449 node=node->rb_left;
450 return (struct rb_node *)node;
451 }
452
453 /*
454 * No right-hand children. Everything down and left is smaller than us,
455 * so any 'next' node must be in the general direction of our parent.
456 * Go up the tree; any time the ancestor is a right-hand child of its
457 * parent, keep going up. First time it's a left-hand child of its
458 * parent, said parent is our 'next' node.
459 */
460 while ((parent = rb_parent(node)) && node == parent->rb_right)
461 node = parent;
462
463 return parent;
464 }
465 EXPORT_SYMBOL(rb_next);
466
467 struct rb_node *rb_prev(const struct rb_node *node)
468 {
469 struct rb_node *parent;
470
471 if (RB_EMPTY_NODE(node))
472 return NULL;
473
474 /*
475 * If we have a left-hand child, go down and then right as far
476 * as we can.
477 */
478 if (node->rb_left) {
479 node = node->rb_left;
480 while (node->rb_right)
481 node=node->rb_right;
482 return (struct rb_node *)node;
483 }
484
485 /*
486 * No left-hand children. Go up till we find an ancestor which
487 * is a right-hand child of its parent.
488 */
489 while ((parent = rb_parent(node)) && node == parent->rb_left)
490 node = parent;
491
492 return parent;
493 }
494 EXPORT_SYMBOL(rb_prev);
495
496 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
497 struct rb_root *root)
498 {
499 struct rb_node *parent = rb_parent(victim);
500
501 /* Set the surrounding nodes to point to the replacement */
502 __rb_change_child(victim, new, parent, root);
503 if (victim->rb_left)
504 rb_set_parent(victim->rb_left, new);
505 if (victim->rb_right)
506 rb_set_parent(victim->rb_right, new);
507
508 /* Copy the pointers/colour from the victim to the replacement */
509 *new = *victim;
510 }
511 EXPORT_SYMBOL(rb_replace_node);
512
513 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
514 {
515 for (;;) {
516 if (node->rb_left)
517 node = node->rb_left;
518 else if (node->rb_right)
519 node = node->rb_right;
520 else
521 return (struct rb_node *)node;
522 }
523 }
524
525 struct rb_node *rb_next_postorder(const struct rb_node *node)
526 {
527 const struct rb_node *parent;
528 if (!node)
529 return NULL;
530 parent = rb_parent(node);
531
532 /* If we're sitting on node, we've already seen our children */
533 if (parent && node == parent->rb_left && parent->rb_right) {
534 /* If we are the parent's left node, go to the parent's right
535 * node then all the way down to the left */
536 return rb_left_deepest_node(parent->rb_right);
537 } else
538 /* Otherwise we are the parent's right node, and the parent
539 * should be next */
540 return (struct rb_node *)parent;
541 }
542 EXPORT_SYMBOL(rb_next_postorder);
543
544 struct rb_node *rb_first_postorder(const struct rb_root *root)
545 {
546 if (!root->rb_node)
547 return NULL;
548
549 return rb_left_deepest_node(root->rb_node);
550 }
551 EXPORT_SYMBOL(rb_first_postorder);
"Das U-Boot" Source Tree