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 249c079addSMichel Lespinasse #include <linux/rbtree_augmented.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 47d72da4a4SPeter Zijlstra /* 48d72da4a4SPeter Zijlstra * Notes on lockless lookups: 49d72da4a4SPeter Zijlstra * 50d72da4a4SPeter Zijlstra * All stores to the tree structure (rb_left and rb_right) must be done using 51d72da4a4SPeter Zijlstra * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the 52d72da4a4SPeter Zijlstra * tree structure as seen in program order. 53d72da4a4SPeter Zijlstra * 54d72da4a4SPeter Zijlstra * These two requirements will allow lockless iteration of the tree -- not 55d72da4a4SPeter Zijlstra * correct iteration mind you, tree rotations are not atomic so a lookup might 56d72da4a4SPeter Zijlstra * miss entire subtrees. 57d72da4a4SPeter Zijlstra * 58d72da4a4SPeter Zijlstra * But they do guarantee that any such traversal will only see valid elements 59d72da4a4SPeter Zijlstra * and that it will indeed complete -- does not get stuck in a loop. 60d72da4a4SPeter Zijlstra * 61d72da4a4SPeter Zijlstra * It also guarantees that if the lookup returns an element it is the 'correct' 62d72da4a4SPeter Zijlstra * one. But not returning an element does _NOT_ mean it's not present. 63d72da4a4SPeter Zijlstra * 64d72da4a4SPeter Zijlstra * NOTE: 65d72da4a4SPeter Zijlstra * 66d72da4a4SPeter Zijlstra * Stores to __rb_parent_color are not important for simple lookups so those 67d72da4a4SPeter Zijlstra * are left undone as of now. Nor did I check for loops involving parent 68d72da4a4SPeter Zijlstra * pointers. 69d72da4a4SPeter Zijlstra */ 70d72da4a4SPeter Zijlstra 7146b6135aSMichel Lespinasse static inline void rb_set_black(struct rb_node *rb) 7246b6135aSMichel Lespinasse { 7346b6135aSMichel Lespinasse rb->__rb_parent_color |= RB_BLACK; 7446b6135aSMichel Lespinasse } 7546b6135aSMichel Lespinasse 765bc9188aSMichel Lespinasse static inline struct rb_node *rb_red_parent(struct rb_node *red) 775bc9188aSMichel Lespinasse { 785bc9188aSMichel Lespinasse return (struct rb_node *)red->__rb_parent_color; 795bc9188aSMichel Lespinasse } 805bc9188aSMichel Lespinasse 815bc9188aSMichel Lespinasse /* 825bc9188aSMichel Lespinasse * Helper function for rotations: 835bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 845bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 855bc9188aSMichel Lespinasse */ 865bc9188aSMichel Lespinasse static inline void 875bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 885bc9188aSMichel Lespinasse struct rb_root *root, int color) 895bc9188aSMichel Lespinasse { 905bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 915bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 925bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 937abc704aSMichel Lespinasse __rb_change_child(old, new, parent, root); 945bc9188aSMichel Lespinasse } 955bc9188aSMichel Lespinasse 9614b94af0SMichel Lespinasse static __always_inline void 9714b94af0SMichel Lespinasse __rb_insert(struct rb_node *node, struct rb_root *root, 98cd9e61edSDavidlohr Bueso bool newleft, struct rb_node **leftmost, 9914b94af0SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 1001da177e4SLinus Torvalds { 1015bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 1021da177e4SLinus Torvalds 103cd9e61edSDavidlohr Bueso if (newleft) 104cd9e61edSDavidlohr Bueso *leftmost = node; 105cd9e61edSDavidlohr Bueso 1066d58452dSMichel Lespinasse while (true) { 1076d58452dSMichel Lespinasse /* 1082aadf7fcSDavidlohr Bueso * Loop invariant: node is red. 1096d58452dSMichel Lespinasse */ 1102aadf7fcSDavidlohr Bueso if (unlikely(!parent)) { 1112aadf7fcSDavidlohr Bueso /* 1122aadf7fcSDavidlohr Bueso * The inserted node is root. Either this is the 1132aadf7fcSDavidlohr Bueso * first node, or we recursed at Case 1 below and 1142aadf7fcSDavidlohr Bueso * are no longer violating 4). 1152aadf7fcSDavidlohr Bueso */ 1165bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1176d58452dSMichel Lespinasse break; 1182aadf7fcSDavidlohr Bueso } 1192aadf7fcSDavidlohr Bueso 1202aadf7fcSDavidlohr Bueso /* 1212aadf7fcSDavidlohr Bueso * If there is a black parent, we are done. 1222aadf7fcSDavidlohr Bueso * Otherwise, take some corrective action as, 1232aadf7fcSDavidlohr Bueso * per 4), we don't want a red root or two 1242aadf7fcSDavidlohr Bueso * consecutive red nodes. 1252aadf7fcSDavidlohr Bueso */ 1262aadf7fcSDavidlohr Bueso if(rb_is_black(parent)) 1276d58452dSMichel Lespinasse break; 1286d58452dSMichel Lespinasse 1295bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1301da177e4SLinus Torvalds 1315bc9188aSMichel Lespinasse tmp = gparent->rb_right; 13259633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1335bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1345bc9188aSMichel Lespinasse /* 135*35dc67d7SDavidlohr Bueso * Case 1 - node's uncle is red (color flips). 1365bc9188aSMichel Lespinasse * 1375bc9188aSMichel Lespinasse * G g 1385bc9188aSMichel Lespinasse * / \ / \ 1395bc9188aSMichel Lespinasse * p u --> P U 1405bc9188aSMichel Lespinasse * / / 1411b9c53e8SWei Yang * n n 1425bc9188aSMichel Lespinasse * 1435bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1445bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1455bc9188aSMichel Lespinasse * at g. 1465bc9188aSMichel Lespinasse */ 1475bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1485bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1491da177e4SLinus Torvalds node = gparent; 1505bc9188aSMichel Lespinasse parent = rb_parent(node); 1515bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1521da177e4SLinus Torvalds continue; 1531da177e4SLinus Torvalds } 1541da177e4SLinus Torvalds 15559633abfSMichel Lespinasse tmp = parent->rb_right; 15659633abfSMichel Lespinasse if (node == tmp) { 1575bc9188aSMichel Lespinasse /* 158*35dc67d7SDavidlohr Bueso * Case 2 - node's uncle is black and node is 159*35dc67d7SDavidlohr Bueso * the parent's right child (left rotate at parent). 1605bc9188aSMichel Lespinasse * 1615bc9188aSMichel Lespinasse * G G 1625bc9188aSMichel Lespinasse * / \ / \ 1635bc9188aSMichel Lespinasse * p U --> n U 1645bc9188aSMichel Lespinasse * \ / 1655bc9188aSMichel Lespinasse * n p 1665bc9188aSMichel Lespinasse * 1675bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1685bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1695bc9188aSMichel Lespinasse */ 170d72da4a4SPeter Zijlstra tmp = node->rb_left; 171d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp); 172d72da4a4SPeter Zijlstra WRITE_ONCE(node->rb_left, parent); 1735bc9188aSMichel Lespinasse if (tmp) 1745bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1755bc9188aSMichel Lespinasse RB_BLACK); 1765bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 17714b94af0SMichel Lespinasse augment_rotate(parent, node); 1781da177e4SLinus Torvalds parent = node; 17959633abfSMichel Lespinasse tmp = node->rb_right; 1801da177e4SLinus Torvalds } 1811da177e4SLinus Torvalds 1825bc9188aSMichel Lespinasse /* 183*35dc67d7SDavidlohr Bueso * Case 3 - node's uncle is black and node is 184*35dc67d7SDavidlohr Bueso * the parent's left child (right rotate at gparent). 1855bc9188aSMichel Lespinasse * 1865bc9188aSMichel Lespinasse * G P 1875bc9188aSMichel Lespinasse * / \ / \ 1885bc9188aSMichel Lespinasse * p U --> n g 1895bc9188aSMichel Lespinasse * / \ 1905bc9188aSMichel Lespinasse * n U 1915bc9188aSMichel Lespinasse */ 192d72da4a4SPeter Zijlstra WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ 193d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, gparent); 1945bc9188aSMichel Lespinasse if (tmp) 1955bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1965bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 19714b94af0SMichel Lespinasse augment_rotate(gparent, parent); 1981f052865SMichel Lespinasse break; 1991da177e4SLinus Torvalds } else { 2005bc9188aSMichel Lespinasse tmp = gparent->rb_left; 2015bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 2025bc9188aSMichel Lespinasse /* Case 1 - color flips */ 2035bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2045bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 2051da177e4SLinus Torvalds node = gparent; 2065bc9188aSMichel Lespinasse parent = rb_parent(node); 2075bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 2081da177e4SLinus Torvalds continue; 2091da177e4SLinus Torvalds } 2101da177e4SLinus Torvalds 21159633abfSMichel Lespinasse tmp = parent->rb_left; 21259633abfSMichel Lespinasse if (node == tmp) { 2135bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 214d72da4a4SPeter Zijlstra tmp = node->rb_right; 215d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp); 216d72da4a4SPeter Zijlstra WRITE_ONCE(node->rb_right, parent); 2175bc9188aSMichel Lespinasse if (tmp) 2185bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2195bc9188aSMichel Lespinasse RB_BLACK); 2205bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 22114b94af0SMichel Lespinasse augment_rotate(parent, node); 2221da177e4SLinus Torvalds parent = node; 22359633abfSMichel Lespinasse tmp = node->rb_left; 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds 2265bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 227d72da4a4SPeter Zijlstra WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ 228d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, gparent); 2295bc9188aSMichel Lespinasse if (tmp) 2305bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2315bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 23214b94af0SMichel Lespinasse augment_rotate(gparent, parent); 2331f052865SMichel Lespinasse break; 2341da177e4SLinus Torvalds } 2351da177e4SLinus Torvalds } 2361da177e4SLinus Torvalds } 2371da177e4SLinus Torvalds 2383cb7a563SMichel Lespinasse /* 2393cb7a563SMichel Lespinasse * Inline version for rb_erase() use - we want to be able to inline 2403cb7a563SMichel Lespinasse * and eliminate the dummy_rotate callback there 2413cb7a563SMichel Lespinasse */ 2423cb7a563SMichel Lespinasse static __always_inline void 2433cb7a563SMichel Lespinasse ____rb_erase_color(struct rb_node *parent, struct rb_root *root, 2449c079addSMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 2451da177e4SLinus Torvalds { 24646b6135aSMichel Lespinasse struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 2471da177e4SLinus Torvalds 248d6ff1273SMichel Lespinasse while (true) { 249d6ff1273SMichel Lespinasse /* 25046b6135aSMichel Lespinasse * Loop invariants: 25146b6135aSMichel Lespinasse * - node is black (or NULL on first iteration) 25246b6135aSMichel Lespinasse * - node is not the root (parent is not NULL) 25346b6135aSMichel Lespinasse * - All leaf paths going through parent and node have a 254d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 255d6ff1273SMichel Lespinasse */ 2566280d235SMichel Lespinasse sibling = parent->rb_right; 25759633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2586280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2596280d235SMichel Lespinasse /* 2606280d235SMichel Lespinasse * Case 1 - left rotate at parent 2616280d235SMichel Lespinasse * 2626280d235SMichel Lespinasse * P S 2636280d235SMichel Lespinasse * / \ / \ 2646280d235SMichel Lespinasse * N s --> p Sr 2656280d235SMichel Lespinasse * / \ / \ 2666280d235SMichel Lespinasse * Sl Sr N Sl 2676280d235SMichel Lespinasse */ 268d72da4a4SPeter Zijlstra tmp1 = sibling->rb_left; 269d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp1); 270d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_left, parent); 2716280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2726280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2736280d235SMichel Lespinasse RB_RED); 2749c079addSMichel Lespinasse augment_rotate(parent, sibling); 2756280d235SMichel Lespinasse sibling = tmp1; 2761da177e4SLinus Torvalds } 2776280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2786280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2796280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2806280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2816280d235SMichel Lespinasse /* 2826280d235SMichel Lespinasse * Case 2 - sibling color flip 2836280d235SMichel Lespinasse * (p could be either color here) 2846280d235SMichel Lespinasse * 2856280d235SMichel Lespinasse * (p) (p) 2866280d235SMichel Lespinasse * / \ / \ 2876280d235SMichel Lespinasse * N S --> N s 2886280d235SMichel Lespinasse * / \ / \ 2896280d235SMichel Lespinasse * Sl Sr Sl Sr 2906280d235SMichel Lespinasse * 29146b6135aSMichel Lespinasse * This leaves us violating 5) which 29246b6135aSMichel Lespinasse * can be fixed by flipping p to black 29346b6135aSMichel Lespinasse * if it was red, or by recursing at p. 29446b6135aSMichel Lespinasse * p is red when coming from Case 1. 2956280d235SMichel Lespinasse */ 2966280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2976280d235SMichel Lespinasse RB_RED); 29846b6135aSMichel Lespinasse if (rb_is_red(parent)) 29946b6135aSMichel Lespinasse rb_set_black(parent); 30046b6135aSMichel Lespinasse else { 3011da177e4SLinus Torvalds node = parent; 30255a98102SDavid Woodhouse parent = rb_parent(node); 30346b6135aSMichel Lespinasse if (parent) 304e125d147SMichel Lespinasse continue; 3051da177e4SLinus Torvalds } 30646b6135aSMichel Lespinasse break; 30746b6135aSMichel Lespinasse } 3086280d235SMichel Lespinasse /* 3096280d235SMichel Lespinasse * Case 3 - right rotate at sibling 3106280d235SMichel Lespinasse * (p could be either color here) 3116280d235SMichel Lespinasse * 3126280d235SMichel Lespinasse * (p) (p) 3136280d235SMichel Lespinasse * / \ / \ 314ce093a04SJie Chen * N S --> N sl 3156280d235SMichel Lespinasse * / \ \ 316ce093a04SJie Chen * sl Sr S 317ce093a04SJie Chen * \ 318ce093a04SJie Chen * Sr 319ce093a04SJie Chen * 320ce093a04SJie Chen * Note: p might be red, and then both 321ce093a04SJie Chen * p and sl are red after rotation(which 322ce093a04SJie Chen * breaks property 4). This is fixed in 323ce093a04SJie Chen * Case 4 (in __rb_rotate_set_parents() 324ce093a04SJie Chen * which set sl the color of p 325ce093a04SJie Chen * and set p RB_BLACK) 326ce093a04SJie Chen * 327ce093a04SJie Chen * (p) (sl) 328ce093a04SJie Chen * / \ / \ 329ce093a04SJie Chen * N sl --> P S 330ce093a04SJie Chen * \ / \ 331ce093a04SJie Chen * S N Sr 3326280d235SMichel Lespinasse * \ 3336280d235SMichel Lespinasse * Sr 3346280d235SMichel Lespinasse */ 335d72da4a4SPeter Zijlstra tmp1 = tmp2->rb_right; 336d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_left, tmp1); 337d72da4a4SPeter Zijlstra WRITE_ONCE(tmp2->rb_right, sibling); 338d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp2); 3396280d235SMichel Lespinasse if (tmp1) 3406280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3416280d235SMichel Lespinasse RB_BLACK); 3429c079addSMichel Lespinasse augment_rotate(sibling, tmp2); 3436280d235SMichel Lespinasse tmp1 = sibling; 3446280d235SMichel Lespinasse sibling = tmp2; 3451da177e4SLinus Torvalds } 3466280d235SMichel Lespinasse /* 3476280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 3486280d235SMichel Lespinasse * (p and sl could be either color here. 3496280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3506280d235SMichel Lespinasse * p's color, and sl keeps its color) 3516280d235SMichel Lespinasse * 3526280d235SMichel Lespinasse * (p) (s) 3536280d235SMichel Lespinasse * / \ / \ 3546280d235SMichel Lespinasse * N S --> P Sr 3556280d235SMichel Lespinasse * / \ / \ 3566280d235SMichel Lespinasse * (sl) sr N (sl) 3576280d235SMichel Lespinasse */ 358d72da4a4SPeter Zijlstra tmp2 = sibling->rb_left; 359d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp2); 360d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_left, parent); 3616280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3626280d235SMichel Lespinasse if (tmp2) 3636280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3646280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3656280d235SMichel Lespinasse RB_BLACK); 3669c079addSMichel Lespinasse augment_rotate(parent, sibling); 3671da177e4SLinus Torvalds break; 368d6ff1273SMichel Lespinasse } else { 3696280d235SMichel Lespinasse sibling = parent->rb_left; 3706280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3716280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 372d72da4a4SPeter Zijlstra tmp1 = sibling->rb_right; 373d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp1); 374d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_right, parent); 3756280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3766280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3776280d235SMichel Lespinasse RB_RED); 3789c079addSMichel Lespinasse augment_rotate(parent, sibling); 3796280d235SMichel Lespinasse sibling = tmp1; 3801da177e4SLinus Torvalds } 3816280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3826280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3836280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3846280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3856280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3866280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3876280d235SMichel Lespinasse RB_RED); 38846b6135aSMichel Lespinasse if (rb_is_red(parent)) 38946b6135aSMichel Lespinasse rb_set_black(parent); 39046b6135aSMichel Lespinasse else { 3911da177e4SLinus Torvalds node = parent; 39255a98102SDavid Woodhouse parent = rb_parent(node); 39346b6135aSMichel Lespinasse if (parent) 394e125d147SMichel Lespinasse continue; 3951da177e4SLinus Torvalds } 39646b6135aSMichel Lespinasse break; 39746b6135aSMichel Lespinasse } 398ce093a04SJie Chen /* Case 3 - left rotate at sibling */ 399d72da4a4SPeter Zijlstra tmp1 = tmp2->rb_left; 400d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_right, tmp1); 401d72da4a4SPeter Zijlstra WRITE_ONCE(tmp2->rb_left, sibling); 402d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp2); 4036280d235SMichel Lespinasse if (tmp1) 4046280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 4056280d235SMichel Lespinasse RB_BLACK); 4069c079addSMichel Lespinasse augment_rotate(sibling, tmp2); 4076280d235SMichel Lespinasse tmp1 = sibling; 4086280d235SMichel Lespinasse sibling = tmp2; 4091da177e4SLinus Torvalds } 410ce093a04SJie Chen /* Case 4 - right rotate at parent + color flips */ 411d72da4a4SPeter Zijlstra tmp2 = sibling->rb_right; 412d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp2); 413d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_right, parent); 4146280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 4156280d235SMichel Lespinasse if (tmp2) 4166280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 4176280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 4186280d235SMichel Lespinasse RB_BLACK); 4199c079addSMichel Lespinasse augment_rotate(parent, sibling); 4201da177e4SLinus Torvalds break; 4211da177e4SLinus Torvalds } 4221da177e4SLinus Torvalds } 4231da177e4SLinus Torvalds } 4243cb7a563SMichel Lespinasse 4253cb7a563SMichel Lespinasse /* Non-inline version for rb_erase_augmented() use */ 4263cb7a563SMichel Lespinasse void __rb_erase_color(struct rb_node *parent, struct rb_root *root, 4273cb7a563SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 4283cb7a563SMichel Lespinasse { 4293cb7a563SMichel Lespinasse ____rb_erase_color(parent, root, augment_rotate); 4303cb7a563SMichel Lespinasse } 4319c079addSMichel Lespinasse EXPORT_SYMBOL(__rb_erase_color); 43214b94af0SMichel Lespinasse 43314b94af0SMichel Lespinasse /* 43414b94af0SMichel Lespinasse * Non-augmented rbtree manipulation functions. 43514b94af0SMichel Lespinasse * 43614b94af0SMichel Lespinasse * We use dummy augmented callbacks here, and have the compiler optimize them 43714b94af0SMichel Lespinasse * out of the rb_insert_color() and rb_erase() function definitions. 43814b94af0SMichel Lespinasse */ 43914b94af0SMichel Lespinasse 44014b94af0SMichel Lespinasse static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} 44114b94af0SMichel Lespinasse static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} 44214b94af0SMichel Lespinasse static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} 44314b94af0SMichel Lespinasse 44414b94af0SMichel Lespinasse static const struct rb_augment_callbacks dummy_callbacks = { 445f231aebfSKees Cook .propagate = dummy_propagate, 446f231aebfSKees Cook .copy = dummy_copy, 447f231aebfSKees Cook .rotate = dummy_rotate 44814b94af0SMichel Lespinasse }; 44914b94af0SMichel Lespinasse 45014b94af0SMichel Lespinasse void rb_insert_color(struct rb_node *node, struct rb_root *root) 45114b94af0SMichel Lespinasse { 452cd9e61edSDavidlohr Bueso __rb_insert(node, root, false, NULL, dummy_rotate); 45314b94af0SMichel Lespinasse } 45414b94af0SMichel Lespinasse EXPORT_SYMBOL(rb_insert_color); 45514b94af0SMichel Lespinasse 45614b94af0SMichel Lespinasse void rb_erase(struct rb_node *node, struct rb_root *root) 45714b94af0SMichel Lespinasse { 4583cb7a563SMichel Lespinasse struct rb_node *rebalance; 459cd9e61edSDavidlohr Bueso rebalance = __rb_erase_augmented(node, root, 460cd9e61edSDavidlohr Bueso NULL, &dummy_callbacks); 4613cb7a563SMichel Lespinasse if (rebalance) 4623cb7a563SMichel Lespinasse ____rb_erase_color(rebalance, root, dummy_rotate); 4631da177e4SLinus Torvalds } 4641da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4651da177e4SLinus Torvalds 466cd9e61edSDavidlohr Bueso void rb_insert_color_cached(struct rb_node *node, 467cd9e61edSDavidlohr Bueso struct rb_root_cached *root, bool leftmost) 468cd9e61edSDavidlohr Bueso { 469cd9e61edSDavidlohr Bueso __rb_insert(node, &root->rb_root, leftmost, 470cd9e61edSDavidlohr Bueso &root->rb_leftmost, dummy_rotate); 471cd9e61edSDavidlohr Bueso } 472cd9e61edSDavidlohr Bueso EXPORT_SYMBOL(rb_insert_color_cached); 473cd9e61edSDavidlohr Bueso 474cd9e61edSDavidlohr Bueso void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) 475cd9e61edSDavidlohr Bueso { 476cd9e61edSDavidlohr Bueso struct rb_node *rebalance; 477cd9e61edSDavidlohr Bueso rebalance = __rb_erase_augmented(node, &root->rb_root, 478cd9e61edSDavidlohr Bueso &root->rb_leftmost, &dummy_callbacks); 479cd9e61edSDavidlohr Bueso if (rebalance) 480cd9e61edSDavidlohr Bueso ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate); 481cd9e61edSDavidlohr Bueso } 482cd9e61edSDavidlohr Bueso EXPORT_SYMBOL(rb_erase_cached); 483cd9e61edSDavidlohr Bueso 48414b94af0SMichel Lespinasse /* 48514b94af0SMichel Lespinasse * Augmented rbtree manipulation functions. 48614b94af0SMichel Lespinasse * 48714b94af0SMichel Lespinasse * This instantiates the same __always_inline functions as in the non-augmented 48814b94af0SMichel Lespinasse * case, but this time with user-defined callbacks. 48914b94af0SMichel Lespinasse */ 49014b94af0SMichel Lespinasse 49114b94af0SMichel Lespinasse void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 492cd9e61edSDavidlohr Bueso bool newleft, struct rb_node **leftmost, 49314b94af0SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 49414b94af0SMichel Lespinasse { 495cd9e61edSDavidlohr Bueso __rb_insert(node, root, newleft, leftmost, augment_rotate); 49614b94af0SMichel Lespinasse } 49714b94af0SMichel Lespinasse EXPORT_SYMBOL(__rb_insert_augmented); 49814b94af0SMichel Lespinasse 4991da177e4SLinus Torvalds /* 5001da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 5011da177e4SLinus Torvalds */ 502f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 5031da177e4SLinus Torvalds { 5041da177e4SLinus Torvalds struct rb_node *n; 5051da177e4SLinus Torvalds 5061da177e4SLinus Torvalds n = root->rb_node; 5071da177e4SLinus Torvalds if (!n) 5081da177e4SLinus Torvalds return NULL; 5091da177e4SLinus Torvalds while (n->rb_left) 5101da177e4SLinus Torvalds n = n->rb_left; 5111da177e4SLinus Torvalds return n; 5121da177e4SLinus Torvalds } 5131da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 5141da177e4SLinus Torvalds 515f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 5161da177e4SLinus Torvalds { 5171da177e4SLinus Torvalds struct rb_node *n; 5181da177e4SLinus Torvalds 5191da177e4SLinus Torvalds n = root->rb_node; 5201da177e4SLinus Torvalds if (!n) 5211da177e4SLinus Torvalds return NULL; 5221da177e4SLinus Torvalds while (n->rb_right) 5231da177e4SLinus Torvalds n = n->rb_right; 5241da177e4SLinus Torvalds return n; 5251da177e4SLinus Torvalds } 5261da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5271da177e4SLinus Torvalds 528f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5291da177e4SLinus Torvalds { 53055a98102SDavid Woodhouse struct rb_node *parent; 53155a98102SDavid Woodhouse 5324c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 53310fd48f2SJens Axboe return NULL; 53410fd48f2SJens Axboe 5357ce6ff9eSMichel Lespinasse /* 5367ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 5377ce6ff9eSMichel Lespinasse * as we can. 5387ce6ff9eSMichel Lespinasse */ 5391da177e4SLinus Torvalds if (node->rb_right) { 5401da177e4SLinus Torvalds node = node->rb_right; 5411da177e4SLinus Torvalds while (node->rb_left) 5421da177e4SLinus Torvalds node=node->rb_left; 543f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5441da177e4SLinus Torvalds } 5451da177e4SLinus Torvalds 5467ce6ff9eSMichel Lespinasse /* 5477ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 5487ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 5497ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 5507ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 5517ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 5527ce6ff9eSMichel Lespinasse */ 55355a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 55455a98102SDavid Woodhouse node = parent; 5551da177e4SLinus Torvalds 55655a98102SDavid Woodhouse return parent; 5571da177e4SLinus Torvalds } 5581da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 5591da177e4SLinus Torvalds 560f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 5611da177e4SLinus Torvalds { 56255a98102SDavid Woodhouse struct rb_node *parent; 56355a98102SDavid Woodhouse 5644c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 56510fd48f2SJens Axboe return NULL; 56610fd48f2SJens Axboe 5677ce6ff9eSMichel Lespinasse /* 5687ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 5697ce6ff9eSMichel Lespinasse * as we can. 5707ce6ff9eSMichel Lespinasse */ 5711da177e4SLinus Torvalds if (node->rb_left) { 5721da177e4SLinus Torvalds node = node->rb_left; 5731da177e4SLinus Torvalds while (node->rb_right) 5741da177e4SLinus Torvalds node=node->rb_right; 575f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5761da177e4SLinus Torvalds } 5771da177e4SLinus Torvalds 5787ce6ff9eSMichel Lespinasse /* 5797ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 5807ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 5817ce6ff9eSMichel Lespinasse */ 58255a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 58355a98102SDavid Woodhouse node = parent; 5841da177e4SLinus Torvalds 58555a98102SDavid Woodhouse return parent; 5861da177e4SLinus Torvalds } 5871da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 5881da177e4SLinus Torvalds 5891da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 5901da177e4SLinus Torvalds struct rb_root *root) 5911da177e4SLinus Torvalds { 59255a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 5931da177e4SLinus Torvalds 594c1adf200SDavid Howells /* Copy the pointers/colour from the victim to the replacement */ 595c1adf200SDavid Howells *new = *victim; 596c1adf200SDavid Howells 5971da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 598c1adf200SDavid Howells if (victim->rb_left) 599c1adf200SDavid Howells rb_set_parent(victim->rb_left, new); 600c1adf200SDavid Howells if (victim->rb_right) 601c1adf200SDavid Howells rb_set_parent(victim->rb_right, new); 6027abc704aSMichel Lespinasse __rb_change_child(victim, new, parent, root); 603c1adf200SDavid Howells } 604c1adf200SDavid Howells EXPORT_SYMBOL(rb_replace_node); 605c1adf200SDavid Howells 606c1adf200SDavid Howells void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, 607c1adf200SDavid Howells struct rb_root *root) 608c1adf200SDavid Howells { 609c1adf200SDavid Howells struct rb_node *parent = rb_parent(victim); 610c1adf200SDavid Howells 611c1adf200SDavid Howells /* Copy the pointers/colour from the victim to the replacement */ 612c1adf200SDavid Howells *new = *victim; 613c1adf200SDavid Howells 614c1adf200SDavid Howells /* Set the surrounding nodes to point to the replacement */ 6151da177e4SLinus Torvalds if (victim->rb_left) 61655a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 6171da177e4SLinus Torvalds if (victim->rb_right) 61855a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 6191da177e4SLinus Torvalds 620c1adf200SDavid Howells /* Set the parent's pointer to the new node last after an RCU barrier 621c1adf200SDavid Howells * so that the pointers onwards are seen to be set correctly when doing 622c1adf200SDavid Howells * an RCU walk over the tree. 623c1adf200SDavid Howells */ 624c1adf200SDavid Howells __rb_change_child_rcu(victim, new, parent, root); 6251da177e4SLinus Torvalds } 626c1adf200SDavid Howells EXPORT_SYMBOL(rb_replace_node_rcu); 6279dee5c51SCody P Schafer 6289dee5c51SCody P Schafer static struct rb_node *rb_left_deepest_node(const struct rb_node *node) 6299dee5c51SCody P Schafer { 6309dee5c51SCody P Schafer for (;;) { 6319dee5c51SCody P Schafer if (node->rb_left) 6329dee5c51SCody P Schafer node = node->rb_left; 6339dee5c51SCody P Schafer else if (node->rb_right) 6349dee5c51SCody P Schafer node = node->rb_right; 6359dee5c51SCody P Schafer else 6369dee5c51SCody P Schafer return (struct rb_node *)node; 6379dee5c51SCody P Schafer } 6389dee5c51SCody P Schafer } 6399dee5c51SCody P Schafer 6409dee5c51SCody P Schafer struct rb_node *rb_next_postorder(const struct rb_node *node) 6419dee5c51SCody P Schafer { 6429dee5c51SCody P Schafer const struct rb_node *parent; 6439dee5c51SCody P Schafer if (!node) 6449dee5c51SCody P Schafer return NULL; 6459dee5c51SCody P Schafer parent = rb_parent(node); 6469dee5c51SCody P Schafer 6479dee5c51SCody P Schafer /* If we're sitting on node, we've already seen our children */ 6489dee5c51SCody P Schafer if (parent && node == parent->rb_left && parent->rb_right) { 6499dee5c51SCody P Schafer /* If we are the parent's left node, go to the parent's right 6509dee5c51SCody P Schafer * node then all the way down to the left */ 6519dee5c51SCody P Schafer return rb_left_deepest_node(parent->rb_right); 6529dee5c51SCody P Schafer } else 6539dee5c51SCody P Schafer /* Otherwise we are the parent's right node, and the parent 6549dee5c51SCody P Schafer * should be next */ 6559dee5c51SCody P Schafer return (struct rb_node *)parent; 6569dee5c51SCody P Schafer } 6579dee5c51SCody P Schafer EXPORT_SYMBOL(rb_next_postorder); 6589dee5c51SCody P Schafer 6599dee5c51SCody P Schafer struct rb_node *rb_first_postorder(const struct rb_root *root) 6609dee5c51SCody P Schafer { 6619dee5c51SCody P Schafer if (!root->rb_node) 6629dee5c51SCody P Schafer return NULL; 6639dee5c51SCody P Schafer 6649dee5c51SCody P Schafer return rb_left_deepest_node(root->rb_node); 6659dee5c51SCody P Schafer } 6669dee5c51SCody P Schafer EXPORT_SYMBOL(rb_first_postorder); 667