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> 241da177e4SLinus Torvalds #include <linux/module.h> 251da177e4SLinus Torvalds 261da177e4SLinus Torvalds static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 271da177e4SLinus Torvalds { 281da177e4SLinus Torvalds struct rb_node *right = node->rb_right; 2955a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 301da177e4SLinus Torvalds 311da177e4SLinus Torvalds if ((node->rb_right = right->rb_left)) 3255a98102SDavid Woodhouse rb_set_parent(right->rb_left, node); 331da177e4SLinus Torvalds right->rb_left = node; 341da177e4SLinus Torvalds 3555a98102SDavid Woodhouse rb_set_parent(right, parent); 3655a98102SDavid Woodhouse 3755a98102SDavid Woodhouse if (parent) 381da177e4SLinus Torvalds { 3955a98102SDavid Woodhouse if (node == parent->rb_left) 4055a98102SDavid Woodhouse parent->rb_left = right; 411da177e4SLinus Torvalds else 4255a98102SDavid Woodhouse parent->rb_right = right; 431da177e4SLinus Torvalds } 441da177e4SLinus Torvalds else 451da177e4SLinus Torvalds root->rb_node = right; 4655a98102SDavid Woodhouse rb_set_parent(node, right); 471da177e4SLinus Torvalds } 481da177e4SLinus Torvalds 491da177e4SLinus Torvalds static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 501da177e4SLinus Torvalds { 511da177e4SLinus Torvalds struct rb_node *left = node->rb_left; 5255a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 531da177e4SLinus Torvalds 541da177e4SLinus Torvalds if ((node->rb_left = left->rb_right)) 5555a98102SDavid Woodhouse rb_set_parent(left->rb_right, node); 561da177e4SLinus Torvalds left->rb_right = node; 571da177e4SLinus Torvalds 5855a98102SDavid Woodhouse rb_set_parent(left, parent); 5955a98102SDavid Woodhouse 6055a98102SDavid Woodhouse if (parent) 611da177e4SLinus Torvalds { 6255a98102SDavid Woodhouse if (node == parent->rb_right) 6355a98102SDavid Woodhouse parent->rb_right = left; 641da177e4SLinus Torvalds else 6555a98102SDavid Woodhouse parent->rb_left = left; 661da177e4SLinus Torvalds } 671da177e4SLinus Torvalds else 681da177e4SLinus Torvalds root->rb_node = left; 6955a98102SDavid Woodhouse rb_set_parent(node, left); 701da177e4SLinus Torvalds } 711da177e4SLinus Torvalds 721da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 731da177e4SLinus Torvalds { 741da177e4SLinus Torvalds struct rb_node *parent, *gparent; 751da177e4SLinus Torvalds 7655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && rb_is_red(parent)) 771da177e4SLinus Torvalds { 7855a98102SDavid Woodhouse gparent = rb_parent(parent); 791da177e4SLinus Torvalds 801da177e4SLinus Torvalds if (parent == gparent->rb_left) 811da177e4SLinus Torvalds { 821da177e4SLinus Torvalds { 831da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_right; 8455a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 851da177e4SLinus Torvalds { 8655a98102SDavid Woodhouse rb_set_black(uncle); 8755a98102SDavid Woodhouse rb_set_black(parent); 8855a98102SDavid Woodhouse rb_set_red(gparent); 891da177e4SLinus Torvalds node = gparent; 901da177e4SLinus Torvalds continue; 911da177e4SLinus Torvalds } 921da177e4SLinus Torvalds } 931da177e4SLinus Torvalds 941da177e4SLinus Torvalds if (parent->rb_right == node) 951da177e4SLinus Torvalds { 961da177e4SLinus Torvalds register struct rb_node *tmp; 971da177e4SLinus Torvalds __rb_rotate_left(parent, root); 981da177e4SLinus Torvalds tmp = parent; 991da177e4SLinus Torvalds parent = node; 1001da177e4SLinus Torvalds node = tmp; 1011da177e4SLinus Torvalds } 1021da177e4SLinus Torvalds 10355a98102SDavid Woodhouse rb_set_black(parent); 10455a98102SDavid Woodhouse rb_set_red(gparent); 1051da177e4SLinus Torvalds __rb_rotate_right(gparent, root); 1061da177e4SLinus Torvalds } else { 1071da177e4SLinus Torvalds { 1081da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_left; 10955a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1101da177e4SLinus Torvalds { 11155a98102SDavid Woodhouse rb_set_black(uncle); 11255a98102SDavid Woodhouse rb_set_black(parent); 11355a98102SDavid Woodhouse rb_set_red(gparent); 1141da177e4SLinus Torvalds node = gparent; 1151da177e4SLinus Torvalds continue; 1161da177e4SLinus Torvalds } 1171da177e4SLinus Torvalds } 1181da177e4SLinus Torvalds 1191da177e4SLinus Torvalds if (parent->rb_left == node) 1201da177e4SLinus Torvalds { 1211da177e4SLinus Torvalds register struct rb_node *tmp; 1221da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1231da177e4SLinus Torvalds tmp = parent; 1241da177e4SLinus Torvalds parent = node; 1251da177e4SLinus Torvalds node = tmp; 1261da177e4SLinus Torvalds } 1271da177e4SLinus Torvalds 12855a98102SDavid Woodhouse rb_set_black(parent); 12955a98102SDavid Woodhouse rb_set_red(gparent); 1301da177e4SLinus Torvalds __rb_rotate_left(gparent, root); 1311da177e4SLinus Torvalds } 1321da177e4SLinus Torvalds } 1331da177e4SLinus Torvalds 13455a98102SDavid Woodhouse rb_set_black(root->rb_node); 1351da177e4SLinus Torvalds } 1361da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 1371da177e4SLinus Torvalds 1381da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 1391da177e4SLinus Torvalds struct rb_root *root) 1401da177e4SLinus Torvalds { 1411da177e4SLinus Torvalds struct rb_node *other; 1421da177e4SLinus Torvalds 14355a98102SDavid Woodhouse while ((!node || rb_is_black(node)) && node != root->rb_node) 1441da177e4SLinus Torvalds { 1451da177e4SLinus Torvalds if (parent->rb_left == node) 1461da177e4SLinus Torvalds { 1471da177e4SLinus Torvalds other = parent->rb_right; 14855a98102SDavid Woodhouse if (rb_is_red(other)) 1491da177e4SLinus Torvalds { 15055a98102SDavid Woodhouse rb_set_black(other); 15155a98102SDavid Woodhouse rb_set_red(parent); 1521da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1531da177e4SLinus Torvalds other = parent->rb_right; 1541da177e4SLinus Torvalds } 15555a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 15655a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1571da177e4SLinus Torvalds { 15855a98102SDavid Woodhouse rb_set_red(other); 1591da177e4SLinus Torvalds node = parent; 16055a98102SDavid Woodhouse parent = rb_parent(node); 1611da177e4SLinus Torvalds } 1621da177e4SLinus Torvalds else 1631da177e4SLinus Torvalds { 16455a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 1651da177e4SLinus Torvalds { 16655a63998SWolfram Strepp rb_set_black(other->rb_left); 16755a98102SDavid Woodhouse rb_set_red(other); 1681da177e4SLinus Torvalds __rb_rotate_right(other, root); 1691da177e4SLinus Torvalds other = parent->rb_right; 1701da177e4SLinus Torvalds } 1712f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 17255a98102SDavid Woodhouse rb_set_black(parent); 17355a98102SDavid Woodhouse rb_set_black(other->rb_right); 1741da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1751da177e4SLinus Torvalds node = root->rb_node; 1761da177e4SLinus Torvalds break; 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds } 1791da177e4SLinus Torvalds else 1801da177e4SLinus Torvalds { 1811da177e4SLinus Torvalds other = parent->rb_left; 18255a98102SDavid Woodhouse if (rb_is_red(other)) 1831da177e4SLinus Torvalds { 18455a98102SDavid Woodhouse rb_set_black(other); 18555a98102SDavid Woodhouse rb_set_red(parent); 1861da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1871da177e4SLinus Torvalds other = parent->rb_left; 1881da177e4SLinus Torvalds } 18955a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 19055a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1911da177e4SLinus Torvalds { 19255a98102SDavid Woodhouse rb_set_red(other); 1931da177e4SLinus Torvalds node = parent; 19455a98102SDavid Woodhouse parent = rb_parent(node); 1951da177e4SLinus Torvalds } 1961da177e4SLinus Torvalds else 1971da177e4SLinus Torvalds { 19855a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 1991da177e4SLinus Torvalds { 20055a63998SWolfram Strepp rb_set_black(other->rb_right); 20155a98102SDavid Woodhouse rb_set_red(other); 2021da177e4SLinus Torvalds __rb_rotate_left(other, root); 2031da177e4SLinus Torvalds other = parent->rb_left; 2041da177e4SLinus Torvalds } 2052f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 20655a98102SDavid Woodhouse rb_set_black(parent); 20755a98102SDavid Woodhouse rb_set_black(other->rb_left); 2081da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2091da177e4SLinus Torvalds node = root->rb_node; 2101da177e4SLinus Torvalds break; 2111da177e4SLinus Torvalds } 2121da177e4SLinus Torvalds } 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds if (node) 21555a98102SDavid Woodhouse rb_set_black(node); 2161da177e4SLinus Torvalds } 2171da177e4SLinus Torvalds 2181da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 2191da177e4SLinus Torvalds { 2201da177e4SLinus Torvalds struct rb_node *child, *parent; 2211da177e4SLinus Torvalds int color; 2221da177e4SLinus Torvalds 2231da177e4SLinus Torvalds if (!node->rb_left) 2241da177e4SLinus Torvalds child = node->rb_right; 2251da177e4SLinus Torvalds else if (!node->rb_right) 2261da177e4SLinus Torvalds child = node->rb_left; 2271da177e4SLinus Torvalds else 2281da177e4SLinus Torvalds { 2291da177e4SLinus Torvalds struct rb_node *old = node, *left; 2301da177e4SLinus Torvalds 2311da177e4SLinus Torvalds node = node->rb_right; 2321da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 2331da177e4SLinus Torvalds node = left; 23416c047adSWolfram Strepp 23516c047adSWolfram Strepp if (rb_parent(old)) { 23616c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 23716c047adSWolfram Strepp rb_parent(old)->rb_left = node; 23816c047adSWolfram Strepp else 23916c047adSWolfram Strepp rb_parent(old)->rb_right = node; 24016c047adSWolfram Strepp } else 24116c047adSWolfram Strepp root->rb_node = node; 24216c047adSWolfram Strepp 2431da177e4SLinus Torvalds child = node->rb_right; 24455a98102SDavid Woodhouse parent = rb_parent(node); 2452f3243aeSDavid Woodhouse color = rb_color(node); 2461da177e4SLinus Torvalds 2474c601178SWolfram Strepp if (parent == old) { 2484c601178SWolfram Strepp parent = node; 2494c601178SWolfram Strepp } else { 2501da177e4SLinus Torvalds if (child) 25155a98102SDavid Woodhouse rb_set_parent(child, parent); 2521975e593SDavid Woodhouse parent->rb_left = child; 2534b324126SWolfram Strepp 2544b324126SWolfram Strepp node->rb_right = old->rb_right; 2554b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 2564c601178SWolfram Strepp } 2571975e593SDavid Woodhouse 2582f3243aeSDavid Woodhouse node->rb_parent_color = old->rb_parent_color; 2591da177e4SLinus Torvalds node->rb_left = old->rb_left; 26055a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 2614b324126SWolfram Strepp 2621da177e4SLinus Torvalds goto color; 2631da177e4SLinus Torvalds } 2641da177e4SLinus Torvalds 26555a98102SDavid Woodhouse parent = rb_parent(node); 2662f3243aeSDavid Woodhouse color = rb_color(node); 2671da177e4SLinus Torvalds 2681da177e4SLinus Torvalds if (child) 26955a98102SDavid Woodhouse rb_set_parent(child, parent); 270b945d6b2SPeter Zijlstra if (parent) 271b945d6b2SPeter Zijlstra { 2721da177e4SLinus Torvalds if (parent->rb_left == node) 2731da177e4SLinus Torvalds parent->rb_left = child; 2741da177e4SLinus Torvalds else 2751da177e4SLinus Torvalds parent->rb_right = child; 27617d9ddc7SPallipadi, Venkatesh } 277b945d6b2SPeter Zijlstra else 278b945d6b2SPeter Zijlstra root->rb_node = child; 2791da177e4SLinus Torvalds 2801da177e4SLinus Torvalds color: 2811da177e4SLinus Torvalds if (color == RB_BLACK) 2821da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 2831da177e4SLinus Torvalds } 2841da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 2851da177e4SLinus Torvalds 286b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 287b945d6b2SPeter Zijlstra { 288b945d6b2SPeter Zijlstra struct rb_node *parent; 289b945d6b2SPeter Zijlstra 290b945d6b2SPeter Zijlstra up: 291b945d6b2SPeter Zijlstra func(node, data); 292b945d6b2SPeter Zijlstra parent = rb_parent(node); 293b945d6b2SPeter Zijlstra if (!parent) 294b945d6b2SPeter Zijlstra return; 295b945d6b2SPeter Zijlstra 296b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 297b945d6b2SPeter Zijlstra func(parent->rb_right, data); 298b945d6b2SPeter Zijlstra else if (parent->rb_left) 299b945d6b2SPeter Zijlstra func(parent->rb_left, data); 300b945d6b2SPeter Zijlstra 301b945d6b2SPeter Zijlstra node = parent; 302b945d6b2SPeter Zijlstra goto up; 303b945d6b2SPeter Zijlstra } 304b945d6b2SPeter Zijlstra 305b945d6b2SPeter Zijlstra /* 306b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 307b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 308b945d6b2SPeter Zijlstra */ 309b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 310b945d6b2SPeter Zijlstra { 311b945d6b2SPeter Zijlstra if (node->rb_left) 312b945d6b2SPeter Zijlstra node = node->rb_left; 313b945d6b2SPeter Zijlstra else if (node->rb_right) 314b945d6b2SPeter Zijlstra node = node->rb_right; 315b945d6b2SPeter Zijlstra 316b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 317b945d6b2SPeter Zijlstra } 318*0b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 319b945d6b2SPeter Zijlstra 320b945d6b2SPeter Zijlstra /* 321b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 322b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 323b945d6b2SPeter Zijlstra */ 324b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 325b945d6b2SPeter Zijlstra { 326b945d6b2SPeter Zijlstra struct rb_node *deepest; 327b945d6b2SPeter Zijlstra 328b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 329b945d6b2SPeter Zijlstra deepest = rb_parent(node); 330b945d6b2SPeter Zijlstra else if (!node->rb_right) 331b945d6b2SPeter Zijlstra deepest = node->rb_left; 332b945d6b2SPeter Zijlstra else if (!node->rb_left) 333b945d6b2SPeter Zijlstra deepest = node->rb_right; 334b945d6b2SPeter Zijlstra else { 335b945d6b2SPeter Zijlstra deepest = rb_next(node); 336b945d6b2SPeter Zijlstra if (deepest->rb_right) 337b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 338b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 339b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 340b945d6b2SPeter Zijlstra } 341b945d6b2SPeter Zijlstra 342b945d6b2SPeter Zijlstra return deepest; 343b945d6b2SPeter Zijlstra } 344*0b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 345b945d6b2SPeter Zijlstra 346b945d6b2SPeter Zijlstra /* 347b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 348b945d6b2SPeter Zijlstra * and any rebalance damage. 349b945d6b2SPeter Zijlstra */ 350b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 351b945d6b2SPeter Zijlstra { 352b945d6b2SPeter Zijlstra if (node) 353b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 354b945d6b2SPeter Zijlstra } 355*0b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 356b945d6b2SPeter Zijlstra 3571da177e4SLinus Torvalds /* 3581da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 3591da177e4SLinus Torvalds */ 360f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 3611da177e4SLinus Torvalds { 3621da177e4SLinus Torvalds struct rb_node *n; 3631da177e4SLinus Torvalds 3641da177e4SLinus Torvalds n = root->rb_node; 3651da177e4SLinus Torvalds if (!n) 3661da177e4SLinus Torvalds return NULL; 3671da177e4SLinus Torvalds while (n->rb_left) 3681da177e4SLinus Torvalds n = n->rb_left; 3691da177e4SLinus Torvalds return n; 3701da177e4SLinus Torvalds } 3711da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 3721da177e4SLinus Torvalds 373f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 3741da177e4SLinus Torvalds { 3751da177e4SLinus Torvalds struct rb_node *n; 3761da177e4SLinus Torvalds 3771da177e4SLinus Torvalds n = root->rb_node; 3781da177e4SLinus Torvalds if (!n) 3791da177e4SLinus Torvalds return NULL; 3801da177e4SLinus Torvalds while (n->rb_right) 3811da177e4SLinus Torvalds n = n->rb_right; 3821da177e4SLinus Torvalds return n; 3831da177e4SLinus Torvalds } 3841da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 3851da177e4SLinus Torvalds 386f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 3871da177e4SLinus Torvalds { 38855a98102SDavid Woodhouse struct rb_node *parent; 38955a98102SDavid Woodhouse 39010fd48f2SJens Axboe if (rb_parent(node) == node) 39110fd48f2SJens Axboe return NULL; 39210fd48f2SJens Axboe 3931da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 3941da177e4SLinus Torvalds as we can. */ 3951da177e4SLinus Torvalds if (node->rb_right) { 3961da177e4SLinus Torvalds node = node->rb_right; 3971da177e4SLinus Torvalds while (node->rb_left) 3981da177e4SLinus Torvalds node=node->rb_left; 399f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4001da177e4SLinus Torvalds } 4011da177e4SLinus Torvalds 4021da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 4031da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 4041da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 4051da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 4061da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 4071da177e4SLinus Torvalds parent is our 'next' node. */ 40855a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 40955a98102SDavid Woodhouse node = parent; 4101da177e4SLinus Torvalds 41155a98102SDavid Woodhouse return parent; 4121da177e4SLinus Torvalds } 4131da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 4141da177e4SLinus Torvalds 415f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 4161da177e4SLinus Torvalds { 41755a98102SDavid Woodhouse struct rb_node *parent; 41855a98102SDavid Woodhouse 41910fd48f2SJens Axboe if (rb_parent(node) == node) 42010fd48f2SJens Axboe return NULL; 42110fd48f2SJens Axboe 4221da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 4231da177e4SLinus Torvalds as we can. */ 4241da177e4SLinus Torvalds if (node->rb_left) { 4251da177e4SLinus Torvalds node = node->rb_left; 4261da177e4SLinus Torvalds while (node->rb_right) 4271da177e4SLinus Torvalds node=node->rb_right; 428f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4291da177e4SLinus Torvalds } 4301da177e4SLinus Torvalds 4311da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 4321da177e4SLinus Torvalds is a right-hand child of its parent */ 43355a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 43455a98102SDavid Woodhouse node = parent; 4351da177e4SLinus Torvalds 43655a98102SDavid Woodhouse return parent; 4371da177e4SLinus Torvalds } 4381da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 4391da177e4SLinus Torvalds 4401da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 4411da177e4SLinus Torvalds struct rb_root *root) 4421da177e4SLinus Torvalds { 44355a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 4441da177e4SLinus Torvalds 4451da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 4461da177e4SLinus Torvalds if (parent) { 4471da177e4SLinus Torvalds if (victim == parent->rb_left) 4481da177e4SLinus Torvalds parent->rb_left = new; 4491da177e4SLinus Torvalds else 4501da177e4SLinus Torvalds parent->rb_right = new; 4511da177e4SLinus Torvalds } else { 4521da177e4SLinus Torvalds root->rb_node = new; 4531da177e4SLinus Torvalds } 4541da177e4SLinus Torvalds if (victim->rb_left) 45555a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 4561da177e4SLinus Torvalds if (victim->rb_right) 45755a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 4581da177e4SLinus Torvalds 4591da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 4601da177e4SLinus Torvalds *new = *victim; 4611da177e4SLinus Torvalds } 4621da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 463