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 426280d235SMichel Lespinasse * nodes will be lowercase. Unknown color nodes shall be drawn as red within 436280d235SMichel Lespinasse * parentheses and have some accompanying text comment. 445bc9188aSMichel Lespinasse */ 455bc9188aSMichel Lespinasse 46bf7ad8eeSMichel Lespinasse #define RB_RED 0 47bf7ad8eeSMichel Lespinasse #define RB_BLACK 1 48bf7ad8eeSMichel Lespinasse 49bf7ad8eeSMichel Lespinasse #define rb_color(r) ((r)->__rb_parent_color & 1) 50bf7ad8eeSMichel Lespinasse #define rb_is_red(r) (!rb_color(r)) 51bf7ad8eeSMichel Lespinasse #define rb_is_black(r) rb_color(r) 52bf7ad8eeSMichel Lespinasse 53bf7ad8eeSMichel Lespinasse static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 54bf7ad8eeSMichel Lespinasse { 55bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 56bf7ad8eeSMichel Lespinasse } 57bf7ad8eeSMichel Lespinasse 585bc9188aSMichel Lespinasse static inline void rb_set_parent_color(struct rb_node *rb, 595bc9188aSMichel Lespinasse struct rb_node *p, int color) 605bc9188aSMichel Lespinasse { 615bc9188aSMichel Lespinasse rb->__rb_parent_color = (unsigned long)p | color; 625bc9188aSMichel Lespinasse } 635bc9188aSMichel Lespinasse 645bc9188aSMichel Lespinasse static inline struct rb_node *rb_red_parent(struct rb_node *red) 655bc9188aSMichel Lespinasse { 665bc9188aSMichel Lespinasse return (struct rb_node *)red->__rb_parent_color; 675bc9188aSMichel Lespinasse } 685bc9188aSMichel Lespinasse 697abc704aSMichel Lespinasse static inline void 707abc704aSMichel Lespinasse __rb_change_child(struct rb_node *old, struct rb_node *new, 717abc704aSMichel Lespinasse struct rb_node *parent, struct rb_root *root) 727abc704aSMichel Lespinasse { 737abc704aSMichel Lespinasse if (parent) { 747abc704aSMichel Lespinasse if (parent->rb_left == old) 757abc704aSMichel Lespinasse parent->rb_left = new; 767abc704aSMichel Lespinasse else 777abc704aSMichel Lespinasse parent->rb_right = new; 787abc704aSMichel Lespinasse } else 797abc704aSMichel Lespinasse root->rb_node = new; 807abc704aSMichel Lespinasse } 817abc704aSMichel Lespinasse 825bc9188aSMichel Lespinasse /* 835bc9188aSMichel Lespinasse * Helper function for rotations: 845bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 855bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 865bc9188aSMichel Lespinasse */ 875bc9188aSMichel Lespinasse static inline void 885bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 895bc9188aSMichel Lespinasse struct rb_root *root, int color) 905bc9188aSMichel Lespinasse { 915bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 925bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 935bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 947abc704aSMichel Lespinasse __rb_change_child(old, new, parent, root); 955bc9188aSMichel Lespinasse } 965bc9188aSMichel Lespinasse 971da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 981da177e4SLinus Torvalds { 995bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 1001da177e4SLinus Torvalds 1016d58452dSMichel Lespinasse while (true) { 1026d58452dSMichel Lespinasse /* 1036d58452dSMichel Lespinasse * Loop invariant: node is red 1046d58452dSMichel Lespinasse * 1056d58452dSMichel Lespinasse * If there is a black parent, we are done. 1066d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 1076d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 1086d58452dSMichel Lespinasse */ 1096d58452dSMichel Lespinasse if (!parent) { 1105bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1116d58452dSMichel Lespinasse break; 1126d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 1136d58452dSMichel Lespinasse break; 1146d58452dSMichel Lespinasse 1155bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1161da177e4SLinus Torvalds 1175bc9188aSMichel Lespinasse tmp = gparent->rb_right; 11859633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1195bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1205bc9188aSMichel Lespinasse /* 1215bc9188aSMichel Lespinasse * Case 1 - color flips 1225bc9188aSMichel Lespinasse * 1235bc9188aSMichel Lespinasse * G g 1245bc9188aSMichel Lespinasse * / \ / \ 1255bc9188aSMichel Lespinasse * p u --> P U 1265bc9188aSMichel Lespinasse * / / 1275bc9188aSMichel Lespinasse * n N 1285bc9188aSMichel Lespinasse * 1295bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1305bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1315bc9188aSMichel Lespinasse * at g. 1325bc9188aSMichel Lespinasse */ 1335bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1345bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1351da177e4SLinus Torvalds node = gparent; 1365bc9188aSMichel Lespinasse parent = rb_parent(node); 1375bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1381da177e4SLinus Torvalds continue; 1391da177e4SLinus Torvalds } 1401da177e4SLinus Torvalds 14159633abfSMichel Lespinasse tmp = parent->rb_right; 14259633abfSMichel Lespinasse if (node == tmp) { 1435bc9188aSMichel Lespinasse /* 1445bc9188aSMichel Lespinasse * Case 2 - left rotate at parent 1455bc9188aSMichel Lespinasse * 1465bc9188aSMichel Lespinasse * G G 1475bc9188aSMichel Lespinasse * / \ / \ 1485bc9188aSMichel Lespinasse * p U --> n U 1495bc9188aSMichel Lespinasse * \ / 1505bc9188aSMichel Lespinasse * n p 1515bc9188aSMichel Lespinasse * 1525bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1535bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1545bc9188aSMichel Lespinasse */ 1555bc9188aSMichel Lespinasse parent->rb_right = tmp = node->rb_left; 1565bc9188aSMichel Lespinasse node->rb_left = parent; 1575bc9188aSMichel Lespinasse if (tmp) 1585bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1595bc9188aSMichel Lespinasse RB_BLACK); 1605bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 1611da177e4SLinus Torvalds parent = node; 16259633abfSMichel Lespinasse tmp = node->rb_right; 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1655bc9188aSMichel Lespinasse /* 1665bc9188aSMichel Lespinasse * Case 3 - right rotate at gparent 1675bc9188aSMichel Lespinasse * 1685bc9188aSMichel Lespinasse * G P 1695bc9188aSMichel Lespinasse * / \ / \ 1705bc9188aSMichel Lespinasse * p U --> n g 1715bc9188aSMichel Lespinasse * / \ 1725bc9188aSMichel Lespinasse * n U 1735bc9188aSMichel Lespinasse */ 17459633abfSMichel Lespinasse gparent->rb_left = tmp; /* == parent->rb_right */ 1755bc9188aSMichel Lespinasse parent->rb_right = gparent; 1765bc9188aSMichel Lespinasse if (tmp) 1775bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1785bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1791f052865SMichel Lespinasse break; 1801da177e4SLinus Torvalds } else { 1815bc9188aSMichel Lespinasse tmp = gparent->rb_left; 1825bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1835bc9188aSMichel Lespinasse /* Case 1 - color flips */ 1845bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1855bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1861da177e4SLinus Torvalds node = gparent; 1875bc9188aSMichel Lespinasse parent = rb_parent(node); 1885bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1891da177e4SLinus Torvalds continue; 1901da177e4SLinus Torvalds } 1911da177e4SLinus Torvalds 19259633abfSMichel Lespinasse tmp = parent->rb_left; 19359633abfSMichel Lespinasse if (node == tmp) { 1945bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 1955bc9188aSMichel Lespinasse parent->rb_left = tmp = node->rb_right; 1965bc9188aSMichel Lespinasse node->rb_right = parent; 1975bc9188aSMichel Lespinasse if (tmp) 1985bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1995bc9188aSMichel Lespinasse RB_BLACK); 2005bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 2011da177e4SLinus Torvalds parent = node; 20259633abfSMichel Lespinasse tmp = node->rb_left; 2031da177e4SLinus Torvalds } 2041da177e4SLinus Torvalds 2055bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 20659633abfSMichel Lespinasse gparent->rb_right = tmp; /* == parent->rb_left */ 2075bc9188aSMichel Lespinasse parent->rb_left = gparent; 2085bc9188aSMichel Lespinasse if (tmp) 2095bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2105bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2111f052865SMichel Lespinasse break; 2121da177e4SLinus Torvalds } 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds } 2151da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 2161da177e4SLinus Torvalds 2171da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 2181da177e4SLinus Torvalds struct rb_root *root) 2191da177e4SLinus Torvalds { 2206280d235SMichel Lespinasse struct rb_node *sibling, *tmp1, *tmp2; 2211da177e4SLinus Torvalds 222d6ff1273SMichel Lespinasse while (true) { 223d6ff1273SMichel Lespinasse /* 224d6ff1273SMichel Lespinasse * Loop invariant: all leaf paths going through node have a 225d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 226d6ff1273SMichel Lespinasse * 227d6ff1273SMichel Lespinasse * If node is red, we can flip it to black to adjust. 228d6ff1273SMichel Lespinasse * If node is the root, all leaf paths go through it. 229d6ff1273SMichel Lespinasse * Otherwise, we need to adjust the tree through color flips 230d6ff1273SMichel Lespinasse * and tree rotations as per one of the 4 cases below. 231d6ff1273SMichel Lespinasse */ 232d6ff1273SMichel Lespinasse if (node && rb_is_red(node)) { 2336280d235SMichel Lespinasse rb_set_parent_color(node, parent, RB_BLACK); 234d6ff1273SMichel Lespinasse break; 235d6ff1273SMichel Lespinasse } else if (!parent) { 236d6ff1273SMichel Lespinasse break; 23759633abfSMichel Lespinasse } 2386280d235SMichel Lespinasse sibling = parent->rb_right; 23959633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2406280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2416280d235SMichel Lespinasse /* 2426280d235SMichel Lespinasse * Case 1 - left rotate at parent 2436280d235SMichel Lespinasse * 2446280d235SMichel Lespinasse * P S 2456280d235SMichel Lespinasse * / \ / \ 2466280d235SMichel Lespinasse * N s --> p Sr 2476280d235SMichel Lespinasse * / \ / \ 2486280d235SMichel Lespinasse * Sl Sr N Sl 2496280d235SMichel Lespinasse */ 2506280d235SMichel Lespinasse parent->rb_right = tmp1 = sibling->rb_left; 2516280d235SMichel Lespinasse sibling->rb_left = parent; 2526280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2536280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2546280d235SMichel Lespinasse RB_RED); 2556280d235SMichel Lespinasse sibling = tmp1; 2561da177e4SLinus Torvalds } 2576280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2586280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2596280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2606280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2616280d235SMichel Lespinasse /* 2626280d235SMichel Lespinasse * Case 2 - sibling color flip 2636280d235SMichel Lespinasse * (p could be either color here) 2646280d235SMichel Lespinasse * 2656280d235SMichel Lespinasse * (p) (p) 2666280d235SMichel Lespinasse * / \ / \ 2676280d235SMichel Lespinasse * N S --> N s 2686280d235SMichel Lespinasse * / \ / \ 2696280d235SMichel Lespinasse * Sl Sr Sl Sr 2706280d235SMichel Lespinasse * 2716280d235SMichel Lespinasse * This leaves us violating 5), so 2726280d235SMichel Lespinasse * recurse at p. If p is red, the 2736280d235SMichel Lespinasse * recursion will just flip it to black 2746280d235SMichel Lespinasse * and exit. If coming from Case 1, 2756280d235SMichel Lespinasse * p is known to be red. 2766280d235SMichel Lespinasse */ 2776280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2786280d235SMichel Lespinasse RB_RED); 2791da177e4SLinus Torvalds node = parent; 28055a98102SDavid Woodhouse parent = rb_parent(node); 281e125d147SMichel Lespinasse continue; 2821da177e4SLinus Torvalds } 2836280d235SMichel Lespinasse /* 2846280d235SMichel Lespinasse * Case 3 - right rotate at sibling 2856280d235SMichel Lespinasse * (p could be either color here) 2866280d235SMichel Lespinasse * 2876280d235SMichel Lespinasse * (p) (p) 2886280d235SMichel Lespinasse * / \ / \ 2896280d235SMichel Lespinasse * N S --> N Sl 2906280d235SMichel Lespinasse * / \ \ 2916280d235SMichel Lespinasse * sl Sr s 2926280d235SMichel Lespinasse * \ 2936280d235SMichel Lespinasse * Sr 2946280d235SMichel Lespinasse */ 2956280d235SMichel Lespinasse sibling->rb_left = tmp1 = tmp2->rb_right; 2966280d235SMichel Lespinasse tmp2->rb_right = sibling; 2976280d235SMichel Lespinasse parent->rb_right = tmp2; 2986280d235SMichel Lespinasse if (tmp1) 2996280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3006280d235SMichel Lespinasse RB_BLACK); 3016280d235SMichel Lespinasse tmp1 = sibling; 3026280d235SMichel Lespinasse sibling = tmp2; 3031da177e4SLinus Torvalds } 3046280d235SMichel Lespinasse /* 3056280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 3066280d235SMichel Lespinasse * (p and sl could be either color here. 3076280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3086280d235SMichel Lespinasse * p's color, and sl keeps its color) 3096280d235SMichel Lespinasse * 3106280d235SMichel Lespinasse * (p) (s) 3116280d235SMichel Lespinasse * / \ / \ 3126280d235SMichel Lespinasse * N S --> P Sr 3136280d235SMichel Lespinasse * / \ / \ 3146280d235SMichel Lespinasse * (sl) sr N (sl) 3156280d235SMichel Lespinasse */ 3166280d235SMichel Lespinasse parent->rb_right = tmp2 = sibling->rb_left; 3176280d235SMichel Lespinasse sibling->rb_left = parent; 3186280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3196280d235SMichel Lespinasse if (tmp2) 3206280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3216280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3226280d235SMichel Lespinasse RB_BLACK); 3231da177e4SLinus Torvalds break; 324d6ff1273SMichel Lespinasse } else { 3256280d235SMichel Lespinasse sibling = parent->rb_left; 3266280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3276280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 3286280d235SMichel Lespinasse parent->rb_left = tmp1 = sibling->rb_right; 3296280d235SMichel Lespinasse sibling->rb_right = parent; 3306280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3316280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3326280d235SMichel Lespinasse RB_RED); 3336280d235SMichel Lespinasse sibling = tmp1; 3341da177e4SLinus Torvalds } 3356280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3366280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3376280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3386280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3396280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3406280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3416280d235SMichel Lespinasse RB_RED); 3421da177e4SLinus Torvalds node = parent; 34355a98102SDavid Woodhouse parent = rb_parent(node); 344e125d147SMichel Lespinasse continue; 3451da177e4SLinus Torvalds } 3466280d235SMichel Lespinasse /* Case 3 - right rotate at sibling */ 3476280d235SMichel Lespinasse sibling->rb_right = tmp1 = tmp2->rb_left; 3486280d235SMichel Lespinasse tmp2->rb_left = sibling; 3496280d235SMichel Lespinasse parent->rb_left = tmp2; 3506280d235SMichel Lespinasse if (tmp1) 3516280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3526280d235SMichel Lespinasse RB_BLACK); 3536280d235SMichel Lespinasse tmp1 = sibling; 3546280d235SMichel Lespinasse sibling = tmp2; 3551da177e4SLinus Torvalds } 3566280d235SMichel Lespinasse /* Case 4 - left rotate at parent + color flips */ 3576280d235SMichel Lespinasse parent->rb_left = tmp2 = sibling->rb_right; 3586280d235SMichel Lespinasse sibling->rb_right = parent; 3596280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3606280d235SMichel Lespinasse if (tmp2) 3616280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3626280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3636280d235SMichel Lespinasse RB_BLACK); 3641da177e4SLinus Torvalds break; 3651da177e4SLinus Torvalds } 3661da177e4SLinus Torvalds } 3671da177e4SLinus Torvalds } 3681da177e4SLinus Torvalds 3691da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 3701da177e4SLinus Torvalds { 371*60670b80SMichel Lespinasse struct rb_node *child = node->rb_right, *tmp = node->rb_left; 372*60670b80SMichel Lespinasse struct rb_node *parent; 3731da177e4SLinus Torvalds int color; 3741da177e4SLinus Torvalds 375*60670b80SMichel Lespinasse if (!tmp) { 376*60670b80SMichel Lespinasse case1: 377*60670b80SMichel Lespinasse /* Case 1: node to erase has no more than 1 child (easy!) */ 378*60670b80SMichel Lespinasse 379*60670b80SMichel Lespinasse parent = rb_parent(node); 380*60670b80SMichel Lespinasse color = rb_color(node); 381*60670b80SMichel Lespinasse 382*60670b80SMichel Lespinasse if (child) 383*60670b80SMichel Lespinasse rb_set_parent(child, parent); 384*60670b80SMichel Lespinasse __rb_change_child(node, child, parent, root); 385*60670b80SMichel Lespinasse } else if (!child) { 386*60670b80SMichel Lespinasse /* Still case 1, but this time the child is node->rb_left */ 387*60670b80SMichel Lespinasse child = tmp; 388*60670b80SMichel Lespinasse goto case1; 389*60670b80SMichel Lespinasse } else { 3901da177e4SLinus Torvalds struct rb_node *old = node, *left; 3911da177e4SLinus Torvalds 392*60670b80SMichel Lespinasse node = child; 3931da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 3941da177e4SLinus Torvalds node = left; 39516c047adSWolfram Strepp 3967abc704aSMichel Lespinasse __rb_change_child(old, node, rb_parent(old), root); 39716c047adSWolfram Strepp 3981da177e4SLinus Torvalds child = node->rb_right; 39955a98102SDavid Woodhouse parent = rb_parent(node); 4002f3243aeSDavid Woodhouse color = rb_color(node); 4011da177e4SLinus Torvalds 4024c601178SWolfram Strepp if (parent == old) { 4034c601178SWolfram Strepp parent = node; 4044c601178SWolfram Strepp } else { 4051da177e4SLinus Torvalds if (child) 40655a98102SDavid Woodhouse rb_set_parent(child, parent); 4071975e593SDavid Woodhouse parent->rb_left = child; 4084b324126SWolfram Strepp 4094b324126SWolfram Strepp node->rb_right = old->rb_right; 4104b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 4114c601178SWolfram Strepp } 4121975e593SDavid Woodhouse 413bf7ad8eeSMichel Lespinasse node->__rb_parent_color = old->__rb_parent_color; 4141da177e4SLinus Torvalds node->rb_left = old->rb_left; 41555a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 4161da177e4SLinus Torvalds } 4171da177e4SLinus Torvalds 4181da177e4SLinus Torvalds if (color == RB_BLACK) 4191da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 4201da177e4SLinus Torvalds } 4211da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4221da177e4SLinus Torvalds 423b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 424b945d6b2SPeter Zijlstra { 425b945d6b2SPeter Zijlstra struct rb_node *parent; 426b945d6b2SPeter Zijlstra 427b945d6b2SPeter Zijlstra up: 428b945d6b2SPeter Zijlstra func(node, data); 429b945d6b2SPeter Zijlstra parent = rb_parent(node); 430b945d6b2SPeter Zijlstra if (!parent) 431b945d6b2SPeter Zijlstra return; 432b945d6b2SPeter Zijlstra 433b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 434b945d6b2SPeter Zijlstra func(parent->rb_right, data); 435b945d6b2SPeter Zijlstra else if (parent->rb_left) 436b945d6b2SPeter Zijlstra func(parent->rb_left, data); 437b945d6b2SPeter Zijlstra 438b945d6b2SPeter Zijlstra node = parent; 439b945d6b2SPeter Zijlstra goto up; 440b945d6b2SPeter Zijlstra } 441b945d6b2SPeter Zijlstra 442b945d6b2SPeter Zijlstra /* 443b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 444b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 445b945d6b2SPeter Zijlstra */ 446b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 447b945d6b2SPeter Zijlstra { 448b945d6b2SPeter Zijlstra if (node->rb_left) 449b945d6b2SPeter Zijlstra node = node->rb_left; 450b945d6b2SPeter Zijlstra else if (node->rb_right) 451b945d6b2SPeter Zijlstra node = node->rb_right; 452b945d6b2SPeter Zijlstra 453b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 454b945d6b2SPeter Zijlstra } 4550b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 456b945d6b2SPeter Zijlstra 457b945d6b2SPeter Zijlstra /* 458b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 459b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 460b945d6b2SPeter Zijlstra */ 461b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 462b945d6b2SPeter Zijlstra { 463b945d6b2SPeter Zijlstra struct rb_node *deepest; 464b945d6b2SPeter Zijlstra 465b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 466b945d6b2SPeter Zijlstra deepest = rb_parent(node); 467b945d6b2SPeter Zijlstra else if (!node->rb_right) 468b945d6b2SPeter Zijlstra deepest = node->rb_left; 469b945d6b2SPeter Zijlstra else if (!node->rb_left) 470b945d6b2SPeter Zijlstra deepest = node->rb_right; 471b945d6b2SPeter Zijlstra else { 472b945d6b2SPeter Zijlstra deepest = rb_next(node); 473b945d6b2SPeter Zijlstra if (deepest->rb_right) 474b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 475b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 476b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 477b945d6b2SPeter Zijlstra } 478b945d6b2SPeter Zijlstra 479b945d6b2SPeter Zijlstra return deepest; 480b945d6b2SPeter Zijlstra } 4810b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 482b945d6b2SPeter Zijlstra 483b945d6b2SPeter Zijlstra /* 484b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 485b945d6b2SPeter Zijlstra * and any rebalance damage. 486b945d6b2SPeter Zijlstra */ 487b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 488b945d6b2SPeter Zijlstra { 489b945d6b2SPeter Zijlstra if (node) 490b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 491b945d6b2SPeter Zijlstra } 4920b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 493b945d6b2SPeter Zijlstra 4941da177e4SLinus Torvalds /* 4951da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 4961da177e4SLinus Torvalds */ 497f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 4981da177e4SLinus Torvalds { 4991da177e4SLinus Torvalds struct rb_node *n; 5001da177e4SLinus Torvalds 5011da177e4SLinus Torvalds n = root->rb_node; 5021da177e4SLinus Torvalds if (!n) 5031da177e4SLinus Torvalds return NULL; 5041da177e4SLinus Torvalds while (n->rb_left) 5051da177e4SLinus Torvalds n = n->rb_left; 5061da177e4SLinus Torvalds return n; 5071da177e4SLinus Torvalds } 5081da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 5091da177e4SLinus Torvalds 510f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 5111da177e4SLinus Torvalds { 5121da177e4SLinus Torvalds struct rb_node *n; 5131da177e4SLinus Torvalds 5141da177e4SLinus Torvalds n = root->rb_node; 5151da177e4SLinus Torvalds if (!n) 5161da177e4SLinus Torvalds return NULL; 5171da177e4SLinus Torvalds while (n->rb_right) 5181da177e4SLinus Torvalds n = n->rb_right; 5191da177e4SLinus Torvalds return n; 5201da177e4SLinus Torvalds } 5211da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5221da177e4SLinus Torvalds 523f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5241da177e4SLinus Torvalds { 52555a98102SDavid Woodhouse struct rb_node *parent; 52655a98102SDavid Woodhouse 5274c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 52810fd48f2SJens Axboe return NULL; 52910fd48f2SJens Axboe 5307ce6ff9eSMichel Lespinasse /* 5317ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 5327ce6ff9eSMichel Lespinasse * as we can. 5337ce6ff9eSMichel Lespinasse */ 5341da177e4SLinus Torvalds if (node->rb_right) { 5351da177e4SLinus Torvalds node = node->rb_right; 5361da177e4SLinus Torvalds while (node->rb_left) 5371da177e4SLinus Torvalds node=node->rb_left; 538f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5391da177e4SLinus Torvalds } 5401da177e4SLinus Torvalds 5417ce6ff9eSMichel Lespinasse /* 5427ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 5437ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 5447ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 5457ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 5467ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 5477ce6ff9eSMichel Lespinasse */ 54855a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 54955a98102SDavid Woodhouse node = parent; 5501da177e4SLinus Torvalds 55155a98102SDavid Woodhouse return parent; 5521da177e4SLinus Torvalds } 5531da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 5541da177e4SLinus Torvalds 555f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 5561da177e4SLinus Torvalds { 55755a98102SDavid Woodhouse struct rb_node *parent; 55855a98102SDavid Woodhouse 5594c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 56010fd48f2SJens Axboe return NULL; 56110fd48f2SJens Axboe 5627ce6ff9eSMichel Lespinasse /* 5637ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 5647ce6ff9eSMichel Lespinasse * as we can. 5657ce6ff9eSMichel Lespinasse */ 5661da177e4SLinus Torvalds if (node->rb_left) { 5671da177e4SLinus Torvalds node = node->rb_left; 5681da177e4SLinus Torvalds while (node->rb_right) 5691da177e4SLinus Torvalds node=node->rb_right; 570f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5711da177e4SLinus Torvalds } 5721da177e4SLinus Torvalds 5737ce6ff9eSMichel Lespinasse /* 5747ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 5757ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 5767ce6ff9eSMichel Lespinasse */ 57755a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 57855a98102SDavid Woodhouse node = parent; 5791da177e4SLinus Torvalds 58055a98102SDavid Woodhouse return parent; 5811da177e4SLinus Torvalds } 5821da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 5831da177e4SLinus Torvalds 5841da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 5851da177e4SLinus Torvalds struct rb_root *root) 5861da177e4SLinus Torvalds { 58755a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 5881da177e4SLinus Torvalds 5891da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 5907abc704aSMichel Lespinasse __rb_change_child(victim, new, parent, root); 5911da177e4SLinus Torvalds if (victim->rb_left) 59255a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 5931da177e4SLinus Torvalds if (victim->rb_right) 59455a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 5951da177e4SLinus Torvalds 5961da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 5971da177e4SLinus Torvalds *new = *victim; 5981da177e4SLinus Torvalds } 5991da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 600