Lines Matching +full:parent +full:- +full:child

1 /* SPDX-License-Identifier: GPL-2.0-or-later */
22 * Please note - only struct rb_augment_callbacks and the prototypes for
26 * See Documentation/core-api/rbtree.rst for documentation and samples.
52 __rb_insert_augmented(node, root, augment->rotate); in rb_insert_augmented()
61 root->rb_leftmost = node; in rb_insert_augmented_cached()
62 rb_insert_augmented(node, &root->rb_root, augment); in rb_insert_augmented_cached()
85 rb = rb_parent(&node->RBFIELD); \
93 new->RBAUGMENTED = old->RBAUGMENTED; \
100 new->RBAUGMENTED = old->RBAUGMENTED; \
119 * RBCOMPUTE: name of function that returns the per-node RBTYPE scalar
126 RBSTRUCT *child; \
128 if (node->RBFIELD.rb_left) { \
129 child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
130 if (child->RBAUGMENTED > max) \
131 max = child->RBAUGMENTED; \
133 if (node->RBFIELD.rb_right) { \
134 child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
135 if (child->RBAUGMENTED > max) \
136 max = child->RBAUGMENTED; \
138 if (exit && node->RBAUGMENTED == max) \
140 node->RBAUGMENTED = max; \
155 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
156 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
157 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
161 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; in rb_set_parent()
167 rb->__rb_parent_color = (unsigned long)p | color; in rb_set_parent_color()
172 struct rb_node *parent, struct rb_root *root) in __rb_change_child() argument
174 if (parent) { in __rb_change_child()
175 if (parent->rb_left == old) in __rb_change_child()
176 WRITE_ONCE(parent->rb_left, new); in __rb_change_child()
178 WRITE_ONCE(parent->rb_right, new); in __rb_change_child()
180 WRITE_ONCE(root->rb_node, new); in __rb_change_child()
183 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
190 struct rb_node *child = node->rb_right; in __rb_erase_augmented() local
191 struct rb_node *tmp = node->rb_left; in __rb_erase_augmented()
192 struct rb_node *parent, *rebalance; in __rb_erase_augmented() local
197 * Case 1: node to erase has no more than 1 child (easy!) in __rb_erase_augmented()
199 * Note that if there is one child it must be red due to 5) in __rb_erase_augmented()
203 pc = node->__rb_parent_color; in __rb_erase_augmented()
204 parent = __rb_parent(pc); in __rb_erase_augmented()
205 __rb_change_child(node, child, parent, root); in __rb_erase_augmented()
206 if (child) { in __rb_erase_augmented()
207 child->__rb_parent_color = pc; in __rb_erase_augmented()
210 rebalance = __rb_is_black(pc) ? parent : NULL; in __rb_erase_augmented()
211 tmp = parent; in __rb_erase_augmented()
212 } else if (!child) { in __rb_erase_augmented()
213 /* Still case 1, but this time the child is node->rb_left */ in __rb_erase_augmented()
214 tmp->__rb_parent_color = pc = node->__rb_parent_color; in __rb_erase_augmented()
215 parent = __rb_parent(pc); in __rb_erase_augmented()
216 __rb_change_child(node, tmp, parent, root); in __rb_erase_augmented()
218 tmp = parent; in __rb_erase_augmented()
220 struct rb_node *successor = child, *child2; in __rb_erase_augmented()
222 tmp = child->rb_left; in __rb_erase_augmented()
225 * Case 2: node's successor is its right child in __rb_erase_augmented()
229 * (x) (s) -> (x) (c) in __rb_erase_augmented()
233 parent = successor; in __rb_erase_augmented()
234 child2 = successor->rb_right; in __rb_erase_augmented()
236 augment->copy(node, successor); in __rb_erase_augmented()
240 * node's right child subtree in __rb_erase_augmented()
244 * (x) (y) -> (x) (y) in __rb_erase_augmented()
253 parent = successor; in __rb_erase_augmented()
255 tmp = tmp->rb_left; in __rb_erase_augmented()
257 child2 = successor->rb_right; in __rb_erase_augmented()
258 WRITE_ONCE(parent->rb_left, child2); in __rb_erase_augmented()
259 WRITE_ONCE(successor->rb_right, child); in __rb_erase_augmented()
260 rb_set_parent(child, successor); in __rb_erase_augmented()
262 augment->copy(node, successor); in __rb_erase_augmented()
263 augment->propagate(parent, successor); in __rb_erase_augmented()
266 tmp = node->rb_left; in __rb_erase_augmented()
267 WRITE_ONCE(successor->rb_left, tmp); in __rb_erase_augmented()
270 pc = node->__rb_parent_color; in __rb_erase_augmented()
275 successor->__rb_parent_color = pc; in __rb_erase_augmented()
276 rb_set_parent_color(child2, parent, RB_BLACK); in __rb_erase_augmented()
279 unsigned long pc2 = successor->__rb_parent_color; in __rb_erase_augmented()
280 successor->__rb_parent_color = pc; in __rb_erase_augmented()
281 rebalance = __rb_is_black(pc2) ? parent : NULL; in __rb_erase_augmented()
286 augment->propagate(tmp, NULL); in __rb_erase_augmented()
296 __rb_erase_color(rebalance, root, augment->rotate); in rb_erase_augmented()
303 if (root->rb_leftmost == node) in rb_erase_augmented_cached()
304 root->rb_leftmost = rb_next(node); in rb_erase_augmented_cached()
305 rb_erase_augmented(node, &root->rb_root, augment); in rb_erase_augmented_cached()