1e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng/* 2e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng Red Black Trees 3e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (C) 1999 Andrea Arcangeli <andrea@suse.de> 4e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (C) 2002 David Woodhouse <dwmw2@infradead.org> 5e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (C) 2012 Michel Lespinasse <walken@google.com> 6e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 7e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng This program is free software; you can redistribute it and/or modify 8e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng it under the terms of the GNU General Public License as published by 9e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng the Free Software Foundation; either version 2 of the License, or 10e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (at your option) any later version. 11e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 12e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng This program is distributed in the hope that it will be useful, 13e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng but WITHOUT ANY WARRANTY; without even the implied warranty of 14e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng GNU General Public License for more details. 16e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 17e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng You should have received a copy of the GNU General Public License 18e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng along with this program; if not, write to the Free Software 19e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 21e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng linux/include/linux/rbtree_augmented.h 22e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng*/ 23e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 24e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#ifndef _LINUX_RBTREE_AUGMENTED_H 25e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define _LINUX_RBTREE_AUGMENTED_H 26e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 27e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#include <linux/compiler.h> 28e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#include <linux/rbtree.h> 29e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 30e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng/* 31e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Please note - only struct rb_augment_callbacks and the prototypes for 32e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * rb_insert_augmented() and rb_erase_augmented() are intended to be public. 33e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * The rest are implementation details you are not expected to depend on. 34e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * 35e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * See Documentation/rbtree.txt for documentation and samples. 36e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 37e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 38e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstruct rb_augment_callbacks { 39e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng void (*propagate)(struct rb_node *node, struct rb_node *stop); 40e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng void (*copy)(struct rb_node *old, struct rb_node *new); 41e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng void (*rotate)(struct rb_node *old, struct rb_node *new); 42e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng}; 43e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 44e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengextern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 45e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); 46e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void 47e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengrb_insert_augmented(struct rb_node *node, struct rb_root *root, 48e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng const struct rb_augment_callbacks *augment) 49e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 50e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng __rb_insert_augmented(node, root, augment->rotate); 51e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 52e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 53e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \ 54e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbtype, rbaugmented, rbcompute) \ 55e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void \ 56e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengrbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \ 57e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ \ 58e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng while (rb != stop) { \ 59e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbstruct *node = rb_entry(rb, rbstruct, rbfield); \ 60e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbtype augmented = rbcompute(node); \ 61e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (node->rbaugmented == augmented) \ 62e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng break; \ 63e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng node->rbaugmented = augmented; \ 64e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rb = rb_parent(&node->rbfield); \ 65e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } \ 66e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} \ 67e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void \ 68e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengrbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ 69e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ \ 70e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ 71e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ 72e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng new->rbaugmented = old->rbaugmented; \ 73e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} \ 74e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic void \ 75e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengrbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ 76e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ \ 77e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ 78e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ 79e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng new->rbaugmented = old->rbaugmented; \ 80e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng old->rbaugmented = rbcompute(old); \ 81e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} \ 82e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengrbstatic const struct rb_augment_callbacks rbname = { \ 83e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rbname ## _propagate, rbname ## _copy, rbname ## _rotate \ 84e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng}; 85e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 86e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 87e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define RB_RED 0 88e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define RB_BLACK 1 89e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 90e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) 91e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 92e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define __rb_color(pc) ((pc) & 1) 93e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define __rb_is_black(pc) __rb_color(pc) 94e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define __rb_is_red(pc) (!__rb_color(pc)) 95e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define rb_color(rb) __rb_color((rb)->__rb_parent_color) 96e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) 97e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) 98e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 99e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 100e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 101e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 102e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 103e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 104e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void rb_set_parent_color(struct rb_node *rb, 105e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng struct rb_node *p, int color) 106e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 107e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rb->__rb_parent_color = (unsigned long)p | color; 108e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 109e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 110e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void 111e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng__rb_change_child(struct rb_node *old, struct rb_node *new, 112e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng struct rb_node *parent, struct rb_root *root) 113e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 114e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (parent) { 115e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (parent->rb_left == old) 116e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent->rb_left = new; 117e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng else 118e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent->rb_right = new; 119e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } else 120e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng root->rb_node = new; 121e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 122e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 123e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengextern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, 124e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); 125e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 126e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic __always_inline struct rb_node * 127e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng__rb_erase_augmented(struct rb_node *node, struct rb_root *root, 128e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng const struct rb_augment_callbacks *augment) 129e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 130e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng struct rb_node *child = node->rb_right, *tmp = node->rb_left; 131e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng struct rb_node *parent, *rebalance; 132e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng unsigned long pc; 133e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 134e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (!tmp) { 135e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng /* 136e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Case 1: node to erase has no more than 1 child (easy!) 137e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * 138e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Note that if there is one child it must be red due to 5) 139e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * and node must be black due to 4). We adjust colors locally 140e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * so as to bypass __rb_erase_color() later on. 141e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 142e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng pc = node->__rb_parent_color; 143e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent = __rb_parent(pc); 144e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng __rb_change_child(node, child, parent, root); 145e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (child) { 146e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng child->__rb_parent_color = pc; 147e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rebalance = NULL; 148e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } else 149e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rebalance = __rb_is_black(pc) ? parent : NULL; 150e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = parent; 151e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } else if (!child) { 152e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng /* Still case 1, but this time the child is node->rb_left */ 153e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp->__rb_parent_color = pc = node->__rb_parent_color; 154e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent = __rb_parent(pc); 155e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng __rb_change_child(node, tmp, parent, root); 156e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rebalance = NULL; 157e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = parent; 158e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } else { 159e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng struct rb_node *successor = child, *child2; 160e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = child->rb_left; 161e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (!tmp) { 162e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng /* 163e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Case 2: node's successor is its right child 164e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * 165e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (n) (s) 166e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * / \ / \ 167e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (x) (s) -> (x) (c) 168e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * \ 169e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (c) 170e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 171e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent = successor; 172e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng child2 = successor->rb_right; 173e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng augment->copy(node, successor); 174e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } else { 175e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng /* 176e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Case 3: node's successor is leftmost under 177e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * node's right child subtree 178e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * 179e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (n) (s) 180e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * / \ / \ 181e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (x) (y) -> (x) (y) 182e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * / / 183e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (p) (p) 184e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * / / 185e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (s) (c) 186e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * \ 187e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * (c) 188e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 189e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng do { 190e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent = successor; 191e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng successor = tmp; 192e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = tmp->rb_left; 193e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } while (tmp); 194e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng parent->rb_left = child2 = successor->rb_right; 195e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng successor->rb_right = child; 196e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rb_set_parent(child, successor); 197e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng augment->copy(node, successor); 198e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng augment->propagate(parent, successor); 199e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 200e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 201e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng successor->rb_left = tmp = node->rb_left; 202e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rb_set_parent(tmp, successor); 203e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 204e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng pc = node->__rb_parent_color; 205e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = __rb_parent(pc); 206e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng __rb_change_child(node, successor, tmp, root); 207e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (child2) { 208e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng successor->__rb_parent_color = pc; 209e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rb_set_parent_color(child2, parent, RB_BLACK); 210e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rebalance = NULL; 211e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } else { 212e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng unsigned long pc2 = successor->__rb_parent_color; 213e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng successor->__rb_parent_color = pc; 214e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng rebalance = __rb_is_black(pc2) ? parent : NULL; 215e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 216e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = successor; 217e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 218e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 219e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng augment->propagate(tmp, NULL); 220e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return rebalance; 221e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 222e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 223e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic __always_inline void 224e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengrb_erase_augmented(struct rb_node *node, struct rb_root *root, 225e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng const struct rb_augment_callbacks *augment) 226e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 227e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng struct rb_node *rebalance = __rb_erase_augmented(node, root, augment); 228e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (rebalance) 229e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng __rb_erase_color(rebalance, root, augment->rotate); 230e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 231e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 232e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#endif /* _LINUX_RBTREE_AUGMENTED_H */ 233