Blame view
lib/rbtree.c
15 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 |
/* Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> (C) 2002 David Woodhouse <dwmw2@infradead.org> |
46b6135a7 rbtree: handle 1-... |
5 |
(C) 2012 Michel Lespinasse <walken@google.com> |
1da177e4c Linux-2.6.12-rc2 |
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/lib/rbtree.c */ |
9c079add0 rbtree: move augm... |
22 |
#include <linux/rbtree_augmented.h> |
8bc3bcc93 lib: reduce the u... |
23 |
#include <linux/export.h> |
1da177e4c Linux-2.6.12-rc2 |
24 |
|
5bc9188aa rbtree: low level... |
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/* * 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 |
6280d2356 rbtree: low level... |
41 42 |
* nodes will be lowercase. Unknown color nodes shall be drawn as red within * parentheses and have some accompanying text comment. |
5bc9188aa rbtree: low level... |
43 |
*/ |
46b6135a7 rbtree: handle 1-... |
44 45 46 47 |
static inline void rb_set_black(struct rb_node *rb) { rb->__rb_parent_color |= RB_BLACK; } |
5bc9188aa rbtree: low level... |
48 49 50 51 |
static inline struct rb_node *rb_red_parent(struct rb_node *red) { return (struct rb_node *)red->__rb_parent_color; } |
5bc9188aa rbtree: low level... |
52 53 54 55 56 57 58 59 60 61 62 63 |
/* * 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); |
7abc704ae rbtree: add __rb_... |
64 |
__rb_change_child(old, new, parent, root); |
5bc9188aa rbtree: low level... |
65 |
} |
14b94af0b rbtree: faster au... |
66 67 68 |
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)) |
1da177e4c Linux-2.6.12-rc2 |
69 |
{ |
5bc9188aa rbtree: low level... |
70 |
struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; |
1da177e4c Linux-2.6.12-rc2 |
71 |
|
6d58452dc rbtree: adjust ro... |
72 73 74 75 76 77 78 79 |
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. */ |
6d58452dc rbtree: adjust ro... |
80 |
if (!parent) { |
5bc9188aa rbtree: low level... |
81 |
rb_set_parent_color(node, NULL, RB_BLACK); |
6d58452dc rbtree: adjust ro... |
82 83 84 |
break; } else if (rb_is_black(parent)) break; |
5bc9188aa rbtree: low level... |
85 |
gparent = rb_red_parent(parent); |
59633abf3 rbtree: optimize ... |
86 87 |
tmp = gparent->rb_right; if (parent != tmp) { /* parent == gparent->rb_left */ |
5bc9188aa rbtree: low level... |
88 89 90 91 92 93 94 95 |
if (tmp && rb_is_red(tmp)) { /* * Case 1 - color flips * * G g * / \ / \ * p u --> P U * / / |
1b9c53e84 lib/rbtree.c: fix... |
96 |
* n n |
5bc9188aa rbtree: low level... |
97 98 99 100 101 102 103 104 105 106 107 |
* * 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; |
1da177e4c Linux-2.6.12-rc2 |
108 |
} |
59633abf3 rbtree: optimize ... |
109 110 |
tmp = parent->rb_right; if (node == tmp) { |
5bc9188aa rbtree: low level... |
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
/* * 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); |
14b94af0b rbtree: faster au... |
129 |
augment_rotate(parent, node); |
1da177e4c Linux-2.6.12-rc2 |
130 |
parent = node; |
59633abf3 rbtree: optimize ... |
131 |
tmp = node->rb_right; |
1da177e4c Linux-2.6.12-rc2 |
132 |
} |
5bc9188aa rbtree: low level... |
133 134 135 136 137 138 139 140 141 |
/* * Case 3 - right rotate at gparent * * G P * / \ / \ * p U --> n g * / \ * n U */ |
59633abf3 rbtree: optimize ... |
142 |
gparent->rb_left = tmp; /* == parent->rb_right */ |
5bc9188aa rbtree: low level... |
143 144 145 146 |
parent->rb_right = gparent; if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); |
14b94af0b rbtree: faster au... |
147 |
augment_rotate(gparent, parent); |
1f0528653 rbtree: break out... |
148 |
break; |
1da177e4c Linux-2.6.12-rc2 |
149 |
} else { |
5bc9188aa rbtree: low level... |
150 151 152 153 154 155 156 157 158 |
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; |
1da177e4c Linux-2.6.12-rc2 |
159 |
} |
59633abf3 rbtree: optimize ... |
160 161 |
tmp = parent->rb_left; if (node == tmp) { |
5bc9188aa rbtree: low level... |
162 163 164 165 166 167 168 |
/* 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); |
14b94af0b rbtree: faster au... |
169 |
augment_rotate(parent, node); |
1da177e4c Linux-2.6.12-rc2 |
170 |
parent = node; |
59633abf3 rbtree: optimize ... |
171 |
tmp = node->rb_left; |
1da177e4c Linux-2.6.12-rc2 |
172 |
} |
5bc9188aa rbtree: low level... |
173 |
/* Case 3 - left rotate at gparent */ |
59633abf3 rbtree: optimize ... |
174 |
gparent->rb_right = tmp; /* == parent->rb_left */ |
5bc9188aa rbtree: low level... |
175 176 177 178 |
parent->rb_left = gparent; if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); |
14b94af0b rbtree: faster au... |
179 |
augment_rotate(gparent, parent); |
1f0528653 rbtree: break out... |
180 |
break; |
1da177e4c Linux-2.6.12-rc2 |
181 182 |
} } |
1da177e4c Linux-2.6.12-rc2 |
183 |
} |
1da177e4c Linux-2.6.12-rc2 |
184 |
|
3cb7a5634 lib/rbtree.c: avo... |
185 186 187 188 189 190 |
/* * 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, |
9c079add0 rbtree: move augm... |
191 |
void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) |
1da177e4c Linux-2.6.12-rc2 |
192 |
{ |
46b6135a7 rbtree: handle 1-... |
193 |
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; |
1da177e4c Linux-2.6.12-rc2 |
194 |
|
d6ff12739 rbtree: adjust no... |
195 196 |
while (true) { /* |
46b6135a7 rbtree: handle 1-... |
197 198 199 200 201 |
* 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. |
d6ff12739 rbtree: adjust no... |
202 |
*/ |
59633abf3 rbtree: optimize ... |
203 204 |
sibling = parent->rb_right; if (node != sibling) { /* node == parent->rb_left */ |
6280d2356 rbtree: low level... |
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 |
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); |
9c079add0 rbtree: move augm... |
220 |
augment_rotate(parent, sibling); |
6280d2356 rbtree: low level... |
221 |
sibling = tmp1; |
1da177e4c Linux-2.6.12-rc2 |
222 |
} |
6280d2356 rbtree: low level... |
223 224 225 226 227 228 229 230 231 232 233 234 235 236 |
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 * |
46b6135a7 rbtree: handle 1-... |
237 238 239 240 |
* 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. |
6280d2356 rbtree: low level... |
241 242 243 |
*/ rb_set_parent_color(sibling, parent, RB_RED); |
46b6135a7 rbtree: handle 1-... |
244 245 246 247 248 249 250 251 252 |
if (rb_is_red(parent)) rb_set_black(parent); else { node = parent; parent = rb_parent(node); if (parent) continue; } break; |
1da177e4c Linux-2.6.12-rc2 |
253 |
} |
6280d2356 rbtree: low level... |
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 |
/* * 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); |
9c079add0 rbtree: move augm... |
272 |
augment_rotate(sibling, tmp2); |
6280d2356 rbtree: low level... |
273 274 |
tmp1 = sibling; sibling = tmp2; |
1da177e4c Linux-2.6.12-rc2 |
275 |
} |
6280d2356 rbtree: low level... |
276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 |
/* * 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); |
9c079add0 rbtree: move augm... |
295 |
augment_rotate(parent, sibling); |
e125d1471 rbtree: optimize ... |
296 |
break; |
d6ff12739 rbtree: adjust no... |
297 |
} else { |
6280d2356 rbtree: low level... |
298 299 300 301 302 303 304 305 |
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); |
9c079add0 rbtree: move augm... |
306 |
augment_rotate(parent, sibling); |
6280d2356 rbtree: low level... |
307 |
sibling = tmp1; |
1da177e4c Linux-2.6.12-rc2 |
308 |
} |
6280d2356 rbtree: low level... |
309 310 311 312 313 314 315 |
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); |
46b6135a7 rbtree: handle 1-... |
316 317 318 319 320 321 322 323 324 |
if (rb_is_red(parent)) rb_set_black(parent); else { node = parent; parent = rb_parent(node); if (parent) continue; } break; |
1da177e4c Linux-2.6.12-rc2 |
325 |
} |
6280d2356 rbtree: low level... |
326 327 328 329 330 331 332 |
/* 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); |
9c079add0 rbtree: move augm... |
333 |
augment_rotate(sibling, tmp2); |
6280d2356 rbtree: low level... |
334 335 |
tmp1 = sibling; sibling = tmp2; |
1da177e4c Linux-2.6.12-rc2 |
336 |
} |
6280d2356 rbtree: low level... |
337 338 339 340 341 342 343 344 |
/* 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); |
9c079add0 rbtree: move augm... |
345 |
augment_rotate(parent, sibling); |
e125d1471 rbtree: optimize ... |
346 |
break; |
1da177e4c Linux-2.6.12-rc2 |
347 348 |
} } |
1da177e4c Linux-2.6.12-rc2 |
349 |
} |
3cb7a5634 lib/rbtree.c: avo... |
350 351 352 353 354 355 356 |
/* 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); } |
9c079add0 rbtree: move augm... |
357 |
EXPORT_SYMBOL(__rb_erase_color); |
14b94af0b rbtree: faster au... |
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 |
/* * 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); void rb_erase(struct rb_node *node, struct rb_root *root) { |
3cb7a5634 lib/rbtree.c: avo... |
382 383 384 385 |
struct rb_node *rebalance; rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); if (rebalance) ____rb_erase_color(rebalance, root, dummy_rotate); |
1da177e4c Linux-2.6.12-rc2 |
386 387 |
} EXPORT_SYMBOL(rb_erase); |
14b94af0b rbtree: faster au... |
388 389 390 391 392 393 394 395 396 397 398 399 400 |
/* * Augmented rbtree manipulation functions. * * This instantiates the same __always_inline functions as in the non-augmented * case, but this time with user-defined callbacks. */ 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); } EXPORT_SYMBOL(__rb_insert_augmented); |
1da177e4c Linux-2.6.12-rc2 |
401 402 403 |
/* * This function returns the first node (in sort order) of the tree. */ |
f4b477c47 rbtree: add const... |
404 |
struct rb_node *rb_first(const struct rb_root *root) |
1da177e4c Linux-2.6.12-rc2 |
405 406 407 408 409 410 411 412 413 414 415 |
{ struct rb_node *n; n = root->rb_node; if (!n) return NULL; while (n->rb_left) n = n->rb_left; return n; } EXPORT_SYMBOL(rb_first); |
f4b477c47 rbtree: add const... |
416 |
struct rb_node *rb_last(const struct rb_root *root) |
1da177e4c Linux-2.6.12-rc2 |
417 418 419 420 421 422 423 424 425 426 427 |
{ struct rb_node *n; n = root->rb_node; if (!n) return NULL; while (n->rb_right) n = n->rb_right; return n; } EXPORT_SYMBOL(rb_last); |
f4b477c47 rbtree: add const... |
428 |
struct rb_node *rb_next(const struct rb_node *node) |
1da177e4c Linux-2.6.12-rc2 |
429 |
{ |
55a981027 [RBTREE] Merge co... |
430 |
struct rb_node *parent; |
4c199a93a rbtree: empty nod... |
431 |
if (RB_EMPTY_NODE(node)) |
10fd48f23 [PATCH] rbtree: f... |
432 |
return NULL; |
7ce6ff9e5 rbtree: coding st... |
433 434 435 436 |
/* * If we have a right-hand child, go down and then left as far * as we can. */ |
1da177e4c Linux-2.6.12-rc2 |
437 438 439 440 |
if (node->rb_right) { node = node->rb_right; while (node->rb_left) node=node->rb_left; |
f4b477c47 rbtree: add const... |
441 |
return (struct rb_node *)node; |
1da177e4c Linux-2.6.12-rc2 |
442 |
} |
7ce6ff9e5 rbtree: coding st... |
443 444 445 446 447 448 449 |
/* * 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. */ |
55a981027 [RBTREE] Merge co... |
450 451 |
while ((parent = rb_parent(node)) && node == parent->rb_right) node = parent; |
1da177e4c Linux-2.6.12-rc2 |
452 |
|
55a981027 [RBTREE] Merge co... |
453 |
return parent; |
1da177e4c Linux-2.6.12-rc2 |
454 455 |
} EXPORT_SYMBOL(rb_next); |
f4b477c47 rbtree: add const... |
456 |
struct rb_node *rb_prev(const struct rb_node *node) |
1da177e4c Linux-2.6.12-rc2 |
457 |
{ |
55a981027 [RBTREE] Merge co... |
458 |
struct rb_node *parent; |
4c199a93a rbtree: empty nod... |
459 |
if (RB_EMPTY_NODE(node)) |
10fd48f23 [PATCH] rbtree: f... |
460 |
return NULL; |
7ce6ff9e5 rbtree: coding st... |
461 462 463 464 |
/* * If we have a left-hand child, go down and then right as far * as we can. */ |
1da177e4c Linux-2.6.12-rc2 |
465 466 467 468 |
if (node->rb_left) { node = node->rb_left; while (node->rb_right) node=node->rb_right; |
f4b477c47 rbtree: add const... |
469 |
return (struct rb_node *)node; |
1da177e4c Linux-2.6.12-rc2 |
470 |
} |
7ce6ff9e5 rbtree: coding st... |
471 472 473 474 |
/* * No left-hand children. Go up till we find an ancestor which * is a right-hand child of its parent. */ |
55a981027 [RBTREE] Merge co... |
475 476 |
while ((parent = rb_parent(node)) && node == parent->rb_left) node = parent; |
1da177e4c Linux-2.6.12-rc2 |
477 |
|
55a981027 [RBTREE] Merge co... |
478 |
return parent; |
1da177e4c Linux-2.6.12-rc2 |
479 480 481 482 483 484 |
} EXPORT_SYMBOL(rb_prev); void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { |
55a981027 [RBTREE] Merge co... |
485 |
struct rb_node *parent = rb_parent(victim); |
1da177e4c Linux-2.6.12-rc2 |
486 487 |
/* Set the surrounding nodes to point to the replacement */ |
7abc704ae rbtree: add __rb_... |
488 |
__rb_change_child(victim, new, parent, root); |
1da177e4c Linux-2.6.12-rc2 |
489 |
if (victim->rb_left) |
55a981027 [RBTREE] Merge co... |
490 |
rb_set_parent(victim->rb_left, new); |
1da177e4c Linux-2.6.12-rc2 |
491 |
if (victim->rb_right) |
55a981027 [RBTREE] Merge co... |
492 |
rb_set_parent(victim->rb_right, new); |
1da177e4c Linux-2.6.12-rc2 |
493 494 495 496 497 |
/* Copy the pointers/colour from the victim to the replacement */ *new = *victim; } EXPORT_SYMBOL(rb_replace_node); |
9dee5c515 rbtree: add posto... |
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 536 537 |
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); |