11a59d1b8SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later 23f735377SArnaldo Carvalho de Melo /* 33f735377SArnaldo Carvalho de Melo Red Black Trees 43f735377SArnaldo Carvalho de Melo (C) 1999 Andrea Arcangeli <andrea@suse.de> 53f735377SArnaldo Carvalho de Melo (C) 2002 David Woodhouse <dwmw2@infradead.org> 63f735377SArnaldo Carvalho de Melo (C) 2012 Michel Lespinasse <walken@google.com> 73f735377SArnaldo Carvalho de Melo 83f735377SArnaldo Carvalho de Melo 93f735377SArnaldo Carvalho de Melo linux/lib/rbtree.c 103f735377SArnaldo Carvalho de Melo */ 113f735377SArnaldo Carvalho de Melo 123f735377SArnaldo Carvalho de Melo #include <linux/rbtree_augmented.h> 133aef2cadSDavidlohr Bueso #include <linux/export.h> 143f735377SArnaldo Carvalho de Melo 153f735377SArnaldo Carvalho de Melo /* 163f735377SArnaldo Carvalho de Melo * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree 173f735377SArnaldo Carvalho de Melo * 183f735377SArnaldo Carvalho de Melo * 1) A node is either red or black 193f735377SArnaldo Carvalho de Melo * 2) The root is black 203f735377SArnaldo Carvalho de Melo * 3) All leaves (NULL) are black 213f735377SArnaldo Carvalho de Melo * 4) Both children of every red node are black 223f735377SArnaldo Carvalho de Melo * 5) Every simple path from root to leaves contains the same number 233f735377SArnaldo Carvalho de Melo * of black nodes. 243f735377SArnaldo Carvalho de Melo * 253f735377SArnaldo Carvalho de Melo * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two 263f735377SArnaldo Carvalho de Melo * consecutive red nodes in a path and every red node is therefore followed by 273f735377SArnaldo Carvalho de Melo * a black. So if B is the number of black nodes on every simple path (as per 283f735377SArnaldo Carvalho de Melo * 5), then the longest possible path due to 4 is 2B. 293f735377SArnaldo Carvalho de Melo * 303f735377SArnaldo Carvalho de Melo * We shall indicate color with case, where black nodes are uppercase and red 313f735377SArnaldo Carvalho de Melo * nodes will be lowercase. Unknown color nodes shall be drawn as red within 323f735377SArnaldo Carvalho de Melo * parentheses and have some accompanying text comment. 333f735377SArnaldo Carvalho de Melo */ 343f735377SArnaldo Carvalho de Melo 353aef2cadSDavidlohr Bueso /* 363aef2cadSDavidlohr Bueso * Notes on lockless lookups: 373aef2cadSDavidlohr Bueso * 383aef2cadSDavidlohr Bueso * All stores to the tree structure (rb_left and rb_right) must be done using 393aef2cadSDavidlohr Bueso * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the 403aef2cadSDavidlohr Bueso * tree structure as seen in program order. 413aef2cadSDavidlohr Bueso * 423aef2cadSDavidlohr Bueso * These two requirements will allow lockless iteration of the tree -- not 433aef2cadSDavidlohr Bueso * correct iteration mind you, tree rotations are not atomic so a lookup might 443aef2cadSDavidlohr Bueso * miss entire subtrees. 453aef2cadSDavidlohr Bueso * 463aef2cadSDavidlohr Bueso * But they do guarantee that any such traversal will only see valid elements 473aef2cadSDavidlohr Bueso * and that it will indeed complete -- does not get stuck in a loop. 483aef2cadSDavidlohr Bueso * 493aef2cadSDavidlohr Bueso * It also guarantees that if the lookup returns an element it is the 'correct' 503aef2cadSDavidlohr Bueso * one. But not returning an element does _NOT_ mean it's not present. 513aef2cadSDavidlohr Bueso * 523aef2cadSDavidlohr Bueso * NOTE: 533aef2cadSDavidlohr Bueso * 543aef2cadSDavidlohr Bueso * Stores to __rb_parent_color are not important for simple lookups so those 553aef2cadSDavidlohr Bueso * are left undone as of now. Nor did I check for loops involving parent 563aef2cadSDavidlohr Bueso * pointers. 573aef2cadSDavidlohr Bueso */ 583aef2cadSDavidlohr Bueso 593f735377SArnaldo Carvalho de Melo static inline void rb_set_black(struct rb_node *rb) 603f735377SArnaldo Carvalho de Melo { 613f735377SArnaldo Carvalho de Melo rb->__rb_parent_color |= RB_BLACK; 623f735377SArnaldo Carvalho de Melo } 633f735377SArnaldo Carvalho de Melo 643f735377SArnaldo Carvalho de Melo static inline struct rb_node *rb_red_parent(struct rb_node *red) 653f735377SArnaldo Carvalho de Melo { 663f735377SArnaldo Carvalho de Melo return (struct rb_node *)red->__rb_parent_color; 673f735377SArnaldo Carvalho de Melo } 683f735377SArnaldo Carvalho de Melo 693f735377SArnaldo Carvalho de Melo /* 703f735377SArnaldo Carvalho de Melo * Helper function for rotations: 713f735377SArnaldo Carvalho de Melo * - old's parent and color get assigned to new 723f735377SArnaldo Carvalho de Melo * - old gets assigned new as a parent and 'color' as a color. 733f735377SArnaldo Carvalho de Melo */ 743f735377SArnaldo Carvalho de Melo static inline void 753f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 763f735377SArnaldo Carvalho de Melo struct rb_root *root, int color) 773f735377SArnaldo Carvalho de Melo { 783f735377SArnaldo Carvalho de Melo struct rb_node *parent = rb_parent(old); 793f735377SArnaldo Carvalho de Melo new->__rb_parent_color = old->__rb_parent_color; 803f735377SArnaldo Carvalho de Melo rb_set_parent_color(old, new, color); 813f735377SArnaldo Carvalho de Melo __rb_change_child(old, new, parent, root); 823f735377SArnaldo Carvalho de Melo } 833f735377SArnaldo Carvalho de Melo 843f735377SArnaldo Carvalho de Melo static __always_inline void 853f735377SArnaldo Carvalho de Melo __rb_insert(struct rb_node *node, struct rb_root *root, 863aef2cadSDavidlohr Bueso bool newleft, struct rb_node **leftmost, 873f735377SArnaldo Carvalho de Melo void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 883f735377SArnaldo Carvalho de Melo { 893f735377SArnaldo Carvalho de Melo struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 903f735377SArnaldo Carvalho de Melo 913aef2cadSDavidlohr Bueso if (newleft) 923aef2cadSDavidlohr Bueso *leftmost = node; 933aef2cadSDavidlohr Bueso 943f735377SArnaldo Carvalho de Melo while (true) { 953f735377SArnaldo Carvalho de Melo /* 963aef2cadSDavidlohr Bueso * Loop invariant: node is red. 973f735377SArnaldo Carvalho de Melo */ 983aef2cadSDavidlohr Bueso if (unlikely(!parent)) { 993aef2cadSDavidlohr Bueso /* 1003aef2cadSDavidlohr Bueso * The inserted node is root. Either this is the 1013aef2cadSDavidlohr Bueso * first node, or we recursed at Case 1 below and 1023aef2cadSDavidlohr Bueso * are no longer violating 4). 1033aef2cadSDavidlohr Bueso */ 1043f735377SArnaldo Carvalho de Melo rb_set_parent_color(node, NULL, RB_BLACK); 1053f735377SArnaldo Carvalho de Melo break; 1063aef2cadSDavidlohr Bueso } 1073aef2cadSDavidlohr Bueso 1083aef2cadSDavidlohr Bueso /* 1093aef2cadSDavidlohr Bueso * If there is a black parent, we are done. 1103aef2cadSDavidlohr Bueso * Otherwise, take some corrective action as, 1113aef2cadSDavidlohr Bueso * per 4), we don't want a red root or two 1123aef2cadSDavidlohr Bueso * consecutive red nodes. 1133aef2cadSDavidlohr Bueso */ 1143aef2cadSDavidlohr Bueso if(rb_is_black(parent)) 1153f735377SArnaldo Carvalho de Melo break; 1163f735377SArnaldo Carvalho de Melo 1173f735377SArnaldo Carvalho de Melo gparent = rb_red_parent(parent); 1183f735377SArnaldo Carvalho de Melo 1193f735377SArnaldo Carvalho de Melo tmp = gparent->rb_right; 1203f735377SArnaldo Carvalho de Melo if (parent != tmp) { /* parent == gparent->rb_left */ 1213f735377SArnaldo Carvalho de Melo if (tmp && rb_is_red(tmp)) { 1223f735377SArnaldo Carvalho de Melo /* 1233aef2cadSDavidlohr Bueso * Case 1 - node's uncle is red (color flips). 1243f735377SArnaldo Carvalho de Melo * 1253f735377SArnaldo Carvalho de Melo * G g 1263f735377SArnaldo Carvalho de Melo * / \ / \ 1273f735377SArnaldo Carvalho de Melo * p u --> P U 1283f735377SArnaldo Carvalho de Melo * / / 1293f735377SArnaldo Carvalho de Melo * n n 1303f735377SArnaldo Carvalho de Melo * 1313f735377SArnaldo Carvalho de Melo * However, since g's parent might be red, and 1323f735377SArnaldo Carvalho de Melo * 4) does not allow this, we need to recurse 1333f735377SArnaldo Carvalho de Melo * at g. 1343f735377SArnaldo Carvalho de Melo */ 1353f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp, gparent, RB_BLACK); 1363f735377SArnaldo Carvalho de Melo rb_set_parent_color(parent, gparent, RB_BLACK); 1373f735377SArnaldo Carvalho de Melo node = gparent; 1383f735377SArnaldo Carvalho de Melo parent = rb_parent(node); 1393f735377SArnaldo Carvalho de Melo rb_set_parent_color(node, parent, RB_RED); 1403f735377SArnaldo Carvalho de Melo continue; 1413f735377SArnaldo Carvalho de Melo } 1423f735377SArnaldo Carvalho de Melo 1433f735377SArnaldo Carvalho de Melo tmp = parent->rb_right; 1443f735377SArnaldo Carvalho de Melo if (node == tmp) { 1453f735377SArnaldo Carvalho de Melo /* 1463aef2cadSDavidlohr Bueso * Case 2 - node's uncle is black and node is 1473aef2cadSDavidlohr Bueso * the parent's right child (left rotate at parent). 1483f735377SArnaldo Carvalho de Melo * 1493f735377SArnaldo Carvalho de Melo * G G 1503f735377SArnaldo Carvalho de Melo * / \ / \ 1513f735377SArnaldo Carvalho de Melo * p U --> n U 1523f735377SArnaldo Carvalho de Melo * \ / 1533f735377SArnaldo Carvalho de Melo * n p 1543f735377SArnaldo Carvalho de Melo * 1553f735377SArnaldo Carvalho de Melo * This still leaves us in violation of 4), the 1563f735377SArnaldo Carvalho de Melo * continuation into Case 3 will fix that. 1573f735377SArnaldo Carvalho de Melo */ 1583aef2cadSDavidlohr Bueso tmp = node->rb_left; 1593aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_right, tmp); 1603aef2cadSDavidlohr Bueso WRITE_ONCE(node->rb_left, parent); 1613f735377SArnaldo Carvalho de Melo if (tmp) 1623f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp, parent, 1633f735377SArnaldo Carvalho de Melo RB_BLACK); 1643f735377SArnaldo Carvalho de Melo rb_set_parent_color(parent, node, RB_RED); 1653f735377SArnaldo Carvalho de Melo augment_rotate(parent, node); 1663f735377SArnaldo Carvalho de Melo parent = node; 1673f735377SArnaldo Carvalho de Melo tmp = node->rb_right; 1683f735377SArnaldo Carvalho de Melo } 1693f735377SArnaldo Carvalho de Melo 1703f735377SArnaldo Carvalho de Melo /* 1713aef2cadSDavidlohr Bueso * Case 3 - node's uncle is black and node is 1723aef2cadSDavidlohr Bueso * the parent's left child (right rotate at gparent). 1733f735377SArnaldo Carvalho de Melo * 1743f735377SArnaldo Carvalho de Melo * G P 1753f735377SArnaldo Carvalho de Melo * / \ / \ 1763f735377SArnaldo Carvalho de Melo * p U --> n g 1773f735377SArnaldo Carvalho de Melo * / \ 1783f735377SArnaldo Carvalho de Melo * n U 1793f735377SArnaldo Carvalho de Melo */ 1803aef2cadSDavidlohr Bueso WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ 1813aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_right, gparent); 1823f735377SArnaldo Carvalho de Melo if (tmp) 1833f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp, gparent, RB_BLACK); 1843f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1853f735377SArnaldo Carvalho de Melo augment_rotate(gparent, parent); 1863f735377SArnaldo Carvalho de Melo break; 1873f735377SArnaldo Carvalho de Melo } else { 1883f735377SArnaldo Carvalho de Melo tmp = gparent->rb_left; 1893f735377SArnaldo Carvalho de Melo if (tmp && rb_is_red(tmp)) { 1903f735377SArnaldo Carvalho de Melo /* Case 1 - color flips */ 1913f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp, gparent, RB_BLACK); 1923f735377SArnaldo Carvalho de Melo rb_set_parent_color(parent, gparent, RB_BLACK); 1933f735377SArnaldo Carvalho de Melo node = gparent; 1943f735377SArnaldo Carvalho de Melo parent = rb_parent(node); 1953f735377SArnaldo Carvalho de Melo rb_set_parent_color(node, parent, RB_RED); 1963f735377SArnaldo Carvalho de Melo continue; 1973f735377SArnaldo Carvalho de Melo } 1983f735377SArnaldo Carvalho de Melo 1993f735377SArnaldo Carvalho de Melo tmp = parent->rb_left; 2003f735377SArnaldo Carvalho de Melo if (node == tmp) { 2013f735377SArnaldo Carvalho de Melo /* Case 2 - right rotate at parent */ 2023aef2cadSDavidlohr Bueso tmp = node->rb_right; 2033aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_left, tmp); 2043aef2cadSDavidlohr Bueso WRITE_ONCE(node->rb_right, parent); 2053f735377SArnaldo Carvalho de Melo if (tmp) 2063f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp, parent, 2073f735377SArnaldo Carvalho de Melo RB_BLACK); 2083f735377SArnaldo Carvalho de Melo rb_set_parent_color(parent, node, RB_RED); 2093f735377SArnaldo Carvalho de Melo augment_rotate(parent, node); 2103f735377SArnaldo Carvalho de Melo parent = node; 2113f735377SArnaldo Carvalho de Melo tmp = node->rb_left; 2123f735377SArnaldo Carvalho de Melo } 2133f735377SArnaldo Carvalho de Melo 2143f735377SArnaldo Carvalho de Melo /* Case 3 - left rotate at gparent */ 2153aef2cadSDavidlohr Bueso WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ 2163aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_left, gparent); 2173f735377SArnaldo Carvalho de Melo if (tmp) 2183f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp, gparent, RB_BLACK); 2193f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(gparent, parent, root, RB_RED); 2203f735377SArnaldo Carvalho de Melo augment_rotate(gparent, parent); 2213f735377SArnaldo Carvalho de Melo break; 2223f735377SArnaldo Carvalho de Melo } 2233f735377SArnaldo Carvalho de Melo } 2243f735377SArnaldo Carvalho de Melo } 2253f735377SArnaldo Carvalho de Melo 2263f735377SArnaldo Carvalho de Melo /* 2273f735377SArnaldo Carvalho de Melo * Inline version for rb_erase() use - we want to be able to inline 2283f735377SArnaldo Carvalho de Melo * and eliminate the dummy_rotate callback there 2293f735377SArnaldo Carvalho de Melo */ 2303f735377SArnaldo Carvalho de Melo static __always_inline void 2313f735377SArnaldo Carvalho de Melo ____rb_erase_color(struct rb_node *parent, struct rb_root *root, 2323f735377SArnaldo Carvalho de Melo void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 2333f735377SArnaldo Carvalho de Melo { 2343f735377SArnaldo Carvalho de Melo struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 2353f735377SArnaldo Carvalho de Melo 2363f735377SArnaldo Carvalho de Melo while (true) { 2373f735377SArnaldo Carvalho de Melo /* 2383f735377SArnaldo Carvalho de Melo * Loop invariants: 2393f735377SArnaldo Carvalho de Melo * - node is black (or NULL on first iteration) 2403f735377SArnaldo Carvalho de Melo * - node is not the root (parent is not NULL) 2413f735377SArnaldo Carvalho de Melo * - All leaf paths going through parent and node have a 2423f735377SArnaldo Carvalho de Melo * black node count that is 1 lower than other leaf paths. 2433f735377SArnaldo Carvalho de Melo */ 2443f735377SArnaldo Carvalho de Melo sibling = parent->rb_right; 2453f735377SArnaldo Carvalho de Melo if (node != sibling) { /* node == parent->rb_left */ 2463f735377SArnaldo Carvalho de Melo if (rb_is_red(sibling)) { 2473f735377SArnaldo Carvalho de Melo /* 2483f735377SArnaldo Carvalho de Melo * Case 1 - left rotate at parent 2493f735377SArnaldo Carvalho de Melo * 2503f735377SArnaldo Carvalho de Melo * P S 2513f735377SArnaldo Carvalho de Melo * / \ / \ 2523f735377SArnaldo Carvalho de Melo * N s --> p Sr 2533f735377SArnaldo Carvalho de Melo * / \ / \ 2543f735377SArnaldo Carvalho de Melo * Sl Sr N Sl 2553f735377SArnaldo Carvalho de Melo */ 2563aef2cadSDavidlohr Bueso tmp1 = sibling->rb_left; 2573aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_right, tmp1); 2583aef2cadSDavidlohr Bueso WRITE_ONCE(sibling->rb_left, parent); 2593f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp1, parent, RB_BLACK); 2603f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(parent, sibling, root, 2613f735377SArnaldo Carvalho de Melo RB_RED); 2623f735377SArnaldo Carvalho de Melo augment_rotate(parent, sibling); 2633f735377SArnaldo Carvalho de Melo sibling = tmp1; 2643f735377SArnaldo Carvalho de Melo } 2653f735377SArnaldo Carvalho de Melo tmp1 = sibling->rb_right; 2663f735377SArnaldo Carvalho de Melo if (!tmp1 || rb_is_black(tmp1)) { 2673f735377SArnaldo Carvalho de Melo tmp2 = sibling->rb_left; 2683f735377SArnaldo Carvalho de Melo if (!tmp2 || rb_is_black(tmp2)) { 2693f735377SArnaldo Carvalho de Melo /* 2703f735377SArnaldo Carvalho de Melo * Case 2 - sibling color flip 2713f735377SArnaldo Carvalho de Melo * (p could be either color here) 2723f735377SArnaldo Carvalho de Melo * 2733f735377SArnaldo Carvalho de Melo * (p) (p) 2743f735377SArnaldo Carvalho de Melo * / \ / \ 2753f735377SArnaldo Carvalho de Melo * N S --> N s 2763f735377SArnaldo Carvalho de Melo * / \ / \ 2773f735377SArnaldo Carvalho de Melo * Sl Sr Sl Sr 2783f735377SArnaldo Carvalho de Melo * 2793f735377SArnaldo Carvalho de Melo * This leaves us violating 5) which 2803f735377SArnaldo Carvalho de Melo * can be fixed by flipping p to black 2813f735377SArnaldo Carvalho de Melo * if it was red, or by recursing at p. 2823f735377SArnaldo Carvalho de Melo * p is red when coming from Case 1. 2833f735377SArnaldo Carvalho de Melo */ 2843f735377SArnaldo Carvalho de Melo rb_set_parent_color(sibling, parent, 2853f735377SArnaldo Carvalho de Melo RB_RED); 2863f735377SArnaldo Carvalho de Melo if (rb_is_red(parent)) 2873f735377SArnaldo Carvalho de Melo rb_set_black(parent); 2883f735377SArnaldo Carvalho de Melo else { 2893f735377SArnaldo Carvalho de Melo node = parent; 2903f735377SArnaldo Carvalho de Melo parent = rb_parent(node); 2913f735377SArnaldo Carvalho de Melo if (parent) 2923f735377SArnaldo Carvalho de Melo continue; 2933f735377SArnaldo Carvalho de Melo } 2943f735377SArnaldo Carvalho de Melo break; 2953f735377SArnaldo Carvalho de Melo } 2963f735377SArnaldo Carvalho de Melo /* 2973f735377SArnaldo Carvalho de Melo * Case 3 - right rotate at sibling 2983f735377SArnaldo Carvalho de Melo * (p could be either color here) 2993f735377SArnaldo Carvalho de Melo * 3003f735377SArnaldo Carvalho de Melo * (p) (p) 3013f735377SArnaldo Carvalho de Melo * / \ / \ 3023aef2cadSDavidlohr Bueso * N S --> N sl 3033f735377SArnaldo Carvalho de Melo * / \ \ 3043aef2cadSDavidlohr Bueso * sl Sr S 3053aef2cadSDavidlohr Bueso * \ 3063aef2cadSDavidlohr Bueso * Sr 3073aef2cadSDavidlohr Bueso * 3083aef2cadSDavidlohr Bueso * Note: p might be red, and then both 3093aef2cadSDavidlohr Bueso * p and sl are red after rotation(which 3103aef2cadSDavidlohr Bueso * breaks property 4). This is fixed in 3113aef2cadSDavidlohr Bueso * Case 4 (in __rb_rotate_set_parents() 3123aef2cadSDavidlohr Bueso * which set sl the color of p 3133aef2cadSDavidlohr Bueso * and set p RB_BLACK) 3143aef2cadSDavidlohr Bueso * 3153aef2cadSDavidlohr Bueso * (p) (sl) 3163aef2cadSDavidlohr Bueso * / \ / \ 3173aef2cadSDavidlohr Bueso * N sl --> P S 3183aef2cadSDavidlohr Bueso * \ / \ 3193aef2cadSDavidlohr Bueso * S N Sr 3203f735377SArnaldo Carvalho de Melo * \ 3213f735377SArnaldo Carvalho de Melo * Sr 3223f735377SArnaldo Carvalho de Melo */ 3233aef2cadSDavidlohr Bueso tmp1 = tmp2->rb_right; 3243aef2cadSDavidlohr Bueso WRITE_ONCE(sibling->rb_left, tmp1); 3253aef2cadSDavidlohr Bueso WRITE_ONCE(tmp2->rb_right, sibling); 3263aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_right, tmp2); 3273f735377SArnaldo Carvalho de Melo if (tmp1) 3283f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp1, sibling, 3293f735377SArnaldo Carvalho de Melo RB_BLACK); 3303f735377SArnaldo Carvalho de Melo augment_rotate(sibling, tmp2); 3313f735377SArnaldo Carvalho de Melo tmp1 = sibling; 3323f735377SArnaldo Carvalho de Melo sibling = tmp2; 3333f735377SArnaldo Carvalho de Melo } 3343f735377SArnaldo Carvalho de Melo /* 3353f735377SArnaldo Carvalho de Melo * Case 4 - left rotate at parent + color flips 3363f735377SArnaldo Carvalho de Melo * (p and sl could be either color here. 3373f735377SArnaldo Carvalho de Melo * After rotation, p becomes black, s acquires 3383f735377SArnaldo Carvalho de Melo * p's color, and sl keeps its color) 3393f735377SArnaldo Carvalho de Melo * 3403f735377SArnaldo Carvalho de Melo * (p) (s) 3413f735377SArnaldo Carvalho de Melo * / \ / \ 3423f735377SArnaldo Carvalho de Melo * N S --> P Sr 3433f735377SArnaldo Carvalho de Melo * / \ / \ 3443f735377SArnaldo Carvalho de Melo * (sl) sr N (sl) 3453f735377SArnaldo Carvalho de Melo */ 3463aef2cadSDavidlohr Bueso tmp2 = sibling->rb_left; 3473aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_right, tmp2); 3483aef2cadSDavidlohr Bueso WRITE_ONCE(sibling->rb_left, parent); 3493f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp1, sibling, RB_BLACK); 3503f735377SArnaldo Carvalho de Melo if (tmp2) 3513f735377SArnaldo Carvalho de Melo rb_set_parent(tmp2, parent); 3523f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(parent, sibling, root, 3533f735377SArnaldo Carvalho de Melo RB_BLACK); 3543f735377SArnaldo Carvalho de Melo augment_rotate(parent, sibling); 3553f735377SArnaldo Carvalho de Melo break; 3563f735377SArnaldo Carvalho de Melo } else { 3573f735377SArnaldo Carvalho de Melo sibling = parent->rb_left; 3583f735377SArnaldo Carvalho de Melo if (rb_is_red(sibling)) { 3593f735377SArnaldo Carvalho de Melo /* Case 1 - right rotate at parent */ 3603aef2cadSDavidlohr Bueso tmp1 = sibling->rb_right; 3613aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_left, tmp1); 3623aef2cadSDavidlohr Bueso WRITE_ONCE(sibling->rb_right, parent); 3633f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp1, parent, RB_BLACK); 3643f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(parent, sibling, root, 3653f735377SArnaldo Carvalho de Melo RB_RED); 3663f735377SArnaldo Carvalho de Melo augment_rotate(parent, sibling); 3673f735377SArnaldo Carvalho de Melo sibling = tmp1; 3683f735377SArnaldo Carvalho de Melo } 3693f735377SArnaldo Carvalho de Melo tmp1 = sibling->rb_left; 3703f735377SArnaldo Carvalho de Melo if (!tmp1 || rb_is_black(tmp1)) { 3713f735377SArnaldo Carvalho de Melo tmp2 = sibling->rb_right; 3723f735377SArnaldo Carvalho de Melo if (!tmp2 || rb_is_black(tmp2)) { 3733f735377SArnaldo Carvalho de Melo /* Case 2 - sibling color flip */ 3743f735377SArnaldo Carvalho de Melo rb_set_parent_color(sibling, parent, 3753f735377SArnaldo Carvalho de Melo RB_RED); 3763f735377SArnaldo Carvalho de Melo if (rb_is_red(parent)) 3773f735377SArnaldo Carvalho de Melo rb_set_black(parent); 3783f735377SArnaldo Carvalho de Melo else { 3793f735377SArnaldo Carvalho de Melo node = parent; 3803f735377SArnaldo Carvalho de Melo parent = rb_parent(node); 3813f735377SArnaldo Carvalho de Melo if (parent) 3823f735377SArnaldo Carvalho de Melo continue; 3833f735377SArnaldo Carvalho de Melo } 3843f735377SArnaldo Carvalho de Melo break; 3853f735377SArnaldo Carvalho de Melo } 3863aef2cadSDavidlohr Bueso /* Case 3 - left rotate at sibling */ 3873aef2cadSDavidlohr Bueso tmp1 = tmp2->rb_left; 3883aef2cadSDavidlohr Bueso WRITE_ONCE(sibling->rb_right, tmp1); 3893aef2cadSDavidlohr Bueso WRITE_ONCE(tmp2->rb_left, sibling); 3903aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_left, tmp2); 3913f735377SArnaldo Carvalho de Melo if (tmp1) 3923f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp1, sibling, 3933f735377SArnaldo Carvalho de Melo RB_BLACK); 3943f735377SArnaldo Carvalho de Melo augment_rotate(sibling, tmp2); 3953f735377SArnaldo Carvalho de Melo tmp1 = sibling; 3963f735377SArnaldo Carvalho de Melo sibling = tmp2; 3973f735377SArnaldo Carvalho de Melo } 3983aef2cadSDavidlohr Bueso /* Case 4 - right rotate at parent + color flips */ 3993aef2cadSDavidlohr Bueso tmp2 = sibling->rb_right; 4003aef2cadSDavidlohr Bueso WRITE_ONCE(parent->rb_left, tmp2); 4013aef2cadSDavidlohr Bueso WRITE_ONCE(sibling->rb_right, parent); 4023f735377SArnaldo Carvalho de Melo rb_set_parent_color(tmp1, sibling, RB_BLACK); 4033f735377SArnaldo Carvalho de Melo if (tmp2) 4043f735377SArnaldo Carvalho de Melo rb_set_parent(tmp2, parent); 4053f735377SArnaldo Carvalho de Melo __rb_rotate_set_parents(parent, sibling, root, 4063f735377SArnaldo Carvalho de Melo RB_BLACK); 4073f735377SArnaldo Carvalho de Melo augment_rotate(parent, sibling); 4083f735377SArnaldo Carvalho de Melo break; 4093f735377SArnaldo Carvalho de Melo } 4103f735377SArnaldo Carvalho de Melo } 4113f735377SArnaldo Carvalho de Melo } 4123f735377SArnaldo Carvalho de Melo 4133f735377SArnaldo Carvalho de Melo /* Non-inline version for rb_erase_augmented() use */ 4143f735377SArnaldo Carvalho de Melo void __rb_erase_color(struct rb_node *parent, struct rb_root *root, 4153f735377SArnaldo Carvalho de Melo void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 4163f735377SArnaldo Carvalho de Melo { 4173f735377SArnaldo Carvalho de Melo ____rb_erase_color(parent, root, augment_rotate); 4183f735377SArnaldo Carvalho de Melo } 4193f735377SArnaldo Carvalho de Melo 4203f735377SArnaldo Carvalho de Melo /* 4213f735377SArnaldo Carvalho de Melo * Non-augmented rbtree manipulation functions. 4223f735377SArnaldo Carvalho de Melo * 4233f735377SArnaldo Carvalho de Melo * We use dummy augmented callbacks here, and have the compiler optimize them 4243f735377SArnaldo Carvalho de Melo * out of the rb_insert_color() and rb_erase() function definitions. 4253f735377SArnaldo Carvalho de Melo */ 4263f735377SArnaldo Carvalho de Melo 4273f735377SArnaldo Carvalho de Melo static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} 4283f735377SArnaldo Carvalho de Melo static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} 4293f735377SArnaldo Carvalho de Melo static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} 4303f735377SArnaldo Carvalho de Melo 4313f735377SArnaldo Carvalho de Melo static const struct rb_augment_callbacks dummy_callbacks = { 4323aef2cadSDavidlohr Bueso .propagate = dummy_propagate, 4333aef2cadSDavidlohr Bueso .copy = dummy_copy, 4343aef2cadSDavidlohr Bueso .rotate = dummy_rotate 4353f735377SArnaldo Carvalho de Melo }; 4363f735377SArnaldo Carvalho de Melo 4373f735377SArnaldo Carvalho de Melo void rb_insert_color(struct rb_node *node, struct rb_root *root) 4383f735377SArnaldo Carvalho de Melo { 4393aef2cadSDavidlohr Bueso __rb_insert(node, root, false, NULL, dummy_rotate); 4403f735377SArnaldo Carvalho de Melo } 4413f735377SArnaldo Carvalho de Melo 4423f735377SArnaldo Carvalho de Melo void rb_erase(struct rb_node *node, struct rb_root *root) 4433f735377SArnaldo Carvalho de Melo { 4443f735377SArnaldo Carvalho de Melo struct rb_node *rebalance; 4453aef2cadSDavidlohr Bueso rebalance = __rb_erase_augmented(node, root, 4463aef2cadSDavidlohr Bueso NULL, &dummy_callbacks); 4473f735377SArnaldo Carvalho de Melo if (rebalance) 4483f735377SArnaldo Carvalho de Melo ____rb_erase_color(rebalance, root, dummy_rotate); 4493f735377SArnaldo Carvalho de Melo } 4503f735377SArnaldo Carvalho de Melo 4513aef2cadSDavidlohr Bueso void rb_insert_color_cached(struct rb_node *node, 4523aef2cadSDavidlohr Bueso struct rb_root_cached *root, bool leftmost) 4533aef2cadSDavidlohr Bueso { 4543aef2cadSDavidlohr Bueso __rb_insert(node, &root->rb_root, leftmost, 4553aef2cadSDavidlohr Bueso &root->rb_leftmost, dummy_rotate); 4563aef2cadSDavidlohr Bueso } 4573aef2cadSDavidlohr Bueso 4583aef2cadSDavidlohr Bueso void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root) 4593aef2cadSDavidlohr Bueso { 4603aef2cadSDavidlohr Bueso struct rb_node *rebalance; 4613aef2cadSDavidlohr Bueso rebalance = __rb_erase_augmented(node, &root->rb_root, 4623aef2cadSDavidlohr Bueso &root->rb_leftmost, &dummy_callbacks); 4633aef2cadSDavidlohr Bueso if (rebalance) 4643aef2cadSDavidlohr Bueso ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate); 4653aef2cadSDavidlohr Bueso } 4663aef2cadSDavidlohr Bueso 4673f735377SArnaldo Carvalho de Melo /* 4683f735377SArnaldo Carvalho de Melo * Augmented rbtree manipulation functions. 4693f735377SArnaldo Carvalho de Melo * 4703f735377SArnaldo Carvalho de Melo * This instantiates the same __always_inline functions as in the non-augmented 4713f735377SArnaldo Carvalho de Melo * case, but this time with user-defined callbacks. 4723f735377SArnaldo Carvalho de Melo */ 4733f735377SArnaldo Carvalho de Melo 4743f735377SArnaldo Carvalho de Melo void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 4753aef2cadSDavidlohr Bueso bool newleft, struct rb_node **leftmost, 4763f735377SArnaldo Carvalho de Melo void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 4773f735377SArnaldo Carvalho de Melo { 4783aef2cadSDavidlohr Bueso __rb_insert(node, root, newleft, leftmost, augment_rotate); 4793f735377SArnaldo Carvalho de Melo } 4803f735377SArnaldo Carvalho de Melo 4813f735377SArnaldo Carvalho de Melo /* 4823f735377SArnaldo Carvalho de Melo * This function returns the first node (in sort order) of the tree. 4833f735377SArnaldo Carvalho de Melo */ 4843f735377SArnaldo Carvalho de Melo struct rb_node *rb_first(const struct rb_root *root) 4853f735377SArnaldo Carvalho de Melo { 4863f735377SArnaldo Carvalho de Melo struct rb_node *n; 4873f735377SArnaldo Carvalho de Melo 4883f735377SArnaldo Carvalho de Melo n = root->rb_node; 4893f735377SArnaldo Carvalho de Melo if (!n) 4903f735377SArnaldo Carvalho de Melo return NULL; 4913f735377SArnaldo Carvalho de Melo while (n->rb_left) 4923f735377SArnaldo Carvalho de Melo n = n->rb_left; 4933f735377SArnaldo Carvalho de Melo return n; 4943f735377SArnaldo Carvalho de Melo } 4953f735377SArnaldo Carvalho de Melo 4963f735377SArnaldo Carvalho de Melo struct rb_node *rb_last(const struct rb_root *root) 4973f735377SArnaldo Carvalho de Melo { 4983f735377SArnaldo Carvalho de Melo struct rb_node *n; 4993f735377SArnaldo Carvalho de Melo 5003f735377SArnaldo Carvalho de Melo n = root->rb_node; 5013f735377SArnaldo Carvalho de Melo if (!n) 5023f735377SArnaldo Carvalho de Melo return NULL; 5033f735377SArnaldo Carvalho de Melo while (n->rb_right) 5043f735377SArnaldo Carvalho de Melo n = n->rb_right; 5053f735377SArnaldo Carvalho de Melo return n; 5063f735377SArnaldo Carvalho de Melo } 5073f735377SArnaldo Carvalho de Melo 5083f735377SArnaldo Carvalho de Melo struct rb_node *rb_next(const struct rb_node *node) 5093f735377SArnaldo Carvalho de Melo { 5103f735377SArnaldo Carvalho de Melo struct rb_node *parent; 5113f735377SArnaldo Carvalho de Melo 5123f735377SArnaldo Carvalho de Melo if (RB_EMPTY_NODE(node)) 5133f735377SArnaldo Carvalho de Melo return NULL; 5143f735377SArnaldo Carvalho de Melo 5153f735377SArnaldo Carvalho de Melo /* 5163f735377SArnaldo Carvalho de Melo * If we have a right-hand child, go down and then left as far 5173f735377SArnaldo Carvalho de Melo * as we can. 5183f735377SArnaldo Carvalho de Melo */ 5193f735377SArnaldo Carvalho de Melo if (node->rb_right) { 5203f735377SArnaldo Carvalho de Melo node = node->rb_right; 5213f735377SArnaldo Carvalho de Melo while (node->rb_left) 5223f735377SArnaldo Carvalho de Melo node=node->rb_left; 5233f735377SArnaldo Carvalho de Melo return (struct rb_node *)node; 5243f735377SArnaldo Carvalho de Melo } 5253f735377SArnaldo Carvalho de Melo 5263f735377SArnaldo Carvalho de Melo /* 5273f735377SArnaldo Carvalho de Melo * No right-hand children. Everything down and left is smaller than us, 5283f735377SArnaldo Carvalho de Melo * so any 'next' node must be in the general direction of our parent. 5293f735377SArnaldo Carvalho de Melo * Go up the tree; any time the ancestor is a right-hand child of its 5303f735377SArnaldo Carvalho de Melo * parent, keep going up. First time it's a left-hand child of its 5313f735377SArnaldo Carvalho de Melo * parent, said parent is our 'next' node. 5323f735377SArnaldo Carvalho de Melo */ 5333f735377SArnaldo Carvalho de Melo while ((parent = rb_parent(node)) && node == parent->rb_right) 5343f735377SArnaldo Carvalho de Melo node = parent; 5353f735377SArnaldo Carvalho de Melo 5363f735377SArnaldo Carvalho de Melo return parent; 5373f735377SArnaldo Carvalho de Melo } 5383f735377SArnaldo Carvalho de Melo 5393f735377SArnaldo Carvalho de Melo struct rb_node *rb_prev(const struct rb_node *node) 5403f735377SArnaldo Carvalho de Melo { 5413f735377SArnaldo Carvalho de Melo struct rb_node *parent; 5423f735377SArnaldo Carvalho de Melo 5433f735377SArnaldo Carvalho de Melo if (RB_EMPTY_NODE(node)) 5443f735377SArnaldo Carvalho de Melo return NULL; 5453f735377SArnaldo Carvalho de Melo 5463f735377SArnaldo Carvalho de Melo /* 5473f735377SArnaldo Carvalho de Melo * If we have a left-hand child, go down and then right as far 5483f735377SArnaldo Carvalho de Melo * as we can. 5493f735377SArnaldo Carvalho de Melo */ 5503f735377SArnaldo Carvalho de Melo if (node->rb_left) { 5513f735377SArnaldo Carvalho de Melo node = node->rb_left; 5523f735377SArnaldo Carvalho de Melo while (node->rb_right) 5533f735377SArnaldo Carvalho de Melo node=node->rb_right; 5543f735377SArnaldo Carvalho de Melo return (struct rb_node *)node; 5553f735377SArnaldo Carvalho de Melo } 5563f735377SArnaldo Carvalho de Melo 5573f735377SArnaldo Carvalho de Melo /* 5583f735377SArnaldo Carvalho de Melo * No left-hand children. Go up till we find an ancestor which 5593f735377SArnaldo Carvalho de Melo * is a right-hand child of its parent. 5603f735377SArnaldo Carvalho de Melo */ 5613f735377SArnaldo Carvalho de Melo while ((parent = rb_parent(node)) && node == parent->rb_left) 5623f735377SArnaldo Carvalho de Melo node = parent; 5633f735377SArnaldo Carvalho de Melo 5643f735377SArnaldo Carvalho de Melo return parent; 5653f735377SArnaldo Carvalho de Melo } 5663f735377SArnaldo Carvalho de Melo 5673f735377SArnaldo Carvalho de Melo void rb_replace_node(struct rb_node *victim, struct rb_node *new, 5683f735377SArnaldo Carvalho de Melo struct rb_root *root) 5693f735377SArnaldo Carvalho de Melo { 5703f735377SArnaldo Carvalho de Melo struct rb_node *parent = rb_parent(victim); 5713f735377SArnaldo Carvalho de Melo 5723aef2cadSDavidlohr Bueso /* Copy the pointers/colour from the victim to the replacement */ 5733aef2cadSDavidlohr Bueso *new = *victim; 5743aef2cadSDavidlohr Bueso 5753f735377SArnaldo Carvalho de Melo /* Set the surrounding nodes to point to the replacement */ 5763f735377SArnaldo Carvalho de Melo if (victim->rb_left) 5773f735377SArnaldo Carvalho de Melo rb_set_parent(victim->rb_left, new); 5783f735377SArnaldo Carvalho de Melo if (victim->rb_right) 5793f735377SArnaldo Carvalho de Melo rb_set_parent(victim->rb_right, new); 5803aef2cadSDavidlohr Bueso __rb_change_child(victim, new, parent, root); 5813aef2cadSDavidlohr Bueso } 5823f735377SArnaldo Carvalho de Melo 5833aef2cadSDavidlohr Bueso void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, 5843aef2cadSDavidlohr Bueso struct rb_root_cached *root) 5853aef2cadSDavidlohr Bueso { 5863aef2cadSDavidlohr Bueso rb_replace_node(victim, new, &root->rb_root); 5873aef2cadSDavidlohr Bueso 5883aef2cadSDavidlohr Bueso if (root->rb_leftmost == victim) 5893aef2cadSDavidlohr Bueso root->rb_leftmost = new; 5903f735377SArnaldo Carvalho de Melo } 5913f735377SArnaldo Carvalho de Melo 5923f735377SArnaldo Carvalho de Melo static struct rb_node *rb_left_deepest_node(const struct rb_node *node) 5933f735377SArnaldo Carvalho de Melo { 5943f735377SArnaldo Carvalho de Melo for (;;) { 5953f735377SArnaldo Carvalho de Melo if (node->rb_left) 5963f735377SArnaldo Carvalho de Melo node = node->rb_left; 5973f735377SArnaldo Carvalho de Melo else if (node->rb_right) 5983f735377SArnaldo Carvalho de Melo node = node->rb_right; 5993f735377SArnaldo Carvalho de Melo else 6003f735377SArnaldo Carvalho de Melo return (struct rb_node *)node; 6013f735377SArnaldo Carvalho de Melo } 6023f735377SArnaldo Carvalho de Melo } 6033f735377SArnaldo Carvalho de Melo 6043f735377SArnaldo Carvalho de Melo struct rb_node *rb_next_postorder(const struct rb_node *node) 6053f735377SArnaldo Carvalho de Melo { 6063f735377SArnaldo Carvalho de Melo const struct rb_node *parent; 6073f735377SArnaldo Carvalho de Melo if (!node) 6083f735377SArnaldo Carvalho de Melo return NULL; 6093f735377SArnaldo Carvalho de Melo parent = rb_parent(node); 6103f735377SArnaldo Carvalho de Melo 6113f735377SArnaldo Carvalho de Melo /* If we're sitting on node, we've already seen our children */ 6123f735377SArnaldo Carvalho de Melo if (parent && node == parent->rb_left && parent->rb_right) { 6133f735377SArnaldo Carvalho de Melo /* If we are the parent's left node, go to the parent's right 6143f735377SArnaldo Carvalho de Melo * node then all the way down to the left */ 6153f735377SArnaldo Carvalho de Melo return rb_left_deepest_node(parent->rb_right); 6163f735377SArnaldo Carvalho de Melo } else 6173f735377SArnaldo Carvalho de Melo /* Otherwise we are the parent's right node, and the parent 6183f735377SArnaldo Carvalho de Melo * should be next */ 6193f735377SArnaldo Carvalho de Melo return (struct rb_node *)parent; 6203f735377SArnaldo Carvalho de Melo } 6213f735377SArnaldo Carvalho de Melo 6223f735377SArnaldo Carvalho de Melo struct rb_node *rb_first_postorder(const struct rb_root *root) 6233f735377SArnaldo Carvalho de Melo { 6243f735377SArnaldo Carvalho de Melo if (!root->rb_node) 6253f735377SArnaldo Carvalho de Melo return NULL; 6263f735377SArnaldo Carvalho de Melo 6273f735377SArnaldo Carvalho de Melo return rb_left_deepest_node(root->rb_node); 6283f735377SArnaldo Carvalho de Melo } 629