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 265bc9188aSMichel Lespinasse /* 275bc9188aSMichel Lespinasse * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree 285bc9188aSMichel Lespinasse * 295bc9188aSMichel Lespinasse * 1) A node is either red or black 305bc9188aSMichel Lespinasse * 2) The root is black 315bc9188aSMichel Lespinasse * 3) All leaves (NULL) are black 325bc9188aSMichel Lespinasse * 4) Both children of every red node are black 335bc9188aSMichel Lespinasse * 5) Every simple path from root to leaves contains the same number 345bc9188aSMichel Lespinasse * of black nodes. 355bc9188aSMichel Lespinasse * 365bc9188aSMichel Lespinasse * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two 375bc9188aSMichel Lespinasse * consecutive red nodes in a path and every red node is therefore followed by 385bc9188aSMichel Lespinasse * a black. So if B is the number of black nodes on every simple path (as per 395bc9188aSMichel Lespinasse * 5), then the longest possible path due to 4 is 2B. 405bc9188aSMichel Lespinasse * 415bc9188aSMichel Lespinasse * We shall indicate color with case, where black nodes are uppercase and red 425bc9188aSMichel Lespinasse * nodes will be lowercase. 435bc9188aSMichel Lespinasse */ 445bc9188aSMichel Lespinasse 45bf7ad8eeSMichel Lespinasse #define RB_RED 0 46bf7ad8eeSMichel Lespinasse #define RB_BLACK 1 47bf7ad8eeSMichel Lespinasse 48bf7ad8eeSMichel Lespinasse #define rb_color(r) ((r)->__rb_parent_color & 1) 49bf7ad8eeSMichel Lespinasse #define rb_is_red(r) (!rb_color(r)) 50bf7ad8eeSMichel Lespinasse #define rb_is_black(r) rb_color(r) 51bf7ad8eeSMichel Lespinasse #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) 52bf7ad8eeSMichel Lespinasse #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) 53bf7ad8eeSMichel Lespinasse 54bf7ad8eeSMichel Lespinasse static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 55bf7ad8eeSMichel Lespinasse { 56bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 57bf7ad8eeSMichel Lespinasse } 58bf7ad8eeSMichel Lespinasse static inline void rb_set_color(struct rb_node *rb, int color) 59bf7ad8eeSMichel Lespinasse { 60bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; 61bf7ad8eeSMichel Lespinasse } 62bf7ad8eeSMichel Lespinasse 635bc9188aSMichel Lespinasse static inline void rb_set_parent_color(struct rb_node *rb, 645bc9188aSMichel Lespinasse struct rb_node *p, int color) 655bc9188aSMichel Lespinasse { 665bc9188aSMichel Lespinasse rb->__rb_parent_color = (unsigned long)p | color; 675bc9188aSMichel Lespinasse } 685bc9188aSMichel Lespinasse 695bc9188aSMichel Lespinasse static inline struct rb_node *rb_red_parent(struct rb_node *red) 705bc9188aSMichel Lespinasse { 715bc9188aSMichel Lespinasse return (struct rb_node *)red->__rb_parent_color; 725bc9188aSMichel Lespinasse } 735bc9188aSMichel Lespinasse 741da177e4SLinus Torvalds static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 751da177e4SLinus Torvalds { 761da177e4SLinus Torvalds struct rb_node *right = node->rb_right; 7755a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 781da177e4SLinus Torvalds 791da177e4SLinus Torvalds if ((node->rb_right = right->rb_left)) 8055a98102SDavid Woodhouse rb_set_parent(right->rb_left, node); 811da177e4SLinus Torvalds right->rb_left = node; 821da177e4SLinus Torvalds 8355a98102SDavid Woodhouse rb_set_parent(right, parent); 8455a98102SDavid Woodhouse 8555a98102SDavid Woodhouse if (parent) 861da177e4SLinus Torvalds { 8755a98102SDavid Woodhouse if (node == parent->rb_left) 8855a98102SDavid Woodhouse parent->rb_left = right; 891da177e4SLinus Torvalds else 9055a98102SDavid Woodhouse parent->rb_right = right; 911da177e4SLinus Torvalds } 921da177e4SLinus Torvalds else 931da177e4SLinus Torvalds root->rb_node = right; 9455a98102SDavid Woodhouse rb_set_parent(node, right); 951da177e4SLinus Torvalds } 961da177e4SLinus Torvalds 971da177e4SLinus Torvalds static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 981da177e4SLinus Torvalds { 991da177e4SLinus Torvalds struct rb_node *left = node->rb_left; 10055a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 1011da177e4SLinus Torvalds 1021da177e4SLinus Torvalds if ((node->rb_left = left->rb_right)) 10355a98102SDavid Woodhouse rb_set_parent(left->rb_right, node); 1041da177e4SLinus Torvalds left->rb_right = node; 1051da177e4SLinus Torvalds 10655a98102SDavid Woodhouse rb_set_parent(left, parent); 10755a98102SDavid Woodhouse 10855a98102SDavid Woodhouse if (parent) 1091da177e4SLinus Torvalds { 11055a98102SDavid Woodhouse if (node == parent->rb_right) 11155a98102SDavid Woodhouse parent->rb_right = left; 1121da177e4SLinus Torvalds else 11355a98102SDavid Woodhouse parent->rb_left = left; 1141da177e4SLinus Torvalds } 1151da177e4SLinus Torvalds else 1161da177e4SLinus Torvalds root->rb_node = left; 11755a98102SDavid Woodhouse rb_set_parent(node, left); 1181da177e4SLinus Torvalds } 1191da177e4SLinus Torvalds 1205bc9188aSMichel Lespinasse /* 1215bc9188aSMichel Lespinasse * Helper function for rotations: 1225bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 1235bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 1245bc9188aSMichel Lespinasse */ 1255bc9188aSMichel Lespinasse static inline void 1265bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 1275bc9188aSMichel Lespinasse struct rb_root *root, int color) 1285bc9188aSMichel Lespinasse { 1295bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 1305bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 1315bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 1325bc9188aSMichel Lespinasse if (parent) { 1335bc9188aSMichel Lespinasse if (parent->rb_left == old) 1345bc9188aSMichel Lespinasse parent->rb_left = new; 1355bc9188aSMichel Lespinasse else 1365bc9188aSMichel Lespinasse parent->rb_right = new; 1375bc9188aSMichel Lespinasse } else 1385bc9188aSMichel Lespinasse root->rb_node = new; 1395bc9188aSMichel Lespinasse } 1405bc9188aSMichel Lespinasse 1411da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 1421da177e4SLinus Torvalds { 1435bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 1441da177e4SLinus Torvalds 1456d58452dSMichel Lespinasse while (true) { 1466d58452dSMichel Lespinasse /* 1476d58452dSMichel Lespinasse * Loop invariant: node is red 1486d58452dSMichel Lespinasse * 1496d58452dSMichel Lespinasse * If there is a black parent, we are done. 1506d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 1516d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 1526d58452dSMichel Lespinasse */ 1536d58452dSMichel Lespinasse if (!parent) { 1545bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1556d58452dSMichel Lespinasse break; 1566d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 1576d58452dSMichel Lespinasse break; 1586d58452dSMichel Lespinasse 1595bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1601da177e4SLinus Torvalds 1615bc9188aSMichel Lespinasse if (parent == gparent->rb_left) { 1625bc9188aSMichel Lespinasse tmp = gparent->rb_right; 1635bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1645bc9188aSMichel Lespinasse /* 1655bc9188aSMichel Lespinasse * Case 1 - color flips 1665bc9188aSMichel Lespinasse * 1675bc9188aSMichel Lespinasse * G g 1685bc9188aSMichel Lespinasse * / \ / \ 1695bc9188aSMichel Lespinasse * p u --> P U 1705bc9188aSMichel Lespinasse * / / 1715bc9188aSMichel Lespinasse * n N 1725bc9188aSMichel Lespinasse * 1735bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1745bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1755bc9188aSMichel Lespinasse * at g. 1765bc9188aSMichel Lespinasse */ 1775bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1785bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1791da177e4SLinus Torvalds node = gparent; 1805bc9188aSMichel Lespinasse parent = rb_parent(node); 1815bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1821da177e4SLinus Torvalds continue; 1831da177e4SLinus Torvalds } 1841da177e4SLinus Torvalds 1851f052865SMichel Lespinasse if (parent->rb_right == node) { 1865bc9188aSMichel Lespinasse /* 1875bc9188aSMichel Lespinasse * Case 2 - left rotate at parent 1885bc9188aSMichel Lespinasse * 1895bc9188aSMichel Lespinasse * G G 1905bc9188aSMichel Lespinasse * / \ / \ 1915bc9188aSMichel Lespinasse * p U --> n U 1925bc9188aSMichel Lespinasse * \ / 1935bc9188aSMichel Lespinasse * n p 1945bc9188aSMichel Lespinasse * 1955bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1965bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1975bc9188aSMichel Lespinasse */ 1985bc9188aSMichel Lespinasse parent->rb_right = tmp = node->rb_left; 1995bc9188aSMichel Lespinasse node->rb_left = parent; 2005bc9188aSMichel Lespinasse if (tmp) 2015bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2025bc9188aSMichel Lespinasse RB_BLACK); 2035bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 2041da177e4SLinus Torvalds parent = node; 2051da177e4SLinus Torvalds } 2061da177e4SLinus Torvalds 2075bc9188aSMichel Lespinasse /* 2085bc9188aSMichel Lespinasse * Case 3 - right rotate at gparent 2095bc9188aSMichel Lespinasse * 2105bc9188aSMichel Lespinasse * G P 2115bc9188aSMichel Lespinasse * / \ / \ 2125bc9188aSMichel Lespinasse * p U --> n g 2135bc9188aSMichel Lespinasse * / \ 2145bc9188aSMichel Lespinasse * n U 2155bc9188aSMichel Lespinasse */ 2165bc9188aSMichel Lespinasse gparent->rb_left = tmp = parent->rb_right; 2175bc9188aSMichel Lespinasse parent->rb_right = gparent; 2185bc9188aSMichel Lespinasse if (tmp) 2195bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2205bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2211f052865SMichel Lespinasse break; 2221da177e4SLinus Torvalds } else { 2235bc9188aSMichel Lespinasse tmp = gparent->rb_left; 2245bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 2255bc9188aSMichel Lespinasse /* Case 1 - color flips */ 2265bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2275bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 2281da177e4SLinus Torvalds node = gparent; 2295bc9188aSMichel Lespinasse parent = rb_parent(node); 2305bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 2311da177e4SLinus Torvalds continue; 2321da177e4SLinus Torvalds } 2331da177e4SLinus Torvalds 2341f052865SMichel Lespinasse if (parent->rb_left == node) { 2355bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 2365bc9188aSMichel Lespinasse parent->rb_left = tmp = node->rb_right; 2375bc9188aSMichel Lespinasse node->rb_right = parent; 2385bc9188aSMichel Lespinasse if (tmp) 2395bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2405bc9188aSMichel Lespinasse RB_BLACK); 2415bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 2421da177e4SLinus Torvalds parent = node; 2431da177e4SLinus Torvalds } 2441da177e4SLinus Torvalds 2455bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 2465bc9188aSMichel Lespinasse gparent->rb_right = tmp = parent->rb_left; 2475bc9188aSMichel Lespinasse parent->rb_left = gparent; 2485bc9188aSMichel Lespinasse if (tmp) 2495bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2505bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2511f052865SMichel Lespinasse break; 2521da177e4SLinus Torvalds } 2531da177e4SLinus Torvalds } 2541da177e4SLinus Torvalds } 2551da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 2561da177e4SLinus Torvalds 2571da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 2581da177e4SLinus Torvalds struct rb_root *root) 2591da177e4SLinus Torvalds { 2601da177e4SLinus Torvalds struct rb_node *other; 2611da177e4SLinus Torvalds 262*d6ff1273SMichel Lespinasse while (true) { 263*d6ff1273SMichel Lespinasse /* 264*d6ff1273SMichel Lespinasse * Loop invariant: all leaf paths going through node have a 265*d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 266*d6ff1273SMichel Lespinasse * 267*d6ff1273SMichel Lespinasse * If node is red, we can flip it to black to adjust. 268*d6ff1273SMichel Lespinasse * If node is the root, all leaf paths go through it. 269*d6ff1273SMichel Lespinasse * Otherwise, we need to adjust the tree through color flips 270*d6ff1273SMichel Lespinasse * and tree rotations as per one of the 4 cases below. 271*d6ff1273SMichel Lespinasse */ 272*d6ff1273SMichel Lespinasse if (node && rb_is_red(node)) { 273*d6ff1273SMichel Lespinasse rb_set_black(node); 274*d6ff1273SMichel Lespinasse break; 275*d6ff1273SMichel Lespinasse } else if (!parent) { 276*d6ff1273SMichel Lespinasse break; 277*d6ff1273SMichel Lespinasse } else if (parent->rb_left == node) { 2781da177e4SLinus Torvalds other = parent->rb_right; 27955a98102SDavid Woodhouse if (rb_is_red(other)) 2801da177e4SLinus Torvalds { 28155a98102SDavid Woodhouse rb_set_black(other); 28255a98102SDavid Woodhouse rb_set_red(parent); 2831da177e4SLinus Torvalds __rb_rotate_left(parent, root); 2841da177e4SLinus Torvalds other = parent->rb_right; 2851da177e4SLinus Torvalds } 28655a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 28755a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 2881da177e4SLinus Torvalds { 28955a98102SDavid Woodhouse rb_set_red(other); 2901da177e4SLinus Torvalds node = parent; 29155a98102SDavid Woodhouse parent = rb_parent(node); 2921da177e4SLinus Torvalds } 2931da177e4SLinus Torvalds else 2941da177e4SLinus Torvalds { 29555a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 2961da177e4SLinus Torvalds { 29755a63998SWolfram Strepp rb_set_black(other->rb_left); 29855a98102SDavid Woodhouse rb_set_red(other); 2991da177e4SLinus Torvalds __rb_rotate_right(other, root); 3001da177e4SLinus Torvalds other = parent->rb_right; 3011da177e4SLinus Torvalds } 3022f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 30355a98102SDavid Woodhouse rb_set_black(parent); 30455a98102SDavid Woodhouse rb_set_black(other->rb_right); 3051da177e4SLinus Torvalds __rb_rotate_left(parent, root); 3061da177e4SLinus Torvalds break; 3071da177e4SLinus Torvalds } 308*d6ff1273SMichel Lespinasse } else { 3091da177e4SLinus Torvalds other = parent->rb_left; 31055a98102SDavid Woodhouse if (rb_is_red(other)) 3111da177e4SLinus Torvalds { 31255a98102SDavid Woodhouse rb_set_black(other); 31355a98102SDavid Woodhouse rb_set_red(parent); 3141da177e4SLinus Torvalds __rb_rotate_right(parent, root); 3151da177e4SLinus Torvalds other = parent->rb_left; 3161da177e4SLinus Torvalds } 31755a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 31855a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 3191da177e4SLinus Torvalds { 32055a98102SDavid Woodhouse rb_set_red(other); 3211da177e4SLinus Torvalds node = parent; 32255a98102SDavid Woodhouse parent = rb_parent(node); 3231da177e4SLinus Torvalds } 3241da177e4SLinus Torvalds else 3251da177e4SLinus Torvalds { 32655a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 3271da177e4SLinus Torvalds { 32855a63998SWolfram Strepp rb_set_black(other->rb_right); 32955a98102SDavid Woodhouse rb_set_red(other); 3301da177e4SLinus Torvalds __rb_rotate_left(other, root); 3311da177e4SLinus Torvalds other = parent->rb_left; 3321da177e4SLinus Torvalds } 3332f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 33455a98102SDavid Woodhouse rb_set_black(parent); 33555a98102SDavid Woodhouse rb_set_black(other->rb_left); 3361da177e4SLinus Torvalds __rb_rotate_right(parent, root); 3371da177e4SLinus Torvalds break; 3381da177e4SLinus Torvalds } 3391da177e4SLinus Torvalds } 3401da177e4SLinus Torvalds } 3411da177e4SLinus Torvalds } 3421da177e4SLinus Torvalds 3431da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 3441da177e4SLinus Torvalds { 3451da177e4SLinus Torvalds struct rb_node *child, *parent; 3461da177e4SLinus Torvalds int color; 3471da177e4SLinus Torvalds 3481da177e4SLinus Torvalds if (!node->rb_left) 3491da177e4SLinus Torvalds child = node->rb_right; 3501da177e4SLinus Torvalds else if (!node->rb_right) 3511da177e4SLinus Torvalds child = node->rb_left; 3521da177e4SLinus Torvalds else 3531da177e4SLinus Torvalds { 3541da177e4SLinus Torvalds struct rb_node *old = node, *left; 3551da177e4SLinus Torvalds 3561da177e4SLinus Torvalds node = node->rb_right; 3571da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 3581da177e4SLinus Torvalds node = left; 35916c047adSWolfram Strepp 36016c047adSWolfram Strepp if (rb_parent(old)) { 36116c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 36216c047adSWolfram Strepp rb_parent(old)->rb_left = node; 36316c047adSWolfram Strepp else 36416c047adSWolfram Strepp rb_parent(old)->rb_right = node; 36516c047adSWolfram Strepp } else 36616c047adSWolfram Strepp root->rb_node = node; 36716c047adSWolfram Strepp 3681da177e4SLinus Torvalds child = node->rb_right; 36955a98102SDavid Woodhouse parent = rb_parent(node); 3702f3243aeSDavid Woodhouse color = rb_color(node); 3711da177e4SLinus Torvalds 3724c601178SWolfram Strepp if (parent == old) { 3734c601178SWolfram Strepp parent = node; 3744c601178SWolfram Strepp } else { 3751da177e4SLinus Torvalds if (child) 37655a98102SDavid Woodhouse rb_set_parent(child, parent); 3771975e593SDavid Woodhouse parent->rb_left = child; 3784b324126SWolfram Strepp 3794b324126SWolfram Strepp node->rb_right = old->rb_right; 3804b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 3814c601178SWolfram Strepp } 3821975e593SDavid Woodhouse 383bf7ad8eeSMichel Lespinasse node->__rb_parent_color = old->__rb_parent_color; 3841da177e4SLinus Torvalds node->rb_left = old->rb_left; 38555a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 3864b324126SWolfram Strepp 3871da177e4SLinus Torvalds goto color; 3881da177e4SLinus Torvalds } 3891da177e4SLinus Torvalds 39055a98102SDavid Woodhouse parent = rb_parent(node); 3912f3243aeSDavid Woodhouse color = rb_color(node); 3921da177e4SLinus Torvalds 3931da177e4SLinus Torvalds if (child) 39455a98102SDavid Woodhouse rb_set_parent(child, parent); 395b945d6b2SPeter Zijlstra if (parent) 396b945d6b2SPeter Zijlstra { 3971da177e4SLinus Torvalds if (parent->rb_left == node) 3981da177e4SLinus Torvalds parent->rb_left = child; 3991da177e4SLinus Torvalds else 4001da177e4SLinus Torvalds parent->rb_right = child; 40117d9ddc7SPallipadi, Venkatesh } 402b945d6b2SPeter Zijlstra else 403b945d6b2SPeter Zijlstra root->rb_node = child; 4041da177e4SLinus Torvalds 4051da177e4SLinus Torvalds color: 4061da177e4SLinus Torvalds if (color == RB_BLACK) 4071da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 4081da177e4SLinus Torvalds } 4091da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4101da177e4SLinus Torvalds 411b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 412b945d6b2SPeter Zijlstra { 413b945d6b2SPeter Zijlstra struct rb_node *parent; 414b945d6b2SPeter Zijlstra 415b945d6b2SPeter Zijlstra up: 416b945d6b2SPeter Zijlstra func(node, data); 417b945d6b2SPeter Zijlstra parent = rb_parent(node); 418b945d6b2SPeter Zijlstra if (!parent) 419b945d6b2SPeter Zijlstra return; 420b945d6b2SPeter Zijlstra 421b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 422b945d6b2SPeter Zijlstra func(parent->rb_right, data); 423b945d6b2SPeter Zijlstra else if (parent->rb_left) 424b945d6b2SPeter Zijlstra func(parent->rb_left, data); 425b945d6b2SPeter Zijlstra 426b945d6b2SPeter Zijlstra node = parent; 427b945d6b2SPeter Zijlstra goto up; 428b945d6b2SPeter Zijlstra } 429b945d6b2SPeter Zijlstra 430b945d6b2SPeter Zijlstra /* 431b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 432b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 433b945d6b2SPeter Zijlstra */ 434b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 435b945d6b2SPeter Zijlstra { 436b945d6b2SPeter Zijlstra if (node->rb_left) 437b945d6b2SPeter Zijlstra node = node->rb_left; 438b945d6b2SPeter Zijlstra else if (node->rb_right) 439b945d6b2SPeter Zijlstra node = node->rb_right; 440b945d6b2SPeter Zijlstra 441b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 442b945d6b2SPeter Zijlstra } 4430b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 444b945d6b2SPeter Zijlstra 445b945d6b2SPeter Zijlstra /* 446b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 447b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 448b945d6b2SPeter Zijlstra */ 449b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 450b945d6b2SPeter Zijlstra { 451b945d6b2SPeter Zijlstra struct rb_node *deepest; 452b945d6b2SPeter Zijlstra 453b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 454b945d6b2SPeter Zijlstra deepest = rb_parent(node); 455b945d6b2SPeter Zijlstra else if (!node->rb_right) 456b945d6b2SPeter Zijlstra deepest = node->rb_left; 457b945d6b2SPeter Zijlstra else if (!node->rb_left) 458b945d6b2SPeter Zijlstra deepest = node->rb_right; 459b945d6b2SPeter Zijlstra else { 460b945d6b2SPeter Zijlstra deepest = rb_next(node); 461b945d6b2SPeter Zijlstra if (deepest->rb_right) 462b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 463b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 464b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 465b945d6b2SPeter Zijlstra } 466b945d6b2SPeter Zijlstra 467b945d6b2SPeter Zijlstra return deepest; 468b945d6b2SPeter Zijlstra } 4690b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 470b945d6b2SPeter Zijlstra 471b945d6b2SPeter Zijlstra /* 472b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 473b945d6b2SPeter Zijlstra * and any rebalance damage. 474b945d6b2SPeter Zijlstra */ 475b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 476b945d6b2SPeter Zijlstra { 477b945d6b2SPeter Zijlstra if (node) 478b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 479b945d6b2SPeter Zijlstra } 4800b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 481b945d6b2SPeter Zijlstra 4821da177e4SLinus Torvalds /* 4831da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 4841da177e4SLinus Torvalds */ 485f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 4861da177e4SLinus Torvalds { 4871da177e4SLinus Torvalds struct rb_node *n; 4881da177e4SLinus Torvalds 4891da177e4SLinus Torvalds n = root->rb_node; 4901da177e4SLinus Torvalds if (!n) 4911da177e4SLinus Torvalds return NULL; 4921da177e4SLinus Torvalds while (n->rb_left) 4931da177e4SLinus Torvalds n = n->rb_left; 4941da177e4SLinus Torvalds return n; 4951da177e4SLinus Torvalds } 4961da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 4971da177e4SLinus Torvalds 498f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 4991da177e4SLinus Torvalds { 5001da177e4SLinus Torvalds struct rb_node *n; 5011da177e4SLinus Torvalds 5021da177e4SLinus Torvalds n = root->rb_node; 5031da177e4SLinus Torvalds if (!n) 5041da177e4SLinus Torvalds return NULL; 5051da177e4SLinus Torvalds while (n->rb_right) 5061da177e4SLinus Torvalds n = n->rb_right; 5071da177e4SLinus Torvalds return n; 5081da177e4SLinus Torvalds } 5091da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5101da177e4SLinus Torvalds 511f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5121da177e4SLinus Torvalds { 51355a98102SDavid Woodhouse struct rb_node *parent; 51455a98102SDavid Woodhouse 5154c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 51610fd48f2SJens Axboe return NULL; 51710fd48f2SJens Axboe 5181da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 5191da177e4SLinus Torvalds as we can. */ 5201da177e4SLinus Torvalds if (node->rb_right) { 5211da177e4SLinus Torvalds node = node->rb_right; 5221da177e4SLinus Torvalds while (node->rb_left) 5231da177e4SLinus Torvalds node=node->rb_left; 524f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5251da177e4SLinus Torvalds } 5261da177e4SLinus Torvalds 5271da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 5281da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 5291da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 5301da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 5311da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 5321da177e4SLinus Torvalds parent is our 'next' node. */ 53355a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 53455a98102SDavid Woodhouse node = parent; 5351da177e4SLinus Torvalds 53655a98102SDavid Woodhouse return parent; 5371da177e4SLinus Torvalds } 5381da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 5391da177e4SLinus Torvalds 540f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 5411da177e4SLinus Torvalds { 54255a98102SDavid Woodhouse struct rb_node *parent; 54355a98102SDavid Woodhouse 5444c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 54510fd48f2SJens Axboe return NULL; 54610fd48f2SJens Axboe 5471da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 5481da177e4SLinus Torvalds as we can. */ 5491da177e4SLinus Torvalds if (node->rb_left) { 5501da177e4SLinus Torvalds node = node->rb_left; 5511da177e4SLinus Torvalds while (node->rb_right) 5521da177e4SLinus Torvalds node=node->rb_right; 553f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5541da177e4SLinus Torvalds } 5551da177e4SLinus Torvalds 5561da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 5571da177e4SLinus Torvalds is a right-hand child of its parent */ 55855a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 55955a98102SDavid Woodhouse node = parent; 5601da177e4SLinus Torvalds 56155a98102SDavid Woodhouse return parent; 5621da177e4SLinus Torvalds } 5631da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 5641da177e4SLinus Torvalds 5651da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 5661da177e4SLinus Torvalds struct rb_root *root) 5671da177e4SLinus Torvalds { 56855a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 5691da177e4SLinus Torvalds 5701da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 5711da177e4SLinus Torvalds if (parent) { 5721da177e4SLinus Torvalds if (victim == parent->rb_left) 5731da177e4SLinus Torvalds parent->rb_left = new; 5741da177e4SLinus Torvalds else 5751da177e4SLinus Torvalds parent->rb_right = new; 5761da177e4SLinus Torvalds } else { 5771da177e4SLinus Torvalds root->rb_node = new; 5781da177e4SLinus Torvalds } 5791da177e4SLinus Torvalds if (victim->rb_left) 58055a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 5811da177e4SLinus Torvalds if (victim->rb_right) 58255a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 5831da177e4SLinus Torvalds 5841da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 5851da177e4SLinus Torvalds *new = *victim; 5861da177e4SLinus Torvalds } 5871da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 588