1*83d290c5STom Rini // SPDX-License-Identifier: GPL-2.0+ 278acc472SPeter Tyser /* 378acc472SPeter Tyser Red Black Trees 478acc472SPeter Tyser (C) 1999 Andrea Arcangeli <andrea@suse.de> 578acc472SPeter Tyser (C) 2002 David Woodhouse <dwmw2@infradead.org> 69dd228b5SHeiko Schocher (C) 2012 Michel Lespinasse <walken@google.com> 778acc472SPeter Tyser 878acc472SPeter Tyser linux/lib/rbtree.c 978acc472SPeter Tyser */ 1078acc472SPeter Tyser 119dd228b5SHeiko Schocher #include <linux/rbtree_augmented.h> 129dd228b5SHeiko Schocher #ifndef __UBOOT__ 139dd228b5SHeiko Schocher #include <linux/export.h> 149dd228b5SHeiko Schocher #else 1578acc472SPeter Tyser #include <ubi_uboot.h> 169dd228b5SHeiko Schocher #endif 179dd228b5SHeiko Schocher /* 189dd228b5SHeiko Schocher * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree 199dd228b5SHeiko Schocher * 209dd228b5SHeiko Schocher * 1) A node is either red or black 219dd228b5SHeiko Schocher * 2) The root is black 229dd228b5SHeiko Schocher * 3) All leaves (NULL) are black 239dd228b5SHeiko Schocher * 4) Both children of every red node are black 249dd228b5SHeiko Schocher * 5) Every simple path from root to leaves contains the same number 259dd228b5SHeiko Schocher * of black nodes. 269dd228b5SHeiko Schocher * 279dd228b5SHeiko Schocher * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two 289dd228b5SHeiko Schocher * consecutive red nodes in a path and every red node is therefore followed by 299dd228b5SHeiko Schocher * a black. So if B is the number of black nodes on every simple path (as per 309dd228b5SHeiko Schocher * 5), then the longest possible path due to 4 is 2B. 319dd228b5SHeiko Schocher * 329dd228b5SHeiko Schocher * We shall indicate color with case, where black nodes are uppercase and red 339dd228b5SHeiko Schocher * nodes will be lowercase. Unknown color nodes shall be drawn as red within 349dd228b5SHeiko Schocher * parentheses and have some accompanying text comment. 359dd228b5SHeiko Schocher */ 3678acc472SPeter Tyser 379dd228b5SHeiko Schocher static inline void rb_set_black(struct rb_node *rb) 3878acc472SPeter Tyser { 399dd228b5SHeiko Schocher rb->__rb_parent_color |= RB_BLACK; 409dd228b5SHeiko Schocher } 4178acc472SPeter Tyser 429dd228b5SHeiko Schocher static inline struct rb_node *rb_red_parent(struct rb_node *red) 439dd228b5SHeiko Schocher { 449dd228b5SHeiko Schocher return (struct rb_node *)red->__rb_parent_color; 459dd228b5SHeiko Schocher } 4678acc472SPeter Tyser 479dd228b5SHeiko Schocher /* 489dd228b5SHeiko Schocher * Helper function for rotations: 499dd228b5SHeiko Schocher * - old's parent and color get assigned to new 509dd228b5SHeiko Schocher * - old gets assigned new as a parent and 'color' as a color. 519dd228b5SHeiko Schocher */ 529dd228b5SHeiko Schocher static inline void 539dd228b5SHeiko Schocher __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, 549dd228b5SHeiko Schocher struct rb_root *root, int color) 559dd228b5SHeiko Schocher { 569dd228b5SHeiko Schocher struct rb_node *parent = rb_parent(old); 579dd228b5SHeiko Schocher new->__rb_parent_color = old->__rb_parent_color; 589dd228b5SHeiko Schocher rb_set_parent_color(old, new, color); 599dd228b5SHeiko Schocher __rb_change_child(old, new, parent, root); 609dd228b5SHeiko Schocher } 6178acc472SPeter Tyser 629dd228b5SHeiko Schocher static __always_inline void 639dd228b5SHeiko Schocher __rb_insert(struct rb_node *node, struct rb_root *root, 649dd228b5SHeiko Schocher void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 659dd228b5SHeiko Schocher { 669dd228b5SHeiko Schocher struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 679dd228b5SHeiko Schocher 689dd228b5SHeiko Schocher while (true) { 699dd228b5SHeiko Schocher /* 709dd228b5SHeiko Schocher * Loop invariant: node is red 719dd228b5SHeiko Schocher * 729dd228b5SHeiko Schocher * If there is a black parent, we are done. 739dd228b5SHeiko Schocher * Otherwise, take some corrective action as we don't 749dd228b5SHeiko Schocher * want a red root or two consecutive red nodes. 759dd228b5SHeiko Schocher */ 769dd228b5SHeiko Schocher if (!parent) { 779dd228b5SHeiko Schocher rb_set_parent_color(node, NULL, RB_BLACK); 789dd228b5SHeiko Schocher break; 799dd228b5SHeiko Schocher } else if (rb_is_black(parent)) 809dd228b5SHeiko Schocher break; 819dd228b5SHeiko Schocher 829dd228b5SHeiko Schocher gparent = rb_red_parent(parent); 839dd228b5SHeiko Schocher 849dd228b5SHeiko Schocher tmp = gparent->rb_right; 859dd228b5SHeiko Schocher if (parent != tmp) { /* parent == gparent->rb_left */ 869dd228b5SHeiko Schocher if (tmp && rb_is_red(tmp)) { 879dd228b5SHeiko Schocher /* 889dd228b5SHeiko Schocher * Case 1 - color flips 899dd228b5SHeiko Schocher * 909dd228b5SHeiko Schocher * G g 919dd228b5SHeiko Schocher * / \ / \ 929dd228b5SHeiko Schocher * p u --> P U 939dd228b5SHeiko Schocher * / / 949dd228b5SHeiko Schocher * n N 959dd228b5SHeiko Schocher * 969dd228b5SHeiko Schocher * However, since g's parent might be red, and 979dd228b5SHeiko Schocher * 4) does not allow this, we need to recurse 989dd228b5SHeiko Schocher * at g. 999dd228b5SHeiko Schocher */ 1009dd228b5SHeiko Schocher rb_set_parent_color(tmp, gparent, RB_BLACK); 1019dd228b5SHeiko Schocher rb_set_parent_color(parent, gparent, RB_BLACK); 1029dd228b5SHeiko Schocher node = gparent; 1039dd228b5SHeiko Schocher parent = rb_parent(node); 1049dd228b5SHeiko Schocher rb_set_parent_color(node, parent, RB_RED); 1059dd228b5SHeiko Schocher continue; 1069dd228b5SHeiko Schocher } 1079dd228b5SHeiko Schocher 1089dd228b5SHeiko Schocher tmp = parent->rb_right; 1099dd228b5SHeiko Schocher if (node == tmp) { 1109dd228b5SHeiko Schocher /* 1119dd228b5SHeiko Schocher * Case 2 - left rotate at parent 1129dd228b5SHeiko Schocher * 1139dd228b5SHeiko Schocher * G G 1149dd228b5SHeiko Schocher * / \ / \ 1159dd228b5SHeiko Schocher * p U --> n U 1169dd228b5SHeiko Schocher * \ / 1179dd228b5SHeiko Schocher * n p 1189dd228b5SHeiko Schocher * 1199dd228b5SHeiko Schocher * This still leaves us in violation of 4), the 1209dd228b5SHeiko Schocher * continuation into Case 3 will fix that. 1219dd228b5SHeiko Schocher */ 1229dd228b5SHeiko Schocher parent->rb_right = tmp = node->rb_left; 1239dd228b5SHeiko Schocher node->rb_left = parent; 1249dd228b5SHeiko Schocher if (tmp) 1259dd228b5SHeiko Schocher rb_set_parent_color(tmp, parent, 1269dd228b5SHeiko Schocher RB_BLACK); 1279dd228b5SHeiko Schocher rb_set_parent_color(parent, node, RB_RED); 1289dd228b5SHeiko Schocher augment_rotate(parent, node); 1299dd228b5SHeiko Schocher parent = node; 1309dd228b5SHeiko Schocher tmp = node->rb_right; 1319dd228b5SHeiko Schocher } 1329dd228b5SHeiko Schocher 1339dd228b5SHeiko Schocher /* 1349dd228b5SHeiko Schocher * Case 3 - right rotate at gparent 1359dd228b5SHeiko Schocher * 1369dd228b5SHeiko Schocher * G P 1379dd228b5SHeiko Schocher * / \ / \ 1389dd228b5SHeiko Schocher * p U --> n g 1399dd228b5SHeiko Schocher * / \ 1409dd228b5SHeiko Schocher * n U 1419dd228b5SHeiko Schocher */ 1429dd228b5SHeiko Schocher gparent->rb_left = tmp; /* == parent->rb_right */ 1439dd228b5SHeiko Schocher parent->rb_right = gparent; 1449dd228b5SHeiko Schocher if (tmp) 1459dd228b5SHeiko Schocher rb_set_parent_color(tmp, gparent, RB_BLACK); 1469dd228b5SHeiko Schocher __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1479dd228b5SHeiko Schocher augment_rotate(gparent, parent); 1489dd228b5SHeiko Schocher break; 1499dd228b5SHeiko Schocher } else { 1509dd228b5SHeiko Schocher tmp = gparent->rb_left; 1519dd228b5SHeiko Schocher if (tmp && rb_is_red(tmp)) { 1529dd228b5SHeiko Schocher /* Case 1 - color flips */ 1539dd228b5SHeiko Schocher rb_set_parent_color(tmp, gparent, RB_BLACK); 1549dd228b5SHeiko Schocher rb_set_parent_color(parent, gparent, RB_BLACK); 1559dd228b5SHeiko Schocher node = gparent; 1569dd228b5SHeiko Schocher parent = rb_parent(node); 1579dd228b5SHeiko Schocher rb_set_parent_color(node, parent, RB_RED); 1589dd228b5SHeiko Schocher continue; 1599dd228b5SHeiko Schocher } 1609dd228b5SHeiko Schocher 1619dd228b5SHeiko Schocher tmp = parent->rb_left; 1629dd228b5SHeiko Schocher if (node == tmp) { 1639dd228b5SHeiko Schocher /* Case 2 - right rotate at parent */ 1649dd228b5SHeiko Schocher parent->rb_left = tmp = node->rb_right; 1659dd228b5SHeiko Schocher node->rb_right = parent; 1669dd228b5SHeiko Schocher if (tmp) 1679dd228b5SHeiko Schocher rb_set_parent_color(tmp, parent, 1689dd228b5SHeiko Schocher RB_BLACK); 1699dd228b5SHeiko Schocher rb_set_parent_color(parent, node, RB_RED); 1709dd228b5SHeiko Schocher augment_rotate(parent, node); 1719dd228b5SHeiko Schocher parent = node; 1729dd228b5SHeiko Schocher tmp = node->rb_left; 1739dd228b5SHeiko Schocher } 1749dd228b5SHeiko Schocher 1759dd228b5SHeiko Schocher /* Case 3 - left rotate at gparent */ 1769dd228b5SHeiko Schocher gparent->rb_right = tmp; /* == parent->rb_left */ 1779dd228b5SHeiko Schocher parent->rb_left = gparent; 1789dd228b5SHeiko Schocher if (tmp) 1799dd228b5SHeiko Schocher rb_set_parent_color(tmp, gparent, RB_BLACK); 1809dd228b5SHeiko Schocher __rb_rotate_set_parents(gparent, parent, root, RB_RED); 1819dd228b5SHeiko Schocher augment_rotate(gparent, parent); 1829dd228b5SHeiko Schocher break; 1839dd228b5SHeiko Schocher } 1849dd228b5SHeiko Schocher } 1859dd228b5SHeiko Schocher } 1869dd228b5SHeiko Schocher 1879dd228b5SHeiko Schocher /* 1889dd228b5SHeiko Schocher * Inline version for rb_erase() use - we want to be able to inline 1899dd228b5SHeiko Schocher * and eliminate the dummy_rotate callback there 1909dd228b5SHeiko Schocher */ 1919dd228b5SHeiko Schocher static __always_inline void 1929dd228b5SHeiko Schocher ____rb_erase_color(struct rb_node *parent, struct rb_root *root, 1939dd228b5SHeiko Schocher void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 1949dd228b5SHeiko Schocher { 1959dd228b5SHeiko Schocher struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 1969dd228b5SHeiko Schocher 1979dd228b5SHeiko Schocher while (true) { 1989dd228b5SHeiko Schocher /* 1999dd228b5SHeiko Schocher * Loop invariants: 2009dd228b5SHeiko Schocher * - node is black (or NULL on first iteration) 2019dd228b5SHeiko Schocher * - node is not the root (parent is not NULL) 2029dd228b5SHeiko Schocher * - All leaf paths going through parent and node have a 2039dd228b5SHeiko Schocher * black node count that is 1 lower than other leaf paths. 2049dd228b5SHeiko Schocher */ 2059dd228b5SHeiko Schocher sibling = parent->rb_right; 2069dd228b5SHeiko Schocher if (node != sibling) { /* node == parent->rb_left */ 2079dd228b5SHeiko Schocher if (rb_is_red(sibling)) { 2089dd228b5SHeiko Schocher /* 2099dd228b5SHeiko Schocher * Case 1 - left rotate at parent 2109dd228b5SHeiko Schocher * 2119dd228b5SHeiko Schocher * P S 2129dd228b5SHeiko Schocher * / \ / \ 2139dd228b5SHeiko Schocher * N s --> p Sr 2149dd228b5SHeiko Schocher * / \ / \ 2159dd228b5SHeiko Schocher * Sl Sr N Sl 2169dd228b5SHeiko Schocher */ 2179dd228b5SHeiko Schocher parent->rb_right = tmp1 = sibling->rb_left; 2189dd228b5SHeiko Schocher sibling->rb_left = parent; 2199dd228b5SHeiko Schocher rb_set_parent_color(tmp1, parent, RB_BLACK); 2209dd228b5SHeiko Schocher __rb_rotate_set_parents(parent, sibling, root, 2219dd228b5SHeiko Schocher RB_RED); 2229dd228b5SHeiko Schocher augment_rotate(parent, sibling); 2239dd228b5SHeiko Schocher sibling = tmp1; 2249dd228b5SHeiko Schocher } 2259dd228b5SHeiko Schocher tmp1 = sibling->rb_right; 2269dd228b5SHeiko Schocher if (!tmp1 || rb_is_black(tmp1)) { 2279dd228b5SHeiko Schocher tmp2 = sibling->rb_left; 2289dd228b5SHeiko Schocher if (!tmp2 || rb_is_black(tmp2)) { 2299dd228b5SHeiko Schocher /* 2309dd228b5SHeiko Schocher * Case 2 - sibling color flip 2319dd228b5SHeiko Schocher * (p could be either color here) 2329dd228b5SHeiko Schocher * 2339dd228b5SHeiko Schocher * (p) (p) 2349dd228b5SHeiko Schocher * / \ / \ 2359dd228b5SHeiko Schocher * N S --> N s 2369dd228b5SHeiko Schocher * / \ / \ 2379dd228b5SHeiko Schocher * Sl Sr Sl Sr 2389dd228b5SHeiko Schocher * 2399dd228b5SHeiko Schocher * This leaves us violating 5) which 2409dd228b5SHeiko Schocher * can be fixed by flipping p to black 2419dd228b5SHeiko Schocher * if it was red, or by recursing at p. 2429dd228b5SHeiko Schocher * p is red when coming from Case 1. 2439dd228b5SHeiko Schocher */ 2449dd228b5SHeiko Schocher rb_set_parent_color(sibling, parent, 2459dd228b5SHeiko Schocher RB_RED); 2469dd228b5SHeiko Schocher if (rb_is_red(parent)) 2479dd228b5SHeiko Schocher rb_set_black(parent); 2489dd228b5SHeiko Schocher else { 2499dd228b5SHeiko Schocher node = parent; 2509dd228b5SHeiko Schocher parent = rb_parent(node); 25178acc472SPeter Tyser if (parent) 2529dd228b5SHeiko Schocher continue; 25378acc472SPeter Tyser } 2549dd228b5SHeiko Schocher break; 25578acc472SPeter Tyser } 2569dd228b5SHeiko Schocher /* 2579dd228b5SHeiko Schocher * Case 3 - right rotate at sibling 2589dd228b5SHeiko Schocher * (p could be either color here) 2599dd228b5SHeiko Schocher * 2609dd228b5SHeiko Schocher * (p) (p) 2619dd228b5SHeiko Schocher * / \ / \ 2629dd228b5SHeiko Schocher * N S --> N Sl 2639dd228b5SHeiko Schocher * / \ \ 2649dd228b5SHeiko Schocher * sl Sr s 2659dd228b5SHeiko Schocher * \ 2669dd228b5SHeiko Schocher * Sr 2679dd228b5SHeiko Schocher */ 2689dd228b5SHeiko Schocher sibling->rb_left = tmp1 = tmp2->rb_right; 2699dd228b5SHeiko Schocher tmp2->rb_right = sibling; 2709dd228b5SHeiko Schocher parent->rb_right = tmp2; 2719dd228b5SHeiko Schocher if (tmp1) 2729dd228b5SHeiko Schocher rb_set_parent_color(tmp1, sibling, 2739dd228b5SHeiko Schocher RB_BLACK); 2749dd228b5SHeiko Schocher augment_rotate(sibling, tmp2); 2759dd228b5SHeiko Schocher tmp1 = sibling; 2769dd228b5SHeiko Schocher sibling = tmp2; 2779dd228b5SHeiko Schocher } 2789dd228b5SHeiko Schocher /* 2799dd228b5SHeiko Schocher * Case 4 - left rotate at parent + color flips 2809dd228b5SHeiko Schocher * (p and sl could be either color here. 2819dd228b5SHeiko Schocher * After rotation, p becomes black, s acquires 2829dd228b5SHeiko Schocher * p's color, and sl keeps its color) 2839dd228b5SHeiko Schocher * 2849dd228b5SHeiko Schocher * (p) (s) 2859dd228b5SHeiko Schocher * / \ / \ 2869dd228b5SHeiko Schocher * N S --> P Sr 2879dd228b5SHeiko Schocher * / \ / \ 2889dd228b5SHeiko Schocher * (sl) sr N (sl) 2899dd228b5SHeiko Schocher */ 2909dd228b5SHeiko Schocher parent->rb_right = tmp2 = sibling->rb_left; 2919dd228b5SHeiko Schocher sibling->rb_left = parent; 2929dd228b5SHeiko Schocher rb_set_parent_color(tmp1, sibling, RB_BLACK); 2939dd228b5SHeiko Schocher if (tmp2) 2949dd228b5SHeiko Schocher rb_set_parent(tmp2, parent); 2959dd228b5SHeiko Schocher __rb_rotate_set_parents(parent, sibling, root, 2969dd228b5SHeiko Schocher RB_BLACK); 2979dd228b5SHeiko Schocher augment_rotate(parent, sibling); 2989dd228b5SHeiko Schocher break; 2999dd228b5SHeiko Schocher } else { 3009dd228b5SHeiko Schocher sibling = parent->rb_left; 3019dd228b5SHeiko Schocher if (rb_is_red(sibling)) { 3029dd228b5SHeiko Schocher /* Case 1 - right rotate at parent */ 3039dd228b5SHeiko Schocher parent->rb_left = tmp1 = sibling->rb_right; 3049dd228b5SHeiko Schocher sibling->rb_right = parent; 3059dd228b5SHeiko Schocher rb_set_parent_color(tmp1, parent, RB_BLACK); 3069dd228b5SHeiko Schocher __rb_rotate_set_parents(parent, sibling, root, 3079dd228b5SHeiko Schocher RB_RED); 3089dd228b5SHeiko Schocher augment_rotate(parent, sibling); 3099dd228b5SHeiko Schocher sibling = tmp1; 3109dd228b5SHeiko Schocher } 3119dd228b5SHeiko Schocher tmp1 = sibling->rb_left; 3129dd228b5SHeiko Schocher if (!tmp1 || rb_is_black(tmp1)) { 3139dd228b5SHeiko Schocher tmp2 = sibling->rb_right; 3149dd228b5SHeiko Schocher if (!tmp2 || rb_is_black(tmp2)) { 3159dd228b5SHeiko Schocher /* Case 2 - sibling color flip */ 3169dd228b5SHeiko Schocher rb_set_parent_color(sibling, parent, 3179dd228b5SHeiko Schocher RB_RED); 3189dd228b5SHeiko Schocher if (rb_is_red(parent)) 3199dd228b5SHeiko Schocher rb_set_black(parent); 3209dd228b5SHeiko Schocher else { 3219dd228b5SHeiko Schocher node = parent; 3229dd228b5SHeiko Schocher parent = rb_parent(node); 32378acc472SPeter Tyser if (parent) 3249dd228b5SHeiko Schocher continue; 3259dd228b5SHeiko Schocher } 3269dd228b5SHeiko Schocher break; 3279dd228b5SHeiko Schocher } 3289dd228b5SHeiko Schocher /* Case 3 - right rotate at sibling */ 3299dd228b5SHeiko Schocher sibling->rb_right = tmp1 = tmp2->rb_left; 3309dd228b5SHeiko Schocher tmp2->rb_left = sibling; 3319dd228b5SHeiko Schocher parent->rb_left = tmp2; 3329dd228b5SHeiko Schocher if (tmp1) 3339dd228b5SHeiko Schocher rb_set_parent_color(tmp1, sibling, 3349dd228b5SHeiko Schocher RB_BLACK); 3359dd228b5SHeiko Schocher augment_rotate(sibling, tmp2); 3369dd228b5SHeiko Schocher tmp1 = sibling; 3379dd228b5SHeiko Schocher sibling = tmp2; 3389dd228b5SHeiko Schocher } 3399dd228b5SHeiko Schocher /* Case 4 - left rotate at parent + color flips */ 3409dd228b5SHeiko Schocher parent->rb_left = tmp2 = sibling->rb_right; 3419dd228b5SHeiko Schocher sibling->rb_right = parent; 3429dd228b5SHeiko Schocher rb_set_parent_color(tmp1, sibling, RB_BLACK); 3439dd228b5SHeiko Schocher if (tmp2) 3449dd228b5SHeiko Schocher rb_set_parent(tmp2, parent); 3459dd228b5SHeiko Schocher __rb_rotate_set_parents(parent, sibling, root, 3469dd228b5SHeiko Schocher RB_BLACK); 3479dd228b5SHeiko Schocher augment_rotate(parent, sibling); 3489dd228b5SHeiko Schocher break; 3499dd228b5SHeiko Schocher } 3509dd228b5SHeiko Schocher } 3519dd228b5SHeiko Schocher } 3529dd228b5SHeiko Schocher 3539dd228b5SHeiko Schocher /* Non-inline version for rb_erase_augmented() use */ 3549dd228b5SHeiko Schocher void __rb_erase_color(struct rb_node *parent, struct rb_root *root, 3559dd228b5SHeiko Schocher void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 35678acc472SPeter Tyser { 3579dd228b5SHeiko Schocher ____rb_erase_color(parent, root, augment_rotate); 35878acc472SPeter Tyser } 3599dd228b5SHeiko Schocher EXPORT_SYMBOL(__rb_erase_color); 3609dd228b5SHeiko Schocher 3619dd228b5SHeiko Schocher /* 3629dd228b5SHeiko Schocher * Non-augmented rbtree manipulation functions. 3639dd228b5SHeiko Schocher * 3649dd228b5SHeiko Schocher * We use dummy augmented callbacks here, and have the compiler optimize them 3659dd228b5SHeiko Schocher * out of the rb_insert_color() and rb_erase() function definitions. 3669dd228b5SHeiko Schocher */ 3679dd228b5SHeiko Schocher 3689dd228b5SHeiko Schocher static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} 3699dd228b5SHeiko Schocher static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} 3709dd228b5SHeiko Schocher static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} 3719dd228b5SHeiko Schocher 3729dd228b5SHeiko Schocher static const struct rb_augment_callbacks dummy_callbacks = { 3739dd228b5SHeiko Schocher dummy_propagate, dummy_copy, dummy_rotate 3749dd228b5SHeiko Schocher }; 37578acc472SPeter Tyser 37678acc472SPeter Tyser void rb_insert_color(struct rb_node *node, struct rb_root *root) 37778acc472SPeter Tyser { 3789dd228b5SHeiko Schocher __rb_insert(node, root, dummy_rotate); 37978acc472SPeter Tyser } 3809dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_insert_color); 38178acc472SPeter Tyser 38278acc472SPeter Tyser void rb_erase(struct rb_node *node, struct rb_root *root) 38378acc472SPeter Tyser { 3849dd228b5SHeiko Schocher struct rb_node *rebalance; 3859dd228b5SHeiko Schocher rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); 3869dd228b5SHeiko Schocher if (rebalance) 3879dd228b5SHeiko Schocher ____rb_erase_color(rebalance, root, dummy_rotate); 38878acc472SPeter Tyser } 3899dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_erase); 39078acc472SPeter Tyser 3919dd228b5SHeiko Schocher /* 3929dd228b5SHeiko Schocher * Augmented rbtree manipulation functions. 3939dd228b5SHeiko Schocher * 3949dd228b5SHeiko Schocher * This instantiates the same __always_inline functions as in the non-augmented 3959dd228b5SHeiko Schocher * case, but this time with user-defined callbacks. 3969dd228b5SHeiko Schocher */ 39778acc472SPeter Tyser 3989dd228b5SHeiko Schocher void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 3999dd228b5SHeiko Schocher void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 40078acc472SPeter Tyser { 4019dd228b5SHeiko Schocher __rb_insert(node, root, augment_rotate); 40278acc472SPeter Tyser } 4039dd228b5SHeiko Schocher EXPORT_SYMBOL(__rb_insert_augmented); 40478acc472SPeter Tyser 40578acc472SPeter Tyser /* 40678acc472SPeter Tyser * This function returns the first node (in sort order) of the tree. 40778acc472SPeter Tyser */ 4089dd228b5SHeiko Schocher struct rb_node *rb_first(const struct rb_root *root) 40978acc472SPeter Tyser { 41078acc472SPeter Tyser struct rb_node *n; 41178acc472SPeter Tyser 41278acc472SPeter Tyser n = root->rb_node; 41378acc472SPeter Tyser if (!n) 41478acc472SPeter Tyser return NULL; 41578acc472SPeter Tyser while (n->rb_left) 41678acc472SPeter Tyser n = n->rb_left; 41778acc472SPeter Tyser return n; 41878acc472SPeter Tyser } 4199dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_first); 42078acc472SPeter Tyser 4219dd228b5SHeiko Schocher struct rb_node *rb_last(const struct rb_root *root) 42278acc472SPeter Tyser { 42378acc472SPeter Tyser struct rb_node *n; 42478acc472SPeter Tyser 42578acc472SPeter Tyser n = root->rb_node; 42678acc472SPeter Tyser if (!n) 42778acc472SPeter Tyser return NULL; 42878acc472SPeter Tyser while (n->rb_right) 42978acc472SPeter Tyser n = n->rb_right; 43078acc472SPeter Tyser return n; 43178acc472SPeter Tyser } 4329dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_last); 43378acc472SPeter Tyser 4349dd228b5SHeiko Schocher struct rb_node *rb_next(const struct rb_node *node) 43578acc472SPeter Tyser { 43678acc472SPeter Tyser struct rb_node *parent; 43778acc472SPeter Tyser 4389dd228b5SHeiko Schocher if (RB_EMPTY_NODE(node)) 43978acc472SPeter Tyser return NULL; 44078acc472SPeter Tyser 4419dd228b5SHeiko Schocher /* 4429dd228b5SHeiko Schocher * If we have a right-hand child, go down and then left as far 4439dd228b5SHeiko Schocher * as we can. 4449dd228b5SHeiko Schocher */ 44578acc472SPeter Tyser if (node->rb_right) { 44678acc472SPeter Tyser node = node->rb_right; 44778acc472SPeter Tyser while (node->rb_left) 44878acc472SPeter Tyser node=node->rb_left; 4499dd228b5SHeiko Schocher return (struct rb_node *)node; 45078acc472SPeter Tyser } 45178acc472SPeter Tyser 4529dd228b5SHeiko Schocher /* 4539dd228b5SHeiko Schocher * No right-hand children. Everything down and left is smaller than us, 4549dd228b5SHeiko Schocher * so any 'next' node must be in the general direction of our parent. 4559dd228b5SHeiko Schocher * Go up the tree; any time the ancestor is a right-hand child of its 4569dd228b5SHeiko Schocher * parent, keep going up. First time it's a left-hand child of its 4579dd228b5SHeiko Schocher * parent, said parent is our 'next' node. 4589dd228b5SHeiko Schocher */ 45978acc472SPeter Tyser while ((parent = rb_parent(node)) && node == parent->rb_right) 46078acc472SPeter Tyser node = parent; 46178acc472SPeter Tyser 46278acc472SPeter Tyser return parent; 46378acc472SPeter Tyser } 4649dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_next); 46578acc472SPeter Tyser 4669dd228b5SHeiko Schocher struct rb_node *rb_prev(const struct rb_node *node) 46778acc472SPeter Tyser { 46878acc472SPeter Tyser struct rb_node *parent; 46978acc472SPeter Tyser 4709dd228b5SHeiko Schocher if (RB_EMPTY_NODE(node)) 47178acc472SPeter Tyser return NULL; 47278acc472SPeter Tyser 4739dd228b5SHeiko Schocher /* 4749dd228b5SHeiko Schocher * If we have a left-hand child, go down and then right as far 4759dd228b5SHeiko Schocher * as we can. 4769dd228b5SHeiko Schocher */ 47778acc472SPeter Tyser if (node->rb_left) { 47878acc472SPeter Tyser node = node->rb_left; 47978acc472SPeter Tyser while (node->rb_right) 48078acc472SPeter Tyser node=node->rb_right; 4819dd228b5SHeiko Schocher return (struct rb_node *)node; 48278acc472SPeter Tyser } 48378acc472SPeter Tyser 4849dd228b5SHeiko Schocher /* 4859dd228b5SHeiko Schocher * No left-hand children. Go up till we find an ancestor which 4869dd228b5SHeiko Schocher * is a right-hand child of its parent. 4879dd228b5SHeiko Schocher */ 48878acc472SPeter Tyser while ((parent = rb_parent(node)) && node == parent->rb_left) 48978acc472SPeter Tyser node = parent; 49078acc472SPeter Tyser 49178acc472SPeter Tyser return parent; 49278acc472SPeter Tyser } 4939dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_prev); 49478acc472SPeter Tyser 49578acc472SPeter Tyser void rb_replace_node(struct rb_node *victim, struct rb_node *new, 49678acc472SPeter Tyser struct rb_root *root) 49778acc472SPeter Tyser { 49878acc472SPeter Tyser struct rb_node *parent = rb_parent(victim); 49978acc472SPeter Tyser 50078acc472SPeter Tyser /* Set the surrounding nodes to point to the replacement */ 5019dd228b5SHeiko Schocher __rb_change_child(victim, new, parent, root); 50278acc472SPeter Tyser if (victim->rb_left) 50378acc472SPeter Tyser rb_set_parent(victim->rb_left, new); 50478acc472SPeter Tyser if (victim->rb_right) 50578acc472SPeter Tyser rb_set_parent(victim->rb_right, new); 50678acc472SPeter Tyser 50778acc472SPeter Tyser /* Copy the pointers/colour from the victim to the replacement */ 50878acc472SPeter Tyser *new = *victim; 50978acc472SPeter Tyser } 5109dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_replace_node); 5119dd228b5SHeiko Schocher 5129dd228b5SHeiko Schocher static struct rb_node *rb_left_deepest_node(const struct rb_node *node) 5139dd228b5SHeiko Schocher { 5149dd228b5SHeiko Schocher for (;;) { 5159dd228b5SHeiko Schocher if (node->rb_left) 5169dd228b5SHeiko Schocher node = node->rb_left; 5179dd228b5SHeiko Schocher else if (node->rb_right) 5189dd228b5SHeiko Schocher node = node->rb_right; 5199dd228b5SHeiko Schocher else 5209dd228b5SHeiko Schocher return (struct rb_node *)node; 5219dd228b5SHeiko Schocher } 5229dd228b5SHeiko Schocher } 5239dd228b5SHeiko Schocher 5249dd228b5SHeiko Schocher struct rb_node *rb_next_postorder(const struct rb_node *node) 5259dd228b5SHeiko Schocher { 5269dd228b5SHeiko Schocher const struct rb_node *parent; 5279dd228b5SHeiko Schocher if (!node) 5289dd228b5SHeiko Schocher return NULL; 5299dd228b5SHeiko Schocher parent = rb_parent(node); 5309dd228b5SHeiko Schocher 5319dd228b5SHeiko Schocher /* If we're sitting on node, we've already seen our children */ 5329dd228b5SHeiko Schocher if (parent && node == parent->rb_left && parent->rb_right) { 5339dd228b5SHeiko Schocher /* If we are the parent's left node, go to the parent's right 5349dd228b5SHeiko Schocher * node then all the way down to the left */ 5359dd228b5SHeiko Schocher return rb_left_deepest_node(parent->rb_right); 5369dd228b5SHeiko Schocher } else 5379dd228b5SHeiko Schocher /* Otherwise we are the parent's right node, and the parent 5389dd228b5SHeiko Schocher * should be next */ 5399dd228b5SHeiko Schocher return (struct rb_node *)parent; 5409dd228b5SHeiko Schocher } 5419dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_next_postorder); 5429dd228b5SHeiko Schocher 5439dd228b5SHeiko Schocher struct rb_node *rb_first_postorder(const struct rb_root *root) 5449dd228b5SHeiko Schocher { 5459dd228b5SHeiko Schocher if (!root->rb_node) 5469dd228b5SHeiko Schocher return NULL; 5479dd228b5SHeiko Schocher 5489dd228b5SHeiko Schocher return rb_left_deepest_node(root->rb_node); 5499dd228b5SHeiko Schocher } 5509dd228b5SHeiko Schocher EXPORT_SYMBOL(rb_first_postorder); 551