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 9455a98102SDavid Woodhouse while ((parent = rb_parent(node)) && rb_is_red(parent)) 951da177e4SLinus Torvalds { 9655a98102SDavid Woodhouse gparent = rb_parent(parent); 971da177e4SLinus Torvalds 981da177e4SLinus Torvalds if (parent == gparent->rb_left) 991da177e4SLinus Torvalds { 1001da177e4SLinus Torvalds { 1011da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_right; 10255a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1031da177e4SLinus Torvalds { 10455a98102SDavid Woodhouse rb_set_black(uncle); 10555a98102SDavid Woodhouse rb_set_black(parent); 10655a98102SDavid Woodhouse rb_set_red(gparent); 1071da177e4SLinus Torvalds node = gparent; 1081da177e4SLinus Torvalds continue; 1091da177e4SLinus Torvalds } 1101da177e4SLinus Torvalds } 1111da177e4SLinus Torvalds 112*1f052865SMichel Lespinasse if (parent->rb_right == node) { 1131da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1141da177e4SLinus Torvalds parent = node; 1151da177e4SLinus Torvalds } 1161da177e4SLinus Torvalds 11755a98102SDavid Woodhouse rb_set_black(parent); 11855a98102SDavid Woodhouse rb_set_red(gparent); 1191da177e4SLinus Torvalds __rb_rotate_right(gparent, root); 120*1f052865SMichel Lespinasse break; 1211da177e4SLinus Torvalds } else { 1221da177e4SLinus Torvalds { 1231da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_left; 12455a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1251da177e4SLinus Torvalds { 12655a98102SDavid Woodhouse rb_set_black(uncle); 12755a98102SDavid Woodhouse rb_set_black(parent); 12855a98102SDavid Woodhouse rb_set_red(gparent); 1291da177e4SLinus Torvalds node = gparent; 1301da177e4SLinus Torvalds continue; 1311da177e4SLinus Torvalds } 1321da177e4SLinus Torvalds } 1331da177e4SLinus Torvalds 134*1f052865SMichel Lespinasse if (parent->rb_left == node) { 1351da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1361da177e4SLinus Torvalds parent = node; 1371da177e4SLinus Torvalds } 1381da177e4SLinus Torvalds 13955a98102SDavid Woodhouse rb_set_black(parent); 14055a98102SDavid Woodhouse rb_set_red(gparent); 1411da177e4SLinus Torvalds __rb_rotate_left(gparent, root); 142*1f052865SMichel Lespinasse break; 1431da177e4SLinus Torvalds } 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds 14655a98102SDavid Woodhouse rb_set_black(root->rb_node); 1471da177e4SLinus Torvalds } 1481da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 1491da177e4SLinus Torvalds 1501da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 1511da177e4SLinus Torvalds struct rb_root *root) 1521da177e4SLinus Torvalds { 1531da177e4SLinus Torvalds struct rb_node *other; 1541da177e4SLinus Torvalds 15555a98102SDavid Woodhouse while ((!node || rb_is_black(node)) && node != root->rb_node) 1561da177e4SLinus Torvalds { 1571da177e4SLinus Torvalds if (parent->rb_left == node) 1581da177e4SLinus Torvalds { 1591da177e4SLinus Torvalds other = parent->rb_right; 16055a98102SDavid Woodhouse if (rb_is_red(other)) 1611da177e4SLinus Torvalds { 16255a98102SDavid Woodhouse rb_set_black(other); 16355a98102SDavid Woodhouse rb_set_red(parent); 1641da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1651da177e4SLinus Torvalds other = parent->rb_right; 1661da177e4SLinus Torvalds } 16755a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 16855a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1691da177e4SLinus Torvalds { 17055a98102SDavid Woodhouse rb_set_red(other); 1711da177e4SLinus Torvalds node = parent; 17255a98102SDavid Woodhouse parent = rb_parent(node); 1731da177e4SLinus Torvalds } 1741da177e4SLinus Torvalds else 1751da177e4SLinus Torvalds { 17655a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 1771da177e4SLinus Torvalds { 17855a63998SWolfram Strepp rb_set_black(other->rb_left); 17955a98102SDavid Woodhouse rb_set_red(other); 1801da177e4SLinus Torvalds __rb_rotate_right(other, root); 1811da177e4SLinus Torvalds other = parent->rb_right; 1821da177e4SLinus Torvalds } 1832f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 18455a98102SDavid Woodhouse rb_set_black(parent); 18555a98102SDavid Woodhouse rb_set_black(other->rb_right); 1861da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1871da177e4SLinus Torvalds node = root->rb_node; 1881da177e4SLinus Torvalds break; 1891da177e4SLinus Torvalds } 1901da177e4SLinus Torvalds } 1911da177e4SLinus Torvalds else 1921da177e4SLinus Torvalds { 1931da177e4SLinus Torvalds other = parent->rb_left; 19455a98102SDavid Woodhouse if (rb_is_red(other)) 1951da177e4SLinus Torvalds { 19655a98102SDavid Woodhouse rb_set_black(other); 19755a98102SDavid Woodhouse rb_set_red(parent); 1981da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1991da177e4SLinus Torvalds other = parent->rb_left; 2001da177e4SLinus Torvalds } 20155a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 20255a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 2031da177e4SLinus Torvalds { 20455a98102SDavid Woodhouse rb_set_red(other); 2051da177e4SLinus Torvalds node = parent; 20655a98102SDavid Woodhouse parent = rb_parent(node); 2071da177e4SLinus Torvalds } 2081da177e4SLinus Torvalds else 2091da177e4SLinus Torvalds { 21055a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 2111da177e4SLinus Torvalds { 21255a63998SWolfram Strepp rb_set_black(other->rb_right); 21355a98102SDavid Woodhouse rb_set_red(other); 2141da177e4SLinus Torvalds __rb_rotate_left(other, root); 2151da177e4SLinus Torvalds other = parent->rb_left; 2161da177e4SLinus Torvalds } 2172f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 21855a98102SDavid Woodhouse rb_set_black(parent); 21955a98102SDavid Woodhouse rb_set_black(other->rb_left); 2201da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2211da177e4SLinus Torvalds node = root->rb_node; 2221da177e4SLinus Torvalds break; 2231da177e4SLinus Torvalds } 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds } 2261da177e4SLinus Torvalds if (node) 22755a98102SDavid Woodhouse rb_set_black(node); 2281da177e4SLinus Torvalds } 2291da177e4SLinus Torvalds 2301da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 2311da177e4SLinus Torvalds { 2321da177e4SLinus Torvalds struct rb_node *child, *parent; 2331da177e4SLinus Torvalds int color; 2341da177e4SLinus Torvalds 2351da177e4SLinus Torvalds if (!node->rb_left) 2361da177e4SLinus Torvalds child = node->rb_right; 2371da177e4SLinus Torvalds else if (!node->rb_right) 2381da177e4SLinus Torvalds child = node->rb_left; 2391da177e4SLinus Torvalds else 2401da177e4SLinus Torvalds { 2411da177e4SLinus Torvalds struct rb_node *old = node, *left; 2421da177e4SLinus Torvalds 2431da177e4SLinus Torvalds node = node->rb_right; 2441da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 2451da177e4SLinus Torvalds node = left; 24616c047adSWolfram Strepp 24716c047adSWolfram Strepp if (rb_parent(old)) { 24816c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 24916c047adSWolfram Strepp rb_parent(old)->rb_left = node; 25016c047adSWolfram Strepp else 25116c047adSWolfram Strepp rb_parent(old)->rb_right = node; 25216c047adSWolfram Strepp } else 25316c047adSWolfram Strepp root->rb_node = node; 25416c047adSWolfram Strepp 2551da177e4SLinus Torvalds child = node->rb_right; 25655a98102SDavid Woodhouse parent = rb_parent(node); 2572f3243aeSDavid Woodhouse color = rb_color(node); 2581da177e4SLinus Torvalds 2594c601178SWolfram Strepp if (parent == old) { 2604c601178SWolfram Strepp parent = node; 2614c601178SWolfram Strepp } else { 2621da177e4SLinus Torvalds if (child) 26355a98102SDavid Woodhouse rb_set_parent(child, parent); 2641975e593SDavid Woodhouse parent->rb_left = child; 2654b324126SWolfram Strepp 2664b324126SWolfram Strepp node->rb_right = old->rb_right; 2674b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 2684c601178SWolfram Strepp } 2691975e593SDavid Woodhouse 270bf7ad8eeSMichel Lespinasse node->__rb_parent_color = old->__rb_parent_color; 2711da177e4SLinus Torvalds node->rb_left = old->rb_left; 27255a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 2734b324126SWolfram Strepp 2741da177e4SLinus Torvalds goto color; 2751da177e4SLinus Torvalds } 2761da177e4SLinus Torvalds 27755a98102SDavid Woodhouse parent = rb_parent(node); 2782f3243aeSDavid Woodhouse color = rb_color(node); 2791da177e4SLinus Torvalds 2801da177e4SLinus Torvalds if (child) 28155a98102SDavid Woodhouse rb_set_parent(child, parent); 282b945d6b2SPeter Zijlstra if (parent) 283b945d6b2SPeter Zijlstra { 2841da177e4SLinus Torvalds if (parent->rb_left == node) 2851da177e4SLinus Torvalds parent->rb_left = child; 2861da177e4SLinus Torvalds else 2871da177e4SLinus Torvalds parent->rb_right = child; 28817d9ddc7SPallipadi, Venkatesh } 289b945d6b2SPeter Zijlstra else 290b945d6b2SPeter Zijlstra root->rb_node = child; 2911da177e4SLinus Torvalds 2921da177e4SLinus Torvalds color: 2931da177e4SLinus Torvalds if (color == RB_BLACK) 2941da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 2951da177e4SLinus Torvalds } 2961da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 2971da177e4SLinus Torvalds 298b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 299b945d6b2SPeter Zijlstra { 300b945d6b2SPeter Zijlstra struct rb_node *parent; 301b945d6b2SPeter Zijlstra 302b945d6b2SPeter Zijlstra up: 303b945d6b2SPeter Zijlstra func(node, data); 304b945d6b2SPeter Zijlstra parent = rb_parent(node); 305b945d6b2SPeter Zijlstra if (!parent) 306b945d6b2SPeter Zijlstra return; 307b945d6b2SPeter Zijlstra 308b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 309b945d6b2SPeter Zijlstra func(parent->rb_right, data); 310b945d6b2SPeter Zijlstra else if (parent->rb_left) 311b945d6b2SPeter Zijlstra func(parent->rb_left, data); 312b945d6b2SPeter Zijlstra 313b945d6b2SPeter Zijlstra node = parent; 314b945d6b2SPeter Zijlstra goto up; 315b945d6b2SPeter Zijlstra } 316b945d6b2SPeter Zijlstra 317b945d6b2SPeter Zijlstra /* 318b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 319b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 320b945d6b2SPeter Zijlstra */ 321b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 322b945d6b2SPeter Zijlstra { 323b945d6b2SPeter Zijlstra if (node->rb_left) 324b945d6b2SPeter Zijlstra node = node->rb_left; 325b945d6b2SPeter Zijlstra else if (node->rb_right) 326b945d6b2SPeter Zijlstra node = node->rb_right; 327b945d6b2SPeter Zijlstra 328b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 329b945d6b2SPeter Zijlstra } 3300b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 331b945d6b2SPeter Zijlstra 332b945d6b2SPeter Zijlstra /* 333b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 334b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 335b945d6b2SPeter Zijlstra */ 336b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 337b945d6b2SPeter Zijlstra { 338b945d6b2SPeter Zijlstra struct rb_node *deepest; 339b945d6b2SPeter Zijlstra 340b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 341b945d6b2SPeter Zijlstra deepest = rb_parent(node); 342b945d6b2SPeter Zijlstra else if (!node->rb_right) 343b945d6b2SPeter Zijlstra deepest = node->rb_left; 344b945d6b2SPeter Zijlstra else if (!node->rb_left) 345b945d6b2SPeter Zijlstra deepest = node->rb_right; 346b945d6b2SPeter Zijlstra else { 347b945d6b2SPeter Zijlstra deepest = rb_next(node); 348b945d6b2SPeter Zijlstra if (deepest->rb_right) 349b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 350b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 351b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 352b945d6b2SPeter Zijlstra } 353b945d6b2SPeter Zijlstra 354b945d6b2SPeter Zijlstra return deepest; 355b945d6b2SPeter Zijlstra } 3560b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 357b945d6b2SPeter Zijlstra 358b945d6b2SPeter Zijlstra /* 359b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 360b945d6b2SPeter Zijlstra * and any rebalance damage. 361b945d6b2SPeter Zijlstra */ 362b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 363b945d6b2SPeter Zijlstra { 364b945d6b2SPeter Zijlstra if (node) 365b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 366b945d6b2SPeter Zijlstra } 3670b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 368b945d6b2SPeter Zijlstra 3691da177e4SLinus Torvalds /* 3701da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 3711da177e4SLinus Torvalds */ 372f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 3731da177e4SLinus Torvalds { 3741da177e4SLinus Torvalds struct rb_node *n; 3751da177e4SLinus Torvalds 3761da177e4SLinus Torvalds n = root->rb_node; 3771da177e4SLinus Torvalds if (!n) 3781da177e4SLinus Torvalds return NULL; 3791da177e4SLinus Torvalds while (n->rb_left) 3801da177e4SLinus Torvalds n = n->rb_left; 3811da177e4SLinus Torvalds return n; 3821da177e4SLinus Torvalds } 3831da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 3841da177e4SLinus Torvalds 385f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 3861da177e4SLinus Torvalds { 3871da177e4SLinus Torvalds struct rb_node *n; 3881da177e4SLinus Torvalds 3891da177e4SLinus Torvalds n = root->rb_node; 3901da177e4SLinus Torvalds if (!n) 3911da177e4SLinus Torvalds return NULL; 3921da177e4SLinus Torvalds while (n->rb_right) 3931da177e4SLinus Torvalds n = n->rb_right; 3941da177e4SLinus Torvalds return n; 3951da177e4SLinus Torvalds } 3961da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 3971da177e4SLinus Torvalds 398f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 3991da177e4SLinus Torvalds { 40055a98102SDavid Woodhouse struct rb_node *parent; 40155a98102SDavid Woodhouse 4024c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 40310fd48f2SJens Axboe return NULL; 40410fd48f2SJens Axboe 4051da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 4061da177e4SLinus Torvalds as we can. */ 4071da177e4SLinus Torvalds if (node->rb_right) { 4081da177e4SLinus Torvalds node = node->rb_right; 4091da177e4SLinus Torvalds while (node->rb_left) 4101da177e4SLinus Torvalds node=node->rb_left; 411f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4121da177e4SLinus Torvalds } 4131da177e4SLinus Torvalds 4141da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 4151da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 4161da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 4171da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 4181da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 4191da177e4SLinus Torvalds parent is our 'next' node. */ 42055a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 42155a98102SDavid Woodhouse node = parent; 4221da177e4SLinus Torvalds 42355a98102SDavid Woodhouse return parent; 4241da177e4SLinus Torvalds } 4251da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 4261da177e4SLinus Torvalds 427f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 4281da177e4SLinus Torvalds { 42955a98102SDavid Woodhouse struct rb_node *parent; 43055a98102SDavid Woodhouse 4314c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 43210fd48f2SJens Axboe return NULL; 43310fd48f2SJens Axboe 4341da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 4351da177e4SLinus Torvalds as we can. */ 4361da177e4SLinus Torvalds if (node->rb_left) { 4371da177e4SLinus Torvalds node = node->rb_left; 4381da177e4SLinus Torvalds while (node->rb_right) 4391da177e4SLinus Torvalds node=node->rb_right; 440f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4411da177e4SLinus Torvalds } 4421da177e4SLinus Torvalds 4431da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 4441da177e4SLinus Torvalds is a right-hand child of its parent */ 44555a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 44655a98102SDavid Woodhouse node = parent; 4471da177e4SLinus Torvalds 44855a98102SDavid Woodhouse return parent; 4491da177e4SLinus Torvalds } 4501da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 4511da177e4SLinus Torvalds 4521da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 4531da177e4SLinus Torvalds struct rb_root *root) 4541da177e4SLinus Torvalds { 45555a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 4561da177e4SLinus Torvalds 4571da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 4581da177e4SLinus Torvalds if (parent) { 4591da177e4SLinus Torvalds if (victim == parent->rb_left) 4601da177e4SLinus Torvalds parent->rb_left = new; 4611da177e4SLinus Torvalds else 4621da177e4SLinus Torvalds parent->rb_right = new; 4631da177e4SLinus Torvalds } else { 4641da177e4SLinus Torvalds root->rb_node = new; 4651da177e4SLinus Torvalds } 4661da177e4SLinus Torvalds if (victim->rb_left) 46755a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 4681da177e4SLinus Torvalds if (victim->rb_right) 46955a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 4701da177e4SLinus Torvalds 4711da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 4721da177e4SLinus Torvalds *new = *victim; 4731da177e4SLinus Torvalds } 4741da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 475