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 504f035ad6SMichel Lespinasse #define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) 514f035ad6SMichel Lespinasse 524f035ad6SMichel Lespinasse #define __rb_color(pc) ((pc) & 1) 534f035ad6SMichel Lespinasse #define __rb_is_black(pc) __rb_color(pc) 544f035ad6SMichel Lespinasse #define __rb_is_red(pc) (!__rb_color(pc)) 554f035ad6SMichel Lespinasse #define rb_color(rb) __rb_color((rb)->__rb_parent_color) 564f035ad6SMichel Lespinasse #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) 574f035ad6SMichel 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 108*14b94af0SMichel Lespinasse static __always_inline void 109*14b94af0SMichel Lespinasse __rb_insert(struct rb_node *node, struct rb_root *root, 110*14b94af0SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 1111da177e4SLinus Torvalds { 1125bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 1131da177e4SLinus Torvalds 1146d58452dSMichel Lespinasse while (true) { 1156d58452dSMichel Lespinasse /* 1166d58452dSMichel Lespinasse * Loop invariant: node is red 1176d58452dSMichel Lespinasse * 1186d58452dSMichel Lespinasse * If there is a black parent, we are done. 1196d58452dSMichel Lespinasse * Otherwise, take some corrective action as we don't 1206d58452dSMichel Lespinasse * want a red root or two consecutive red nodes. 1216d58452dSMichel Lespinasse */ 1226d58452dSMichel Lespinasse if (!parent) { 1235bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1246d58452dSMichel Lespinasse break; 1256d58452dSMichel Lespinasse } else if (rb_is_black(parent)) 1266d58452dSMichel Lespinasse break; 1276d58452dSMichel Lespinasse 1285bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1291da177e4SLinus Torvalds 1305bc9188aSMichel Lespinasse tmp = gparent->rb_right; 13159633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1325bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1335bc9188aSMichel Lespinasse /* 1345bc9188aSMichel Lespinasse * Case 1 - color flips 1355bc9188aSMichel Lespinasse * 1365bc9188aSMichel Lespinasse * G g 1375bc9188aSMichel Lespinasse * / \ / \ 1385bc9188aSMichel Lespinasse * p u --> P U 1395bc9188aSMichel Lespinasse * / / 1405bc9188aSMichel Lespinasse * n N 1415bc9188aSMichel Lespinasse * 1425bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1435bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1445bc9188aSMichel Lespinasse * at g. 1455bc9188aSMichel Lespinasse */ 1465bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1475bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1481da177e4SLinus Torvalds node = gparent; 1495bc9188aSMichel Lespinasse parent = rb_parent(node); 1505bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1511da177e4SLinus Torvalds continue; 1521da177e4SLinus Torvalds } 1531da177e4SLinus Torvalds 15459633abfSMichel Lespinasse tmp = parent->rb_right; 15559633abfSMichel Lespinasse if (node == tmp) { 1565bc9188aSMichel Lespinasse /* 1575bc9188aSMichel Lespinasse * Case 2 - left rotate at parent 1585bc9188aSMichel Lespinasse * 1595bc9188aSMichel Lespinasse * G G 1605bc9188aSMichel Lespinasse * / \ / \ 1615bc9188aSMichel Lespinasse * p U --> n U 1625bc9188aSMichel Lespinasse * \ / 1635bc9188aSMichel Lespinasse * n p 1645bc9188aSMichel Lespinasse * 1655bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1665bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1675bc9188aSMichel Lespinasse */ 1685bc9188aSMichel Lespinasse parent->rb_right = tmp = node->rb_left; 1695bc9188aSMichel Lespinasse node->rb_left = parent; 1705bc9188aSMichel Lespinasse if (tmp) 1715bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1725bc9188aSMichel Lespinasse RB_BLACK); 1735bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 174*14b94af0SMichel Lespinasse augment_rotate(parent, node); 1751da177e4SLinus Torvalds parent = node; 17659633abfSMichel Lespinasse tmp = node->rb_right; 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds 1795bc9188aSMichel Lespinasse /* 1805bc9188aSMichel Lespinasse * Case 3 - right rotate at gparent 1815bc9188aSMichel Lespinasse * 1825bc9188aSMichel Lespinasse * G P 1835bc9188aSMichel Lespinasse * / \ / \ 1845bc9188aSMichel Lespinasse * p U --> n g 1855bc9188aSMichel Lespinasse * / \ 1865bc9188aSMichel Lespinasse * n U 1875bc9188aSMichel Lespinasse */ 18859633abfSMichel Lespinasse gparent->rb_left = tmp; /* == parent->rb_right */ 1895bc9188aSMichel Lespinasse parent->rb_right = gparent; 1905bc9188aSMichel Lespinasse if (tmp) 1915bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1925bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 193*14b94af0SMichel Lespinasse augment_rotate(gparent, parent); 1941f052865SMichel Lespinasse break; 1951da177e4SLinus Torvalds } else { 1965bc9188aSMichel Lespinasse tmp = gparent->rb_left; 1975bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1985bc9188aSMichel Lespinasse /* Case 1 - color flips */ 1995bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2005bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 2011da177e4SLinus Torvalds node = gparent; 2025bc9188aSMichel Lespinasse parent = rb_parent(node); 2035bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 2041da177e4SLinus Torvalds continue; 2051da177e4SLinus Torvalds } 2061da177e4SLinus Torvalds 20759633abfSMichel Lespinasse tmp = parent->rb_left; 20859633abfSMichel Lespinasse if (node == tmp) { 2095bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 2105bc9188aSMichel Lespinasse parent->rb_left = tmp = node->rb_right; 2115bc9188aSMichel Lespinasse node->rb_right = parent; 2125bc9188aSMichel Lespinasse if (tmp) 2135bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2145bc9188aSMichel Lespinasse RB_BLACK); 2155bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 216*14b94af0SMichel Lespinasse augment_rotate(parent, node); 2171da177e4SLinus Torvalds parent = node; 21859633abfSMichel Lespinasse tmp = node->rb_left; 2191da177e4SLinus Torvalds } 2201da177e4SLinus Torvalds 2215bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 22259633abfSMichel Lespinasse gparent->rb_right = tmp; /* == parent->rb_left */ 2235bc9188aSMichel Lespinasse parent->rb_left = gparent; 2245bc9188aSMichel Lespinasse if (tmp) 2255bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2265bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 227*14b94af0SMichel Lespinasse augment_rotate(gparent, parent); 2281f052865SMichel Lespinasse break; 2291da177e4SLinus Torvalds } 2301da177e4SLinus Torvalds } 2311da177e4SLinus Torvalds } 2321da177e4SLinus Torvalds 233*14b94af0SMichel Lespinasse static __always_inline void 234*14b94af0SMichel Lespinasse __rb_erase_color(struct rb_node *parent, struct rb_root *root, 235*14b94af0SMichel Lespinasse const struct rb_augment_callbacks *augment) 2361da177e4SLinus Torvalds { 23746b6135aSMichel Lespinasse struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 2381da177e4SLinus Torvalds 239d6ff1273SMichel Lespinasse while (true) { 240d6ff1273SMichel Lespinasse /* 24146b6135aSMichel Lespinasse * Loop invariants: 24246b6135aSMichel Lespinasse * - node is black (or NULL on first iteration) 24346b6135aSMichel Lespinasse * - node is not the root (parent is not NULL) 24446b6135aSMichel Lespinasse * - All leaf paths going through parent and node have a 245d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 246d6ff1273SMichel Lespinasse */ 2476280d235SMichel Lespinasse sibling = parent->rb_right; 24859633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2496280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2506280d235SMichel Lespinasse /* 2516280d235SMichel Lespinasse * Case 1 - left rotate at parent 2526280d235SMichel Lespinasse * 2536280d235SMichel Lespinasse * P S 2546280d235SMichel Lespinasse * / \ / \ 2556280d235SMichel Lespinasse * N s --> p Sr 2566280d235SMichel Lespinasse * / \ / \ 2576280d235SMichel Lespinasse * Sl Sr N Sl 2586280d235SMichel Lespinasse */ 2596280d235SMichel Lespinasse parent->rb_right = tmp1 = sibling->rb_left; 2606280d235SMichel Lespinasse sibling->rb_left = parent; 2616280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2626280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2636280d235SMichel Lespinasse RB_RED); 264*14b94af0SMichel Lespinasse augment->rotate(parent, sibling); 2656280d235SMichel Lespinasse sibling = tmp1; 2661da177e4SLinus Torvalds } 2676280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2686280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2696280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2706280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2716280d235SMichel Lespinasse /* 2726280d235SMichel Lespinasse * Case 2 - sibling color flip 2736280d235SMichel Lespinasse * (p could be either color here) 2746280d235SMichel Lespinasse * 2756280d235SMichel Lespinasse * (p) (p) 2766280d235SMichel Lespinasse * / \ / \ 2776280d235SMichel Lespinasse * N S --> N s 2786280d235SMichel Lespinasse * / \ / \ 2796280d235SMichel Lespinasse * Sl Sr Sl Sr 2806280d235SMichel Lespinasse * 28146b6135aSMichel Lespinasse * This leaves us violating 5) which 28246b6135aSMichel Lespinasse * can be fixed by flipping p to black 28346b6135aSMichel Lespinasse * if it was red, or by recursing at p. 28446b6135aSMichel Lespinasse * p is red when coming from Case 1. 2856280d235SMichel Lespinasse */ 2866280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2876280d235SMichel Lespinasse RB_RED); 28846b6135aSMichel Lespinasse if (rb_is_red(parent)) 28946b6135aSMichel Lespinasse rb_set_black(parent); 29046b6135aSMichel Lespinasse else { 2911da177e4SLinus Torvalds node = parent; 29255a98102SDavid Woodhouse parent = rb_parent(node); 29346b6135aSMichel Lespinasse if (parent) 294e125d147SMichel Lespinasse continue; 2951da177e4SLinus Torvalds } 29646b6135aSMichel Lespinasse break; 29746b6135aSMichel Lespinasse } 2986280d235SMichel Lespinasse /* 2996280d235SMichel Lespinasse * Case 3 - right rotate at sibling 3006280d235SMichel Lespinasse * (p could be either color here) 3016280d235SMichel Lespinasse * 3026280d235SMichel Lespinasse * (p) (p) 3036280d235SMichel Lespinasse * / \ / \ 3046280d235SMichel Lespinasse * N S --> N Sl 3056280d235SMichel Lespinasse * / \ \ 3066280d235SMichel Lespinasse * sl Sr s 3076280d235SMichel Lespinasse * \ 3086280d235SMichel Lespinasse * Sr 3096280d235SMichel Lespinasse */ 3106280d235SMichel Lespinasse sibling->rb_left = tmp1 = tmp2->rb_right; 3116280d235SMichel Lespinasse tmp2->rb_right = sibling; 3126280d235SMichel Lespinasse parent->rb_right = tmp2; 3136280d235SMichel Lespinasse if (tmp1) 3146280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3156280d235SMichel Lespinasse RB_BLACK); 316*14b94af0SMichel Lespinasse augment->rotate(sibling, tmp2); 3176280d235SMichel Lespinasse tmp1 = sibling; 3186280d235SMichel Lespinasse sibling = tmp2; 3191da177e4SLinus Torvalds } 3206280d235SMichel Lespinasse /* 3216280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 3226280d235SMichel Lespinasse * (p and sl could be either color here. 3236280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3246280d235SMichel Lespinasse * p's color, and sl keeps its color) 3256280d235SMichel Lespinasse * 3266280d235SMichel Lespinasse * (p) (s) 3276280d235SMichel Lespinasse * / \ / \ 3286280d235SMichel Lespinasse * N S --> P Sr 3296280d235SMichel Lespinasse * / \ / \ 3306280d235SMichel Lespinasse * (sl) sr N (sl) 3316280d235SMichel Lespinasse */ 3326280d235SMichel Lespinasse parent->rb_right = tmp2 = sibling->rb_left; 3336280d235SMichel Lespinasse sibling->rb_left = parent; 3346280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3356280d235SMichel Lespinasse if (tmp2) 3366280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3376280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3386280d235SMichel Lespinasse RB_BLACK); 339*14b94af0SMichel Lespinasse augment->rotate(parent, sibling); 3401da177e4SLinus Torvalds break; 341d6ff1273SMichel Lespinasse } else { 3426280d235SMichel Lespinasse sibling = parent->rb_left; 3436280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3446280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 3456280d235SMichel Lespinasse parent->rb_left = tmp1 = sibling->rb_right; 3466280d235SMichel Lespinasse sibling->rb_right = parent; 3476280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3486280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3496280d235SMichel Lespinasse RB_RED); 350*14b94af0SMichel Lespinasse augment->rotate(parent, sibling); 3516280d235SMichel Lespinasse sibling = tmp1; 3521da177e4SLinus Torvalds } 3536280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3546280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3556280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3566280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3576280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3586280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3596280d235SMichel Lespinasse RB_RED); 36046b6135aSMichel Lespinasse if (rb_is_red(parent)) 36146b6135aSMichel Lespinasse rb_set_black(parent); 36246b6135aSMichel Lespinasse else { 3631da177e4SLinus Torvalds node = parent; 36455a98102SDavid Woodhouse parent = rb_parent(node); 36546b6135aSMichel Lespinasse if (parent) 366e125d147SMichel Lespinasse continue; 3671da177e4SLinus Torvalds } 36846b6135aSMichel Lespinasse break; 36946b6135aSMichel Lespinasse } 3706280d235SMichel Lespinasse /* Case 3 - right rotate at sibling */ 3716280d235SMichel Lespinasse sibling->rb_right = tmp1 = tmp2->rb_left; 3726280d235SMichel Lespinasse tmp2->rb_left = sibling; 3736280d235SMichel Lespinasse parent->rb_left = tmp2; 3746280d235SMichel Lespinasse if (tmp1) 3756280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3766280d235SMichel Lespinasse RB_BLACK); 377*14b94af0SMichel Lespinasse augment->rotate(sibling, tmp2); 3786280d235SMichel Lespinasse tmp1 = sibling; 3796280d235SMichel Lespinasse sibling = tmp2; 3801da177e4SLinus Torvalds } 3816280d235SMichel Lespinasse /* Case 4 - left rotate at parent + color flips */ 3826280d235SMichel Lespinasse parent->rb_left = tmp2 = sibling->rb_right; 3836280d235SMichel Lespinasse sibling->rb_right = parent; 3846280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3856280d235SMichel Lespinasse if (tmp2) 3866280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3876280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3886280d235SMichel Lespinasse RB_BLACK); 389*14b94af0SMichel Lespinasse augment->rotate(parent, sibling); 3901da177e4SLinus Torvalds break; 3911da177e4SLinus Torvalds } 3921da177e4SLinus Torvalds } 3931da177e4SLinus Torvalds } 3941da177e4SLinus Torvalds 395*14b94af0SMichel Lespinasse static __always_inline void 396*14b94af0SMichel Lespinasse __rb_erase(struct rb_node *node, struct rb_root *root, 397*14b94af0SMichel Lespinasse const struct rb_augment_callbacks *augment) 3981da177e4SLinus Torvalds { 39960670b80SMichel Lespinasse struct rb_node *child = node->rb_right, *tmp = node->rb_left; 40046b6135aSMichel Lespinasse struct rb_node *parent, *rebalance; 4014f035ad6SMichel Lespinasse unsigned long pc; 4021da177e4SLinus Torvalds 40360670b80SMichel Lespinasse if (!tmp) { 40446b6135aSMichel Lespinasse /* 40546b6135aSMichel Lespinasse * Case 1: node to erase has no more than 1 child (easy!) 40646b6135aSMichel Lespinasse * 40746b6135aSMichel Lespinasse * Note that if there is one child it must be red due to 5) 40846b6135aSMichel Lespinasse * and node must be black due to 4). We adjust colors locally 40946b6135aSMichel Lespinasse * so as to bypass __rb_erase_color() later on. 41046b6135aSMichel Lespinasse */ 4114f035ad6SMichel Lespinasse pc = node->__rb_parent_color; 4124f035ad6SMichel Lespinasse parent = __rb_parent(pc); 41360670b80SMichel Lespinasse __rb_change_child(node, child, parent, root); 41446b6135aSMichel Lespinasse if (child) { 4154f035ad6SMichel Lespinasse child->__rb_parent_color = pc; 41646b6135aSMichel Lespinasse rebalance = NULL; 4174f035ad6SMichel Lespinasse } else 4184f035ad6SMichel Lespinasse rebalance = __rb_is_black(pc) ? parent : NULL; 419*14b94af0SMichel Lespinasse tmp = parent; 42060670b80SMichel Lespinasse } else if (!child) { 42160670b80SMichel Lespinasse /* Still case 1, but this time the child is node->rb_left */ 4224f035ad6SMichel Lespinasse tmp->__rb_parent_color = pc = node->__rb_parent_color; 4234f035ad6SMichel Lespinasse parent = __rb_parent(pc); 42446b6135aSMichel Lespinasse __rb_change_child(node, tmp, parent, root); 42546b6135aSMichel Lespinasse rebalance = NULL; 426*14b94af0SMichel Lespinasse tmp = parent; 42760670b80SMichel Lespinasse } else { 4284f035ad6SMichel Lespinasse struct rb_node *successor = child, *child2; 4294f035ad6SMichel Lespinasse tmp = child->rb_left; 4304f035ad6SMichel Lespinasse if (!tmp) { 4314f035ad6SMichel Lespinasse /* 4324f035ad6SMichel Lespinasse * Case 2: node's successor is its right child 4334f035ad6SMichel Lespinasse * 4344f035ad6SMichel Lespinasse * (n) (s) 4354f035ad6SMichel Lespinasse * / \ / \ 4364f035ad6SMichel Lespinasse * (x) (s) -> (x) (c) 4374f035ad6SMichel Lespinasse * \ 4384f035ad6SMichel Lespinasse * (c) 4394f035ad6SMichel Lespinasse */ 440*14b94af0SMichel Lespinasse parent = successor; 441*14b94af0SMichel Lespinasse child2 = successor->rb_right; 442*14b94af0SMichel Lespinasse augment->copy(node, successor); 4434c601178SWolfram Strepp } else { 4444f035ad6SMichel Lespinasse /* 4454f035ad6SMichel Lespinasse * Case 3: node's successor is leftmost under 4464f035ad6SMichel Lespinasse * node's right child subtree 4474f035ad6SMichel Lespinasse * 4484f035ad6SMichel Lespinasse * (n) (s) 4494f035ad6SMichel Lespinasse * / \ / \ 4504f035ad6SMichel Lespinasse * (x) (y) -> (x) (y) 4514f035ad6SMichel Lespinasse * / / 4524f035ad6SMichel Lespinasse * (p) (p) 4534f035ad6SMichel Lespinasse * / / 4544f035ad6SMichel Lespinasse * (s) (c) 4554f035ad6SMichel Lespinasse * \ 4564f035ad6SMichel Lespinasse * (c) 4574f035ad6SMichel Lespinasse */ 4584f035ad6SMichel Lespinasse do { 4594f035ad6SMichel Lespinasse parent = successor; 4604f035ad6SMichel Lespinasse successor = tmp; 4614f035ad6SMichel Lespinasse tmp = tmp->rb_left; 4624f035ad6SMichel Lespinasse } while (tmp); 4634f035ad6SMichel Lespinasse parent->rb_left = child2 = successor->rb_right; 4644f035ad6SMichel Lespinasse successor->rb_right = child; 4654f035ad6SMichel Lespinasse rb_set_parent(child, successor); 466*14b94af0SMichel Lespinasse augment->copy(node, successor); 467*14b94af0SMichel Lespinasse augment->propagate(parent, successor); 4684c601178SWolfram Strepp } 4691975e593SDavid Woodhouse 4704f035ad6SMichel Lespinasse successor->rb_left = tmp = node->rb_left; 4714f035ad6SMichel Lespinasse rb_set_parent(tmp, successor); 4724f035ad6SMichel Lespinasse 4734f035ad6SMichel Lespinasse pc = node->__rb_parent_color; 4744f035ad6SMichel Lespinasse tmp = __rb_parent(pc); 4754f035ad6SMichel Lespinasse __rb_change_child(node, successor, tmp, root); 4764f035ad6SMichel Lespinasse if (child2) { 4774f035ad6SMichel Lespinasse successor->__rb_parent_color = pc; 4784f035ad6SMichel Lespinasse rb_set_parent_color(child2, parent, RB_BLACK); 47946b6135aSMichel Lespinasse rebalance = NULL; 48046b6135aSMichel Lespinasse } else { 4814f035ad6SMichel Lespinasse unsigned long pc2 = successor->__rb_parent_color; 4824f035ad6SMichel Lespinasse successor->__rb_parent_color = pc; 4834f035ad6SMichel Lespinasse rebalance = __rb_is_black(pc2) ? parent : NULL; 48446b6135aSMichel Lespinasse } 485*14b94af0SMichel Lespinasse tmp = successor; 4861da177e4SLinus Torvalds } 4871da177e4SLinus Torvalds 488*14b94af0SMichel Lespinasse augment->propagate(tmp, NULL); 48946b6135aSMichel Lespinasse if (rebalance) 490*14b94af0SMichel Lespinasse __rb_erase_color(rebalance, root, augment); 491*14b94af0SMichel Lespinasse } 492*14b94af0SMichel Lespinasse 493*14b94af0SMichel Lespinasse /* 494*14b94af0SMichel Lespinasse * Non-augmented rbtree manipulation functions. 495*14b94af0SMichel Lespinasse * 496*14b94af0SMichel Lespinasse * We use dummy augmented callbacks here, and have the compiler optimize them 497*14b94af0SMichel Lespinasse * out of the rb_insert_color() and rb_erase() function definitions. 498*14b94af0SMichel Lespinasse */ 499*14b94af0SMichel Lespinasse 500*14b94af0SMichel Lespinasse static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} 501*14b94af0SMichel Lespinasse static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} 502*14b94af0SMichel Lespinasse static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} 503*14b94af0SMichel Lespinasse 504*14b94af0SMichel Lespinasse static const struct rb_augment_callbacks dummy_callbacks = { 505*14b94af0SMichel Lespinasse dummy_propagate, dummy_copy, dummy_rotate 506*14b94af0SMichel Lespinasse }; 507*14b94af0SMichel Lespinasse 508*14b94af0SMichel Lespinasse void rb_insert_color(struct rb_node *node, struct rb_root *root) 509*14b94af0SMichel Lespinasse { 510*14b94af0SMichel Lespinasse __rb_insert(node, root, dummy_rotate); 511*14b94af0SMichel Lespinasse } 512*14b94af0SMichel Lespinasse EXPORT_SYMBOL(rb_insert_color); 513*14b94af0SMichel Lespinasse 514*14b94af0SMichel Lespinasse void rb_erase(struct rb_node *node, struct rb_root *root) 515*14b94af0SMichel Lespinasse { 516*14b94af0SMichel Lespinasse __rb_erase(node, root, &dummy_callbacks); 5171da177e4SLinus Torvalds } 5181da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 5191da177e4SLinus Torvalds 520*14b94af0SMichel Lespinasse /* 521*14b94af0SMichel Lespinasse * Augmented rbtree manipulation functions. 522*14b94af0SMichel Lespinasse * 523*14b94af0SMichel Lespinasse * This instantiates the same __always_inline functions as in the non-augmented 524*14b94af0SMichel Lespinasse * case, but this time with user-defined callbacks. 525*14b94af0SMichel Lespinasse */ 526*14b94af0SMichel Lespinasse 527*14b94af0SMichel Lespinasse void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 528*14b94af0SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 529*14b94af0SMichel Lespinasse { 530*14b94af0SMichel Lespinasse __rb_insert(node, root, augment_rotate); 531*14b94af0SMichel Lespinasse } 532*14b94af0SMichel Lespinasse EXPORT_SYMBOL(__rb_insert_augmented); 533*14b94af0SMichel Lespinasse 534*14b94af0SMichel Lespinasse void rb_erase_augmented(struct rb_node *node, struct rb_root *root, 535*14b94af0SMichel Lespinasse const struct rb_augment_callbacks *augment) 536*14b94af0SMichel Lespinasse { 537*14b94af0SMichel Lespinasse __rb_erase(node, root, augment); 538*14b94af0SMichel Lespinasse } 539*14b94af0SMichel Lespinasse EXPORT_SYMBOL(rb_erase_augmented); 540*14b94af0SMichel Lespinasse 541b945d6b2SPeter Zijlstra static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) 542b945d6b2SPeter Zijlstra { 543b945d6b2SPeter Zijlstra struct rb_node *parent; 544b945d6b2SPeter Zijlstra 545b945d6b2SPeter Zijlstra up: 546b945d6b2SPeter Zijlstra func(node, data); 547b945d6b2SPeter Zijlstra parent = rb_parent(node); 548b945d6b2SPeter Zijlstra if (!parent) 549b945d6b2SPeter Zijlstra return; 550b945d6b2SPeter Zijlstra 551b945d6b2SPeter Zijlstra if (node == parent->rb_left && parent->rb_right) 552b945d6b2SPeter Zijlstra func(parent->rb_right, data); 553b945d6b2SPeter Zijlstra else if (parent->rb_left) 554b945d6b2SPeter Zijlstra func(parent->rb_left, data); 555b945d6b2SPeter Zijlstra 556b945d6b2SPeter Zijlstra node = parent; 557b945d6b2SPeter Zijlstra goto up; 558b945d6b2SPeter Zijlstra } 559b945d6b2SPeter Zijlstra 560b945d6b2SPeter Zijlstra /* 561b945d6b2SPeter Zijlstra * after inserting @node into the tree, update the tree to account for 562b945d6b2SPeter Zijlstra * both the new entry and any damage done by rebalance 563b945d6b2SPeter Zijlstra */ 564b945d6b2SPeter Zijlstra void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) 565b945d6b2SPeter Zijlstra { 566b945d6b2SPeter Zijlstra if (node->rb_left) 567b945d6b2SPeter Zijlstra node = node->rb_left; 568b945d6b2SPeter Zijlstra else if (node->rb_right) 569b945d6b2SPeter Zijlstra node = node->rb_right; 570b945d6b2SPeter Zijlstra 571b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 572b945d6b2SPeter Zijlstra } 5730b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_insert); 574b945d6b2SPeter Zijlstra 575b945d6b2SPeter Zijlstra /* 576b945d6b2SPeter Zijlstra * before removing the node, find the deepest node on the rebalance path 577b945d6b2SPeter Zijlstra * that will still be there after @node gets removed 578b945d6b2SPeter Zijlstra */ 579b945d6b2SPeter Zijlstra struct rb_node *rb_augment_erase_begin(struct rb_node *node) 580b945d6b2SPeter Zijlstra { 581b945d6b2SPeter Zijlstra struct rb_node *deepest; 582b945d6b2SPeter Zijlstra 583b945d6b2SPeter Zijlstra if (!node->rb_right && !node->rb_left) 584b945d6b2SPeter Zijlstra deepest = rb_parent(node); 585b945d6b2SPeter Zijlstra else if (!node->rb_right) 586b945d6b2SPeter Zijlstra deepest = node->rb_left; 587b945d6b2SPeter Zijlstra else if (!node->rb_left) 588b945d6b2SPeter Zijlstra deepest = node->rb_right; 589b945d6b2SPeter Zijlstra else { 590b945d6b2SPeter Zijlstra deepest = rb_next(node); 591b945d6b2SPeter Zijlstra if (deepest->rb_right) 592b945d6b2SPeter Zijlstra deepest = deepest->rb_right; 593b945d6b2SPeter Zijlstra else if (rb_parent(deepest) != node) 594b945d6b2SPeter Zijlstra deepest = rb_parent(deepest); 595b945d6b2SPeter Zijlstra } 596b945d6b2SPeter Zijlstra 597b945d6b2SPeter Zijlstra return deepest; 598b945d6b2SPeter Zijlstra } 5990b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_begin); 600b945d6b2SPeter Zijlstra 601b945d6b2SPeter Zijlstra /* 602b945d6b2SPeter Zijlstra * after removal, update the tree to account for the removed entry 603b945d6b2SPeter Zijlstra * and any rebalance damage. 604b945d6b2SPeter Zijlstra */ 605b945d6b2SPeter Zijlstra void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) 606b945d6b2SPeter Zijlstra { 607b945d6b2SPeter Zijlstra if (node) 608b945d6b2SPeter Zijlstra rb_augment_path(node, func, data); 609b945d6b2SPeter Zijlstra } 6100b6bb66dSAndreas Gruenbacher EXPORT_SYMBOL(rb_augment_erase_end); 611b945d6b2SPeter Zijlstra 6121da177e4SLinus Torvalds /* 6131da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 6141da177e4SLinus Torvalds */ 615f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 6161da177e4SLinus Torvalds { 6171da177e4SLinus Torvalds struct rb_node *n; 6181da177e4SLinus Torvalds 6191da177e4SLinus Torvalds n = root->rb_node; 6201da177e4SLinus Torvalds if (!n) 6211da177e4SLinus Torvalds return NULL; 6221da177e4SLinus Torvalds while (n->rb_left) 6231da177e4SLinus Torvalds n = n->rb_left; 6241da177e4SLinus Torvalds return n; 6251da177e4SLinus Torvalds } 6261da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 6271da177e4SLinus Torvalds 628f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 6291da177e4SLinus Torvalds { 6301da177e4SLinus Torvalds struct rb_node *n; 6311da177e4SLinus Torvalds 6321da177e4SLinus Torvalds n = root->rb_node; 6331da177e4SLinus Torvalds if (!n) 6341da177e4SLinus Torvalds return NULL; 6351da177e4SLinus Torvalds while (n->rb_right) 6361da177e4SLinus Torvalds n = n->rb_right; 6371da177e4SLinus Torvalds return n; 6381da177e4SLinus Torvalds } 6391da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 6401da177e4SLinus Torvalds 641f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 6421da177e4SLinus Torvalds { 64355a98102SDavid Woodhouse struct rb_node *parent; 64455a98102SDavid Woodhouse 6454c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 64610fd48f2SJens Axboe return NULL; 64710fd48f2SJens Axboe 6487ce6ff9eSMichel Lespinasse /* 6497ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 6507ce6ff9eSMichel Lespinasse * as we can. 6517ce6ff9eSMichel Lespinasse */ 6521da177e4SLinus Torvalds if (node->rb_right) { 6531da177e4SLinus Torvalds node = node->rb_right; 6541da177e4SLinus Torvalds while (node->rb_left) 6551da177e4SLinus Torvalds node=node->rb_left; 656f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 6571da177e4SLinus Torvalds } 6581da177e4SLinus Torvalds 6597ce6ff9eSMichel Lespinasse /* 6607ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 6617ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 6627ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 6637ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 6647ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 6657ce6ff9eSMichel Lespinasse */ 66655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 66755a98102SDavid Woodhouse node = parent; 6681da177e4SLinus Torvalds 66955a98102SDavid Woodhouse return parent; 6701da177e4SLinus Torvalds } 6711da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 6721da177e4SLinus Torvalds 673f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 6741da177e4SLinus Torvalds { 67555a98102SDavid Woodhouse struct rb_node *parent; 67655a98102SDavid Woodhouse 6774c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 67810fd48f2SJens Axboe return NULL; 67910fd48f2SJens Axboe 6807ce6ff9eSMichel Lespinasse /* 6817ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 6827ce6ff9eSMichel Lespinasse * as we can. 6837ce6ff9eSMichel Lespinasse */ 6841da177e4SLinus Torvalds if (node->rb_left) { 6851da177e4SLinus Torvalds node = node->rb_left; 6861da177e4SLinus Torvalds while (node->rb_right) 6871da177e4SLinus Torvalds node=node->rb_right; 688f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 6891da177e4SLinus Torvalds } 6901da177e4SLinus Torvalds 6917ce6ff9eSMichel Lespinasse /* 6927ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 6937ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 6947ce6ff9eSMichel Lespinasse */ 69555a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 69655a98102SDavid Woodhouse node = parent; 6971da177e4SLinus Torvalds 69855a98102SDavid Woodhouse return parent; 6991da177e4SLinus Torvalds } 7001da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 7011da177e4SLinus Torvalds 7021da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 7031da177e4SLinus Torvalds struct rb_root *root) 7041da177e4SLinus Torvalds { 70555a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 7061da177e4SLinus Torvalds 7071da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 7087abc704aSMichel Lespinasse __rb_change_child(victim, new, parent, root); 7091da177e4SLinus Torvalds if (victim->rb_left) 71055a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 7111da177e4SLinus Torvalds if (victim->rb_right) 71255a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 7131da177e4SLinus Torvalds 7141da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 7151da177e4SLinus Torvalds *new = *victim; 7161da177e4SLinus Torvalds } 7171da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 718