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