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