Blame view
lib/rbtree.c
17.1 KB
1a59d1b8e treewide: Replace... |
1 |
// SPDX-License-Identifier: GPL-2.0-or-later |
1da177e4c Linux-2.6.12-rc2 |
2 3 4 5 |
/* Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> (C) 2002 David Woodhouse <dwmw2@infradead.org> |
46b6135a7 rbtree: handle 1-... |
6 |
(C) 2012 Michel Lespinasse <walken@google.com> |
1da177e4c Linux-2.6.12-rc2 |
7 8 9 |
linux/lib/rbtree.c */ |
9c079add0 rbtree: move augm... |
10 |
#include <linux/rbtree_augmented.h> |
8bc3bcc93 lib: reduce the u... |
11 |
#include <linux/export.h> |
1da177e4c Linux-2.6.12-rc2 |
12 |
|
5bc9188aa rbtree: low level... |
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/* * 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... |
29 30 |
* nodes will be lowercase. Unknown color nodes shall be drawn as red within * parentheses and have some accompanying text comment. |
5bc9188aa rbtree: low level... |
31 |
*/ |
d72da4a4d rbtree: Make lock... |
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
/* * Notes on lockless lookups: * * All stores to the tree structure (rb_left and rb_right) must be done using * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the * tree structure as seen in program order. * * These two requirements will allow lockless iteration of the tree -- not * correct iteration mind you, tree rotations are not atomic so a lookup might * miss entire subtrees. * * But they do guarantee that any such traversal will only see valid elements * and that it will indeed complete -- does not get stuck in a loop. * * It also guarantees that if the lookup returns an element it is the 'correct' * one. But not returning an element does _NOT_ mean it's not present. * * NOTE: * * Stores to __rb_parent_color are not important for simple lookups so those * are left undone as of now. Nor did I check for loops involving parent * pointers. */ |
46b6135a7 rbtree: handle 1-... |
55 56 57 58 |
static inline void rb_set_black(struct rb_node *rb) { rb->__rb_parent_color |= RB_BLACK; } |
5bc9188aa rbtree: low level... |
59 60 61 62 |
static inline struct rb_node *rb_red_parent(struct rb_node *red) { return (struct rb_node *)red->__rb_parent_color; } |
5bc9188aa rbtree: low level... |
63 64 65 66 67 68 69 70 71 72 73 74 |
/* * 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_... |
75 |
__rb_change_child(old, new, parent, root); |
5bc9188aa rbtree: low level... |
76 |
} |
14b94af0b rbtree: faster au... |
77 78 79 |
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 |
80 |
{ |
5bc9188aa rbtree: low level... |
81 |
struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; |
1da177e4c Linux-2.6.12-rc2 |
82 |
|
6d58452dc rbtree: adjust ro... |
83 84 |
while (true) { /* |
2aadf7fc7 rbtree: optimize ... |
85 |
* Loop invariant: node is red. |
6d58452dc rbtree: adjust ro... |
86 |
*/ |
2aadf7fc7 rbtree: optimize ... |
87 88 89 90 91 92 |
if (unlikely(!parent)) { /* * The inserted node is root. Either this is the * first node, or we recursed at Case 1 below and * are no longer violating 4). */ |
5bc9188aa rbtree: low level... |
93 |
rb_set_parent_color(node, NULL, RB_BLACK); |
6d58452dc rbtree: adjust ro... |
94 |
break; |
2aadf7fc7 rbtree: optimize ... |
95 96 97 98 99 100 101 102 103 |
} /* * If there is a black parent, we are done. * Otherwise, take some corrective action as, * per 4), we don't want a red root or two * consecutive red nodes. */ if(rb_is_black(parent)) |
6d58452dc rbtree: adjust ro... |
104 |
break; |
5bc9188aa rbtree: low level... |
105 |
gparent = rb_red_parent(parent); |
59633abf3 rbtree: optimize ... |
106 107 |
tmp = gparent->rb_right; if (parent != tmp) { /* parent == gparent->rb_left */ |
5bc9188aa rbtree: low level... |
108 109 |
if (tmp && rb_is_red(tmp)) { /* |
35dc67d7d rbtree: add some ... |
110 |
* Case 1 - node's uncle is red (color flips). |
5bc9188aa rbtree: low level... |
111 112 113 114 115 |
* * G g * / \ / \ * p u --> P U * / / |
1b9c53e84 lib/rbtree.c: fix... |
116 |
* n n |
5bc9188aa rbtree: low level... |
117 118 119 120 121 122 123 124 125 126 127 |
* * 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 |
128 |
} |
59633abf3 rbtree: optimize ... |
129 130 |
tmp = parent->rb_right; if (node == tmp) { |
5bc9188aa rbtree: low level... |
131 |
/* |
35dc67d7d rbtree: add some ... |
132 133 |
* Case 2 - node's uncle is black and node is * the parent's right child (left rotate at parent). |
5bc9188aa rbtree: low level... |
134 135 136 137 138 139 140 141 142 143 |
* * G G * / \ / \ * p U --> n U * \ / * n p * * This still leaves us in violation of 4), the * continuation into Case 3 will fix that. */ |
d72da4a4d rbtree: Make lock... |
144 145 146 |
tmp = node->rb_left; WRITE_ONCE(parent->rb_right, tmp); WRITE_ONCE(node->rb_left, parent); |
5bc9188aa rbtree: low level... |
147 148 149 150 |
if (tmp) rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); |
14b94af0b rbtree: faster au... |
151 |
augment_rotate(parent, node); |
1da177e4c Linux-2.6.12-rc2 |
152 |
parent = node; |
59633abf3 rbtree: optimize ... |
153 |
tmp = node->rb_right; |
1da177e4c Linux-2.6.12-rc2 |
154 |
} |
5bc9188aa rbtree: low level... |
155 |
/* |
35dc67d7d rbtree: add some ... |
156 157 |
* Case 3 - node's uncle is black and node is * the parent's left child (right rotate at gparent). |
5bc9188aa rbtree: low level... |
158 159 160 161 162 163 164 |
* * G P * / \ / \ * p U --> n g * / \ * n U */ |
d72da4a4d rbtree: Make lock... |
165 166 |
WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ WRITE_ONCE(parent->rb_right, gparent); |
5bc9188aa rbtree: low level... |
167 168 169 |
if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); |
14b94af0b rbtree: faster au... |
170 |
augment_rotate(gparent, parent); |
1f0528653 rbtree: break out... |
171 |
break; |
1da177e4c Linux-2.6.12-rc2 |
172 |
} else { |
5bc9188aa rbtree: low level... |
173 174 175 176 177 178 179 180 181 |
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 |
182 |
} |
59633abf3 rbtree: optimize ... |
183 184 |
tmp = parent->rb_left; if (node == tmp) { |
5bc9188aa rbtree: low level... |
185 |
/* Case 2 - right rotate at parent */ |
d72da4a4d rbtree: Make lock... |
186 187 188 |
tmp = node->rb_right; WRITE_ONCE(parent->rb_left, tmp); WRITE_ONCE(node->rb_right, parent); |
5bc9188aa rbtree: low level... |
189 190 191 192 |
if (tmp) rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); |
14b94af0b rbtree: faster au... |
193 |
augment_rotate(parent, node); |
1da177e4c Linux-2.6.12-rc2 |
194 |
parent = node; |
59633abf3 rbtree: optimize ... |
195 |
tmp = node->rb_left; |
1da177e4c Linux-2.6.12-rc2 |
196 |
} |
5bc9188aa rbtree: low level... |
197 |
/* Case 3 - left rotate at gparent */ |
d72da4a4d rbtree: Make lock... |
198 199 |
WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ WRITE_ONCE(parent->rb_left, gparent); |
5bc9188aa rbtree: low level... |
200 201 202 |
if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); |
14b94af0b rbtree: faster au... |
203 |
augment_rotate(gparent, parent); |
1f0528653 rbtree: break out... |
204 |
break; |
1da177e4c Linux-2.6.12-rc2 |
205 206 |
} } |
1da177e4c Linux-2.6.12-rc2 |
207 |
} |
1da177e4c Linux-2.6.12-rc2 |
208 |
|
3cb7a5634 lib/rbtree.c: avo... |
209 210 211 212 213 214 |
/* * 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... |
215 |
void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) |
1da177e4c Linux-2.6.12-rc2 |
216 |
{ |
46b6135a7 rbtree: handle 1-... |
217 |
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; |
1da177e4c Linux-2.6.12-rc2 |
218 |
|
d6ff12739 rbtree: adjust no... |
219 220 |
while (true) { /* |
46b6135a7 rbtree: handle 1-... |
221 222 223 224 225 |
* 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... |
226 |
*/ |
59633abf3 rbtree: optimize ... |
227 228 |
sibling = parent->rb_right; if (node != sibling) { /* node == parent->rb_left */ |
6280d2356 rbtree: low level... |
229 230 231 232 233 234 235 236 237 238 |
if (rb_is_red(sibling)) { /* * Case 1 - left rotate at parent * * P S * / \ / \ * N s --> p Sr * / \ / \ * Sl Sr N Sl */ |
d72da4a4d rbtree: Make lock... |
239 240 241 |
tmp1 = sibling->rb_left; WRITE_ONCE(parent->rb_right, tmp1); WRITE_ONCE(sibling->rb_left, parent); |
6280d2356 rbtree: low level... |
242 243 244 |
rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); |
9c079add0 rbtree: move augm... |
245 |
augment_rotate(parent, sibling); |
6280d2356 rbtree: low level... |
246 |
sibling = tmp1; |
1da177e4c Linux-2.6.12-rc2 |
247 |
} |
6280d2356 rbtree: low level... |
248 249 250 251 252 253 254 255 256 257 258 259 260 261 |
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-... |
262 263 264 265 |
* 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... |
266 267 268 |
*/ rb_set_parent_color(sibling, parent, RB_RED); |
46b6135a7 rbtree: handle 1-... |
269 270 271 272 273 274 275 276 277 |
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 |
278 |
} |
6280d2356 rbtree: low level... |
279 280 281 282 283 284 |
/* * Case 3 - right rotate at sibling * (p could be either color here) * * (p) (p) * / \ / \ |
ce093a045 lib/rbtree.c: fix... |
285 |
* N S --> N sl |
6280d2356 rbtree: low level... |
286 |
* / \ \ |
ce093a045 lib/rbtree.c: fix... |
287 |
* sl Sr S |
6280d2356 rbtree: low level... |
288 289 |
* \ * Sr |
ce093a045 lib/rbtree.c: fix... |
290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 |
* * Note: p might be red, and then both * p and sl are red after rotation(which * breaks property 4). This is fixed in * Case 4 (in __rb_rotate_set_parents() * which set sl the color of p * and set p RB_BLACK) * * (p) (sl) * / \ / \ * N sl --> P S * \ / \ * S N Sr * \ * Sr |
6280d2356 rbtree: low level... |
305 |
*/ |
d72da4a4d rbtree: Make lock... |
306 307 308 309 |
tmp1 = tmp2->rb_right; WRITE_ONCE(sibling->rb_left, tmp1); WRITE_ONCE(tmp2->rb_right, sibling); WRITE_ONCE(parent->rb_right, tmp2); |
6280d2356 rbtree: low level... |
310 311 312 |
if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); |
9c079add0 rbtree: move augm... |
313 |
augment_rotate(sibling, tmp2); |
6280d2356 rbtree: low level... |
314 315 |
tmp1 = sibling; sibling = tmp2; |
1da177e4c Linux-2.6.12-rc2 |
316 |
} |
6280d2356 rbtree: low level... |
317 318 319 320 321 322 323 324 325 326 327 328 |
/* * 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) */ |
d72da4a4d rbtree: Make lock... |
329 330 331 |
tmp2 = sibling->rb_left; WRITE_ONCE(parent->rb_right, tmp2); WRITE_ONCE(sibling->rb_left, parent); |
6280d2356 rbtree: low level... |
332 333 334 335 336 |
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... |
337 |
augment_rotate(parent, sibling); |
e125d1471 rbtree: optimize ... |
338 |
break; |
d6ff12739 rbtree: adjust no... |
339 |
} else { |
6280d2356 rbtree: low level... |
340 341 342 |
sibling = parent->rb_left; if (rb_is_red(sibling)) { /* Case 1 - right rotate at parent */ |
d72da4a4d rbtree: Make lock... |
343 344 345 |
tmp1 = sibling->rb_right; WRITE_ONCE(parent->rb_left, tmp1); WRITE_ONCE(sibling->rb_right, parent); |
6280d2356 rbtree: low level... |
346 347 348 |
rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); |
9c079add0 rbtree: move augm... |
349 |
augment_rotate(parent, sibling); |
6280d2356 rbtree: low level... |
350 |
sibling = tmp1; |
1da177e4c Linux-2.6.12-rc2 |
351 |
} |
6280d2356 rbtree: low level... |
352 353 354 355 356 357 358 |
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-... |
359 360 361 362 363 364 365 366 367 |
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 |
368 |
} |
ce093a045 lib/rbtree.c: fix... |
369 |
/* Case 3 - left rotate at sibling */ |
d72da4a4d rbtree: Make lock... |
370 371 372 373 |
tmp1 = tmp2->rb_left; WRITE_ONCE(sibling->rb_right, tmp1); WRITE_ONCE(tmp2->rb_left, sibling); WRITE_ONCE(parent->rb_left, tmp2); |
6280d2356 rbtree: low level... |
374 375 376 |
if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); |
9c079add0 rbtree: move augm... |
377 |
augment_rotate(sibling, tmp2); |
6280d2356 rbtree: low level... |
378 379 |
tmp1 = sibling; sibling = tmp2; |
1da177e4c Linux-2.6.12-rc2 |
380 |
} |
ce093a045 lib/rbtree.c: fix... |
381 |
/* Case 4 - right rotate at parent + color flips */ |
d72da4a4d rbtree: Make lock... |
382 383 384 |
tmp2 = sibling->rb_right; WRITE_ONCE(parent->rb_left, tmp2); WRITE_ONCE(sibling->rb_right, parent); |
6280d2356 rbtree: low level... |
385 386 387 388 389 |
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... |
390 |
augment_rotate(parent, sibling); |
e125d1471 rbtree: optimize ... |
391 |
break; |
1da177e4c Linux-2.6.12-rc2 |
392 393 |
} } |
1da177e4c Linux-2.6.12-rc2 |
394 |
} |
3cb7a5634 lib/rbtree.c: avo... |
395 396 397 398 399 400 401 |
/* 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... |
402 |
EXPORT_SYMBOL(__rb_erase_color); |
14b94af0b rbtree: faster au... |
403 404 405 406 407 408 409 410 411 412 413 414 415 |
/* * 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 = { |
f231aebfc rbtree: use desig... |
416 417 418 |
.propagate = dummy_propagate, .copy = dummy_copy, .rotate = dummy_rotate |
14b94af0b rbtree: faster au... |
419 420 421 422 |
}; void rb_insert_color(struct rb_node *node, struct rb_root *root) { |
9f973cb38 lib/rbtree: avoid... |
423 |
__rb_insert(node, root, dummy_rotate); |
14b94af0b rbtree: faster au... |
424 425 426 427 428 |
} EXPORT_SYMBOL(rb_insert_color); void rb_erase(struct rb_node *node, struct rb_root *root) { |
3cb7a5634 lib/rbtree.c: avo... |
429 |
struct rb_node *rebalance; |
9f973cb38 lib/rbtree: avoid... |
430 |
rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); |
3cb7a5634 lib/rbtree.c: avo... |
431 432 |
if (rebalance) ____rb_erase_color(rebalance, root, dummy_rotate); |
1da177e4c Linux-2.6.12-rc2 |
433 434 |
} EXPORT_SYMBOL(rb_erase); |
14b94af0b rbtree: faster au... |
435 436 437 438 439 440 441 442 443 444 |
/* * 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)) { |
9f973cb38 lib/rbtree: avoid... |
445 |
__rb_insert(node, root, augment_rotate); |
14b94af0b rbtree: faster au... |
446 447 |
} EXPORT_SYMBOL(__rb_insert_augmented); |
1da177e4c Linux-2.6.12-rc2 |
448 449 450 |
/* * This function returns the first node (in sort order) of the tree. */ |
f4b477c47 rbtree: add const... |
451 |
struct rb_node *rb_first(const struct rb_root *root) |
1da177e4c Linux-2.6.12-rc2 |
452 453 454 455 456 457 458 459 460 461 462 |
{ 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... |
463 |
struct rb_node *rb_last(const struct rb_root *root) |
1da177e4c Linux-2.6.12-rc2 |
464 465 466 467 468 469 470 471 472 473 474 |
{ 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... |
475 |
struct rb_node *rb_next(const struct rb_node *node) |
1da177e4c Linux-2.6.12-rc2 |
476 |
{ |
55a981027 [RBTREE] Merge co... |
477 |
struct rb_node *parent; |
4c199a93a rbtree: empty nod... |
478 |
if (RB_EMPTY_NODE(node)) |
10fd48f23 [PATCH] rbtree: f... |
479 |
return NULL; |
7ce6ff9e5 rbtree: coding st... |
480 481 482 483 |
/* * If we have a right-hand child, go down and then left as far * as we can. */ |
1da177e4c Linux-2.6.12-rc2 |
484 |
if (node->rb_right) { |
cd9e61ed1 rbtree: cache lef... |
485 |
node = node->rb_right; |
1da177e4c Linux-2.6.12-rc2 |
486 487 |
while (node->rb_left) node=node->rb_left; |
f4b477c47 rbtree: add const... |
488 |
return (struct rb_node *)node; |
1da177e4c Linux-2.6.12-rc2 |
489 |
} |
7ce6ff9e5 rbtree: coding st... |
490 491 492 493 494 495 496 |
/* * 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... |
497 498 |
while ((parent = rb_parent(node)) && node == parent->rb_right) node = parent; |
1da177e4c Linux-2.6.12-rc2 |
499 |
|
55a981027 [RBTREE] Merge co... |
500 |
return parent; |
1da177e4c Linux-2.6.12-rc2 |
501 502 |
} EXPORT_SYMBOL(rb_next); |
f4b477c47 rbtree: add const... |
503 |
struct rb_node *rb_prev(const struct rb_node *node) |
1da177e4c Linux-2.6.12-rc2 |
504 |
{ |
55a981027 [RBTREE] Merge co... |
505 |
struct rb_node *parent; |
4c199a93a rbtree: empty nod... |
506 |
if (RB_EMPTY_NODE(node)) |
10fd48f23 [PATCH] rbtree: f... |
507 |
return NULL; |
7ce6ff9e5 rbtree: coding st... |
508 509 510 511 |
/* * If we have a left-hand child, go down and then right as far * as we can. */ |
1da177e4c Linux-2.6.12-rc2 |
512 |
if (node->rb_left) { |
cd9e61ed1 rbtree: cache lef... |
513 |
node = node->rb_left; |
1da177e4c Linux-2.6.12-rc2 |
514 515 |
while (node->rb_right) node=node->rb_right; |
f4b477c47 rbtree: add const... |
516 |
return (struct rb_node *)node; |
1da177e4c Linux-2.6.12-rc2 |
517 |
} |
7ce6ff9e5 rbtree: coding st... |
518 519 520 521 |
/* * No left-hand children. Go up till we find an ancestor which * is a right-hand child of its parent. */ |
55a981027 [RBTREE] Merge co... |
522 523 |
while ((parent = rb_parent(node)) && node == parent->rb_left) node = parent; |
1da177e4c Linux-2.6.12-rc2 |
524 |
|
55a981027 [RBTREE] Merge co... |
525 |
return parent; |
1da177e4c Linux-2.6.12-rc2 |
526 527 528 529 530 531 |
} EXPORT_SYMBOL(rb_prev); void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { |
55a981027 [RBTREE] Merge co... |
532 |
struct rb_node *parent = rb_parent(victim); |
1da177e4c Linux-2.6.12-rc2 |
533 |
|
c1adf2005 Introduce rb_repl... |
534 535 |
/* Copy the pointers/colour from the victim to the replacement */ *new = *victim; |
1da177e4c Linux-2.6.12-rc2 |
536 |
/* Set the surrounding nodes to point to the replacement */ |
1da177e4c Linux-2.6.12-rc2 |
537 |
if (victim->rb_left) |
55a981027 [RBTREE] Merge co... |
538 |
rb_set_parent(victim->rb_left, new); |
1da177e4c Linux-2.6.12-rc2 |
539 |
if (victim->rb_right) |
55a981027 [RBTREE] Merge co... |
540 |
rb_set_parent(victim->rb_right, new); |
c1adf2005 Introduce rb_repl... |
541 542 543 544 545 546 547 548 |
__rb_change_child(victim, new, parent, root); } EXPORT_SYMBOL(rb_replace_node); void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { struct rb_node *parent = rb_parent(victim); |
1da177e4c Linux-2.6.12-rc2 |
549 550 551 |
/* Copy the pointers/colour from the victim to the replacement */ *new = *victim; |
c1adf2005 Introduce rb_repl... |
552 553 554 555 556 557 558 559 560 561 562 563 |
/* Set the surrounding nodes to point to the replacement */ if (victim->rb_left) rb_set_parent(victim->rb_left, new); if (victim->rb_right) rb_set_parent(victim->rb_right, new); /* Set the parent's pointer to the new node last after an RCU barrier * so that the pointers onwards are seen to be set correctly when doing * an RCU walk over the tree. */ __rb_change_child_rcu(victim, new, parent, root); |
1da177e4c Linux-2.6.12-rc2 |
564 |
} |
c1adf2005 Introduce rb_repl... |
565 |
EXPORT_SYMBOL(rb_replace_node_rcu); |
9dee5c515 rbtree: add posto... |
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 |
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); |