11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds Red Black Trees 31da177e4SLinus Torvalds (C) 1999 Andrea Arcangeli <andrea@suse.de> 41da177e4SLinus Torvalds (C) 2002 David Woodhouse <dwmw2@infradead.org> 51da177e4SLinus Torvalds 61da177e4SLinus Torvalds This program is free software; you can redistribute it and/or modify 71da177e4SLinus Torvalds it under the terms of the GNU General Public License as published by 81da177e4SLinus Torvalds the Free Software Foundation; either version 2 of the License, or 91da177e4SLinus Torvalds (at your option) any later version. 101da177e4SLinus Torvalds 111da177e4SLinus Torvalds This program is distributed in the hope that it will be useful, 121da177e4SLinus Torvalds but WITHOUT ANY WARRANTY; without even the implied warranty of 131da177e4SLinus Torvalds MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 141da177e4SLinus Torvalds GNU General Public License for more details. 151da177e4SLinus Torvalds 161da177e4SLinus Torvalds You should have received a copy of the GNU General Public License 171da177e4SLinus Torvalds along with this program; if not, write to the Free Software 181da177e4SLinus Torvalds Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 191da177e4SLinus Torvalds 201da177e4SLinus Torvalds linux/lib/rbtree.c 211da177e4SLinus Torvalds */ 221da177e4SLinus Torvalds 231da177e4SLinus Torvalds #include <linux/rbtree.h> 248bc3bcc9SPaul Gortmaker #include <linux/export.h> 251da177e4SLinus Torvalds 26bf7ad8eeSMichel Lespinasse #define RB_RED 0 27bf7ad8eeSMichel Lespinasse #define RB_BLACK 1 28bf7ad8eeSMichel Lespinasse 29bf7ad8eeSMichel Lespinasse #define rb_color(r) ((r)->__rb_parent_color & 1) 30bf7ad8eeSMichel Lespinasse #define rb_is_red(r) (!rb_color(r)) 31bf7ad8eeSMichel Lespinasse #define rb_is_black(r) rb_color(r) 32bf7ad8eeSMichel Lespinasse #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) 33bf7ad8eeSMichel Lespinasse #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) 34bf7ad8eeSMichel Lespinasse 35bf7ad8eeSMichel Lespinasse static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 36bf7ad8eeSMichel Lespinasse { 37bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 38bf7ad8eeSMichel Lespinasse } 39bf7ad8eeSMichel Lespinasse static inline void rb_set_color(struct rb_node *rb, int color) 40bf7ad8eeSMichel Lespinasse { 41bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; 42bf7ad8eeSMichel Lespinasse } 43bf7ad8eeSMichel Lespinasse 441da177e4SLinus Torvalds static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 451da177e4SLinus Torvalds { 461da177e4SLinus Torvalds struct rb_node *right = node->rb_right; 4755a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 481da177e4SLinus Torvalds 491da177e4SLinus Torvalds if ((node->rb_right = right->rb_left)) 5055a98102SDavid Woodhouse rb_set_parent(right->rb_left, node); 511da177e4SLinus Torvalds right->rb_left = node; 521da177e4SLinus Torvalds 5355a98102SDavid Woodhouse rb_set_parent(right, parent); 5455a98102SDavid Woodhouse 5555a98102SDavid Woodhouse if (parent) 561da177e4SLinus Torvalds { 5755a98102SDavid Woodhouse if (node == parent->rb_left) 5855a98102SDavid Woodhouse parent->rb_left = right; 591da177e4SLinus Torvalds else 6055a98102SDavid Woodhouse parent->rb_right = right; 611da177e4SLinus Torvalds } 621da177e4SLinus Torvalds else 631da177e4SLinus Torvalds root->rb_node = right; 6455a98102SDavid Woodhouse rb_set_parent(node, right); 651da177e4SLinus Torvalds } 661da177e4SLinus Torvalds 671da177e4SLinus Torvalds static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 681da177e4SLinus Torvalds { 691da177e4SLinus Torvalds struct rb_node *left = node->rb_left; 7055a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 711da177e4SLinus Torvalds 721da177e4SLinus Torvalds if ((node->rb_left = left->rb_right)) 7355a98102SDavid Woodhouse rb_set_parent(left->rb_right, node); 741da177e4SLinus Torvalds left->rb_right = node; 751da177e4SLinus Torvalds 7655a98102SDavid Woodhouse rb_set_parent(left, parent); 7755a98102SDavid Woodhouse 7855a98102SDavid Woodhouse if (parent) 791da177e4SLinus Torvalds { 8055a98102SDavid Woodhouse if (node == parent->rb_right) 8155a98102SDavid Woodhouse parent->rb_right = left; 821da177e4SLinus Torvalds else 8355a98102SDavid Woodhouse parent->rb_left = left; 841da177e4SLinus Torvalds } 851da177e4SLinus Torvalds else 861da177e4SLinus Torvalds root->rb_node = left; 8755a98102SDavid Woodhouse rb_set_parent(node, left); 881da177e4SLinus Torvalds } 891da177e4SLinus Torvalds 901da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 911da177e4SLinus Torvalds { 921da177e4SLinus Torvalds struct rb_node *parent, *gparent; 931da177e4SLinus Torvalds 94*6d58452dSMichel Lespinasse while (true) { 95*6d58452dSMichel Lespinasse /* 96*6d58452dSMichel Lespinasse * Loop invariant: node is red 97*6d58452dSMichel Lespinasse * 98*6d58452dSMichel Lespinasse * If there is a black parent, we are done. 99*6d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 100*6d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 101*6d58452dSMichel Lespinasse */ 102*6d58452dSMichel Lespinasse parent = rb_parent(node); 103*6d58452dSMichel Lespinasse if (!parent) { 104*6d58452dSMichel Lespinasse rb_set_black(node); 105*6d58452dSMichel Lespinasse break; 106*6d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 107*6d58452dSMichel Lespinasse break; 108*6d58452dSMichel Lespinasse 10955a98102SDavid Woodhouse gparent = rb_parent(parent); 1101da177e4SLinus Torvalds 1111da177e4SLinus Torvalds if (parent == gparent->rb_left) 1121da177e4SLinus Torvalds { 1131da177e4SLinus Torvalds { 1141da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_right; 11555a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1161da177e4SLinus Torvalds { 11755a98102SDavid Woodhouse rb_set_black(uncle); 11855a98102SDavid Woodhouse rb_set_black(parent); 11955a98102SDavid Woodhouse rb_set_red(gparent); 1201da177e4SLinus Torvalds node = gparent; 1211da177e4SLinus Torvalds continue; 1221da177e4SLinus Torvalds } 1231da177e4SLinus Torvalds } 1241da177e4SLinus Torvalds 1251f052865SMichel Lespinasse if (parent->rb_right == node) { 1261da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1271da177e4SLinus Torvalds parent = node; 1281da177e4SLinus Torvalds } 1291da177e4SLinus Torvalds 13055a98102SDavid Woodhouse rb_set_black(parent); 13155a98102SDavid Woodhouse rb_set_red(gparent); 1321da177e4SLinus Torvalds __rb_rotate_right(gparent, root); 1331f052865SMichel Lespinasse break; 1341da177e4SLinus Torvalds } else { 1351da177e4SLinus Torvalds { 1361da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_left; 13755a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1381da177e4SLinus Torvalds { 13955a98102SDavid Woodhouse rb_set_black(uncle); 14055a98102SDavid Woodhouse rb_set_black(parent); 14155a98102SDavid Woodhouse rb_set_red(gparent); 1421da177e4SLinus Torvalds node = gparent; 1431da177e4SLinus Torvalds continue; 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds 1471f052865SMichel Lespinasse if (parent->rb_left == node) { 1481da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1491da177e4SLinus Torvalds parent = node; 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds 15255a98102SDavid Woodhouse rb_set_black(parent); 15355a98102SDavid Woodhouse rb_set_red(gparent); 1541da177e4SLinus Torvalds __rb_rotate_left(gparent, root); 1551f052865SMichel Lespinasse break; 1561da177e4SLinus Torvalds } 1571da177e4SLinus Torvalds } 1581da177e4SLinus Torvalds } 1591da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 1601da177e4SLinus Torvalds 1611da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 1621da177e4SLinus Torvalds struct rb_root *root) 1631da177e4SLinus Torvalds { 1641da177e4SLinus Torvalds struct rb_node *other; 1651da177e4SLinus Torvalds 16655a98102SDavid Woodhouse while ((!node || rb_is_black(node)) && node != root->rb_node) 1671da177e4SLinus Torvalds { 1681da177e4SLinus Torvalds if (parent->rb_left == node) 1691da177e4SLinus Torvalds { 1701da177e4SLinus Torvalds other = parent->rb_right; 17155a98102SDavid Woodhouse if (rb_is_red(other)) 1721da177e4SLinus Torvalds { 17355a98102SDavid Woodhouse rb_set_black(other); 17455a98102SDavid Woodhouse rb_set_red(parent); 1751da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1761da177e4SLinus Torvalds other = parent->rb_right; 1771da177e4SLinus Torvalds } 17855a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 17955a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1801da177e4SLinus Torvalds { 18155a98102SDavid Woodhouse rb_set_red(other); 1821da177e4SLinus Torvalds node = parent; 18355a98102SDavid Woodhouse parent = rb_parent(node); 1841da177e4SLinus Torvalds } 1851da177e4SLinus Torvalds else 1861da177e4SLinus Torvalds { 18755a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 1881da177e4SLinus Torvalds { 18955a63998SWolfram Strepp rb_set_black(other->rb_left); 19055a98102SDavid Woodhouse rb_set_red(other); 1911da177e4SLinus Torvalds __rb_rotate_right(other, root); 1921da177e4SLinus Torvalds other = parent->rb_right; 1931da177e4SLinus Torvalds } 1942f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 19555a98102SDavid Woodhouse rb_set_black(parent); 19655a98102SDavid Woodhouse rb_set_black(other->rb_right); 1971da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1981da177e4SLinus Torvalds node = root->rb_node; 1991da177e4SLinus Torvalds break; 2001da177e4SLinus Torvalds } 2011da177e4SLinus Torvalds } 2021da177e4SLinus Torvalds else 2031da177e4SLinus Torvalds { 2041da177e4SLinus Torvalds other = parent->rb_left; 20555a98102SDavid Woodhouse if (rb_is_red(other)) 2061da177e4SLinus Torvalds { 20755a98102SDavid Woodhouse rb_set_black(other); 20855a98102SDavid Woodhouse rb_set_red(parent); 2091da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2101da177e4SLinus Torvalds other = parent->rb_left; 2111da177e4SLinus Torvalds } 21255a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 21355a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 2141da177e4SLinus Torvalds { 21555a98102SDavid Woodhouse rb_set_red(other); 2161da177e4SLinus Torvalds node = parent; 21755a98102SDavid Woodhouse parent = rb_parent(node); 2181da177e4SLinus Torvalds } 2191da177e4SLinus Torvalds else 2201da177e4SLinus Torvalds { 22155a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 2221da177e4SLinus Torvalds { 22355a63998SWolfram Strepp rb_set_black(other->rb_right); 22455a98102SDavid Woodhouse rb_set_red(other); 2251da177e4SLinus Torvalds __rb_rotate_left(other, root); 2261da177e4SLinus Torvalds other = parent->rb_left; 2271da177e4SLinus Torvalds } 2282f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 22955a98102SDavid Woodhouse rb_set_black(parent); 23055a98102SDavid Woodhouse rb_set_black(other->rb_left); 2311da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2321da177e4SLinus Torvalds node = root->rb_node; 2331da177e4SLinus Torvalds break; 2341da177e4SLinus Torvalds } 2351da177e4SLinus Torvalds } 2361da177e4SLinus Torvalds } 2371da177e4SLinus Torvalds if (node) 23855a98102SDavid Woodhouse rb_set_black(node); 2391da177e4SLinus Torvalds } 2401da177e4SLinus Torvalds 2411da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 2421da177e4SLinus Torvalds { 2431da177e4SLinus Torvalds struct rb_node *child, *parent; 2441da177e4SLinus Torvalds int color; 2451da177e4SLinus Torvalds 2461da177e4SLinus Torvalds if (!node->rb_left) 2471da177e4SLinus Torvalds child = node->rb_right; 2481da177e4SLinus Torvalds else if (!node->rb_right) 2491da177e4SLinus Torvalds child = node->rb_left; 2501da177e4SLinus Torvalds else 2511da177e4SLinus Torvalds { 2521da177e4SLinus Torvalds struct rb_node *old = node, *left; 2531da177e4SLinus Torvalds 2541da177e4SLinus Torvalds node = node->rb_right; 2551da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 2561da177e4SLinus Torvalds node = left; 25716c047adSWolfram Strepp 25816c047adSWolfram Strepp if (rb_parent(old)) { 25916c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 26016c047adSWolfram Strepp rb_parent(old)->rb_left = node; 26116c047adSWolfram Strepp else 26216c047adSWolfram Strepp rb_parent(old)->rb_right = node; 26316c047adSWolfram Strepp } else 26416c047adSWolfram Strepp root->rb_node = node; 26516c047adSWolfram Strepp 2661da177e4SLinus Torvalds child = node->rb_right; 26755a98102SDavid Woodhouse parent = rb_parent(node); 2682f3243aeSDavid Woodhouse color = rb_color(node); 2691da177e4SLinus Torvalds 2704c601178SWolfram Strepp if (parent == old) { 2714c601178SWolfram Strepp parent = node; 2724c601178SWolfram Strepp } else { 2731da177e4SLinus Torvalds if (child) 27455a98102SDavid Woodhouse rb_set_parent(child, parent); 2751975e593SDavid Woodhouse parent->rb_left = child; 2764b324126SWolfram Strepp 2774b324126SWolfram Strepp node->rb_right = old->rb_right; 2784b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 2794c601178SWolfram Strepp } 2801975e593SDavid Woodhouse 281bf7ad8eeSMichel Lespinasse node->__rb_parent_color = old->__rb_parent_color; 2821da177e4SLinus Torvalds node->rb_left = old->rb_left; 28355a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 2844b324126SWolfram Strepp 2851da177e4SLinus Torvalds goto color; 2861da177e4SLinus Torvalds } 2871da177e4SLinus Torvalds 28855a98102SDavid Woodhouse parent = rb_parent(node); 2892f3243aeSDavid Woodhouse color = rb_color(node); 2901da177e4SLinus Torvalds 2911da177e4SLinus Torvalds if (child) 29255a98102SDavid Woodhouse rb_set_parent(child, parent); 293b945d6b2SPeter Zijlstra if (parent) 294b945d6b2SPeter Zijlstra { 2951da177e4SLinus Torvalds if (parent->rb_left == node) 2961da177e4SLinus Torvalds parent->rb_left = child; 2971da177e4SLinus Torvalds else 2981da177e4SLinus Torvalds parent->rb_right = child; 29917d9ddc7SPallipadi, Venkatesh } 300b945d6b2SPeter Zijlstra else 301b945d6b2SPeter Zijlstra root->rb_node = child; 3021da177e4SLinus Torvalds 3031da177e4SLinus Torvalds color: 3041da177e4SLinus Torvalds if (color == RB_BLACK) 3051da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 3061da177e4SLinus Torvalds } 3071da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 3081da177e4SLinus Torvalds 309b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 310b945d6b2SPeter Zijlstra { 311b945d6b2SPeter Zijlstra struct rb_node *parent; 312b945d6b2SPeter Zijlstra 313b945d6b2SPeter Zijlstra up: 314b945d6b2SPeter Zijlstra func(node, data); 315b945d6b2SPeter Zijlstra parent = rb_parent(node); 316b945d6b2SPeter Zijlstra if (!parent) 317b945d6b2SPeter Zijlstra return; 318b945d6b2SPeter Zijlstra 319b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 320b945d6b2SPeter Zijlstra func(parent->rb_right, data); 321b945d6b2SPeter Zijlstra else if (parent->rb_left) 322b945d6b2SPeter Zijlstra func(parent->rb_left, data); 323b945d6b2SPeter Zijlstra 324b945d6b2SPeter Zijlstra node = parent; 325b945d6b2SPeter Zijlstra goto up; 326b945d6b2SPeter Zijlstra } 327b945d6b2SPeter Zijlstra 328b945d6b2SPeter Zijlstra /* 329b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 330b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 331b945d6b2SPeter Zijlstra */ 332b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 333b945d6b2SPeter Zijlstra { 334b945d6b2SPeter Zijlstra if (node->rb_left) 335b945d6b2SPeter Zijlstra node = node->rb_left; 336b945d6b2SPeter Zijlstra else if (node->rb_right) 337b945d6b2SPeter Zijlstra node = node->rb_right; 338b945d6b2SPeter Zijlstra 339b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 340b945d6b2SPeter Zijlstra } 3410b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 342b945d6b2SPeter Zijlstra 343b945d6b2SPeter Zijlstra /* 344b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 345b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 346b945d6b2SPeter Zijlstra */ 347b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 348b945d6b2SPeter Zijlstra { 349b945d6b2SPeter Zijlstra struct rb_node *deepest; 350b945d6b2SPeter Zijlstra 351b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 352b945d6b2SPeter Zijlstra deepest = rb_parent(node); 353b945d6b2SPeter Zijlstra else if (!node->rb_right) 354b945d6b2SPeter Zijlstra deepest = node->rb_left; 355b945d6b2SPeter Zijlstra else if (!node->rb_left) 356b945d6b2SPeter Zijlstra deepest = node->rb_right; 357b945d6b2SPeter Zijlstra else { 358b945d6b2SPeter Zijlstra deepest = rb_next(node); 359b945d6b2SPeter Zijlstra if (deepest->rb_right) 360b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 361b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 362b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 363b945d6b2SPeter Zijlstra } 364b945d6b2SPeter Zijlstra 365b945d6b2SPeter Zijlstra return deepest; 366b945d6b2SPeter Zijlstra } 3670b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 368b945d6b2SPeter Zijlstra 369b945d6b2SPeter Zijlstra /* 370b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 371b945d6b2SPeter Zijlstra * and any rebalance damage. 372b945d6b2SPeter Zijlstra */ 373b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 374b945d6b2SPeter Zijlstra { 375b945d6b2SPeter Zijlstra if (node) 376b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 377b945d6b2SPeter Zijlstra } 3780b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 379b945d6b2SPeter Zijlstra 3801da177e4SLinus Torvalds /* 3811da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 3821da177e4SLinus Torvalds */ 383f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 3841da177e4SLinus Torvalds { 3851da177e4SLinus Torvalds struct rb_node *n; 3861da177e4SLinus Torvalds 3871da177e4SLinus Torvalds n = root->rb_node; 3881da177e4SLinus Torvalds if (!n) 3891da177e4SLinus Torvalds return NULL; 3901da177e4SLinus Torvalds while (n->rb_left) 3911da177e4SLinus Torvalds n = n->rb_left; 3921da177e4SLinus Torvalds return n; 3931da177e4SLinus Torvalds } 3941da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 3951da177e4SLinus Torvalds 396f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 3971da177e4SLinus Torvalds { 3981da177e4SLinus Torvalds struct rb_node *n; 3991da177e4SLinus Torvalds 4001da177e4SLinus Torvalds n = root->rb_node; 4011da177e4SLinus Torvalds if (!n) 4021da177e4SLinus Torvalds return NULL; 4031da177e4SLinus Torvalds while (n->rb_right) 4041da177e4SLinus Torvalds n = n->rb_right; 4051da177e4SLinus Torvalds return n; 4061da177e4SLinus Torvalds } 4071da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 4081da177e4SLinus Torvalds 409f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 4101da177e4SLinus Torvalds { 41155a98102SDavid Woodhouse struct rb_node *parent; 41255a98102SDavid Woodhouse 4134c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 41410fd48f2SJens Axboe return NULL; 41510fd48f2SJens Axboe 4161da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 4171da177e4SLinus Torvalds as we can. */ 4181da177e4SLinus Torvalds if (node->rb_right) { 4191da177e4SLinus Torvalds node = node->rb_right; 4201da177e4SLinus Torvalds while (node->rb_left) 4211da177e4SLinus Torvalds node=node->rb_left; 422f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4231da177e4SLinus Torvalds } 4241da177e4SLinus Torvalds 4251da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 4261da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 4271da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 4281da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 4291da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 4301da177e4SLinus Torvalds parent is our 'next' node. */ 43155a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 43255a98102SDavid Woodhouse node = parent; 4331da177e4SLinus Torvalds 43455a98102SDavid Woodhouse return parent; 4351da177e4SLinus Torvalds } 4361da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 4371da177e4SLinus Torvalds 438f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 4391da177e4SLinus Torvalds { 44055a98102SDavid Woodhouse struct rb_node *parent; 44155a98102SDavid Woodhouse 4424c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 44310fd48f2SJens Axboe return NULL; 44410fd48f2SJens Axboe 4451da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 4461da177e4SLinus Torvalds as we can. */ 4471da177e4SLinus Torvalds if (node->rb_left) { 4481da177e4SLinus Torvalds node = node->rb_left; 4491da177e4SLinus Torvalds while (node->rb_right) 4501da177e4SLinus Torvalds node=node->rb_right; 451f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4521da177e4SLinus Torvalds } 4531da177e4SLinus Torvalds 4541da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 4551da177e4SLinus Torvalds is a right-hand child of its parent */ 45655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 45755a98102SDavid Woodhouse node = parent; 4581da177e4SLinus Torvalds 45955a98102SDavid Woodhouse return parent; 4601da177e4SLinus Torvalds } 4611da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 4621da177e4SLinus Torvalds 4631da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 4641da177e4SLinus Torvalds struct rb_root *root) 4651da177e4SLinus Torvalds { 46655a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 4671da177e4SLinus Torvalds 4681da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 4691da177e4SLinus Torvalds if (parent) { 4701da177e4SLinus Torvalds if (victim == parent->rb_left) 4711da177e4SLinus Torvalds parent->rb_left = new; 4721da177e4SLinus Torvalds else 4731da177e4SLinus Torvalds parent->rb_right = new; 4741da177e4SLinus Torvalds } else { 4751da177e4SLinus Torvalds root->rb_node = new; 4761da177e4SLinus Torvalds } 4771da177e4SLinus Torvalds if (victim->rb_left) 47855a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 4791da177e4SLinus Torvalds if (victim->rb_right) 48055a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 4811da177e4SLinus Torvalds 4821da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 4831da177e4SLinus Torvalds *new = *victim; 4841da177e4SLinus Torvalds } 4851da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 486