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); 47*17d9ddc7SPallipadi, Venkatesh 48*17d9ddc7SPallipadi, Venkatesh if (root->augment_cb) { 49*17d9ddc7SPallipadi, Venkatesh root->augment_cb(node); 50*17d9ddc7SPallipadi, Venkatesh root->augment_cb(right); 51*17d9ddc7SPallipadi, Venkatesh } 521da177e4SLinus Torvalds } 531da177e4SLinus Torvalds 541da177e4SLinus Torvalds static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 551da177e4SLinus Torvalds { 561da177e4SLinus Torvalds struct rb_node *left = node->rb_left; 5755a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 581da177e4SLinus Torvalds 591da177e4SLinus Torvalds if ((node->rb_left = left->rb_right)) 6055a98102SDavid Woodhouse rb_set_parent(left->rb_right, node); 611da177e4SLinus Torvalds left->rb_right = node; 621da177e4SLinus Torvalds 6355a98102SDavid Woodhouse rb_set_parent(left, parent); 6455a98102SDavid Woodhouse 6555a98102SDavid Woodhouse if (parent) 661da177e4SLinus Torvalds { 6755a98102SDavid Woodhouse if (node == parent->rb_right) 6855a98102SDavid Woodhouse parent->rb_right = left; 691da177e4SLinus Torvalds else 7055a98102SDavid Woodhouse parent->rb_left = left; 711da177e4SLinus Torvalds } 721da177e4SLinus Torvalds else 731da177e4SLinus Torvalds root->rb_node = left; 7455a98102SDavid Woodhouse rb_set_parent(node, left); 75*17d9ddc7SPallipadi, Venkatesh 76*17d9ddc7SPallipadi, Venkatesh if (root->augment_cb) { 77*17d9ddc7SPallipadi, Venkatesh root->augment_cb(node); 78*17d9ddc7SPallipadi, Venkatesh root->augment_cb(left); 79*17d9ddc7SPallipadi, Venkatesh } 801da177e4SLinus Torvalds } 811da177e4SLinus Torvalds 821da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 831da177e4SLinus Torvalds { 841da177e4SLinus Torvalds struct rb_node *parent, *gparent; 851da177e4SLinus Torvalds 86*17d9ddc7SPallipadi, Venkatesh if (root->augment_cb) 87*17d9ddc7SPallipadi, Venkatesh root->augment_cb(node); 88*17d9ddc7SPallipadi, Venkatesh 8955a98102SDavid Woodhouse while ((parent = rb_parent(node)) && rb_is_red(parent)) 901da177e4SLinus Torvalds { 9155a98102SDavid Woodhouse gparent = rb_parent(parent); 921da177e4SLinus Torvalds 931da177e4SLinus Torvalds if (parent == gparent->rb_left) 941da177e4SLinus Torvalds { 951da177e4SLinus Torvalds { 961da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_right; 9755a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 981da177e4SLinus Torvalds { 9955a98102SDavid Woodhouse rb_set_black(uncle); 10055a98102SDavid Woodhouse rb_set_black(parent); 10155a98102SDavid Woodhouse rb_set_red(gparent); 1021da177e4SLinus Torvalds node = gparent; 1031da177e4SLinus Torvalds continue; 1041da177e4SLinus Torvalds } 1051da177e4SLinus Torvalds } 1061da177e4SLinus Torvalds 1071da177e4SLinus Torvalds if (parent->rb_right == node) 1081da177e4SLinus Torvalds { 1091da177e4SLinus Torvalds register struct rb_node *tmp; 1101da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1111da177e4SLinus Torvalds tmp = parent; 1121da177e4SLinus Torvalds parent = node; 1131da177e4SLinus Torvalds node = tmp; 1141da177e4SLinus Torvalds } 1151da177e4SLinus Torvalds 11655a98102SDavid Woodhouse rb_set_black(parent); 11755a98102SDavid Woodhouse rb_set_red(gparent); 1181da177e4SLinus Torvalds __rb_rotate_right(gparent, root); 1191da177e4SLinus Torvalds } else { 1201da177e4SLinus Torvalds { 1211da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_left; 12255a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1231da177e4SLinus Torvalds { 12455a98102SDavid Woodhouse rb_set_black(uncle); 12555a98102SDavid Woodhouse rb_set_black(parent); 12655a98102SDavid Woodhouse rb_set_red(gparent); 1271da177e4SLinus Torvalds node = gparent; 1281da177e4SLinus Torvalds continue; 1291da177e4SLinus Torvalds } 1301da177e4SLinus Torvalds } 1311da177e4SLinus Torvalds 1321da177e4SLinus Torvalds if (parent->rb_left == node) 1331da177e4SLinus Torvalds { 1341da177e4SLinus Torvalds register struct rb_node *tmp; 1351da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1361da177e4SLinus Torvalds tmp = parent; 1371da177e4SLinus Torvalds parent = node; 1381da177e4SLinus Torvalds node = tmp; 1391da177e4SLinus Torvalds } 1401da177e4SLinus Torvalds 14155a98102SDavid Woodhouse rb_set_black(parent); 14255a98102SDavid Woodhouse rb_set_red(gparent); 1431da177e4SLinus Torvalds __rb_rotate_left(gparent, root); 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds 14755a98102SDavid Woodhouse rb_set_black(root->rb_node); 1481da177e4SLinus Torvalds } 1491da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 1501da177e4SLinus Torvalds 1511da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 1521da177e4SLinus Torvalds struct rb_root *root) 1531da177e4SLinus Torvalds { 1541da177e4SLinus Torvalds struct rb_node *other; 1551da177e4SLinus Torvalds 15655a98102SDavid Woodhouse while ((!node || rb_is_black(node)) && node != root->rb_node) 1571da177e4SLinus Torvalds { 1581da177e4SLinus Torvalds if (parent->rb_left == node) 1591da177e4SLinus Torvalds { 1601da177e4SLinus Torvalds other = parent->rb_right; 16155a98102SDavid Woodhouse if (rb_is_red(other)) 1621da177e4SLinus Torvalds { 16355a98102SDavid Woodhouse rb_set_black(other); 16455a98102SDavid Woodhouse rb_set_red(parent); 1651da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1661da177e4SLinus Torvalds other = parent->rb_right; 1671da177e4SLinus Torvalds } 16855a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 16955a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1701da177e4SLinus Torvalds { 17155a98102SDavid Woodhouse rb_set_red(other); 1721da177e4SLinus Torvalds node = parent; 17355a98102SDavid Woodhouse parent = rb_parent(node); 1741da177e4SLinus Torvalds } 1751da177e4SLinus Torvalds else 1761da177e4SLinus Torvalds { 17755a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 1781da177e4SLinus Torvalds { 17955a63998SWolfram Strepp rb_set_black(other->rb_left); 18055a98102SDavid Woodhouse rb_set_red(other); 1811da177e4SLinus Torvalds __rb_rotate_right(other, root); 1821da177e4SLinus Torvalds other = parent->rb_right; 1831da177e4SLinus Torvalds } 1842f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 18555a98102SDavid Woodhouse rb_set_black(parent); 18655a98102SDavid Woodhouse rb_set_black(other->rb_right); 1871da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1881da177e4SLinus Torvalds node = root->rb_node; 1891da177e4SLinus Torvalds break; 1901da177e4SLinus Torvalds } 1911da177e4SLinus Torvalds } 1921da177e4SLinus Torvalds else 1931da177e4SLinus Torvalds { 1941da177e4SLinus Torvalds other = parent->rb_left; 19555a98102SDavid Woodhouse if (rb_is_red(other)) 1961da177e4SLinus Torvalds { 19755a98102SDavid Woodhouse rb_set_black(other); 19855a98102SDavid Woodhouse rb_set_red(parent); 1991da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2001da177e4SLinus Torvalds other = parent->rb_left; 2011da177e4SLinus Torvalds } 20255a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 20355a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 2041da177e4SLinus Torvalds { 20555a98102SDavid Woodhouse rb_set_red(other); 2061da177e4SLinus Torvalds node = parent; 20755a98102SDavid Woodhouse parent = rb_parent(node); 2081da177e4SLinus Torvalds } 2091da177e4SLinus Torvalds else 2101da177e4SLinus Torvalds { 21155a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 2121da177e4SLinus Torvalds { 21355a63998SWolfram Strepp rb_set_black(other->rb_right); 21455a98102SDavid Woodhouse rb_set_red(other); 2151da177e4SLinus Torvalds __rb_rotate_left(other, root); 2161da177e4SLinus Torvalds other = parent->rb_left; 2171da177e4SLinus Torvalds } 2182f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 21955a98102SDavid Woodhouse rb_set_black(parent); 22055a98102SDavid Woodhouse rb_set_black(other->rb_left); 2211da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2221da177e4SLinus Torvalds node = root->rb_node; 2231da177e4SLinus Torvalds break; 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds } 2261da177e4SLinus Torvalds } 2271da177e4SLinus Torvalds if (node) 22855a98102SDavid Woodhouse rb_set_black(node); 2291da177e4SLinus Torvalds } 2301da177e4SLinus Torvalds 2311da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 2321da177e4SLinus Torvalds { 2331da177e4SLinus Torvalds struct rb_node *child, *parent; 2341da177e4SLinus Torvalds int color; 2351da177e4SLinus Torvalds 2361da177e4SLinus Torvalds if (!node->rb_left) 2371da177e4SLinus Torvalds child = node->rb_right; 2381da177e4SLinus Torvalds else if (!node->rb_right) 2391da177e4SLinus Torvalds child = node->rb_left; 2401da177e4SLinus Torvalds else 2411da177e4SLinus Torvalds { 2421da177e4SLinus Torvalds struct rb_node *old = node, *left; 243*17d9ddc7SPallipadi, Venkatesh int old_parent_cb = 0; 244*17d9ddc7SPallipadi, Venkatesh int successor_parent_cb = 0; 2451da177e4SLinus Torvalds 2461da177e4SLinus Torvalds node = node->rb_right; 2471da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 2481da177e4SLinus Torvalds node = left; 24916c047adSWolfram Strepp 25016c047adSWolfram Strepp if (rb_parent(old)) { 251*17d9ddc7SPallipadi, Venkatesh old_parent_cb = 1; 25216c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 25316c047adSWolfram Strepp rb_parent(old)->rb_left = node; 25416c047adSWolfram Strepp else 25516c047adSWolfram Strepp rb_parent(old)->rb_right = node; 25616c047adSWolfram Strepp } else 25716c047adSWolfram Strepp root->rb_node = node; 25816c047adSWolfram Strepp 2591da177e4SLinus Torvalds child = node->rb_right; 26055a98102SDavid Woodhouse parent = rb_parent(node); 2612f3243aeSDavid Woodhouse color = rb_color(node); 2621da177e4SLinus Torvalds 2634c601178SWolfram Strepp if (parent == old) { 2644c601178SWolfram Strepp parent = node; 2654c601178SWolfram Strepp } else { 266*17d9ddc7SPallipadi, Venkatesh successor_parent_cb = 1; 2671da177e4SLinus Torvalds if (child) 26855a98102SDavid Woodhouse rb_set_parent(child, parent); 269*17d9ddc7SPallipadi, Venkatesh 2701975e593SDavid Woodhouse parent->rb_left = child; 2714b324126SWolfram Strepp 2724b324126SWolfram Strepp node->rb_right = old->rb_right; 2734b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 2744c601178SWolfram Strepp } 2751975e593SDavid Woodhouse 2762f3243aeSDavid Woodhouse node->rb_parent_color = old->rb_parent_color; 2771da177e4SLinus Torvalds node->rb_left = old->rb_left; 27855a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 2794b324126SWolfram Strepp 280*17d9ddc7SPallipadi, Venkatesh if (root->augment_cb) { 281*17d9ddc7SPallipadi, Venkatesh /* 282*17d9ddc7SPallipadi, Venkatesh * Here, three different nodes can have new children. 283*17d9ddc7SPallipadi, Venkatesh * The parent of the successor node that was selected 284*17d9ddc7SPallipadi, Venkatesh * to replace the node to be erased. 285*17d9ddc7SPallipadi, Venkatesh * The node that is getting erased and is now replaced 286*17d9ddc7SPallipadi, Venkatesh * by its successor. 287*17d9ddc7SPallipadi, Venkatesh * The parent of the node getting erased-replaced. 288*17d9ddc7SPallipadi, Venkatesh */ 289*17d9ddc7SPallipadi, Venkatesh if (successor_parent_cb) 290*17d9ddc7SPallipadi, Venkatesh root->augment_cb(parent); 291*17d9ddc7SPallipadi, Venkatesh 292*17d9ddc7SPallipadi, Venkatesh root->augment_cb(node); 293*17d9ddc7SPallipadi, Venkatesh 294*17d9ddc7SPallipadi, Venkatesh if (old_parent_cb) 295*17d9ddc7SPallipadi, Venkatesh root->augment_cb(rb_parent(old)); 296*17d9ddc7SPallipadi, Venkatesh } 297*17d9ddc7SPallipadi, Venkatesh 2981da177e4SLinus Torvalds goto color; 2991da177e4SLinus Torvalds } 3001da177e4SLinus Torvalds 30155a98102SDavid Woodhouse parent = rb_parent(node); 3022f3243aeSDavid Woodhouse color = rb_color(node); 3031da177e4SLinus Torvalds 3041da177e4SLinus Torvalds if (child) 30555a98102SDavid Woodhouse rb_set_parent(child, parent); 306*17d9ddc7SPallipadi, Venkatesh 307*17d9ddc7SPallipadi, Venkatesh if (parent) { 3081da177e4SLinus Torvalds if (parent->rb_left == node) 3091da177e4SLinus Torvalds parent->rb_left = child; 3101da177e4SLinus Torvalds else 3111da177e4SLinus Torvalds parent->rb_right = child; 312*17d9ddc7SPallipadi, Venkatesh 313*17d9ddc7SPallipadi, Venkatesh if (root->augment_cb) 314*17d9ddc7SPallipadi, Venkatesh root->augment_cb(parent); 315*17d9ddc7SPallipadi, Venkatesh 316*17d9ddc7SPallipadi, Venkatesh } else { 3171da177e4SLinus Torvalds root->rb_node = child; 318*17d9ddc7SPallipadi, Venkatesh } 3191da177e4SLinus Torvalds 3201da177e4SLinus Torvalds color: 3211da177e4SLinus Torvalds if (color == RB_BLACK) 3221da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 3231da177e4SLinus Torvalds } 3241da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 3251da177e4SLinus Torvalds 3261da177e4SLinus Torvalds /* 3271da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 3281da177e4SLinus Torvalds */ 329f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 3301da177e4SLinus Torvalds { 3311da177e4SLinus Torvalds struct rb_node *n; 3321da177e4SLinus Torvalds 3331da177e4SLinus Torvalds n = root->rb_node; 3341da177e4SLinus Torvalds if (!n) 3351da177e4SLinus Torvalds return NULL; 3361da177e4SLinus Torvalds while (n->rb_left) 3371da177e4SLinus Torvalds n = n->rb_left; 3381da177e4SLinus Torvalds return n; 3391da177e4SLinus Torvalds } 3401da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 3411da177e4SLinus Torvalds 342f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 3431da177e4SLinus Torvalds { 3441da177e4SLinus Torvalds struct rb_node *n; 3451da177e4SLinus Torvalds 3461da177e4SLinus Torvalds n = root->rb_node; 3471da177e4SLinus Torvalds if (!n) 3481da177e4SLinus Torvalds return NULL; 3491da177e4SLinus Torvalds while (n->rb_right) 3501da177e4SLinus Torvalds n = n->rb_right; 3511da177e4SLinus Torvalds return n; 3521da177e4SLinus Torvalds } 3531da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 3541da177e4SLinus Torvalds 355f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 3561da177e4SLinus Torvalds { 35755a98102SDavid Woodhouse struct rb_node *parent; 35855a98102SDavid Woodhouse 35910fd48f2SJens Axboe if (rb_parent(node) == node) 36010fd48f2SJens Axboe return NULL; 36110fd48f2SJens Axboe 3621da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 3631da177e4SLinus Torvalds as we can. */ 3641da177e4SLinus Torvalds if (node->rb_right) { 3651da177e4SLinus Torvalds node = node->rb_right; 3661da177e4SLinus Torvalds while (node->rb_left) 3671da177e4SLinus Torvalds node=node->rb_left; 368f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 3691da177e4SLinus Torvalds } 3701da177e4SLinus Torvalds 3711da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 3721da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 3731da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 3741da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 3751da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 3761da177e4SLinus Torvalds parent is our 'next' node. */ 37755a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 37855a98102SDavid Woodhouse node = parent; 3791da177e4SLinus Torvalds 38055a98102SDavid Woodhouse return parent; 3811da177e4SLinus Torvalds } 3821da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 3831da177e4SLinus Torvalds 384f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 3851da177e4SLinus Torvalds { 38655a98102SDavid Woodhouse struct rb_node *parent; 38755a98102SDavid Woodhouse 38810fd48f2SJens Axboe if (rb_parent(node) == node) 38910fd48f2SJens Axboe return NULL; 39010fd48f2SJens Axboe 3911da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 3921da177e4SLinus Torvalds as we can. */ 3931da177e4SLinus Torvalds if (node->rb_left) { 3941da177e4SLinus Torvalds node = node->rb_left; 3951da177e4SLinus Torvalds while (node->rb_right) 3961da177e4SLinus Torvalds node=node->rb_right; 397f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 3981da177e4SLinus Torvalds } 3991da177e4SLinus Torvalds 4001da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 4011da177e4SLinus Torvalds is a right-hand child of its parent */ 40255a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 40355a98102SDavid Woodhouse node = parent; 4041da177e4SLinus Torvalds 40555a98102SDavid Woodhouse return parent; 4061da177e4SLinus Torvalds } 4071da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 4081da177e4SLinus Torvalds 4091da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 4101da177e4SLinus Torvalds struct rb_root *root) 4111da177e4SLinus Torvalds { 41255a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 4131da177e4SLinus Torvalds 4141da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 4151da177e4SLinus Torvalds if (parent) { 4161da177e4SLinus Torvalds if (victim == parent->rb_left) 4171da177e4SLinus Torvalds parent->rb_left = new; 4181da177e4SLinus Torvalds else 4191da177e4SLinus Torvalds parent->rb_right = new; 4201da177e4SLinus Torvalds } else { 4211da177e4SLinus Torvalds root->rb_node = new; 4221da177e4SLinus Torvalds } 4231da177e4SLinus Torvalds if (victim->rb_left) 42455a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 4251da177e4SLinus Torvalds if (victim->rb_right) 42655a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 4271da177e4SLinus Torvalds 4281da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 4291da177e4SLinus Torvalds *new = *victim; 4301da177e4SLinus Torvalds } 4311da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 432