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 26*bf7ad8eeSMichel Lespinasse #define RB_RED 0 27*bf7ad8eeSMichel Lespinasse #define RB_BLACK 1 28*bf7ad8eeSMichel Lespinasse 29*bf7ad8eeSMichel Lespinasse #define rb_color(r) ((r)->__rb_parent_color & 1) 30*bf7ad8eeSMichel Lespinasse #define rb_is_red(r) (!rb_color(r)) 31*bf7ad8eeSMichel Lespinasse #define rb_is_black(r) rb_color(r) 32*bf7ad8eeSMichel Lespinasse #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) 33*bf7ad8eeSMichel Lespinasse #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) 34*bf7ad8eeSMichel Lespinasse 35*bf7ad8eeSMichel Lespinasse static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 36*bf7ad8eeSMichel Lespinasse { 37*bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 38*bf7ad8eeSMichel Lespinasse } 39*bf7ad8eeSMichel Lespinasse static inline void rb_set_color(struct rb_node *rb, int color) 40*bf7ad8eeSMichel Lespinasse { 41*bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; 42*bf7ad8eeSMichel Lespinasse } 43*bf7ad8eeSMichel 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 1121da177e4SLinus Torvalds if (parent->rb_right == node) 1131da177e4SLinus Torvalds { 1141da177e4SLinus Torvalds register struct rb_node *tmp; 1151da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1161da177e4SLinus Torvalds tmp = parent; 1171da177e4SLinus Torvalds parent = node; 1181da177e4SLinus Torvalds node = tmp; 1191da177e4SLinus Torvalds } 1201da177e4SLinus Torvalds 12155a98102SDavid Woodhouse rb_set_black(parent); 12255a98102SDavid Woodhouse rb_set_red(gparent); 1231da177e4SLinus Torvalds __rb_rotate_right(gparent, root); 1241da177e4SLinus Torvalds } else { 1251da177e4SLinus Torvalds { 1261da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_left; 12755a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1281da177e4SLinus Torvalds { 12955a98102SDavid Woodhouse rb_set_black(uncle); 13055a98102SDavid Woodhouse rb_set_black(parent); 13155a98102SDavid Woodhouse rb_set_red(gparent); 1321da177e4SLinus Torvalds node = gparent; 1331da177e4SLinus Torvalds continue; 1341da177e4SLinus Torvalds } 1351da177e4SLinus Torvalds } 1361da177e4SLinus Torvalds 1371da177e4SLinus Torvalds if (parent->rb_left == node) 1381da177e4SLinus Torvalds { 1391da177e4SLinus Torvalds register struct rb_node *tmp; 1401da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1411da177e4SLinus Torvalds tmp = parent; 1421da177e4SLinus Torvalds parent = node; 1431da177e4SLinus Torvalds node = tmp; 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds 14655a98102SDavid Woodhouse rb_set_black(parent); 14755a98102SDavid Woodhouse rb_set_red(gparent); 1481da177e4SLinus Torvalds __rb_rotate_left(gparent, root); 1491da177e4SLinus Torvalds } 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds 15255a98102SDavid Woodhouse rb_set_black(root->rb_node); 1531da177e4SLinus Torvalds } 1541da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 1551da177e4SLinus Torvalds 1561da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 1571da177e4SLinus Torvalds struct rb_root *root) 1581da177e4SLinus Torvalds { 1591da177e4SLinus Torvalds struct rb_node *other; 1601da177e4SLinus Torvalds 16155a98102SDavid Woodhouse while ((!node || rb_is_black(node)) && node != root->rb_node) 1621da177e4SLinus Torvalds { 1631da177e4SLinus Torvalds if (parent->rb_left == node) 1641da177e4SLinus Torvalds { 1651da177e4SLinus Torvalds other = parent->rb_right; 16655a98102SDavid Woodhouse if (rb_is_red(other)) 1671da177e4SLinus Torvalds { 16855a98102SDavid Woodhouse rb_set_black(other); 16955a98102SDavid Woodhouse rb_set_red(parent); 1701da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1711da177e4SLinus Torvalds other = parent->rb_right; 1721da177e4SLinus Torvalds } 17355a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 17455a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1751da177e4SLinus Torvalds { 17655a98102SDavid Woodhouse rb_set_red(other); 1771da177e4SLinus Torvalds node = parent; 17855a98102SDavid Woodhouse parent = rb_parent(node); 1791da177e4SLinus Torvalds } 1801da177e4SLinus Torvalds else 1811da177e4SLinus Torvalds { 18255a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 1831da177e4SLinus Torvalds { 18455a63998SWolfram Strepp rb_set_black(other->rb_left); 18555a98102SDavid Woodhouse rb_set_red(other); 1861da177e4SLinus Torvalds __rb_rotate_right(other, root); 1871da177e4SLinus Torvalds other = parent->rb_right; 1881da177e4SLinus Torvalds } 1892f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 19055a98102SDavid Woodhouse rb_set_black(parent); 19155a98102SDavid Woodhouse rb_set_black(other->rb_right); 1921da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1931da177e4SLinus Torvalds node = root->rb_node; 1941da177e4SLinus Torvalds break; 1951da177e4SLinus Torvalds } 1961da177e4SLinus Torvalds } 1971da177e4SLinus Torvalds else 1981da177e4SLinus Torvalds { 1991da177e4SLinus Torvalds other = parent->rb_left; 20055a98102SDavid Woodhouse if (rb_is_red(other)) 2011da177e4SLinus Torvalds { 20255a98102SDavid Woodhouse rb_set_black(other); 20355a98102SDavid Woodhouse rb_set_red(parent); 2041da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2051da177e4SLinus Torvalds other = parent->rb_left; 2061da177e4SLinus Torvalds } 20755a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 20855a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 2091da177e4SLinus Torvalds { 21055a98102SDavid Woodhouse rb_set_red(other); 2111da177e4SLinus Torvalds node = parent; 21255a98102SDavid Woodhouse parent = rb_parent(node); 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds else 2151da177e4SLinus Torvalds { 21655a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 2171da177e4SLinus Torvalds { 21855a63998SWolfram Strepp rb_set_black(other->rb_right); 21955a98102SDavid Woodhouse rb_set_red(other); 2201da177e4SLinus Torvalds __rb_rotate_left(other, root); 2211da177e4SLinus Torvalds other = parent->rb_left; 2221da177e4SLinus Torvalds } 2232f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 22455a98102SDavid Woodhouse rb_set_black(parent); 22555a98102SDavid Woodhouse rb_set_black(other->rb_left); 2261da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2271da177e4SLinus Torvalds node = root->rb_node; 2281da177e4SLinus Torvalds break; 2291da177e4SLinus Torvalds } 2301da177e4SLinus Torvalds } 2311da177e4SLinus Torvalds } 2321da177e4SLinus Torvalds if (node) 23355a98102SDavid Woodhouse rb_set_black(node); 2341da177e4SLinus Torvalds } 2351da177e4SLinus Torvalds 2361da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 2371da177e4SLinus Torvalds { 2381da177e4SLinus Torvalds struct rb_node *child, *parent; 2391da177e4SLinus Torvalds int color; 2401da177e4SLinus Torvalds 2411da177e4SLinus Torvalds if (!node->rb_left) 2421da177e4SLinus Torvalds child = node->rb_right; 2431da177e4SLinus Torvalds else if (!node->rb_right) 2441da177e4SLinus Torvalds child = node->rb_left; 2451da177e4SLinus Torvalds else 2461da177e4SLinus Torvalds { 2471da177e4SLinus Torvalds struct rb_node *old = node, *left; 2481da177e4SLinus Torvalds 2491da177e4SLinus Torvalds node = node->rb_right; 2501da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 2511da177e4SLinus Torvalds node = left; 25216c047adSWolfram Strepp 25316c047adSWolfram Strepp if (rb_parent(old)) { 25416c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 25516c047adSWolfram Strepp rb_parent(old)->rb_left = node; 25616c047adSWolfram Strepp else 25716c047adSWolfram Strepp rb_parent(old)->rb_right = node; 25816c047adSWolfram Strepp } else 25916c047adSWolfram Strepp root->rb_node = node; 26016c047adSWolfram Strepp 2611da177e4SLinus Torvalds child = node->rb_right; 26255a98102SDavid Woodhouse parent = rb_parent(node); 2632f3243aeSDavid Woodhouse color = rb_color(node); 2641da177e4SLinus Torvalds 2654c601178SWolfram Strepp if (parent == old) { 2664c601178SWolfram Strepp parent = node; 2674c601178SWolfram Strepp } else { 2681da177e4SLinus Torvalds if (child) 26955a98102SDavid Woodhouse rb_set_parent(child, parent); 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 276*bf7ad8eeSMichel Lespinasse 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 2801da177e4SLinus Torvalds goto color; 2811da177e4SLinus Torvalds } 2821da177e4SLinus Torvalds 28355a98102SDavid Woodhouse parent = rb_parent(node); 2842f3243aeSDavid Woodhouse color = rb_color(node); 2851da177e4SLinus Torvalds 2861da177e4SLinus Torvalds if (child) 28755a98102SDavid Woodhouse rb_set_parent(child, parent); 288b945d6b2SPeter Zijlstra if (parent) 289b945d6b2SPeter Zijlstra { 2901da177e4SLinus Torvalds if (parent->rb_left == node) 2911da177e4SLinus Torvalds parent->rb_left = child; 2921da177e4SLinus Torvalds else 2931da177e4SLinus Torvalds parent->rb_right = child; 29417d9ddc7SPallipadi, Venkatesh } 295b945d6b2SPeter Zijlstra else 296b945d6b2SPeter Zijlstra root->rb_node = child; 2971da177e4SLinus Torvalds 2981da177e4SLinus Torvalds color: 2991da177e4SLinus Torvalds if (color == RB_BLACK) 3001da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 3011da177e4SLinus Torvalds } 3021da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 3031da177e4SLinus Torvalds 304b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 305b945d6b2SPeter Zijlstra { 306b945d6b2SPeter Zijlstra struct rb_node *parent; 307b945d6b2SPeter Zijlstra 308b945d6b2SPeter Zijlstra up: 309b945d6b2SPeter Zijlstra func(node, data); 310b945d6b2SPeter Zijlstra parent = rb_parent(node); 311b945d6b2SPeter Zijlstra if (!parent) 312b945d6b2SPeter Zijlstra return; 313b945d6b2SPeter Zijlstra 314b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 315b945d6b2SPeter Zijlstra func(parent->rb_right, data); 316b945d6b2SPeter Zijlstra else if (parent->rb_left) 317b945d6b2SPeter Zijlstra func(parent->rb_left, data); 318b945d6b2SPeter Zijlstra 319b945d6b2SPeter Zijlstra node = parent; 320b945d6b2SPeter Zijlstra goto up; 321b945d6b2SPeter Zijlstra } 322b945d6b2SPeter Zijlstra 323b945d6b2SPeter Zijlstra /* 324b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 325b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 326b945d6b2SPeter Zijlstra */ 327b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 328b945d6b2SPeter Zijlstra { 329b945d6b2SPeter Zijlstra if (node->rb_left) 330b945d6b2SPeter Zijlstra node = node->rb_left; 331b945d6b2SPeter Zijlstra else if (node->rb_right) 332b945d6b2SPeter Zijlstra node = node->rb_right; 333b945d6b2SPeter Zijlstra 334b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 335b945d6b2SPeter Zijlstra } 3360b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 337b945d6b2SPeter Zijlstra 338b945d6b2SPeter Zijlstra /* 339b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 340b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 341b945d6b2SPeter Zijlstra */ 342b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 343b945d6b2SPeter Zijlstra { 344b945d6b2SPeter Zijlstra struct rb_node *deepest; 345b945d6b2SPeter Zijlstra 346b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 347b945d6b2SPeter Zijlstra deepest = rb_parent(node); 348b945d6b2SPeter Zijlstra else if (!node->rb_right) 349b945d6b2SPeter Zijlstra deepest = node->rb_left; 350b945d6b2SPeter Zijlstra else if (!node->rb_left) 351b945d6b2SPeter Zijlstra deepest = node->rb_right; 352b945d6b2SPeter Zijlstra else { 353b945d6b2SPeter Zijlstra deepest = rb_next(node); 354b945d6b2SPeter Zijlstra if (deepest->rb_right) 355b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 356b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 357b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 358b945d6b2SPeter Zijlstra } 359b945d6b2SPeter Zijlstra 360b945d6b2SPeter Zijlstra return deepest; 361b945d6b2SPeter Zijlstra } 3620b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 363b945d6b2SPeter Zijlstra 364b945d6b2SPeter Zijlstra /* 365b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 366b945d6b2SPeter Zijlstra * and any rebalance damage. 367b945d6b2SPeter Zijlstra */ 368b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 369b945d6b2SPeter Zijlstra { 370b945d6b2SPeter Zijlstra if (node) 371b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 372b945d6b2SPeter Zijlstra } 3730b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 374b945d6b2SPeter Zijlstra 3751da177e4SLinus Torvalds /* 3761da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 3771da177e4SLinus Torvalds */ 378f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 3791da177e4SLinus Torvalds { 3801da177e4SLinus Torvalds struct rb_node *n; 3811da177e4SLinus Torvalds 3821da177e4SLinus Torvalds n = root->rb_node; 3831da177e4SLinus Torvalds if (!n) 3841da177e4SLinus Torvalds return NULL; 3851da177e4SLinus Torvalds while (n->rb_left) 3861da177e4SLinus Torvalds n = n->rb_left; 3871da177e4SLinus Torvalds return n; 3881da177e4SLinus Torvalds } 3891da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 3901da177e4SLinus Torvalds 391f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 3921da177e4SLinus Torvalds { 3931da177e4SLinus Torvalds struct rb_node *n; 3941da177e4SLinus Torvalds 3951da177e4SLinus Torvalds n = root->rb_node; 3961da177e4SLinus Torvalds if (!n) 3971da177e4SLinus Torvalds return NULL; 3981da177e4SLinus Torvalds while (n->rb_right) 3991da177e4SLinus Torvalds n = n->rb_right; 4001da177e4SLinus Torvalds return n; 4011da177e4SLinus Torvalds } 4021da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 4031da177e4SLinus Torvalds 404f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 4051da177e4SLinus Torvalds { 40655a98102SDavid Woodhouse struct rb_node *parent; 40755a98102SDavid Woodhouse 4084c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 40910fd48f2SJens Axboe return NULL; 41010fd48f2SJens Axboe 4111da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 4121da177e4SLinus Torvalds as we can. */ 4131da177e4SLinus Torvalds if (node->rb_right) { 4141da177e4SLinus Torvalds node = node->rb_right; 4151da177e4SLinus Torvalds while (node->rb_left) 4161da177e4SLinus Torvalds node=node->rb_left; 417f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4181da177e4SLinus Torvalds } 4191da177e4SLinus Torvalds 4201da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 4211da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 4221da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 4231da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 4241da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 4251da177e4SLinus Torvalds parent is our 'next' node. */ 42655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 42755a98102SDavid Woodhouse node = parent; 4281da177e4SLinus Torvalds 42955a98102SDavid Woodhouse return parent; 4301da177e4SLinus Torvalds } 4311da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 4321da177e4SLinus Torvalds 433f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 4341da177e4SLinus Torvalds { 43555a98102SDavid Woodhouse struct rb_node *parent; 43655a98102SDavid Woodhouse 4374c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 43810fd48f2SJens Axboe return NULL; 43910fd48f2SJens Axboe 4401da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 4411da177e4SLinus Torvalds as we can. */ 4421da177e4SLinus Torvalds if (node->rb_left) { 4431da177e4SLinus Torvalds node = node->rb_left; 4441da177e4SLinus Torvalds while (node->rb_right) 4451da177e4SLinus Torvalds node=node->rb_right; 446f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 4471da177e4SLinus Torvalds } 4481da177e4SLinus Torvalds 4491da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 4501da177e4SLinus Torvalds is a right-hand child of its parent */ 45155a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 45255a98102SDavid Woodhouse node = parent; 4531da177e4SLinus Torvalds 45455a98102SDavid Woodhouse return parent; 4551da177e4SLinus Torvalds } 4561da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 4571da177e4SLinus Torvalds 4581da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 4591da177e4SLinus Torvalds struct rb_root *root) 4601da177e4SLinus Torvalds { 46155a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 4621da177e4SLinus Torvalds 4631da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 4641da177e4SLinus Torvalds if (parent) { 4651da177e4SLinus Torvalds if (victim == parent->rb_left) 4661da177e4SLinus Torvalds parent->rb_left = new; 4671da177e4SLinus Torvalds else 4681da177e4SLinus Torvalds parent->rb_right = new; 4691da177e4SLinus Torvalds } else { 4701da177e4SLinus Torvalds root->rb_node = new; 4711da177e4SLinus Torvalds } 4721da177e4SLinus Torvalds if (victim->rb_left) 47355a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 4741da177e4SLinus Torvalds if (victim->rb_right) 47555a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 4761da177e4SLinus Torvalds 4771da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 4781da177e4SLinus Torvalds *new = *victim; 4791da177e4SLinus Torvalds } 4801da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 481