1*1a59d1b8SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later 21da177e4SLinus Torvalds /* 31da177e4SLinus Torvalds Red Black Trees 41da177e4SLinus Torvalds (C) 1999 Andrea Arcangeli <andrea@suse.de> 51da177e4SLinus Torvalds (C) 2002 David Woodhouse <dwmw2@infradead.org> 646b6135aSMichel Lespinasse (C) 2012 Michel Lespinasse <walken@google.com> 71da177e4SLinus Torvalds 81da177e4SLinus Torvalds 91da177e4SLinus Torvalds linux/lib/rbtree.c 101da177e4SLinus Torvalds */ 111da177e4SLinus Torvalds 129c079addSMichel Lespinasse #include <linux/rbtree_augmented.h> 138bc3bcc9SPaul Gortmaker #include <linux/export.h> 141da177e4SLinus Torvalds 155bc9188aSMichel Lespinasse /* 165bc9188aSMichel Lespinasse * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree 175bc9188aSMichel Lespinasse * 185bc9188aSMichel Lespinasse * 1) A node is either red or black 195bc9188aSMichel Lespinasse * 2) The root is black 205bc9188aSMichel Lespinasse * 3) All leaves (NULL) are black 215bc9188aSMichel Lespinasse * 4) Both children of every red node are black 225bc9188aSMichel Lespinasse * 5) Every simple path from root to leaves contains the same number 235bc9188aSMichel Lespinasse * of black nodes. 245bc9188aSMichel Lespinasse * 255bc9188aSMichel Lespinasse * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two 265bc9188aSMichel Lespinasse * consecutive red nodes in a path and every red node is therefore followed by 275bc9188aSMichel Lespinasse * a black. So if B is the number of black nodes on every simple path (as per 285bc9188aSMichel Lespinasse * 5), then the longest possible path due to 4 is 2B. 295bc9188aSMichel Lespinasse * 305bc9188aSMichel Lespinasse * We shall indicate color with case, where black nodes are uppercase and red 316280d235SMichel Lespinasse * nodes will be lowercase. Unknown color nodes shall be drawn as red within 326280d235SMichel Lespinasse * parentheses and have some accompanying text comment. 335bc9188aSMichel Lespinasse */ 345bc9188aSMichel Lespinasse 35d72da4a4SPeter Zijlstra /* 36d72da4a4SPeter Zijlstra * Notes on lockless lookups: 37d72da4a4SPeter Zijlstra * 38d72da4a4SPeter Zijlstra * All stores to the tree structure (rb_left and rb_right) must be done using 39d72da4a4SPeter Zijlstra * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the 40d72da4a4SPeter Zijlstra * tree structure as seen in program order. 41d72da4a4SPeter Zijlstra * 42d72da4a4SPeter Zijlstra * These two requirements will allow lockless iteration of the tree -- not 43d72da4a4SPeter Zijlstra * correct iteration mind you, tree rotations are not atomic so a lookup might 44d72da4a4SPeter Zijlstra * miss entire subtrees. 45d72da4a4SPeter Zijlstra * 46d72da4a4SPeter Zijlstra * But they do guarantee that any such traversal will only see valid elements 47d72da4a4SPeter Zijlstra * and that it will indeed complete -- does not get stuck in a loop. 48d72da4a4SPeter Zijlstra * 49d72da4a4SPeter Zijlstra * It also guarantees that if the lookup returns an element it is the 'correct' 50d72da4a4SPeter Zijlstra * one. But not returning an element does _NOT_ mean it's not present. 51d72da4a4SPeter Zijlstra * 52d72da4a4SPeter Zijlstra * NOTE: 53d72da4a4SPeter Zijlstra * 54d72da4a4SPeter Zijlstra * Stores to __rb_parent_color are not important for simple lookups so those 55d72da4a4SPeter Zijlstra * are left undone as of now. Nor did I check for loops involving parent 56d72da4a4SPeter Zijlstra * pointers. 57d72da4a4SPeter Zijlstra */ 58d72da4a4SPeter Zijlstra 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 645bc9188aSMichel Lespinasse static inline struct rb_node *rb_red_parent(struct rb_node *red) 655bc9188aSMichel Lespinasse { 665bc9188aSMichel Lespinasse return (struct rb_node *)red->__rb_parent_color; 675bc9188aSMichel Lespinasse } 685bc9188aSMichel Lespinasse 695bc9188aSMichel Lespinasse /* 705bc9188aSMichel Lespinasse * Helper function for rotations: 715bc9188aSMichel Lespinasse * - old's parent and color get assigned to new 725bc9188aSMichel Lespinasse * - old gets assigned new as a parent and 'color' as a color. 735bc9188aSMichel Lespinasse */ 745bc9188aSMichel Lespinasse static inline void 755bc9188aSMichel Lespinasse __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 765bc9188aSMichel Lespinasse struct rb_root *root, int color) 775bc9188aSMichel Lespinasse { 785bc9188aSMichel Lespinasse struct rb_node *parent = rb_parent(old); 795bc9188aSMichel Lespinasse new->__rb_parent_color = old->__rb_parent_color; 805bc9188aSMichel Lespinasse rb_set_parent_color(old, new, color); 817abc704aSMichel Lespinasse __rb_change_child(old, new, parent, root); 825bc9188aSMichel Lespinasse } 835bc9188aSMichel Lespinasse 8414b94af0SMichel Lespinasse static __always_inline void 8514b94af0SMichel Lespinasse __rb_insert(struct rb_node *node, struct rb_root *root, 86cd9e61edSDavidlohr Bueso bool newleft, struct rb_node **leftmost, 8714b94af0SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 881da177e4SLinus Torvalds { 895bc9188aSMichel Lespinasse struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 901da177e4SLinus Torvalds 91cd9e61edSDavidlohr Bueso if (newleft) 92cd9e61edSDavidlohr Bueso *leftmost = node; 93cd9e61edSDavidlohr Bueso 946d58452dSMichel Lespinasse while (true) { 956d58452dSMichel Lespinasse /* 962aadf7fcSDavidlohr Bueso * Loop invariant: node is red. 976d58452dSMichel Lespinasse */ 982aadf7fcSDavidlohr Bueso if (unlikely(!parent)) { 992aadf7fcSDavidlohr Bueso /* 1002aadf7fcSDavidlohr Bueso * The inserted node is root. Either this is the 1012aadf7fcSDavidlohr Bueso * first node, or we recursed at Case 1 below and 1022aadf7fcSDavidlohr Bueso * are no longer violating 4). 1032aadf7fcSDavidlohr Bueso */ 1045bc9188aSMichel Lespinasse rb_set_parent_color(node, NULL, RB_BLACK); 1056d58452dSMichel Lespinasse break; 1062aadf7fcSDavidlohr Bueso } 1072aadf7fcSDavidlohr Bueso 1082aadf7fcSDavidlohr Bueso /* 1092aadf7fcSDavidlohr Bueso * If there is a black parent, we are done. 1102aadf7fcSDavidlohr Bueso * Otherwise, take some corrective action as, 1112aadf7fcSDavidlohr Bueso * per 4), we don't want a red root or two 1122aadf7fcSDavidlohr Bueso * consecutive red nodes. 1132aadf7fcSDavidlohr Bueso */ 1142aadf7fcSDavidlohr Bueso if(rb_is_black(parent)) 1156d58452dSMichel Lespinasse break; 1166d58452dSMichel Lespinasse 1175bc9188aSMichel Lespinasse gparent = rb_red_parent(parent); 1181da177e4SLinus Torvalds 1195bc9188aSMichel Lespinasse tmp = gparent->rb_right; 12059633abfSMichel Lespinasse if (parent != tmp) { /* parent == gparent->rb_left */ 1215bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1225bc9188aSMichel Lespinasse /* 12335dc67d7SDavidlohr Bueso * Case 1 - node's uncle is red (color flips). 1245bc9188aSMichel Lespinasse * 1255bc9188aSMichel Lespinasse * G g 1265bc9188aSMichel Lespinasse * / \ / \ 1275bc9188aSMichel Lespinasse * p u --> P U 1285bc9188aSMichel Lespinasse * / / 1291b9c53e8SWei Yang * n n 1305bc9188aSMichel Lespinasse * 1315bc9188aSMichel Lespinasse * However, since g's parent might be red, and 1325bc9188aSMichel Lespinasse * 4) does not allow this, we need to recurse 1335bc9188aSMichel Lespinasse * at g. 1345bc9188aSMichel Lespinasse */ 1355bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1365bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1371da177e4SLinus Torvalds node = gparent; 1385bc9188aSMichel Lespinasse parent = rb_parent(node); 1395bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1401da177e4SLinus Torvalds continue; 1411da177e4SLinus Torvalds } 1421da177e4SLinus Torvalds 14359633abfSMichel Lespinasse tmp = parent->rb_right; 14459633abfSMichel Lespinasse if (node == tmp) { 1455bc9188aSMichel Lespinasse /* 14635dc67d7SDavidlohr Bueso * Case 2 - node's uncle is black and node is 14735dc67d7SDavidlohr Bueso * the parent's right child (left rotate at parent). 1485bc9188aSMichel Lespinasse * 1495bc9188aSMichel Lespinasse * G G 1505bc9188aSMichel Lespinasse * / \ / \ 1515bc9188aSMichel Lespinasse * p U --> n U 1525bc9188aSMichel Lespinasse * \ / 1535bc9188aSMichel Lespinasse * n p 1545bc9188aSMichel Lespinasse * 1555bc9188aSMichel Lespinasse * This still leaves us in violation of 4), the 1565bc9188aSMichel Lespinasse * continuation into Case 3 will fix that. 1575bc9188aSMichel Lespinasse */ 158d72da4a4SPeter Zijlstra tmp = node->rb_left; 159d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp); 160d72da4a4SPeter Zijlstra WRITE_ONCE(node->rb_left, parent); 1615bc9188aSMichel Lespinasse if (tmp) 1625bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 1635bc9188aSMichel Lespinasse RB_BLACK); 1645bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 16514b94af0SMichel Lespinasse augment_rotate(parent, node); 1661da177e4SLinus Torvalds parent = node; 16759633abfSMichel Lespinasse tmp = node->rb_right; 1681da177e4SLinus Torvalds } 1691da177e4SLinus Torvalds 1705bc9188aSMichel Lespinasse /* 17135dc67d7SDavidlohr Bueso * Case 3 - node's uncle is black and node is 17235dc67d7SDavidlohr Bueso * the parent's left child (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 */ 180d72da4a4SPeter Zijlstra WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ 181d72da4a4SPeter Zijlstra WRITE_ONCE(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); 18514b94af0SMichel Lespinasse augment_rotate(gparent, parent); 1861f052865SMichel Lespinasse break; 1871da177e4SLinus Torvalds } else { 1885bc9188aSMichel Lespinasse tmp = gparent->rb_left; 1895bc9188aSMichel Lespinasse if (tmp && rb_is_red(tmp)) { 1905bc9188aSMichel Lespinasse /* Case 1 - color flips */ 1915bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 1925bc9188aSMichel Lespinasse rb_set_parent_color(parent, gparent, RB_BLACK); 1931da177e4SLinus Torvalds node = gparent; 1945bc9188aSMichel Lespinasse parent = rb_parent(node); 1955bc9188aSMichel Lespinasse rb_set_parent_color(node, parent, RB_RED); 1961da177e4SLinus Torvalds continue; 1971da177e4SLinus Torvalds } 1981da177e4SLinus Torvalds 19959633abfSMichel Lespinasse tmp = parent->rb_left; 20059633abfSMichel Lespinasse if (node == tmp) { 2015bc9188aSMichel Lespinasse /* Case 2 - right rotate at parent */ 202d72da4a4SPeter Zijlstra tmp = node->rb_right; 203d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp); 204d72da4a4SPeter Zijlstra WRITE_ONCE(node->rb_right, parent); 2055bc9188aSMichel Lespinasse if (tmp) 2065bc9188aSMichel Lespinasse rb_set_parent_color(tmp, parent, 2075bc9188aSMichel Lespinasse RB_BLACK); 2085bc9188aSMichel Lespinasse rb_set_parent_color(parent, node, RB_RED); 20914b94af0SMichel Lespinasse augment_rotate(parent, node); 2101da177e4SLinus Torvalds parent = node; 21159633abfSMichel Lespinasse tmp = node->rb_left; 2121da177e4SLinus Torvalds } 2131da177e4SLinus Torvalds 2145bc9188aSMichel Lespinasse /* Case 3 - left rotate at gparent */ 215d72da4a4SPeter Zijlstra WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ 216d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, gparent); 2175bc9188aSMichel Lespinasse if (tmp) 2185bc9188aSMichel Lespinasse rb_set_parent_color(tmp, gparent, RB_BLACK); 2195bc9188aSMichel Lespinasse __rb_rotate_set_parents(gparent, parent, root, RB_RED); 22014b94af0SMichel Lespinasse augment_rotate(gparent, parent); 2211f052865SMichel Lespinasse break; 2221da177e4SLinus Torvalds } 2231da177e4SLinus Torvalds } 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds 2263cb7a563SMichel Lespinasse /* 2273cb7a563SMichel Lespinasse * Inline version for rb_erase() use - we want to be able to inline 2283cb7a563SMichel Lespinasse * and eliminate the dummy_rotate callback there 2293cb7a563SMichel Lespinasse */ 2303cb7a563SMichel Lespinasse static __always_inline void 2313cb7a563SMichel Lespinasse ____rb_erase_color(struct rb_node *parent, struct rb_root *root, 2329c079addSMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 2331da177e4SLinus Torvalds { 23446b6135aSMichel Lespinasse struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 2351da177e4SLinus Torvalds 236d6ff1273SMichel Lespinasse while (true) { 237d6ff1273SMichel Lespinasse /* 23846b6135aSMichel Lespinasse * Loop invariants: 23946b6135aSMichel Lespinasse * - node is black (or NULL on first iteration) 24046b6135aSMichel Lespinasse * - node is not the root (parent is not NULL) 24146b6135aSMichel Lespinasse * - All leaf paths going through parent and node have a 242d6ff1273SMichel Lespinasse * black node count that is 1 lower than other leaf paths. 243d6ff1273SMichel Lespinasse */ 2446280d235SMichel Lespinasse sibling = parent->rb_right; 24559633abfSMichel Lespinasse if (node != sibling) { /* node == parent->rb_left */ 2466280d235SMichel Lespinasse if (rb_is_red(sibling)) { 2476280d235SMichel Lespinasse /* 2486280d235SMichel Lespinasse * Case 1 - left rotate at parent 2496280d235SMichel Lespinasse * 2506280d235SMichel Lespinasse * P S 2516280d235SMichel Lespinasse * / \ / \ 2526280d235SMichel Lespinasse * N s --> p Sr 2536280d235SMichel Lespinasse * / \ / \ 2546280d235SMichel Lespinasse * Sl Sr N Sl 2556280d235SMichel Lespinasse */ 256d72da4a4SPeter Zijlstra tmp1 = sibling->rb_left; 257d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp1); 258d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_left, parent); 2596280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 2606280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 2616280d235SMichel Lespinasse RB_RED); 2629c079addSMichel Lespinasse augment_rotate(parent, sibling); 2636280d235SMichel Lespinasse sibling = tmp1; 2641da177e4SLinus Torvalds } 2656280d235SMichel Lespinasse tmp1 = sibling->rb_right; 2666280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 2676280d235SMichel Lespinasse tmp2 = sibling->rb_left; 2686280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 2696280d235SMichel Lespinasse /* 2706280d235SMichel Lespinasse * Case 2 - sibling color flip 2716280d235SMichel Lespinasse * (p could be either color here) 2726280d235SMichel Lespinasse * 2736280d235SMichel Lespinasse * (p) (p) 2746280d235SMichel Lespinasse * / \ / \ 2756280d235SMichel Lespinasse * N S --> N s 2766280d235SMichel Lespinasse * / \ / \ 2776280d235SMichel Lespinasse * Sl Sr Sl Sr 2786280d235SMichel Lespinasse * 27946b6135aSMichel Lespinasse * This leaves us violating 5) which 28046b6135aSMichel Lespinasse * can be fixed by flipping p to black 28146b6135aSMichel Lespinasse * if it was red, or by recursing at p. 28246b6135aSMichel Lespinasse * p is red when coming from Case 1. 2836280d235SMichel Lespinasse */ 2846280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 2856280d235SMichel Lespinasse RB_RED); 28646b6135aSMichel Lespinasse if (rb_is_red(parent)) 28746b6135aSMichel Lespinasse rb_set_black(parent); 28846b6135aSMichel Lespinasse else { 2891da177e4SLinus Torvalds node = parent; 29055a98102SDavid Woodhouse parent = rb_parent(node); 29146b6135aSMichel Lespinasse if (parent) 292e125d147SMichel Lespinasse continue; 2931da177e4SLinus Torvalds } 29446b6135aSMichel Lespinasse break; 29546b6135aSMichel Lespinasse } 2966280d235SMichel Lespinasse /* 2976280d235SMichel Lespinasse * Case 3 - right rotate at sibling 2986280d235SMichel Lespinasse * (p could be either color here) 2996280d235SMichel Lespinasse * 3006280d235SMichel Lespinasse * (p) (p) 3016280d235SMichel Lespinasse * / \ / \ 302ce093a04SJie Chen * N S --> N sl 3036280d235SMichel Lespinasse * / \ \ 304ce093a04SJie Chen * sl Sr S 305ce093a04SJie Chen * \ 306ce093a04SJie Chen * Sr 307ce093a04SJie Chen * 308ce093a04SJie Chen * Note: p might be red, and then both 309ce093a04SJie Chen * p and sl are red after rotation(which 310ce093a04SJie Chen * breaks property 4). This is fixed in 311ce093a04SJie Chen * Case 4 (in __rb_rotate_set_parents() 312ce093a04SJie Chen * which set sl the color of p 313ce093a04SJie Chen * and set p RB_BLACK) 314ce093a04SJie Chen * 315ce093a04SJie Chen * (p) (sl) 316ce093a04SJie Chen * / \ / \ 317ce093a04SJie Chen * N sl --> P S 318ce093a04SJie Chen * \ / \ 319ce093a04SJie Chen * S N Sr 3206280d235SMichel Lespinasse * \ 3216280d235SMichel Lespinasse * Sr 3226280d235SMichel Lespinasse */ 323d72da4a4SPeter Zijlstra tmp1 = tmp2->rb_right; 324d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_left, tmp1); 325d72da4a4SPeter Zijlstra WRITE_ONCE(tmp2->rb_right, sibling); 326d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp2); 3276280d235SMichel Lespinasse if (tmp1) 3286280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3296280d235SMichel Lespinasse RB_BLACK); 3309c079addSMichel Lespinasse augment_rotate(sibling, tmp2); 3316280d235SMichel Lespinasse tmp1 = sibling; 3326280d235SMichel Lespinasse sibling = tmp2; 3331da177e4SLinus Torvalds } 3346280d235SMichel Lespinasse /* 3356280d235SMichel Lespinasse * Case 4 - left rotate at parent + color flips 3366280d235SMichel Lespinasse * (p and sl could be either color here. 3376280d235SMichel Lespinasse * After rotation, p becomes black, s acquires 3386280d235SMichel Lespinasse * p's color, and sl keeps its color) 3396280d235SMichel Lespinasse * 3406280d235SMichel Lespinasse * (p) (s) 3416280d235SMichel Lespinasse * / \ / \ 3426280d235SMichel Lespinasse * N S --> P Sr 3436280d235SMichel Lespinasse * / \ / \ 3446280d235SMichel Lespinasse * (sl) sr N (sl) 3456280d235SMichel Lespinasse */ 346d72da4a4SPeter Zijlstra tmp2 = sibling->rb_left; 347d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_right, tmp2); 348d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_left, parent); 3496280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 3506280d235SMichel Lespinasse if (tmp2) 3516280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 3526280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3536280d235SMichel Lespinasse RB_BLACK); 3549c079addSMichel Lespinasse augment_rotate(parent, sibling); 3551da177e4SLinus Torvalds break; 356d6ff1273SMichel Lespinasse } else { 3576280d235SMichel Lespinasse sibling = parent->rb_left; 3586280d235SMichel Lespinasse if (rb_is_red(sibling)) { 3596280d235SMichel Lespinasse /* Case 1 - right rotate at parent */ 360d72da4a4SPeter Zijlstra tmp1 = sibling->rb_right; 361d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp1); 362d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_right, parent); 3636280d235SMichel Lespinasse rb_set_parent_color(tmp1, parent, RB_BLACK); 3646280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 3656280d235SMichel Lespinasse RB_RED); 3669c079addSMichel Lespinasse augment_rotate(parent, sibling); 3676280d235SMichel Lespinasse sibling = tmp1; 3681da177e4SLinus Torvalds } 3696280d235SMichel Lespinasse tmp1 = sibling->rb_left; 3706280d235SMichel Lespinasse if (!tmp1 || rb_is_black(tmp1)) { 3716280d235SMichel Lespinasse tmp2 = sibling->rb_right; 3726280d235SMichel Lespinasse if (!tmp2 || rb_is_black(tmp2)) { 3736280d235SMichel Lespinasse /* Case 2 - sibling color flip */ 3746280d235SMichel Lespinasse rb_set_parent_color(sibling, parent, 3756280d235SMichel Lespinasse RB_RED); 37646b6135aSMichel Lespinasse if (rb_is_red(parent)) 37746b6135aSMichel Lespinasse rb_set_black(parent); 37846b6135aSMichel Lespinasse else { 3791da177e4SLinus Torvalds node = parent; 38055a98102SDavid Woodhouse parent = rb_parent(node); 38146b6135aSMichel Lespinasse if (parent) 382e125d147SMichel Lespinasse continue; 3831da177e4SLinus Torvalds } 38446b6135aSMichel Lespinasse break; 38546b6135aSMichel Lespinasse } 386ce093a04SJie Chen /* Case 3 - left rotate at sibling */ 387d72da4a4SPeter Zijlstra tmp1 = tmp2->rb_left; 388d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_right, tmp1); 389d72da4a4SPeter Zijlstra WRITE_ONCE(tmp2->rb_left, sibling); 390d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp2); 3916280d235SMichel Lespinasse if (tmp1) 3926280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, 3936280d235SMichel Lespinasse RB_BLACK); 3949c079addSMichel Lespinasse augment_rotate(sibling, tmp2); 3956280d235SMichel Lespinasse tmp1 = sibling; 3966280d235SMichel Lespinasse sibling = tmp2; 3971da177e4SLinus Torvalds } 398ce093a04SJie Chen /* Case 4 - right rotate at parent + color flips */ 399d72da4a4SPeter Zijlstra tmp2 = sibling->rb_right; 400d72da4a4SPeter Zijlstra WRITE_ONCE(parent->rb_left, tmp2); 401d72da4a4SPeter Zijlstra WRITE_ONCE(sibling->rb_right, parent); 4026280d235SMichel Lespinasse rb_set_parent_color(tmp1, sibling, RB_BLACK); 4036280d235SMichel Lespinasse if (tmp2) 4046280d235SMichel Lespinasse rb_set_parent(tmp2, parent); 4056280d235SMichel Lespinasse __rb_rotate_set_parents(parent, sibling, root, 4066280d235SMichel Lespinasse RB_BLACK); 4079c079addSMichel Lespinasse augment_rotate(parent, sibling); 4081da177e4SLinus Torvalds break; 4091da177e4SLinus Torvalds } 4101da177e4SLinus Torvalds } 4111da177e4SLinus Torvalds } 4123cb7a563SMichel Lespinasse 4133cb7a563SMichel Lespinasse /* Non-inline version for rb_erase_augmented() use */ 4143cb7a563SMichel Lespinasse void __rb_erase_color(struct rb_node *parent, struct rb_root *root, 4153cb7a563SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 4163cb7a563SMichel Lespinasse { 4173cb7a563SMichel Lespinasse ____rb_erase_color(parent, root, augment_rotate); 4183cb7a563SMichel Lespinasse } 4199c079addSMichel Lespinasse EXPORT_SYMBOL(__rb_erase_color); 42014b94af0SMichel Lespinasse 42114b94af0SMichel Lespinasse /* 42214b94af0SMichel Lespinasse * Non-augmented rbtree manipulation functions. 42314b94af0SMichel Lespinasse * 42414b94af0SMichel Lespinasse * We use dummy augmented callbacks here, and have the compiler optimize them 42514b94af0SMichel Lespinasse * out of the rb_insert_color() and rb_erase() function definitions. 42614b94af0SMichel Lespinasse */ 42714b94af0SMichel Lespinasse 42814b94af0SMichel Lespinasse static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} 42914b94af0SMichel Lespinasse static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} 43014b94af0SMichel Lespinasse static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} 43114b94af0SMichel Lespinasse 43214b94af0SMichel Lespinasse static const struct rb_augment_callbacks dummy_callbacks = { 433f231aebfSKees Cook .propagate = dummy_propagate, 434f231aebfSKees Cook .copy = dummy_copy, 435f231aebfSKees Cook .rotate = dummy_rotate 43614b94af0SMichel Lespinasse }; 43714b94af0SMichel Lespinasse 43814b94af0SMichel Lespinasse void rb_insert_color(struct rb_node *node, struct rb_root *root) 43914b94af0SMichel Lespinasse { 440cd9e61edSDavidlohr Bueso __rb_insert(node, root, false, NULL, dummy_rotate); 44114b94af0SMichel Lespinasse } 44214b94af0SMichel Lespinasse EXPORT_SYMBOL(rb_insert_color); 44314b94af0SMichel Lespinasse 44414b94af0SMichel Lespinasse void rb_erase(struct rb_node *node, struct rb_root *root) 44514b94af0SMichel Lespinasse { 4463cb7a563SMichel Lespinasse struct rb_node *rebalance; 447cd9e61edSDavidlohr Bueso rebalance = __rb_erase_augmented(node, root, 448cd9e61edSDavidlohr Bueso NULL, &dummy_callbacks); 4493cb7a563SMichel Lespinasse if (rebalance) 4503cb7a563SMichel Lespinasse ____rb_erase_color(rebalance, root, dummy_rotate); 4511da177e4SLinus Torvalds } 4521da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 4531da177e4SLinus Torvalds 454cd9e61edSDavidlohr Bueso void rb_insert_color_cached(struct rb_node *node, 455cd9e61edSDavidlohr Bueso struct rb_root_cached *root, bool leftmost) 456cd9e61edSDavidlohr Bueso { 457cd9e61edSDavidlohr Bueso __rb_insert(node, &root->rb_root, leftmost, 458cd9e61edSDavidlohr Bueso &root->rb_leftmost, dummy_rotate); 459cd9e61edSDavidlohr Bueso } 460cd9e61edSDavidlohr Bueso EXPORT_SYMBOL(rb_insert_color_cached); 461cd9e61edSDavidlohr Bueso 462cd9e61edSDavidlohr Bueso void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) 463cd9e61edSDavidlohr Bueso { 464cd9e61edSDavidlohr Bueso struct rb_node *rebalance; 465cd9e61edSDavidlohr Bueso rebalance = __rb_erase_augmented(node, &root->rb_root, 466cd9e61edSDavidlohr Bueso &root->rb_leftmost, &dummy_callbacks); 467cd9e61edSDavidlohr Bueso if (rebalance) 468cd9e61edSDavidlohr Bueso ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate); 469cd9e61edSDavidlohr Bueso } 470cd9e61edSDavidlohr Bueso EXPORT_SYMBOL(rb_erase_cached); 471cd9e61edSDavidlohr Bueso 47214b94af0SMichel Lespinasse /* 47314b94af0SMichel Lespinasse * Augmented rbtree manipulation functions. 47414b94af0SMichel Lespinasse * 47514b94af0SMichel Lespinasse * This instantiates the same __always_inline functions as in the non-augmented 47614b94af0SMichel Lespinasse * case, but this time with user-defined callbacks. 47714b94af0SMichel Lespinasse */ 47814b94af0SMichel Lespinasse 47914b94af0SMichel Lespinasse void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 480cd9e61edSDavidlohr Bueso bool newleft, struct rb_node **leftmost, 48114b94af0SMichel Lespinasse void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 48214b94af0SMichel Lespinasse { 483cd9e61edSDavidlohr Bueso __rb_insert(node, root, newleft, leftmost, augment_rotate); 48414b94af0SMichel Lespinasse } 48514b94af0SMichel Lespinasse EXPORT_SYMBOL(__rb_insert_augmented); 48614b94af0SMichel Lespinasse 4871da177e4SLinus Torvalds /* 4881da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 4891da177e4SLinus Torvalds */ 490f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 4911da177e4SLinus Torvalds { 4921da177e4SLinus Torvalds struct rb_node *n; 4931da177e4SLinus Torvalds 4941da177e4SLinus Torvalds n = root->rb_node; 4951da177e4SLinus Torvalds if (!n) 4961da177e4SLinus Torvalds return NULL; 4971da177e4SLinus Torvalds while (n->rb_left) 4981da177e4SLinus Torvalds n = n->rb_left; 4991da177e4SLinus Torvalds return n; 5001da177e4SLinus Torvalds } 5011da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 5021da177e4SLinus Torvalds 503f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 5041da177e4SLinus Torvalds { 5051da177e4SLinus Torvalds struct rb_node *n; 5061da177e4SLinus Torvalds 5071da177e4SLinus Torvalds n = root->rb_node; 5081da177e4SLinus Torvalds if (!n) 5091da177e4SLinus Torvalds return NULL; 5101da177e4SLinus Torvalds while (n->rb_right) 5111da177e4SLinus Torvalds n = n->rb_right; 5121da177e4SLinus Torvalds return n; 5131da177e4SLinus Torvalds } 5141da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 5151da177e4SLinus Torvalds 516f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 5171da177e4SLinus Torvalds { 51855a98102SDavid Woodhouse struct rb_node *parent; 51955a98102SDavid Woodhouse 5204c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 52110fd48f2SJens Axboe return NULL; 52210fd48f2SJens Axboe 5237ce6ff9eSMichel Lespinasse /* 5247ce6ff9eSMichel Lespinasse * If we have a right-hand child, go down and then left as far 5257ce6ff9eSMichel Lespinasse * as we can. 5267ce6ff9eSMichel Lespinasse */ 5271da177e4SLinus Torvalds if (node->rb_right) { 5281da177e4SLinus Torvalds node = node->rb_right; 5291da177e4SLinus Torvalds while (node->rb_left) 5301da177e4SLinus Torvalds node=node->rb_left; 531f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5321da177e4SLinus Torvalds } 5331da177e4SLinus Torvalds 5347ce6ff9eSMichel Lespinasse /* 5357ce6ff9eSMichel Lespinasse * No right-hand children. Everything down and left is smaller than us, 5367ce6ff9eSMichel Lespinasse * so any 'next' node must be in the general direction of our parent. 5377ce6ff9eSMichel Lespinasse * Go up the tree; any time the ancestor is a right-hand child of its 5387ce6ff9eSMichel Lespinasse * parent, keep going up. First time it's a left-hand child of its 5397ce6ff9eSMichel Lespinasse * parent, said parent is our 'next' node. 5407ce6ff9eSMichel Lespinasse */ 54155a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 54255a98102SDavid Woodhouse node = parent; 5431da177e4SLinus Torvalds 54455a98102SDavid Woodhouse return parent; 5451da177e4SLinus Torvalds } 5461da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 5471da177e4SLinus Torvalds 548f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 5491da177e4SLinus Torvalds { 55055a98102SDavid Woodhouse struct rb_node *parent; 55155a98102SDavid Woodhouse 5524c199a93SMichel Lespinasse if (RB_EMPTY_NODE(node)) 55310fd48f2SJens Axboe return NULL; 55410fd48f2SJens Axboe 5557ce6ff9eSMichel Lespinasse /* 5567ce6ff9eSMichel Lespinasse * If we have a left-hand child, go down and then right as far 5577ce6ff9eSMichel Lespinasse * as we can. 5587ce6ff9eSMichel Lespinasse */ 5591da177e4SLinus Torvalds if (node->rb_left) { 5601da177e4SLinus Torvalds node = node->rb_left; 5611da177e4SLinus Torvalds while (node->rb_right) 5621da177e4SLinus Torvalds node=node->rb_right; 563f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 5641da177e4SLinus Torvalds } 5651da177e4SLinus Torvalds 5667ce6ff9eSMichel Lespinasse /* 5677ce6ff9eSMichel Lespinasse * No left-hand children. Go up till we find an ancestor which 5687ce6ff9eSMichel Lespinasse * is a right-hand child of its parent. 5697ce6ff9eSMichel Lespinasse */ 57055a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 57155a98102SDavid Woodhouse node = parent; 5721da177e4SLinus Torvalds 57355a98102SDavid Woodhouse return parent; 5741da177e4SLinus Torvalds } 5751da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 5761da177e4SLinus Torvalds 5771da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 5781da177e4SLinus Torvalds struct rb_root *root) 5791da177e4SLinus Torvalds { 58055a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 5811da177e4SLinus Torvalds 582c1adf200SDavid Howells /* Copy the pointers/colour from the victim to the replacement */ 583c1adf200SDavid Howells *new = *victim; 584c1adf200SDavid Howells 5851da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 586c1adf200SDavid Howells if (victim->rb_left) 587c1adf200SDavid Howells rb_set_parent(victim->rb_left, new); 588c1adf200SDavid Howells if (victim->rb_right) 589c1adf200SDavid Howells rb_set_parent(victim->rb_right, new); 5907abc704aSMichel Lespinasse __rb_change_child(victim, new, parent, root); 591c1adf200SDavid Howells } 592c1adf200SDavid Howells EXPORT_SYMBOL(rb_replace_node); 593c1adf200SDavid Howells 594338f1d9dSChris Wilson void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, 595338f1d9dSChris Wilson struct rb_root_cached *root) 596338f1d9dSChris Wilson { 597338f1d9dSChris Wilson rb_replace_node(victim, new, &root->rb_root); 598338f1d9dSChris Wilson 599338f1d9dSChris Wilson if (root->rb_leftmost == victim) 600338f1d9dSChris Wilson root->rb_leftmost = new; 601338f1d9dSChris Wilson } 602338f1d9dSChris Wilson EXPORT_SYMBOL(rb_replace_node_cached); 603338f1d9dSChris Wilson 604c1adf200SDavid Howells void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, 605c1adf200SDavid Howells struct rb_root *root) 606c1adf200SDavid Howells { 607c1adf200SDavid Howells struct rb_node *parent = rb_parent(victim); 608c1adf200SDavid Howells 609c1adf200SDavid Howells /* Copy the pointers/colour from the victim to the replacement */ 610c1adf200SDavid Howells *new = *victim; 611c1adf200SDavid Howells 612c1adf200SDavid Howells /* Set the surrounding nodes to point to the replacement */ 6131da177e4SLinus Torvalds if (victim->rb_left) 61455a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 6151da177e4SLinus Torvalds if (victim->rb_right) 61655a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 6171da177e4SLinus Torvalds 618c1adf200SDavid Howells /* Set the parent's pointer to the new node last after an RCU barrier 619c1adf200SDavid Howells * so that the pointers onwards are seen to be set correctly when doing 620c1adf200SDavid Howells * an RCU walk over the tree. 621c1adf200SDavid Howells */ 622c1adf200SDavid Howells __rb_change_child_rcu(victim, new, parent, root); 6231da177e4SLinus Torvalds } 624c1adf200SDavid Howells EXPORT_SYMBOL(rb_replace_node_rcu); 6259dee5c51SCody P Schafer 6269dee5c51SCody P Schafer static struct rb_node *rb_left_deepest_node(const struct rb_node *node) 6279dee5c51SCody P Schafer { 6289dee5c51SCody P Schafer for (;;) { 6299dee5c51SCody P Schafer if (node->rb_left) 6309dee5c51SCody P Schafer node = node->rb_left; 6319dee5c51SCody P Schafer else if (node->rb_right) 6329dee5c51SCody P Schafer node = node->rb_right; 6339dee5c51SCody P Schafer else 6349dee5c51SCody P Schafer return (struct rb_node *)node; 6359dee5c51SCody P Schafer } 6369dee5c51SCody P Schafer } 6379dee5c51SCody P Schafer 6389dee5c51SCody P Schafer struct rb_node *rb_next_postorder(const struct rb_node *node) 6399dee5c51SCody P Schafer { 6409dee5c51SCody P Schafer const struct rb_node *parent; 6419dee5c51SCody P Schafer if (!node) 6429dee5c51SCody P Schafer return NULL; 6439dee5c51SCody P Schafer parent = rb_parent(node); 6449dee5c51SCody P Schafer 6459dee5c51SCody P Schafer /* If we're sitting on node, we've already seen our children */ 6469dee5c51SCody P Schafer if (parent && node == parent->rb_left && parent->rb_right) { 6479dee5c51SCody P Schafer /* If we are the parent's left node, go to the parent's right 6489dee5c51SCody P Schafer * node then all the way down to the left */ 6499dee5c51SCody P Schafer return rb_left_deepest_node(parent->rb_right); 6509dee5c51SCody P Schafer } else 6519dee5c51SCody P Schafer /* Otherwise we are the parent's right node, and the parent 6529dee5c51SCody P Schafer * should be next */ 6539dee5c51SCody P Schafer return (struct rb_node *)parent; 6549dee5c51SCody P Schafer } 6559dee5c51SCody P Schafer EXPORT_SYMBOL(rb_next_postorder); 6569dee5c51SCody P Schafer 6579dee5c51SCody P Schafer struct rb_node *rb_first_postorder(const struct rb_root *root) 6589dee5c51SCody P Schafer { 6599dee5c51SCody P Schafer if (!root->rb_node) 6609dee5c51SCody P Schafer return NULL; 6619dee5c51SCody P Schafer 6629dee5c51SCody P Schafer return rb_left_deepest_node(root->rb_node); 6639dee5c51SCody P Schafer } 6649dee5c51SCody P Schafer EXPORT_SYMBOL(rb_first_postorder); 665