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> 546b6135aSMichel Lespinasse (C) 2012 Michel Lespinasse <walken@google.com> 61da177e4SLinus Torvalds 71da177e4SLinus Torvalds This program is free software; you can redistribute it and/or modify 81da177e4SLinus Torvalds it under the terms of the GNU General Public License as published by 91da177e4SLinus Torvalds the Free Software Foundation; either version 2 of the License, or 101da177e4SLinus Torvalds (at your option) any later version. 111da177e4SLinus Torvalds 121da177e4SLinus Torvalds This program is distributed in the hope that it will be useful, 131da177e4SLinus Torvalds but WITHOUT ANY WARRANTY; without even the implied warranty of 141da177e4SLinus Torvalds MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 151da177e4SLinus Torvalds GNU General Public License for more details. 161da177e4SLinus Torvalds 171da177e4SLinus Torvalds You should have received a copy of the GNU General Public License 181da177e4SLinus Torvalds along with this program; if not, write to the Free Software 191da177e4SLinus Torvalds Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 201da177e4SLinus Torvalds 211da177e4SLinus Torvalds linux/lib/rbtree.c 221da177e4SLinus Torvalds */ 231da177e4SLinus Torvalds 241da177e4SLinus Torvalds #include <linux/rbtree.h> 258bc3bcc9SPaul Gortmaker #include <linux/export.h> 261da177e4SLinus Torvalds 275bc9188aSMichel Lespinasse /* 285bc9188aSMichel Lespinasse * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree 295bc9188aSMichel Lespinasse * 305bc9188aSMichel Lespinasse * 1) A node is either red or black 315bc9188aSMichel Lespinasse * 2) The root is black 325bc9188aSMichel Lespinasse * 3) All leaves (NULL) are black 335bc9188aSMichel Lespinasse * 4) Both children of every red node are black 345bc9188aSMichel Lespinasse * 5) Every simple path from root to leaves contains the same number 355bc9188aSMichel Lespinasse * of black nodes. 365bc9188aSMichel Lespinasse * 375bc9188aSMichel Lespinasse * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two 385bc9188aSMichel Lespinasse * consecutive red nodes in a path and every red node is therefore followed by 395bc9188aSMichel Lespinasse * a black. So if B is the number of black nodes on every simple path (as per 405bc9188aSMichel Lespinasse * 5), then the longest possible path due to 4 is 2B. 415bc9188aSMichel Lespinasse * 425bc9188aSMichel Lespinasse * We shall indicate color with case, where black nodes are uppercase and red 436280d235SMichel Lespinasse * nodes will be lowercase. Unknown color nodes shall be drawn as red within 446280d235SMichel Lespinasse * parentheses and have some accompanying text comment. 455bc9188aSMichel Lespinasse */ 465bc9188aSMichel Lespinasse 47bf7ad8eeSMichel Lespinasse #define RB_RED 0 48bf7ad8eeSMichel Lespinasse #define RB_BLACK 1 49bf7ad8eeSMichel Lespinasse 50*4f035ad6SMichel Lespinasse #define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) 51*4f035ad6SMichel Lespinasse 52*4f035ad6SMichel Lespinasse #define __rb_color(pc) ((pc) & 1) 53*4f035ad6SMichel Lespinasse #define __rb_is_black(pc) __rb_color(pc) 54*4f035ad6SMichel Lespinasse #define __rb_is_red(pc) (!__rb_color(pc)) 55*4f035ad6SMichel Lespinasse #define rb_color(rb) __rb_color((rb)->__rb_parent_color) 56*4f035ad6SMichel Lespinasse #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) 57*4f035ad6SMichel Lespinasse #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) 58bf7ad8eeSMichel Lespinasse 5946b6135aSMichel Lespinasse static inline void rb_set_black(struct rb_node *rb) 6046b6135aSMichel Lespinasse { 6146b6135aSMichel Lespinasse rb->__rb_parent_color |= RB_BLACK; 6246b6135aSMichel Lespinasse } 6346b6135aSMichel Lespinasse 64bf7ad8eeSMichel Lespinasse static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 65bf7ad8eeSMichel Lespinasse { 66bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 67bf7ad8eeSMichel Lespinasse } 68bf7ad8eeSMichel Lespinasse 695bc9188aSMichel Lespinasse static inline void rb_set_parent_color(struct rb_node *rb, 705bc9188aSMichel Lespinasse struct rb_node *p, int color) 715bc9188aSMichel Lespinasse { 725bc9188aSMichel Lespinasse rb->__rb_parent_color = (unsigned long)p | color; 735bc9188aSMichel Lespinasse } 745bc9188aSMichel Lespinasse 755bc9188aSMichel Lespinasse static inline struct rb_node *rb_red_parent(struct rb_node *red) 765bc9188aSMichel Lespinasse { 775bc9188aSMichel Lespinasse return (struct rb_node *)red->__rb_parent_color; 785bc9188aSMichel Lespinasse } 795bc9188aSMichel Lespinasse 807abc704aSMichel Lespinasse static inline void 817abc704aSMichel Lespinasse __rb_change_child(struct rb_node *old, struct rb_node *new, 827abc704aSMichel Lespinasse struct rb_node *parent, struct rb_root *root) 837abc704aSMichel Lespinasse { 847abc704aSMichel Lespinasse if (parent) { 857abc704aSMichel Lespinasse if (parent->rb_left == old) 867abc704aSMichel Lespinasse parent->rb_left = new; 877abc704aSMichel Lespinasse else 887abc704aSMichel Lespinasse parent->rb_right = new; 897abc704aSMichel Lespinasse } else 907abc704aSMichel Lespinasse root->rb_node = new; 917abc704aSMichel Lespinasse } 927abc704aSMichel Lespinasse 935bc9188aSMichel Lespinasse /* 945bc9188aSMichel Lespinasse * Helper function for rotations: 955bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 965bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 975bc9188aSMichel Lespinasse */ 985bc9188aSMichel Lespinasse static inline void 995bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 1005bc9188aSMichel Lespinasse struct rb_root *root, int color) 1015bc9188aSMichel Lespinasse { 1025bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 1035bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 1045bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 1057abc704aSMichel Lespinasse __rb_change_child(old, new, parent, root); 1065bc9188aSMichel Lespinasse } 1075bc9188aSMichel Lespinasse 1081da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 1091da177e4SLinus Torvalds { 1105bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 1111da177e4SLinus Torvalds 1126d58452dSMichel Lespinasse while (true) { 1136d58452dSMichel Lespinasse /* 1146d58452dSMichel Lespinasse * Loop invariant: node is red 1156d58452dSMichel Lespinasse * 1166d58452dSMichel Lespinasse * If there is a black parent, we are done. 1176d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 1186d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 1196d58452dSMichel Lespinasse */ 1206d58452dSMichel Lespinasse if (!parent) { 1215bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1226d58452dSMichel Lespinasse break; 1236d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 1246d58452dSMichel Lespinasse break; 1256d58452dSMichel Lespinasse 1265bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1271da177e4SLinus Torvalds 1285bc9188aSMichel Lespinasse tmp = gparent->rb_right; 12959633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1305bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1315bc9188aSMichel Lespinasse /* 1325bc9188aSMichel Lespinasse * Case 1 - color flips 1335bc9188aSMichel Lespinasse * 1345bc9188aSMichel Lespinasse * G g 1355bc9188aSMichel Lespinasse * / \ / \ 1365bc9188aSMichel Lespinasse * p u --> P U 1375bc9188aSMichel Lespinasse * / / 1385bc9188aSMichel Lespinasse * n N 1395bc9188aSMichel Lespinasse * 1405bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1415bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1425bc9188aSMichel Lespinasse * at g. 1435bc9188aSMichel Lespinasse */ 1445bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1455bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1461da177e4SLinus Torvalds node = gparent; 1475bc9188aSMichel Lespinasse parent = rb_parent(node); 1485bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1491da177e4SLinus Torvalds continue; 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds 15259633abfSMichel Lespinasse tmp = parent->rb_right; 15359633abfSMichel Lespinasse if (node == tmp) { 1545bc9188aSMichel Lespinasse /* 1555bc9188aSMichel Lespinasse * Case 2 - left rotate at parent 1565bc9188aSMichel Lespinasse * 1575bc9188aSMichel Lespinasse * G G 1585bc9188aSMichel Lespinasse * / \ / \ 1595bc9188aSMichel Lespinasse * p U --> n U 1605bc9188aSMichel Lespinasse * \ / 1615bc9188aSMichel Lespinasse * n p 1625bc9188aSMichel Lespinasse * 1635bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1645bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1655bc9188aSMichel Lespinasse */ 1665bc9188aSMichel Lespinasse parent->rb_right = tmp = node->rb_left; 1675bc9188aSMichel Lespinasse node->rb_left = parent; 1685bc9188aSMichel Lespinasse if (tmp) 1695bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1705bc9188aSMichel Lespinasse RB_BLACK); 1715bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 1721da177e4SLinus Torvalds parent = node; 17359633abfSMichel Lespinasse tmp = node->rb_right; 1741da177e4SLinus Torvalds } 1751da177e4SLinus Torvalds 1765bc9188aSMichel Lespinasse /* 1775bc9188aSMichel Lespinasse * Case 3 - right rotate at gparent 1785bc9188aSMichel Lespinasse * 1795bc9188aSMichel Lespinasse * G P 1805bc9188aSMichel Lespinasse * / \ / \ 1815bc9188aSMichel Lespinasse * p U --> n g 1825bc9188aSMichel Lespinasse * / \ 1835bc9188aSMichel Lespinasse * n U 1845bc9188aSMichel Lespinasse */ 18559633abfSMichel Lespinasse gparent->rb_left = tmp; /* == parent->rb_right */ 1865bc9188aSMichel Lespinasse parent->rb_right = gparent; 1875bc9188aSMichel Lespinasse if (tmp) 1885bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1895bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1901f052865SMichel Lespinasse break; 1911da177e4SLinus Torvalds } else { 1925bc9188aSMichel Lespinasse tmp = gparent->rb_left; 1935bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1945bc9188aSMichel Lespinasse /* Case 1 - color flips */ 1955bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1965bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1971da177e4SLinus Torvalds node = gparent; 1985bc9188aSMichel Lespinasse parent = rb_parent(node); 1995bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 2001da177e4SLinus Torvalds continue; 2011da177e4SLinus Torvalds } 2021da177e4SLinus Torvalds 20359633abfSMichel Lespinasse tmp = parent->rb_left; 20459633abfSMichel Lespinasse if (node == tmp) { 2055bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 2065bc9188aSMichel Lespinasse parent->rb_left = tmp = node->rb_right; 2075bc9188aSMichel Lespinasse node->rb_right = parent; 2085bc9188aSMichel Lespinasse if (tmp) 2095bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2105bc9188aSMichel Lespinasse RB_BLACK); 2115bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 2121da177e4SLinus Torvalds parent = node; 21359633abfSMichel Lespinasse tmp = node->rb_left; 2141da177e4SLinus Torvalds } 2151da177e4SLinus Torvalds 2165bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 21759633abfSMichel Lespinasse gparent->rb_right = tmp; /* == parent->rb_left */ 2185bc9188aSMichel Lespinasse parent->rb_left = gparent; 2195bc9188aSMichel Lespinasse if (tmp) 2205bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2215bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2221f052865SMichel Lespinasse break; 2231da177e4SLinus Torvalds } 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds } 2261da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 2271da177e4SLinus Torvalds 22846b6135aSMichel Lespinasse static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) 2291da177e4SLinus Torvalds { 23046b6135aSMichel Lespinasse struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 2311da177e4SLinus Torvalds 232d6ff1273SMichel Lespinasse while (true) { 233d6ff1273SMichel Lespinasse /* 23446b6135aSMichel Lespinasse * Loop invariants: 23546b6135aSMichel Lespinasse * - node is black (or NULL on first iteration) 23646b6135aSMichel Lespinasse * - node is not the root (parent is not NULL) 23746b6135aSMichel Lespinasse * - All leaf paths going through parent and node have a 238d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 239d6ff1273SMichel Lespinasse */ 2406280d235SMichel Lespinasse sibling = parent->rb_right; 24159633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2426280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2436280d235SMichel Lespinasse /* 2446280d235SMichel Lespinasse * Case 1 - left rotate at parent 2456280d235SMichel Lespinasse * 2466280d235SMichel Lespinasse * P S 2476280d235SMichel Lespinasse * / \ / \ 2486280d235SMichel Lespinasse * N s --> p Sr 2496280d235SMichel Lespinasse * / \ / \ 2506280d235SMichel Lespinasse * Sl Sr N Sl 2516280d235SMichel Lespinasse */ 2526280d235SMichel Lespinasse parent->rb_right = tmp1 = sibling->rb_left; 2536280d235SMichel Lespinasse sibling->rb_left = parent; 2546280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2556280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2566280d235SMichel Lespinasse RB_RED); 2576280d235SMichel Lespinasse sibling = tmp1; 2581da177e4SLinus Torvalds } 2596280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2606280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2616280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2626280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2636280d235SMichel Lespinasse /* 2646280d235SMichel Lespinasse * Case 2 - sibling color flip 2656280d235SMichel Lespinasse * (p could be either color here) 2666280d235SMichel Lespinasse * 2676280d235SMichel Lespinasse * (p) (p) 2686280d235SMichel Lespinasse * / \ / \ 2696280d235SMichel Lespinasse * N S --> N s 2706280d235SMichel Lespinasse * / \ / \ 2716280d235SMichel Lespinasse * Sl Sr Sl Sr 2726280d235SMichel Lespinasse * 27346b6135aSMichel Lespinasse * This leaves us violating 5) which 27446b6135aSMichel Lespinasse * can be fixed by flipping p to black 27546b6135aSMichel Lespinasse * if it was red, or by recursing at p. 27646b6135aSMichel Lespinasse * p is red when coming from Case 1. 2776280d235SMichel Lespinasse */ 2786280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2796280d235SMichel Lespinasse RB_RED); 28046b6135aSMichel Lespinasse if (rb_is_red(parent)) 28146b6135aSMichel Lespinasse rb_set_black(parent); 28246b6135aSMichel Lespinasse else { 2831da177e4SLinus Torvalds node = parent; 28455a98102SDavid Woodhouse parent = rb_parent(node); 28546b6135aSMichel Lespinasse if (parent) 286e125d147SMichel Lespinasse continue; 2871da177e4SLinus Torvalds } 28846b6135aSMichel Lespinasse break; 28946b6135aSMichel Lespinasse } 2906280d235SMichel Lespinasse /* 2916280d235SMichel Lespinasse * Case 3 - right rotate at sibling 2926280d235SMichel Lespinasse * (p could be either color here) 2936280d235SMichel Lespinasse * 2946280d235SMichel Lespinasse * (p) (p) 2956280d235SMichel Lespinasse * / \ / \ 2966280d235SMichel Lespinasse * N S --> N Sl 2976280d235SMichel Lespinasse * / \ \ 2986280d235SMichel Lespinasse * sl Sr s 2996280d235SMichel Lespinasse * \ 3006280d235SMichel Lespinasse * Sr 3016280d235SMichel Lespinasse */ 3026280d235SMichel Lespinasse sibling->rb_left = tmp1 = tmp2->rb_right; 3036280d235SMichel Lespinasse tmp2->rb_right = sibling; 3046280d235SMichel Lespinasse parent->rb_right = tmp2; 3056280d235SMichel Lespinasse if (tmp1) 3066280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3076280d235SMichel Lespinasse RB_BLACK); 3086280d235SMichel Lespinasse tmp1 = sibling; 3096280d235SMichel Lespinasse sibling = tmp2; 3101da177e4SLinus Torvalds } 3116280d235SMichel Lespinasse /* 3126280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 3136280d235SMichel Lespinasse * (p and sl could be either color here. 3146280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3156280d235SMichel Lespinasse * p's color, and sl keeps its color) 3166280d235SMichel Lespinasse * 3176280d235SMichel Lespinasse * (p) (s) 3186280d235SMichel Lespinasse * / \ / \ 3196280d235SMichel Lespinasse * N S --> P Sr 3206280d235SMichel Lespinasse * / \ / \ 3216280d235SMichel Lespinasse * (sl) sr N (sl) 3226280d235SMichel Lespinasse */ 3236280d235SMichel Lespinasse parent->rb_right = tmp2 = sibling->rb_left; 3246280d235SMichel Lespinasse sibling->rb_left = parent; 3256280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3266280d235SMichel Lespinasse if (tmp2) 3276280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3286280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3296280d235SMichel Lespinasse RB_BLACK); 3301da177e4SLinus Torvalds break; 331d6ff1273SMichel Lespinasse } else { 3326280d235SMichel Lespinasse sibling = parent->rb_left; 3336280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3346280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 3356280d235SMichel Lespinasse parent->rb_left = tmp1 = sibling->rb_right; 3366280d235SMichel Lespinasse sibling->rb_right = parent; 3376280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3386280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3396280d235SMichel Lespinasse RB_RED); 3406280d235SMichel Lespinasse sibling = tmp1; 3411da177e4SLinus Torvalds } 3426280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3436280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3446280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3456280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3466280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3476280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3486280d235SMichel Lespinasse RB_RED); 34946b6135aSMichel Lespinasse if (rb_is_red(parent)) 35046b6135aSMichel Lespinasse rb_set_black(parent); 35146b6135aSMichel Lespinasse else { 3521da177e4SLinus Torvalds node = parent; 35355a98102SDavid Woodhouse parent = rb_parent(node); 35446b6135aSMichel Lespinasse if (parent) 355e125d147SMichel Lespinasse continue; 3561da177e4SLinus Torvalds } 35746b6135aSMichel Lespinasse break; 35846b6135aSMichel Lespinasse } 3596280d235SMichel Lespinasse /* Case 3 - right rotate at sibling */ 3606280d235SMichel Lespinasse sibling->rb_right = tmp1 = tmp2->rb_left; 3616280d235SMichel Lespinasse tmp2->rb_left = sibling; 3626280d235SMichel Lespinasse parent->rb_left = tmp2; 3636280d235SMichel Lespinasse if (tmp1) 3646280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3656280d235SMichel Lespinasse RB_BLACK); 3666280d235SMichel Lespinasse tmp1 = sibling; 3676280d235SMichel Lespinasse sibling = tmp2; 3681da177e4SLinus Torvalds } 3696280d235SMichel Lespinasse /* Case 4 - left rotate at parent + color flips */ 3706280d235SMichel Lespinasse parent->rb_left = tmp2 = sibling->rb_right; 3716280d235SMichel Lespinasse sibling->rb_right = parent; 3726280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3736280d235SMichel Lespinasse if (tmp2) 3746280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3756280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3766280d235SMichel Lespinasse RB_BLACK); 3771da177e4SLinus Torvalds break; 3781da177e4SLinus Torvalds } 3791da177e4SLinus Torvalds } 3801da177e4SLinus Torvalds } 3811da177e4SLinus Torvalds 3821da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 3831da177e4SLinus Torvalds { 38460670b80SMichel Lespinasse struct rb_node *child = node->rb_right, *tmp = node->rb_left; 38546b6135aSMichel Lespinasse struct rb_node *parent, *rebalance; 386*4f035ad6SMichel Lespinasse unsigned long pc; 3871da177e4SLinus Torvalds 38860670b80SMichel Lespinasse if (!tmp) { 38946b6135aSMichel Lespinasse /* 39046b6135aSMichel Lespinasse * Case 1: node to erase has no more than 1 child (easy!) 39146b6135aSMichel Lespinasse * 39246b6135aSMichel Lespinasse * Note that if there is one child it must be red due to 5) 39346b6135aSMichel Lespinasse * and node must be black due to 4). We adjust colors locally 39446b6135aSMichel Lespinasse * so as to bypass __rb_erase_color() later on. 39546b6135aSMichel Lespinasse */ 396*4f035ad6SMichel Lespinasse pc = node->__rb_parent_color; 397*4f035ad6SMichel Lespinasse parent = __rb_parent(pc); 39860670b80SMichel Lespinasse __rb_change_child(node, child, parent, root); 39946b6135aSMichel Lespinasse if (child) { 400*4f035ad6SMichel Lespinasse child->__rb_parent_color = pc; 40146b6135aSMichel Lespinasse rebalance = NULL; 402*4f035ad6SMichel Lespinasse } else 403*4f035ad6SMichel Lespinasse rebalance = __rb_is_black(pc) ? parent : NULL; 40460670b80SMichel Lespinasse } else if (!child) { 40560670b80SMichel Lespinasse /* Still case 1, but this time the child is node->rb_left */ 406*4f035ad6SMichel Lespinasse tmp->__rb_parent_color = pc = node->__rb_parent_color; 407*4f035ad6SMichel Lespinasse parent = __rb_parent(pc); 40846b6135aSMichel Lespinasse __rb_change_child(node, tmp, parent, root); 40946b6135aSMichel Lespinasse rebalance = NULL; 41060670b80SMichel Lespinasse } else { 411*4f035ad6SMichel Lespinasse struct rb_node *successor = child, *child2; 412*4f035ad6SMichel Lespinasse tmp = child->rb_left; 413*4f035ad6SMichel Lespinasse if (!tmp) { 414*4f035ad6SMichel Lespinasse /* 415*4f035ad6SMichel Lespinasse * Case 2: node's successor is its right child 416*4f035ad6SMichel Lespinasse * 417*4f035ad6SMichel Lespinasse * (n) (s) 418*4f035ad6SMichel Lespinasse * / \ / \ 419*4f035ad6SMichel Lespinasse * (x) (s) -> (x) (c) 420*4f035ad6SMichel Lespinasse * \ 421*4f035ad6SMichel Lespinasse * (c) 422*4f035ad6SMichel Lespinasse */ 423*4f035ad6SMichel Lespinasse parent = child; 424*4f035ad6SMichel Lespinasse child2 = child->rb_right; 4254c601178SWolfram Strepp } else { 426*4f035ad6SMichel Lespinasse /* 427*4f035ad6SMichel Lespinasse * Case 3: node's successor is leftmost under 428*4f035ad6SMichel Lespinasse * node's right child subtree 429*4f035ad6SMichel Lespinasse * 430*4f035ad6SMichel Lespinasse * (n) (s) 431*4f035ad6SMichel Lespinasse * / \ / \ 432*4f035ad6SMichel Lespinasse * (x) (y) -> (x) (y) 433*4f035ad6SMichel Lespinasse * / / 434*4f035ad6SMichel Lespinasse * (p) (p) 435*4f035ad6SMichel Lespinasse * / / 436*4f035ad6SMichel Lespinasse * (s) (c) 437*4f035ad6SMichel Lespinasse * \ 438*4f035ad6SMichel Lespinasse * (c) 439*4f035ad6SMichel Lespinasse */ 440*4f035ad6SMichel Lespinasse do { 441*4f035ad6SMichel Lespinasse parent = successor; 442*4f035ad6SMichel Lespinasse successor = tmp; 443*4f035ad6SMichel Lespinasse tmp = tmp->rb_left; 444*4f035ad6SMichel Lespinasse } while (tmp); 445*4f035ad6SMichel Lespinasse parent->rb_left = child2 = successor->rb_right; 446*4f035ad6SMichel Lespinasse successor->rb_right = child; 447*4f035ad6SMichel Lespinasse rb_set_parent(child, successor); 4484c601178SWolfram Strepp } 4491975e593SDavid Woodhouse 450*4f035ad6SMichel Lespinasse successor->rb_left = tmp = node->rb_left; 451*4f035ad6SMichel Lespinasse rb_set_parent(tmp, successor); 452*4f035ad6SMichel Lespinasse 453*4f035ad6SMichel Lespinasse pc = node->__rb_parent_color; 454*4f035ad6SMichel Lespinasse tmp = __rb_parent(pc); 455*4f035ad6SMichel Lespinasse __rb_change_child(node, successor, tmp, root); 456*4f035ad6SMichel Lespinasse if (child2) { 457*4f035ad6SMichel Lespinasse successor->__rb_parent_color = pc; 458*4f035ad6SMichel Lespinasse rb_set_parent_color(child2, parent, RB_BLACK); 45946b6135aSMichel Lespinasse rebalance = NULL; 46046b6135aSMichel Lespinasse } else { 461*4f035ad6SMichel Lespinasse unsigned long pc2 = successor->__rb_parent_color; 462*4f035ad6SMichel Lespinasse successor->__rb_parent_color = pc; 463*4f035ad6SMichel Lespinasse rebalance = __rb_is_black(pc2) ? parent : NULL; 46446b6135aSMichel Lespinasse } 4651da177e4SLinus Torvalds } 4661da177e4SLinus Torvalds 46746b6135aSMichel Lespinasse if (rebalance) 46846b6135aSMichel Lespinasse __rb_erase_color(rebalance, root); 4691da177e4SLinus Torvalds } 4701da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4711da177e4SLinus Torvalds 472b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 473b945d6b2SPeter Zijlstra { 474b945d6b2SPeter Zijlstra struct rb_node *parent; 475b945d6b2SPeter Zijlstra 476b945d6b2SPeter Zijlstra up: 477b945d6b2SPeter Zijlstra func(node, data); 478b945d6b2SPeter Zijlstra parent = rb_parent(node); 479b945d6b2SPeter Zijlstra if (!parent) 480b945d6b2SPeter Zijlstra return; 481b945d6b2SPeter Zijlstra 482b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 483b945d6b2SPeter Zijlstra func(parent->rb_right, data); 484b945d6b2SPeter Zijlstra else if (parent->rb_left) 485b945d6b2SPeter Zijlstra func(parent->rb_left, data); 486b945d6b2SPeter Zijlstra 487b945d6b2SPeter Zijlstra node = parent; 488b945d6b2SPeter Zijlstra goto up; 489b945d6b2SPeter Zijlstra } 490b945d6b2SPeter Zijlstra 491b945d6b2SPeter Zijlstra /* 492b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 493b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 494b945d6b2SPeter Zijlstra */ 495b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 496b945d6b2SPeter Zijlstra { 497b945d6b2SPeter Zijlstra if (node->rb_left) 498b945d6b2SPeter Zijlstra node = node->rb_left; 499b945d6b2SPeter Zijlstra else if (node->rb_right) 500b945d6b2SPeter Zijlstra node = node->rb_right; 501b945d6b2SPeter Zijlstra 502b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 503b945d6b2SPeter Zijlstra } 5040b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 505b945d6b2SPeter Zijlstra 506b945d6b2SPeter Zijlstra /* 507b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 508b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 509b945d6b2SPeter Zijlstra */ 510b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 511b945d6b2SPeter Zijlstra { 512b945d6b2SPeter Zijlstra struct rb_node *deepest; 513b945d6b2SPeter Zijlstra 514b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 515b945d6b2SPeter Zijlstra deepest = rb_parent(node); 516b945d6b2SPeter Zijlstra else if (!node->rb_right) 517b945d6b2SPeter Zijlstra deepest = node->rb_left; 518b945d6b2SPeter Zijlstra else if (!node->rb_left) 519b945d6b2SPeter Zijlstra deepest = node->rb_right; 520b945d6b2SPeter Zijlstra else { 521b945d6b2SPeter Zijlstra deepest = rb_next(node); 522b945d6b2SPeter Zijlstra if (deepest->rb_right) 523b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 524b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 525b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 526b945d6b2SPeter Zijlstra } 527b945d6b2SPeter Zijlstra 528b945d6b2SPeter Zijlstra return deepest; 529b945d6b2SPeter Zijlstra } 5300b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 531b945d6b2SPeter Zijlstra 532b945d6b2SPeter Zijlstra /* 533b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 534b945d6b2SPeter Zijlstra * and any rebalance damage. 535b945d6b2SPeter Zijlstra */ 536b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 537b945d6b2SPeter Zijlstra { 538b945d6b2SPeter Zijlstra if (node) 539b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 540b945d6b2SPeter Zijlstra } 5410b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 542b945d6b2SPeter Zijlstra 5431da177e4SLinus Torvalds /* 5441da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 5451da177e4SLinus Torvalds */ 546f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 5471da177e4SLinus Torvalds { 5481da177e4SLinus Torvalds struct rb_node *n; 5491da177e4SLinus Torvalds 5501da177e4SLinus Torvalds n = root->rb_node; 5511da177e4SLinus Torvalds if (!n) 5521da177e4SLinus Torvalds return NULL; 5531da177e4SLinus Torvalds while (n->rb_left) 5541da177e4SLinus Torvalds n = n->rb_left; 5551da177e4SLinus Torvalds return n; 5561da177e4SLinus Torvalds } 5571da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 5581da177e4SLinus Torvalds 559f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 5601da177e4SLinus Torvalds { 5611da177e4SLinus Torvalds struct rb_node *n; 5621da177e4SLinus Torvalds 5631da177e4SLinus Torvalds n = root->rb_node; 5641da177e4SLinus Torvalds if (!n) 5651da177e4SLinus Torvalds return NULL; 5661da177e4SLinus Torvalds while (n->rb_right) 5671da177e4SLinus Torvalds n = n->rb_right; 5681da177e4SLinus Torvalds return n; 5691da177e4SLinus Torvalds } 5701da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5711da177e4SLinus Torvalds 572f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5731da177e4SLinus Torvalds { 57455a98102SDavid Woodhouse struct rb_node *parent; 57555a98102SDavid Woodhouse 5764c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 57710fd48f2SJens Axboe return NULL; 57810fd48f2SJens Axboe 5797ce6ff9eSMichel Lespinasse /* 5807ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 5817ce6ff9eSMichel Lespinasse * as we can. 5827ce6ff9eSMichel Lespinasse */ 5831da177e4SLinus Torvalds if (node->rb_right) { 5841da177e4SLinus Torvalds node = node->rb_right; 5851da177e4SLinus Torvalds while (node->rb_left) 5861da177e4SLinus Torvalds node=node->rb_left; 587f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5881da177e4SLinus Torvalds } 5891da177e4SLinus Torvalds 5907ce6ff9eSMichel Lespinasse /* 5917ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 5927ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 5937ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 5947ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 5957ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 5967ce6ff9eSMichel Lespinasse */ 59755a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 59855a98102SDavid Woodhouse node = parent; 5991da177e4SLinus Torvalds 60055a98102SDavid Woodhouse return parent; 6011da177e4SLinus Torvalds } 6021da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 6031da177e4SLinus Torvalds 604f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 6051da177e4SLinus Torvalds { 60655a98102SDavid Woodhouse struct rb_node *parent; 60755a98102SDavid Woodhouse 6084c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 60910fd48f2SJens Axboe return NULL; 61010fd48f2SJens Axboe 6117ce6ff9eSMichel Lespinasse /* 6127ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 6137ce6ff9eSMichel Lespinasse * as we can. 6147ce6ff9eSMichel Lespinasse */ 6151da177e4SLinus Torvalds if (node->rb_left) { 6161da177e4SLinus Torvalds node = node->rb_left; 6171da177e4SLinus Torvalds while (node->rb_right) 6181da177e4SLinus Torvalds node=node->rb_right; 619f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 6201da177e4SLinus Torvalds } 6211da177e4SLinus Torvalds 6227ce6ff9eSMichel Lespinasse /* 6237ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 6247ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 6257ce6ff9eSMichel Lespinasse */ 62655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 62755a98102SDavid Woodhouse node = parent; 6281da177e4SLinus Torvalds 62955a98102SDavid Woodhouse return parent; 6301da177e4SLinus Torvalds } 6311da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 6321da177e4SLinus Torvalds 6331da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 6341da177e4SLinus Torvalds struct rb_root *root) 6351da177e4SLinus Torvalds { 63655a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 6371da177e4SLinus Torvalds 6381da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 6397abc704aSMichel Lespinasse __rb_change_child(victim, new, parent, root); 6401da177e4SLinus Torvalds if (victim->rb_left) 64155a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 6421da177e4SLinus Torvalds if (victim->rb_right) 64355a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 6441da177e4SLinus Torvalds 6451da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 6461da177e4SLinus Torvalds *new = *victim; 6471da177e4SLinus Torvalds } 6481da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 649