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> 5*46b6135aSMichel 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 50bf7ad8eeSMichel Lespinasse #define rb_color(r) ((r)->__rb_parent_color & 1) 51bf7ad8eeSMichel Lespinasse #define rb_is_red(r) (!rb_color(r)) 52bf7ad8eeSMichel Lespinasse #define rb_is_black(r) rb_color(r) 53bf7ad8eeSMichel Lespinasse 54*46b6135aSMichel Lespinasse static inline void rb_set_black(struct rb_node *rb) 55*46b6135aSMichel Lespinasse { 56*46b6135aSMichel Lespinasse rb->__rb_parent_color |= RB_BLACK; 57*46b6135aSMichel Lespinasse } 58*46b6135aSMichel Lespinasse 59bf7ad8eeSMichel Lespinasse static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 60bf7ad8eeSMichel Lespinasse { 61bf7ad8eeSMichel Lespinasse rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 62bf7ad8eeSMichel Lespinasse } 63bf7ad8eeSMichel Lespinasse 645bc9188aSMichel Lespinasse static inline void rb_set_parent_color(struct rb_node *rb, 655bc9188aSMichel Lespinasse struct rb_node *p, int color) 665bc9188aSMichel Lespinasse { 675bc9188aSMichel Lespinasse rb->__rb_parent_color = (unsigned long)p | color; 685bc9188aSMichel Lespinasse } 695bc9188aSMichel Lespinasse 705bc9188aSMichel Lespinasse static inline struct rb_node *rb_red_parent(struct rb_node *red) 715bc9188aSMichel Lespinasse { 725bc9188aSMichel Lespinasse return (struct rb_node *)red->__rb_parent_color; 735bc9188aSMichel Lespinasse } 745bc9188aSMichel Lespinasse 757abc704aSMichel Lespinasse static inline void 767abc704aSMichel Lespinasse __rb_change_child(struct rb_node *old, struct rb_node *new, 777abc704aSMichel Lespinasse struct rb_node *parent, struct rb_root *root) 787abc704aSMichel Lespinasse { 797abc704aSMichel Lespinasse if (parent) { 807abc704aSMichel Lespinasse if (parent->rb_left == old) 817abc704aSMichel Lespinasse parent->rb_left = new; 827abc704aSMichel Lespinasse else 837abc704aSMichel Lespinasse parent->rb_right = new; 847abc704aSMichel Lespinasse } else 857abc704aSMichel Lespinasse root->rb_node = new; 867abc704aSMichel Lespinasse } 877abc704aSMichel Lespinasse 885bc9188aSMichel Lespinasse /* 895bc9188aSMichel Lespinasse * Helper function for rotations: 905bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 915bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 925bc9188aSMichel Lespinasse */ 935bc9188aSMichel Lespinasse static inline void 945bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 955bc9188aSMichel Lespinasse struct rb_root *root, int color) 965bc9188aSMichel Lespinasse { 975bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 985bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 995bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 1007abc704aSMichel Lespinasse __rb_change_child(old, new, parent, root); 1015bc9188aSMichel Lespinasse } 1025bc9188aSMichel Lespinasse 1031da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 1041da177e4SLinus Torvalds { 1055bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 1061da177e4SLinus Torvalds 1076d58452dSMichel Lespinasse while (true) { 1086d58452dSMichel Lespinasse /* 1096d58452dSMichel Lespinasse * Loop invariant: node is red 1106d58452dSMichel Lespinasse * 1116d58452dSMichel Lespinasse * If there is a black parent, we are done. 1126d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 1136d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 1146d58452dSMichel Lespinasse */ 1156d58452dSMichel Lespinasse if (!parent) { 1165bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1176d58452dSMichel Lespinasse break; 1186d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 1196d58452dSMichel Lespinasse break; 1206d58452dSMichel Lespinasse 1215bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1221da177e4SLinus Torvalds 1235bc9188aSMichel Lespinasse tmp = gparent->rb_right; 12459633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1255bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1265bc9188aSMichel Lespinasse /* 1275bc9188aSMichel Lespinasse * Case 1 - color flips 1285bc9188aSMichel Lespinasse * 1295bc9188aSMichel Lespinasse * G g 1305bc9188aSMichel Lespinasse * / \ / \ 1315bc9188aSMichel Lespinasse * p u --> P U 1325bc9188aSMichel Lespinasse * / / 1335bc9188aSMichel Lespinasse * n N 1345bc9188aSMichel Lespinasse * 1355bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1365bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1375bc9188aSMichel Lespinasse * at g. 1385bc9188aSMichel Lespinasse */ 1395bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1405bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1411da177e4SLinus Torvalds node = gparent; 1425bc9188aSMichel Lespinasse parent = rb_parent(node); 1435bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1441da177e4SLinus Torvalds continue; 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds 14759633abfSMichel Lespinasse tmp = parent->rb_right; 14859633abfSMichel Lespinasse if (node == tmp) { 1495bc9188aSMichel Lespinasse /* 1505bc9188aSMichel Lespinasse * Case 2 - left rotate at parent 1515bc9188aSMichel Lespinasse * 1525bc9188aSMichel Lespinasse * G G 1535bc9188aSMichel Lespinasse * / \ / \ 1545bc9188aSMichel Lespinasse * p U --> n U 1555bc9188aSMichel Lespinasse * \ / 1565bc9188aSMichel Lespinasse * n p 1575bc9188aSMichel Lespinasse * 1585bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1595bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1605bc9188aSMichel Lespinasse */ 1615bc9188aSMichel Lespinasse parent->rb_right = tmp = node->rb_left; 1625bc9188aSMichel Lespinasse node->rb_left = parent; 1635bc9188aSMichel Lespinasse if (tmp) 1645bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1655bc9188aSMichel Lespinasse RB_BLACK); 1665bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 1671da177e4SLinus Torvalds parent = node; 16859633abfSMichel Lespinasse tmp = node->rb_right; 1691da177e4SLinus Torvalds } 1701da177e4SLinus Torvalds 1715bc9188aSMichel Lespinasse /* 1725bc9188aSMichel Lespinasse * Case 3 - right rotate at gparent 1735bc9188aSMichel Lespinasse * 1745bc9188aSMichel Lespinasse * G P 1755bc9188aSMichel Lespinasse * / \ / \ 1765bc9188aSMichel Lespinasse * p U --> n g 1775bc9188aSMichel Lespinasse * / \ 1785bc9188aSMichel Lespinasse * n U 1795bc9188aSMichel Lespinasse */ 18059633abfSMichel Lespinasse gparent->rb_left = tmp; /* == parent->rb_right */ 1815bc9188aSMichel Lespinasse parent->rb_right = gparent; 1825bc9188aSMichel Lespinasse if (tmp) 1835bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1845bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1851f052865SMichel Lespinasse break; 1861da177e4SLinus Torvalds } else { 1875bc9188aSMichel Lespinasse tmp = gparent->rb_left; 1885bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1895bc9188aSMichel Lespinasse /* Case 1 - color flips */ 1905bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1915bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1921da177e4SLinus Torvalds node = gparent; 1935bc9188aSMichel Lespinasse parent = rb_parent(node); 1945bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1951da177e4SLinus Torvalds continue; 1961da177e4SLinus Torvalds } 1971da177e4SLinus Torvalds 19859633abfSMichel Lespinasse tmp = parent->rb_left; 19959633abfSMichel Lespinasse if (node == tmp) { 2005bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 2015bc9188aSMichel Lespinasse parent->rb_left = tmp = node->rb_right; 2025bc9188aSMichel Lespinasse node->rb_right = parent; 2035bc9188aSMichel Lespinasse if (tmp) 2045bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2055bc9188aSMichel Lespinasse RB_BLACK); 2065bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 2071da177e4SLinus Torvalds parent = node; 20859633abfSMichel Lespinasse tmp = node->rb_left; 2091da177e4SLinus Torvalds } 2101da177e4SLinus Torvalds 2115bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 21259633abfSMichel Lespinasse gparent->rb_right = tmp; /* == parent->rb_left */ 2135bc9188aSMichel Lespinasse parent->rb_left = gparent; 2145bc9188aSMichel Lespinasse if (tmp) 2155bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2165bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2171f052865SMichel Lespinasse break; 2181da177e4SLinus Torvalds } 2191da177e4SLinus Torvalds } 2201da177e4SLinus Torvalds } 2211da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 2221da177e4SLinus Torvalds 223*46b6135aSMichel Lespinasse static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) 2241da177e4SLinus Torvalds { 225*46b6135aSMichel Lespinasse struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 2261da177e4SLinus Torvalds 227d6ff1273SMichel Lespinasse while (true) { 228d6ff1273SMichel Lespinasse /* 229*46b6135aSMichel Lespinasse * Loop invariants: 230*46b6135aSMichel Lespinasse * - node is black (or NULL on first iteration) 231*46b6135aSMichel Lespinasse * - node is not the root (parent is not NULL) 232*46b6135aSMichel Lespinasse * - All leaf paths going through parent and node have a 233d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 234d6ff1273SMichel Lespinasse */ 2356280d235SMichel Lespinasse sibling = parent->rb_right; 23659633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2376280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2386280d235SMichel Lespinasse /* 2396280d235SMichel Lespinasse * Case 1 - left rotate at parent 2406280d235SMichel Lespinasse * 2416280d235SMichel Lespinasse * P S 2426280d235SMichel Lespinasse * / \ / \ 2436280d235SMichel Lespinasse * N s --> p Sr 2446280d235SMichel Lespinasse * / \ / \ 2456280d235SMichel Lespinasse * Sl Sr N Sl 2466280d235SMichel Lespinasse */ 2476280d235SMichel Lespinasse parent->rb_right = tmp1 = sibling->rb_left; 2486280d235SMichel Lespinasse sibling->rb_left = parent; 2496280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2506280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2516280d235SMichel Lespinasse RB_RED); 2526280d235SMichel Lespinasse sibling = tmp1; 2531da177e4SLinus Torvalds } 2546280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2556280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2566280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2576280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2586280d235SMichel Lespinasse /* 2596280d235SMichel Lespinasse * Case 2 - sibling color flip 2606280d235SMichel Lespinasse * (p could be either color here) 2616280d235SMichel Lespinasse * 2626280d235SMichel Lespinasse * (p) (p) 2636280d235SMichel Lespinasse * / \ / \ 2646280d235SMichel Lespinasse * N S --> N s 2656280d235SMichel Lespinasse * / \ / \ 2666280d235SMichel Lespinasse * Sl Sr Sl Sr 2676280d235SMichel Lespinasse * 268*46b6135aSMichel Lespinasse * This leaves us violating 5) which 269*46b6135aSMichel Lespinasse * can be fixed by flipping p to black 270*46b6135aSMichel Lespinasse * if it was red, or by recursing at p. 271*46b6135aSMichel Lespinasse * p is red when coming from Case 1. 2726280d235SMichel Lespinasse */ 2736280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2746280d235SMichel Lespinasse RB_RED); 275*46b6135aSMichel Lespinasse if (rb_is_red(parent)) 276*46b6135aSMichel Lespinasse rb_set_black(parent); 277*46b6135aSMichel Lespinasse else { 2781da177e4SLinus Torvalds node = parent; 27955a98102SDavid Woodhouse parent = rb_parent(node); 280*46b6135aSMichel Lespinasse if (parent) 281e125d147SMichel Lespinasse continue; 2821da177e4SLinus Torvalds } 283*46b6135aSMichel Lespinasse break; 284*46b6135aSMichel Lespinasse } 2856280d235SMichel Lespinasse /* 2866280d235SMichel Lespinasse * Case 3 - right rotate at sibling 2876280d235SMichel Lespinasse * (p could be either color here) 2886280d235SMichel Lespinasse * 2896280d235SMichel Lespinasse * (p) (p) 2906280d235SMichel Lespinasse * / \ / \ 2916280d235SMichel Lespinasse * N S --> N Sl 2926280d235SMichel Lespinasse * / \ \ 2936280d235SMichel Lespinasse * sl Sr s 2946280d235SMichel Lespinasse * \ 2956280d235SMichel Lespinasse * Sr 2966280d235SMichel Lespinasse */ 2976280d235SMichel Lespinasse sibling->rb_left = tmp1 = tmp2->rb_right; 2986280d235SMichel Lespinasse tmp2->rb_right = sibling; 2996280d235SMichel Lespinasse parent->rb_right = tmp2; 3006280d235SMichel Lespinasse if (tmp1) 3016280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3026280d235SMichel Lespinasse RB_BLACK); 3036280d235SMichel Lespinasse tmp1 = sibling; 3046280d235SMichel Lespinasse sibling = tmp2; 3051da177e4SLinus Torvalds } 3066280d235SMichel Lespinasse /* 3076280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 3086280d235SMichel Lespinasse * (p and sl could be either color here. 3096280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3106280d235SMichel Lespinasse * p's color, and sl keeps its color) 3116280d235SMichel Lespinasse * 3126280d235SMichel Lespinasse * (p) (s) 3136280d235SMichel Lespinasse * / \ / \ 3146280d235SMichel Lespinasse * N S --> P Sr 3156280d235SMichel Lespinasse * / \ / \ 3166280d235SMichel Lespinasse * (sl) sr N (sl) 3176280d235SMichel Lespinasse */ 3186280d235SMichel Lespinasse parent->rb_right = tmp2 = sibling->rb_left; 3196280d235SMichel Lespinasse sibling->rb_left = parent; 3206280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3216280d235SMichel Lespinasse if (tmp2) 3226280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3236280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3246280d235SMichel Lespinasse RB_BLACK); 3251da177e4SLinus Torvalds break; 326d6ff1273SMichel Lespinasse } else { 3276280d235SMichel Lespinasse sibling = parent->rb_left; 3286280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3296280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 3306280d235SMichel Lespinasse parent->rb_left = tmp1 = sibling->rb_right; 3316280d235SMichel Lespinasse sibling->rb_right = parent; 3326280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3336280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3346280d235SMichel Lespinasse RB_RED); 3356280d235SMichel Lespinasse sibling = tmp1; 3361da177e4SLinus Torvalds } 3376280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3386280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3396280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3406280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3416280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3426280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3436280d235SMichel Lespinasse RB_RED); 344*46b6135aSMichel Lespinasse if (rb_is_red(parent)) 345*46b6135aSMichel Lespinasse rb_set_black(parent); 346*46b6135aSMichel Lespinasse else { 3471da177e4SLinus Torvalds node = parent; 34855a98102SDavid Woodhouse parent = rb_parent(node); 349*46b6135aSMichel Lespinasse if (parent) 350e125d147SMichel Lespinasse continue; 3511da177e4SLinus Torvalds } 352*46b6135aSMichel Lespinasse break; 353*46b6135aSMichel Lespinasse } 3546280d235SMichel Lespinasse /* Case 3 - right rotate at sibling */ 3556280d235SMichel Lespinasse sibling->rb_right = tmp1 = tmp2->rb_left; 3566280d235SMichel Lespinasse tmp2->rb_left = sibling; 3576280d235SMichel Lespinasse parent->rb_left = tmp2; 3586280d235SMichel Lespinasse if (tmp1) 3596280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3606280d235SMichel Lespinasse RB_BLACK); 3616280d235SMichel Lespinasse tmp1 = sibling; 3626280d235SMichel Lespinasse sibling = tmp2; 3631da177e4SLinus Torvalds } 3646280d235SMichel Lespinasse /* Case 4 - left rotate at parent + color flips */ 3656280d235SMichel Lespinasse parent->rb_left = tmp2 = sibling->rb_right; 3666280d235SMichel Lespinasse sibling->rb_right = parent; 3676280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3686280d235SMichel Lespinasse if (tmp2) 3696280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3706280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3716280d235SMichel Lespinasse RB_BLACK); 3721da177e4SLinus Torvalds break; 3731da177e4SLinus Torvalds } 3741da177e4SLinus Torvalds } 3751da177e4SLinus Torvalds } 3761da177e4SLinus Torvalds 3771da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 3781da177e4SLinus Torvalds { 37960670b80SMichel Lespinasse struct rb_node *child = node->rb_right, *tmp = node->rb_left; 380*46b6135aSMichel Lespinasse struct rb_node *parent, *rebalance; 3811da177e4SLinus Torvalds 38260670b80SMichel Lespinasse if (!tmp) { 383*46b6135aSMichel Lespinasse /* 384*46b6135aSMichel Lespinasse * Case 1: node to erase has no more than 1 child (easy!) 385*46b6135aSMichel Lespinasse * 386*46b6135aSMichel Lespinasse * Note that if there is one child it must be red due to 5) 387*46b6135aSMichel Lespinasse * and node must be black due to 4). We adjust colors locally 388*46b6135aSMichel Lespinasse * so as to bypass __rb_erase_color() later on. 389*46b6135aSMichel Lespinasse */ 39060670b80SMichel Lespinasse 39160670b80SMichel Lespinasse parent = rb_parent(node); 39260670b80SMichel Lespinasse __rb_change_child(node, child, parent, root); 393*46b6135aSMichel Lespinasse if (child) { 394*46b6135aSMichel Lespinasse rb_set_parent_color(child, parent, RB_BLACK); 395*46b6135aSMichel Lespinasse rebalance = NULL; 396*46b6135aSMichel Lespinasse } else { 397*46b6135aSMichel Lespinasse rebalance = rb_is_black(node) ? parent : NULL; 398*46b6135aSMichel Lespinasse } 39960670b80SMichel Lespinasse } else if (!child) { 40060670b80SMichel Lespinasse /* Still case 1, but this time the child is node->rb_left */ 401*46b6135aSMichel Lespinasse parent = rb_parent(node); 402*46b6135aSMichel Lespinasse __rb_change_child(node, tmp, parent, root); 403*46b6135aSMichel Lespinasse rb_set_parent_color(tmp, parent, RB_BLACK); 404*46b6135aSMichel Lespinasse rebalance = NULL; 40560670b80SMichel Lespinasse } else { 4061da177e4SLinus Torvalds struct rb_node *old = node, *left; 4071da177e4SLinus Torvalds 40860670b80SMichel Lespinasse node = child; 4091da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 4101da177e4SLinus Torvalds node = left; 41116c047adSWolfram Strepp 4127abc704aSMichel Lespinasse __rb_change_child(old, node, rb_parent(old), root); 41316c047adSWolfram Strepp 4141da177e4SLinus Torvalds child = node->rb_right; 41555a98102SDavid Woodhouse parent = rb_parent(node); 4161da177e4SLinus Torvalds 4174c601178SWolfram Strepp if (parent == old) { 4184c601178SWolfram Strepp parent = node; 4194c601178SWolfram Strepp } else { 4201975e593SDavid Woodhouse parent->rb_left = child; 4214b324126SWolfram Strepp 4224b324126SWolfram Strepp node->rb_right = old->rb_right; 4234b324126SWolfram Strepp rb_set_parent(old->rb_right, node); 4244c601178SWolfram Strepp } 4251975e593SDavid Woodhouse 426*46b6135aSMichel Lespinasse if (child) { 427*46b6135aSMichel Lespinasse rb_set_parent_color(child, parent, RB_BLACK); 428*46b6135aSMichel Lespinasse rebalance = NULL; 429*46b6135aSMichel Lespinasse } else { 430*46b6135aSMichel Lespinasse rebalance = rb_is_black(node) ? parent : NULL; 431*46b6135aSMichel Lespinasse } 432bf7ad8eeSMichel Lespinasse node->__rb_parent_color = old->__rb_parent_color; 4331da177e4SLinus Torvalds node->rb_left = old->rb_left; 43455a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 4351da177e4SLinus Torvalds } 4361da177e4SLinus Torvalds 437*46b6135aSMichel Lespinasse if (rebalance) 438*46b6135aSMichel Lespinasse __rb_erase_color(rebalance, root); 4391da177e4SLinus Torvalds } 4401da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4411da177e4SLinus Torvalds 442b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 443b945d6b2SPeter Zijlstra { 444b945d6b2SPeter Zijlstra struct rb_node *parent; 445b945d6b2SPeter Zijlstra 446b945d6b2SPeter Zijlstra up: 447b945d6b2SPeter Zijlstra func(node, data); 448b945d6b2SPeter Zijlstra parent = rb_parent(node); 449b945d6b2SPeter Zijlstra if (!parent) 450b945d6b2SPeter Zijlstra return; 451b945d6b2SPeter Zijlstra 452b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 453b945d6b2SPeter Zijlstra func(parent->rb_right, data); 454b945d6b2SPeter Zijlstra else if (parent->rb_left) 455b945d6b2SPeter Zijlstra func(parent->rb_left, data); 456b945d6b2SPeter Zijlstra 457b945d6b2SPeter Zijlstra node = parent; 458b945d6b2SPeter Zijlstra goto up; 459b945d6b2SPeter Zijlstra } 460b945d6b2SPeter Zijlstra 461b945d6b2SPeter Zijlstra /* 462b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 463b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 464b945d6b2SPeter Zijlstra */ 465b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 466b945d6b2SPeter Zijlstra { 467b945d6b2SPeter Zijlstra if (node->rb_left) 468b945d6b2SPeter Zijlstra node = node->rb_left; 469b945d6b2SPeter Zijlstra else if (node->rb_right) 470b945d6b2SPeter Zijlstra node = node->rb_right; 471b945d6b2SPeter Zijlstra 472b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 473b945d6b2SPeter Zijlstra } 4740b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 475b945d6b2SPeter Zijlstra 476b945d6b2SPeter Zijlstra /* 477b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 478b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 479b945d6b2SPeter Zijlstra */ 480b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 481b945d6b2SPeter Zijlstra { 482b945d6b2SPeter Zijlstra struct rb_node *deepest; 483b945d6b2SPeter Zijlstra 484b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 485b945d6b2SPeter Zijlstra deepest = rb_parent(node); 486b945d6b2SPeter Zijlstra else if (!node->rb_right) 487b945d6b2SPeter Zijlstra deepest = node->rb_left; 488b945d6b2SPeter Zijlstra else if (!node->rb_left) 489b945d6b2SPeter Zijlstra deepest = node->rb_right; 490b945d6b2SPeter Zijlstra else { 491b945d6b2SPeter Zijlstra deepest = rb_next(node); 492b945d6b2SPeter Zijlstra if (deepest->rb_right) 493b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 494b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 495b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 496b945d6b2SPeter Zijlstra } 497b945d6b2SPeter Zijlstra 498b945d6b2SPeter Zijlstra return deepest; 499b945d6b2SPeter Zijlstra } 5000b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 501b945d6b2SPeter Zijlstra 502b945d6b2SPeter Zijlstra /* 503b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 504b945d6b2SPeter Zijlstra * and any rebalance damage. 505b945d6b2SPeter Zijlstra */ 506b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 507b945d6b2SPeter Zijlstra { 508b945d6b2SPeter Zijlstra if (node) 509b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 510b945d6b2SPeter Zijlstra } 5110b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 512b945d6b2SPeter Zijlstra 5131da177e4SLinus Torvalds /* 5141da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 5151da177e4SLinus Torvalds */ 516f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 5171da177e4SLinus Torvalds { 5181da177e4SLinus Torvalds struct rb_node *n; 5191da177e4SLinus Torvalds 5201da177e4SLinus Torvalds n = root->rb_node; 5211da177e4SLinus Torvalds if (!n) 5221da177e4SLinus Torvalds return NULL; 5231da177e4SLinus Torvalds while (n->rb_left) 5241da177e4SLinus Torvalds n = n->rb_left; 5251da177e4SLinus Torvalds return n; 5261da177e4SLinus Torvalds } 5271da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 5281da177e4SLinus Torvalds 529f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 5301da177e4SLinus Torvalds { 5311da177e4SLinus Torvalds struct rb_node *n; 5321da177e4SLinus Torvalds 5331da177e4SLinus Torvalds n = root->rb_node; 5341da177e4SLinus Torvalds if (!n) 5351da177e4SLinus Torvalds return NULL; 5361da177e4SLinus Torvalds while (n->rb_right) 5371da177e4SLinus Torvalds n = n->rb_right; 5381da177e4SLinus Torvalds return n; 5391da177e4SLinus Torvalds } 5401da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5411da177e4SLinus Torvalds 542f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5431da177e4SLinus Torvalds { 54455a98102SDavid Woodhouse struct rb_node *parent; 54555a98102SDavid Woodhouse 5464c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 54710fd48f2SJens Axboe return NULL; 54810fd48f2SJens Axboe 5497ce6ff9eSMichel Lespinasse /* 5507ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 5517ce6ff9eSMichel Lespinasse * as we can. 5527ce6ff9eSMichel Lespinasse */ 5531da177e4SLinus Torvalds if (node->rb_right) { 5541da177e4SLinus Torvalds node = node->rb_right; 5551da177e4SLinus Torvalds while (node->rb_left) 5561da177e4SLinus Torvalds node=node->rb_left; 557f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5581da177e4SLinus Torvalds } 5591da177e4SLinus Torvalds 5607ce6ff9eSMichel Lespinasse /* 5617ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 5627ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 5637ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 5647ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 5657ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 5667ce6ff9eSMichel Lespinasse */ 56755a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 56855a98102SDavid Woodhouse node = parent; 5691da177e4SLinus Torvalds 57055a98102SDavid Woodhouse return parent; 5711da177e4SLinus Torvalds } 5721da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 5731da177e4SLinus Torvalds 574f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 5751da177e4SLinus Torvalds { 57655a98102SDavid Woodhouse struct rb_node *parent; 57755a98102SDavid Woodhouse 5784c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 57910fd48f2SJens Axboe return NULL; 58010fd48f2SJens Axboe 5817ce6ff9eSMichel Lespinasse /* 5827ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 5837ce6ff9eSMichel Lespinasse * as we can. 5847ce6ff9eSMichel Lespinasse */ 5851da177e4SLinus Torvalds if (node->rb_left) { 5861da177e4SLinus Torvalds node = node->rb_left; 5871da177e4SLinus Torvalds while (node->rb_right) 5881da177e4SLinus Torvalds node=node->rb_right; 589f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5901da177e4SLinus Torvalds } 5911da177e4SLinus Torvalds 5927ce6ff9eSMichel Lespinasse /* 5937ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 5947ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 5957ce6ff9eSMichel Lespinasse */ 59655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 59755a98102SDavid Woodhouse node = parent; 5981da177e4SLinus Torvalds 59955a98102SDavid Woodhouse return parent; 6001da177e4SLinus Torvalds } 6011da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 6021da177e4SLinus Torvalds 6031da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 6041da177e4SLinus Torvalds struct rb_root *root) 6051da177e4SLinus Torvalds { 60655a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 6071da177e4SLinus Torvalds 6081da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 6097abc704aSMichel Lespinasse __rb_change_child(victim, new, parent, root); 6101da177e4SLinus Torvalds if (victim->rb_left) 61155a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 6121da177e4SLinus Torvalds if (victim->rb_right) 61355a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 6141da177e4SLinus Torvalds 6151da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 6161da177e4SLinus Torvalds *new = *victim; 6171da177e4SLinus Torvalds } 6181da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 619