1 /* SPDX-License-Identifier: GPL-2.0-or-later */ 2 /* 3 Red Black Trees 4 (C) 1999 Andrea Arcangeli <andrea@suse.de> 5 (C) 2002 David Woodhouse <dwmw2@infradead.org> 6 (C) 2012 Michel Lespinasse <walken@google.com> 7 8 9 tools/linux/include/linux/rbtree_augmented.h 10 11 Copied from: 12 linux/include/linux/rbtree_augmented.h 13 */ 14 15 #ifndef _TOOLS_LINUX_RBTREE_AUGMENTED_H 16 #define _TOOLS_LINUX_RBTREE_AUGMENTED_H 17 18 #include <linux/compiler.h> 19 #include <linux/rbtree.h> 20 21 /* 22 * Please note - only struct rb_augment_callbacks and the prototypes for 23 * rb_insert_augmented() and rb_erase_augmented() are intended to be public. 24 * The rest are implementation details you are not expected to depend on. 25 * 26 * See Documentation/rbtree.txt for documentation and samples. 27 */ 28 29 struct rb_augment_callbacks { 30 void (*propagate)(struct rb_node *node, struct rb_node *stop); 31 void (*copy)(struct rb_node *old, struct rb_node *new); 32 void (*rotate)(struct rb_node *old, struct rb_node *new); 33 }; 34 35 extern void __rb_insert_augmented(struct rb_node *node, 36 struct rb_root *root, 37 bool newleft, struct rb_node **leftmost, 38 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); 39 /* 40 * Fixup the rbtree and update the augmented information when rebalancing. 41 * 42 * On insertion, the user must update the augmented information on the path 43 * leading to the inserted node, then call rb_link_node() as usual and 44 * rb_augment_inserted() instead of the usual rb_insert_color() call. 45 * If rb_augment_inserted() rebalances the rbtree, it will callback into 46 * a user provided function to update the augmented information on the 47 * affected subtrees. 48 */ 49 static inline void 50 rb_insert_augmented(struct rb_node *node, struct rb_root *root, 51 const struct rb_augment_callbacks *augment) 52 { 53 __rb_insert_augmented(node, root, false, NULL, augment->rotate); 54 } 55 56 static inline void 57 rb_insert_augmented_cached(struct rb_node *node, 58 struct rb_root_cached *root, bool newleft, 59 const struct rb_augment_callbacks *augment) 60 { 61 __rb_insert_augmented(node, &root->rb_root, 62 newleft, &root->rb_leftmost, augment->rotate); 63 } 64 65 #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \ 66 rbtype, rbaugmented, rbcompute) \ 67 static inline void \ 68 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \ 69 { \ 70 while (rb != stop) { \ 71 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \ 72 rbtype augmented = rbcompute(node); \ 73 if (node->rbaugmented == augmented) \ 74 break; \ 75 node->rbaugmented = augmented; \ 76 rb = rb_parent(&node->rbfield); \ 77 } \ 78 } \ 79 static inline void \ 80 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ 81 { \ 82 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ 83 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ 84 new->rbaugmented = old->rbaugmented; \ 85 } \ 86 static void \ 87 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ 88 { \ 89 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ 90 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ 91 new->rbaugmented = old->rbaugmented; \ 92 old->rbaugmented = rbcompute(old); \ 93 } \ 94 rbstatic const struct rb_augment_callbacks rbname = { \ 95 .propagate = rbname ## _propagate, \ 96 .copy = rbname ## _copy, \ 97 .rotate = rbname ## _rotate \ 98 }; 99 100 101 #define RB_RED 0 102 #define RB_BLACK 1 103 104 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) 105 106 #define __rb_color(pc) ((pc) & 1) 107 #define __rb_is_black(pc) __rb_color(pc) 108 #define __rb_is_red(pc) (!__rb_color(pc)) 109 #define rb_color(rb) __rb_color((rb)->__rb_parent_color) 110 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) 111 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) 112 113 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 114 { 115 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; 116 } 117 118 static inline void rb_set_parent_color(struct rb_node *rb, 119 struct rb_node *p, int color) 120 { 121 rb->__rb_parent_color = (unsigned long)p | color; 122 } 123 124 static inline void 125 __rb_change_child(struct rb_node *old, struct rb_node *new, 126 struct rb_node *parent, struct rb_root *root) 127 { 128 if (parent) { 129 if (parent->rb_left == old) 130 WRITE_ONCE(parent->rb_left, new); 131 else 132 WRITE_ONCE(parent->rb_right, new); 133 } else 134 WRITE_ONCE(root->rb_node, new); 135 } 136 137 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, 138 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); 139 140 static __always_inline struct rb_node * 141 __rb_erase_augmented(struct rb_node *node, struct rb_root *root, 142 struct rb_node **leftmost, 143 const struct rb_augment_callbacks *augment) 144 { 145 struct rb_node *child = node->rb_right; 146 struct rb_node *tmp = node->rb_left; 147 struct rb_node *parent, *rebalance; 148 unsigned long pc; 149 150 if (leftmost && node == *leftmost) 151 *leftmost = rb_next(node); 152 153 if (!tmp) { 154 /* 155 * Case 1: node to erase has no more than 1 child (easy!) 156 * 157 * Note that if there is one child it must be red due to 5) 158 * and node must be black due to 4). We adjust colors locally 159 * so as to bypass __rb_erase_color() later on. 160 */ 161 pc = node->__rb_parent_color; 162 parent = __rb_parent(pc); 163 __rb_change_child(node, child, parent, root); 164 if (child) { 165 child->__rb_parent_color = pc; 166 rebalance = NULL; 167 } else 168 rebalance = __rb_is_black(pc) ? parent : NULL; 169 tmp = parent; 170 } else if (!child) { 171 /* Still case 1, but this time the child is node->rb_left */ 172 tmp->__rb_parent_color = pc = node->__rb_parent_color; 173 parent = __rb_parent(pc); 174 __rb_change_child(node, tmp, parent, root); 175 rebalance = NULL; 176 tmp = parent; 177 } else { 178 struct rb_node *successor = child, *child2; 179 180 tmp = child->rb_left; 181 if (!tmp) { 182 /* 183 * Case 2: node's successor is its right child 184 * 185 * (n) (s) 186 * / \ / \ 187 * (x) (s) -> (x) (c) 188 * \ 189 * (c) 190 */ 191 parent = successor; 192 child2 = successor->rb_right; 193 194 augment->copy(node, successor); 195 } else { 196 /* 197 * Case 3: node's successor is leftmost under 198 * node's right child subtree 199 * 200 * (n) (s) 201 * / \ / \ 202 * (x) (y) -> (x) (y) 203 * / / 204 * (p) (p) 205 * / / 206 * (s) (c) 207 * \ 208 * (c) 209 */ 210 do { 211 parent = successor; 212 successor = tmp; 213 tmp = tmp->rb_left; 214 } while (tmp); 215 child2 = successor->rb_right; 216 WRITE_ONCE(parent->rb_left, child2); 217 WRITE_ONCE(successor->rb_right, child); 218 rb_set_parent(child, successor); 219 220 augment->copy(node, successor); 221 augment->propagate(parent, successor); 222 } 223 224 tmp = node->rb_left; 225 WRITE_ONCE(successor->rb_left, tmp); 226 rb_set_parent(tmp, successor); 227 228 pc = node->__rb_parent_color; 229 tmp = __rb_parent(pc); 230 __rb_change_child(node, successor, tmp, root); 231 232 if (child2) { 233 successor->__rb_parent_color = pc; 234 rb_set_parent_color(child2, parent, RB_BLACK); 235 rebalance = NULL; 236 } else { 237 unsigned long pc2 = successor->__rb_parent_color; 238 successor->__rb_parent_color = pc; 239 rebalance = __rb_is_black(pc2) ? parent : NULL; 240 } 241 tmp = successor; 242 } 243 244 augment->propagate(tmp, NULL); 245 return rebalance; 246 } 247 248 static __always_inline void 249 rb_erase_augmented(struct rb_node *node, struct rb_root *root, 250 const struct rb_augment_callbacks *augment) 251 { 252 struct rb_node *rebalance = __rb_erase_augmented(node, root, 253 NULL, augment); 254 if (rebalance) 255 __rb_erase_color(rebalance, root, augment->rotate); 256 } 257 258 static __always_inline void 259 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root, 260 const struct rb_augment_callbacks *augment) 261 { 262 struct rb_node *rebalance = __rb_erase_augmented(node, &root->rb_root, 263 &root->rb_leftmost, 264 augment); 265 if (rebalance) 266 __rb_erase_color(rebalance, &root->rb_root, augment->rotate); 267 } 268 269 #endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */ 270