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 695bc9188aSMichel Lespinasse /* 705bc9188aSMichel Lespinasse * Helper function for rotations: 715bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 725bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 735bc9188aSMichel Lespinasse */ 745bc9188aSMichel Lespinasse static inline void 755bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 765bc9188aSMichel Lespinasse struct rb_root *root, int color) 775bc9188aSMichel Lespinasse { 785bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 795bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 805bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 815bc9188aSMichel Lespinasse if (parent) { 825bc9188aSMichel Lespinasse if (parent->rb_left == old) 835bc9188aSMichel Lespinasse parent->rb_left = new; 845bc9188aSMichel Lespinasse else 855bc9188aSMichel Lespinasse parent->rb_right = new; 865bc9188aSMichel Lespinasse } else 875bc9188aSMichel Lespinasse root->rb_node = new; 885bc9188aSMichel Lespinasse } 895bc9188aSMichel Lespinasse 901da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 911da177e4SLinus Torvalds { 925bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 931da177e4SLinus Torvalds 946d58452dSMichel Lespinasse while (true) { 956d58452dSMichel Lespinasse /* 966d58452dSMichel Lespinasse * Loop invariant: node is red 976d58452dSMichel Lespinasse * 986d58452dSMichel Lespinasse * If there is a black parent, we are done. 996d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 1006d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 1016d58452dSMichel Lespinasse */ 1026d58452dSMichel Lespinasse if (!parent) { 1035bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1046d58452dSMichel Lespinasse break; 1056d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 1066d58452dSMichel Lespinasse break; 1076d58452dSMichel Lespinasse 1085bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1091da177e4SLinus Torvalds 1105bc9188aSMichel Lespinasse tmp = gparent->rb_right; 111*59633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1125bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1135bc9188aSMichel Lespinasse /* 1145bc9188aSMichel Lespinasse * Case 1 - color flips 1155bc9188aSMichel Lespinasse * 1165bc9188aSMichel Lespinasse * G g 1175bc9188aSMichel Lespinasse * / \ / \ 1185bc9188aSMichel Lespinasse * p u --> P U 1195bc9188aSMichel Lespinasse * / / 1205bc9188aSMichel Lespinasse * n N 1215bc9188aSMichel Lespinasse * 1225bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1235bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1245bc9188aSMichel Lespinasse * at g. 1255bc9188aSMichel Lespinasse */ 1265bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1275bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1281da177e4SLinus Torvalds node = gparent; 1295bc9188aSMichel Lespinasse parent = rb_parent(node); 1305bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1311da177e4SLinus Torvalds continue; 1321da177e4SLinus Torvalds } 1331da177e4SLinus Torvalds 134*59633abfSMichel Lespinasse tmp = parent->rb_right; 135*59633abfSMichel Lespinasse if (node == tmp) { 1365bc9188aSMichel Lespinasse /* 1375bc9188aSMichel Lespinasse * Case 2 - left rotate at parent 1385bc9188aSMichel Lespinasse * 1395bc9188aSMichel Lespinasse * G G 1405bc9188aSMichel Lespinasse * / \ / \ 1415bc9188aSMichel Lespinasse * p U --> n U 1425bc9188aSMichel Lespinasse * \ / 1435bc9188aSMichel Lespinasse * n p 1445bc9188aSMichel Lespinasse * 1455bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1465bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1475bc9188aSMichel Lespinasse */ 1485bc9188aSMichel Lespinasse parent->rb_right = tmp = node->rb_left; 1495bc9188aSMichel Lespinasse node->rb_left = parent; 1505bc9188aSMichel Lespinasse if (tmp) 1515bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1525bc9188aSMichel Lespinasse RB_BLACK); 1535bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 1541da177e4SLinus Torvalds parent = node; 155*59633abfSMichel Lespinasse tmp = node->rb_right; 1561da177e4SLinus Torvalds } 1571da177e4SLinus Torvalds 1585bc9188aSMichel Lespinasse /* 1595bc9188aSMichel Lespinasse * Case 3 - right rotate at gparent 1605bc9188aSMichel Lespinasse * 1615bc9188aSMichel Lespinasse * G P 1625bc9188aSMichel Lespinasse * / \ / \ 1635bc9188aSMichel Lespinasse * p U --> n g 1645bc9188aSMichel Lespinasse * / \ 1655bc9188aSMichel Lespinasse * n U 1665bc9188aSMichel Lespinasse */ 167*59633abfSMichel Lespinasse gparent->rb_left = tmp; /* == parent->rb_right */ 1685bc9188aSMichel Lespinasse parent->rb_right = gparent; 1695bc9188aSMichel Lespinasse if (tmp) 1705bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1715bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1721f052865SMichel Lespinasse break; 1731da177e4SLinus Torvalds } else { 1745bc9188aSMichel Lespinasse tmp = gparent->rb_left; 1755bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1765bc9188aSMichel Lespinasse /* Case 1 - color flips */ 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 185*59633abfSMichel Lespinasse tmp = parent->rb_left; 186*59633abfSMichel Lespinasse if (node == tmp) { 1875bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 1885bc9188aSMichel Lespinasse parent->rb_left = tmp = node->rb_right; 1895bc9188aSMichel Lespinasse node->rb_right = parent; 1905bc9188aSMichel Lespinasse if (tmp) 1915bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1925bc9188aSMichel Lespinasse RB_BLACK); 1935bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 1941da177e4SLinus Torvalds parent = node; 195*59633abfSMichel Lespinasse tmp = node->rb_left; 1961da177e4SLinus Torvalds } 1971da177e4SLinus Torvalds 1985bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 199*59633abfSMichel Lespinasse gparent->rb_right = tmp; /* == parent->rb_left */ 2005bc9188aSMichel Lespinasse parent->rb_left = gparent; 2015bc9188aSMichel Lespinasse if (tmp) 2025bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2035bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2041f052865SMichel Lespinasse break; 2051da177e4SLinus Torvalds } 2061da177e4SLinus Torvalds } 2071da177e4SLinus Torvalds } 2081da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 2091da177e4SLinus Torvalds 2101da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 2111da177e4SLinus Torvalds struct rb_root *root) 2121da177e4SLinus Torvalds { 2136280d235SMichel Lespinasse struct rb_node *sibling, *tmp1, *tmp2; 2141da177e4SLinus Torvalds 215d6ff1273SMichel Lespinasse while (true) { 216d6ff1273SMichel Lespinasse /* 217d6ff1273SMichel Lespinasse * Loop invariant: all leaf paths going through node have a 218d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 219d6ff1273SMichel Lespinasse * 220d6ff1273SMichel Lespinasse * If node is red, we can flip it to black to adjust. 221d6ff1273SMichel Lespinasse * If node is the root, all leaf paths go through it. 222d6ff1273SMichel Lespinasse * Otherwise, we need to adjust the tree through color flips 223d6ff1273SMichel Lespinasse * and tree rotations as per one of the 4 cases below. 224d6ff1273SMichel Lespinasse */ 225d6ff1273SMichel Lespinasse if (node && rb_is_red(node)) { 2266280d235SMichel Lespinasse rb_set_parent_color(node, parent, RB_BLACK); 227d6ff1273SMichel Lespinasse break; 228d6ff1273SMichel Lespinasse } else if (!parent) { 229d6ff1273SMichel Lespinasse break; 230*59633abfSMichel Lespinasse } 2316280d235SMichel Lespinasse sibling = parent->rb_right; 232*59633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2336280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2346280d235SMichel Lespinasse /* 2356280d235SMichel Lespinasse * Case 1 - left rotate at parent 2366280d235SMichel Lespinasse * 2376280d235SMichel Lespinasse * P S 2386280d235SMichel Lespinasse * / \ / \ 2396280d235SMichel Lespinasse * N s --> p Sr 2406280d235SMichel Lespinasse * / \ / \ 2416280d235SMichel Lespinasse * Sl Sr N Sl 2426280d235SMichel Lespinasse */ 2436280d235SMichel Lespinasse parent->rb_right = tmp1 = sibling->rb_left; 2446280d235SMichel Lespinasse sibling->rb_left = parent; 2456280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2466280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2476280d235SMichel Lespinasse RB_RED); 2486280d235SMichel Lespinasse sibling = tmp1; 2491da177e4SLinus Torvalds } 2506280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2516280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2526280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2536280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2546280d235SMichel Lespinasse /* 2556280d235SMichel Lespinasse * Case 2 - sibling color flip 2566280d235SMichel Lespinasse * (p could be either color here) 2576280d235SMichel Lespinasse * 2586280d235SMichel Lespinasse * (p) (p) 2596280d235SMichel Lespinasse * / \ / \ 2606280d235SMichel Lespinasse * N S --> N s 2616280d235SMichel Lespinasse * / \ / \ 2626280d235SMichel Lespinasse * Sl Sr Sl Sr 2636280d235SMichel Lespinasse * 2646280d235SMichel Lespinasse * This leaves us violating 5), so 2656280d235SMichel Lespinasse * recurse at p. If p is red, the 2666280d235SMichel Lespinasse * recursion will just flip it to black 2676280d235SMichel Lespinasse * and exit. If coming from Case 1, 2686280d235SMichel Lespinasse * p is known to be red. 2696280d235SMichel Lespinasse */ 2706280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2716280d235SMichel Lespinasse RB_RED); 2721da177e4SLinus Torvalds node = parent; 27355a98102SDavid Woodhouse parent = rb_parent(node); 274e125d147SMichel Lespinasse continue; 2751da177e4SLinus Torvalds } 2766280d235SMichel Lespinasse /* 2776280d235SMichel Lespinasse * Case 3 - right rotate at sibling 2786280d235SMichel Lespinasse * (p could be either color here) 2796280d235SMichel Lespinasse * 2806280d235SMichel Lespinasse * (p) (p) 2816280d235SMichel Lespinasse * / \ / \ 2826280d235SMichel Lespinasse * N S --> N Sl 2836280d235SMichel Lespinasse * / \ \ 2846280d235SMichel Lespinasse * sl Sr s 2856280d235SMichel Lespinasse * \ 2866280d235SMichel Lespinasse * Sr 2876280d235SMichel Lespinasse */ 2886280d235SMichel Lespinasse sibling->rb_left = tmp1 = tmp2->rb_right; 2896280d235SMichel Lespinasse tmp2->rb_right = sibling; 2906280d235SMichel Lespinasse parent->rb_right = tmp2; 2916280d235SMichel Lespinasse if (tmp1) 2926280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 2936280d235SMichel Lespinasse RB_BLACK); 2946280d235SMichel Lespinasse tmp1 = sibling; 2956280d235SMichel Lespinasse sibling = tmp2; 2961da177e4SLinus Torvalds } 2976280d235SMichel Lespinasse /* 2986280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 2996280d235SMichel Lespinasse * (p and sl could be either color here. 3006280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3016280d235SMichel Lespinasse * p's color, and sl keeps its color) 3026280d235SMichel Lespinasse * 3036280d235SMichel Lespinasse * (p) (s) 3046280d235SMichel Lespinasse * / \ / \ 3056280d235SMichel Lespinasse * N S --> P Sr 3066280d235SMichel Lespinasse * / \ / \ 3076280d235SMichel Lespinasse * (sl) sr N (sl) 3086280d235SMichel Lespinasse */ 3096280d235SMichel Lespinasse parent->rb_right = tmp2 = sibling->rb_left; 3106280d235SMichel Lespinasse sibling->rb_left = parent; 3116280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3126280d235SMichel Lespinasse if (tmp2) 3136280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3146280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3156280d235SMichel Lespinasse RB_BLACK); 3161da177e4SLinus Torvalds break; 317d6ff1273SMichel Lespinasse } else { 3186280d235SMichel Lespinasse sibling = parent->rb_left; 3196280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3206280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 3216280d235SMichel Lespinasse parent->rb_left = tmp1 = sibling->rb_right; 3226280d235SMichel Lespinasse sibling->rb_right = parent; 3236280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3246280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3256280d235SMichel Lespinasse RB_RED); 3266280d235SMichel Lespinasse sibling = tmp1; 3271da177e4SLinus Torvalds } 3286280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3296280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3306280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3316280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3326280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3336280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3346280d235SMichel Lespinasse RB_RED); 3351da177e4SLinus Torvalds node = parent; 33655a98102SDavid Woodhouse parent = rb_parent(node); 337e125d147SMichel Lespinasse continue; 3381da177e4SLinus Torvalds } 3396280d235SMichel Lespinasse /* Case 3 - right rotate at sibling */ 3406280d235SMichel Lespinasse sibling->rb_right = tmp1 = tmp2->rb_left; 3416280d235SMichel Lespinasse tmp2->rb_left = sibling; 3426280d235SMichel Lespinasse parent->rb_left = tmp2; 3436280d235SMichel Lespinasse if (tmp1) 3446280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3456280d235SMichel Lespinasse RB_BLACK); 3466280d235SMichel Lespinasse tmp1 = sibling; 3476280d235SMichel Lespinasse sibling = tmp2; 3481da177e4SLinus Torvalds } 3496280d235SMichel Lespinasse /* Case 4 - left rotate at parent + color flips */ 3506280d235SMichel Lespinasse parent->rb_left = tmp2 = sibling->rb_right; 3516280d235SMichel Lespinasse sibling->rb_right = parent; 3526280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3536280d235SMichel Lespinasse if (tmp2) 3546280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3556280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3566280d235SMichel Lespinasse RB_BLACK); 3571da177e4SLinus Torvalds break; 3581da177e4SLinus Torvalds } 3591da177e4SLinus Torvalds } 3601da177e4SLinus Torvalds } 3611da177e4SLinus Torvalds 3621da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 3631da177e4SLinus Torvalds { 3641da177e4SLinus Torvalds struct rb_node *child, *parent; 3651da177e4SLinus Torvalds int color; 3661da177e4SLinus Torvalds 3671da177e4SLinus Torvalds if (!node->rb_left) 3681da177e4SLinus Torvalds child = node->rb_right; 3691da177e4SLinus Torvalds else if (!node->rb_right) 3701da177e4SLinus Torvalds child = node->rb_left; 3717ce6ff9eSMichel Lespinasse else { 3721da177e4SLinus Torvalds struct rb_node *old = node, *left; 3731da177e4SLinus Torvalds 3741da177e4SLinus Torvalds node = node->rb_right; 3751da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 3761da177e4SLinus Torvalds node = left; 37716c047adSWolfram Strepp 37816c047adSWolfram Strepp if (rb_parent(old)) { 37916c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 38016c047adSWolfram Strepp rb_parent(old)->rb_left = node; 38116c047adSWolfram Strepp else 38216c047adSWolfram Strepp rb_parent(old)->rb_right = node; 38316c047adSWolfram Strepp } else 38416c047adSWolfram Strepp root->rb_node = node; 38516c047adSWolfram Strepp 3861da177e4SLinus Torvalds child = node->rb_right; 38755a98102SDavid Woodhouse parent = rb_parent(node); 3882f3243aeSDavid Woodhouse color = rb_color(node); 3891da177e4SLinus Torvalds 3904c601178SWolfram Strepp if (parent == old) { 3914c601178SWolfram Strepp parent = node; 3924c601178SWolfram Strepp } else { 3931da177e4SLinus Torvalds if (child) 39455a98102SDavid Woodhouse rb_set_parent(child, parent); 3951975e593SDavid Woodhouse parent->rb_left = child; 3964b324126SWolfram Strepp 3974b324126SWolfram Strepp node->rb_right = old->rb_right; 3984b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 3994c601178SWolfram Strepp } 4001975e593SDavid Woodhouse 401bf7ad8eeSMichel Lespinasse node->__rb_parent_color = old->__rb_parent_color; 4021da177e4SLinus Torvalds node->rb_left = old->rb_left; 40355a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 4044b324126SWolfram Strepp 4051da177e4SLinus Torvalds goto color; 4061da177e4SLinus Torvalds } 4071da177e4SLinus Torvalds 40855a98102SDavid Woodhouse parent = rb_parent(node); 4092f3243aeSDavid Woodhouse color = rb_color(node); 4101da177e4SLinus Torvalds 4111da177e4SLinus Torvalds if (child) 41255a98102SDavid Woodhouse rb_set_parent(child, parent); 4137ce6ff9eSMichel Lespinasse if (parent) { 4141da177e4SLinus Torvalds if (parent->rb_left == node) 4151da177e4SLinus Torvalds parent->rb_left = child; 4161da177e4SLinus Torvalds else 4171da177e4SLinus Torvalds parent->rb_right = child; 4187ce6ff9eSMichel Lespinasse } else 419b945d6b2SPeter Zijlstra root->rb_node = child; 4201da177e4SLinus Torvalds 4211da177e4SLinus Torvalds color: 4221da177e4SLinus Torvalds if (color == RB_BLACK) 4231da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 4241da177e4SLinus Torvalds } 4251da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4261da177e4SLinus Torvalds 427b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 428b945d6b2SPeter Zijlstra { 429b945d6b2SPeter Zijlstra struct rb_node *parent; 430b945d6b2SPeter Zijlstra 431b945d6b2SPeter Zijlstra up: 432b945d6b2SPeter Zijlstra func(node, data); 433b945d6b2SPeter Zijlstra parent = rb_parent(node); 434b945d6b2SPeter Zijlstra if (!parent) 435b945d6b2SPeter Zijlstra return; 436b945d6b2SPeter Zijlstra 437b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 438b945d6b2SPeter Zijlstra func(parent->rb_right, data); 439b945d6b2SPeter Zijlstra else if (parent->rb_left) 440b945d6b2SPeter Zijlstra func(parent->rb_left, data); 441b945d6b2SPeter Zijlstra 442b945d6b2SPeter Zijlstra node = parent; 443b945d6b2SPeter Zijlstra goto up; 444b945d6b2SPeter Zijlstra } 445b945d6b2SPeter Zijlstra 446b945d6b2SPeter Zijlstra /* 447b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 448b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 449b945d6b2SPeter Zijlstra */ 450b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 451b945d6b2SPeter Zijlstra { 452b945d6b2SPeter Zijlstra if (node->rb_left) 453b945d6b2SPeter Zijlstra node = node->rb_left; 454b945d6b2SPeter Zijlstra else if (node->rb_right) 455b945d6b2SPeter Zijlstra node = node->rb_right; 456b945d6b2SPeter Zijlstra 457b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 458b945d6b2SPeter Zijlstra } 4590b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 460b945d6b2SPeter Zijlstra 461b945d6b2SPeter Zijlstra /* 462b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 463b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 464b945d6b2SPeter Zijlstra */ 465b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 466b945d6b2SPeter Zijlstra { 467b945d6b2SPeter Zijlstra struct rb_node *deepest; 468b945d6b2SPeter Zijlstra 469b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 470b945d6b2SPeter Zijlstra deepest = rb_parent(node); 471b945d6b2SPeter Zijlstra else if (!node->rb_right) 472b945d6b2SPeter Zijlstra deepest = node->rb_left; 473b945d6b2SPeter Zijlstra else if (!node->rb_left) 474b945d6b2SPeter Zijlstra deepest = node->rb_right; 475b945d6b2SPeter Zijlstra else { 476b945d6b2SPeter Zijlstra deepest = rb_next(node); 477b945d6b2SPeter Zijlstra if (deepest->rb_right) 478b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 479b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 480b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 481b945d6b2SPeter Zijlstra } 482b945d6b2SPeter Zijlstra 483b945d6b2SPeter Zijlstra return deepest; 484b945d6b2SPeter Zijlstra } 4850b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 486b945d6b2SPeter Zijlstra 487b945d6b2SPeter Zijlstra /* 488b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 489b945d6b2SPeter Zijlstra * and any rebalance damage. 490b945d6b2SPeter Zijlstra */ 491b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 492b945d6b2SPeter Zijlstra { 493b945d6b2SPeter Zijlstra if (node) 494b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 495b945d6b2SPeter Zijlstra } 4960b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 497b945d6b2SPeter Zijlstra 4981da177e4SLinus Torvalds /* 4991da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 5001da177e4SLinus Torvalds */ 501f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 5021da177e4SLinus Torvalds { 5031da177e4SLinus Torvalds struct rb_node *n; 5041da177e4SLinus Torvalds 5051da177e4SLinus Torvalds n = root->rb_node; 5061da177e4SLinus Torvalds if (!n) 5071da177e4SLinus Torvalds return NULL; 5081da177e4SLinus Torvalds while (n->rb_left) 5091da177e4SLinus Torvalds n = n->rb_left; 5101da177e4SLinus Torvalds return n; 5111da177e4SLinus Torvalds } 5121da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 5131da177e4SLinus Torvalds 514f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 5151da177e4SLinus Torvalds { 5161da177e4SLinus Torvalds struct rb_node *n; 5171da177e4SLinus Torvalds 5181da177e4SLinus Torvalds n = root->rb_node; 5191da177e4SLinus Torvalds if (!n) 5201da177e4SLinus Torvalds return NULL; 5211da177e4SLinus Torvalds while (n->rb_right) 5221da177e4SLinus Torvalds n = n->rb_right; 5231da177e4SLinus Torvalds return n; 5241da177e4SLinus Torvalds } 5251da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5261da177e4SLinus Torvalds 527f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5281da177e4SLinus Torvalds { 52955a98102SDavid Woodhouse struct rb_node *parent; 53055a98102SDavid Woodhouse 5314c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 53210fd48f2SJens Axboe return NULL; 53310fd48f2SJens Axboe 5347ce6ff9eSMichel Lespinasse /* 5357ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 5367ce6ff9eSMichel Lespinasse * as we can. 5377ce6ff9eSMichel Lespinasse */ 5381da177e4SLinus Torvalds if (node->rb_right) { 5391da177e4SLinus Torvalds node = node->rb_right; 5401da177e4SLinus Torvalds while (node->rb_left) 5411da177e4SLinus Torvalds node=node->rb_left; 542f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5431da177e4SLinus Torvalds } 5441da177e4SLinus Torvalds 5457ce6ff9eSMichel Lespinasse /* 5467ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 5477ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 5487ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 5497ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 5507ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 5517ce6ff9eSMichel Lespinasse */ 55255a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 55355a98102SDavid Woodhouse node = parent; 5541da177e4SLinus Torvalds 55555a98102SDavid Woodhouse return parent; 5561da177e4SLinus Torvalds } 5571da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 5581da177e4SLinus Torvalds 559f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 5601da177e4SLinus Torvalds { 56155a98102SDavid Woodhouse struct rb_node *parent; 56255a98102SDavid Woodhouse 5634c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 56410fd48f2SJens Axboe return NULL; 56510fd48f2SJens Axboe 5667ce6ff9eSMichel Lespinasse /* 5677ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 5687ce6ff9eSMichel Lespinasse * as we can. 5697ce6ff9eSMichel Lespinasse */ 5701da177e4SLinus Torvalds if (node->rb_left) { 5711da177e4SLinus Torvalds node = node->rb_left; 5721da177e4SLinus Torvalds while (node->rb_right) 5731da177e4SLinus Torvalds node=node->rb_right; 574f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5751da177e4SLinus Torvalds } 5761da177e4SLinus Torvalds 5777ce6ff9eSMichel Lespinasse /* 5787ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 5797ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 5807ce6ff9eSMichel Lespinasse */ 58155a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 58255a98102SDavid Woodhouse node = parent; 5831da177e4SLinus Torvalds 58455a98102SDavid Woodhouse return parent; 5851da177e4SLinus Torvalds } 5861da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 5871da177e4SLinus Torvalds 5881da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 5891da177e4SLinus Torvalds struct rb_root *root) 5901da177e4SLinus Torvalds { 59155a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 5921da177e4SLinus Torvalds 5931da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 5941da177e4SLinus Torvalds if (parent) { 5951da177e4SLinus Torvalds if (victim == parent->rb_left) 5961da177e4SLinus Torvalds parent->rb_left = new; 5971da177e4SLinus Torvalds else 5981da177e4SLinus Torvalds parent->rb_right = new; 5991da177e4SLinus Torvalds } else { 6001da177e4SLinus Torvalds root->rb_node = new; 6011da177e4SLinus Torvalds } 6021da177e4SLinus Torvalds if (victim->rb_left) 60355a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 6041da177e4SLinus Torvalds if (victim->rb_right) 60555a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 6061da177e4SLinus Torvalds 6071da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 6081da177e4SLinus Torvalds *new = *victim; 6091da177e4SLinus Torvalds } 6101da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 611