Lines Matching +full:child +full:- +full:node
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.
30 void (*propagate)(struct rb_node *node, struct rb_node *stop);
35 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
42 * leading to the inserted node, then call rb_link_node() as usual and
49 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented() argument
52 __rb_insert_augmented(node, root, augment->rotate); in rb_insert_augmented()
56 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached() argument
61 root->rb_leftmost = node; in rb_insert_augmented_cached()
62 rb_insert_augmented(node, &root->rb_root, augment); in rb_insert_augmented_cached()
82 RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \
83 if (RBCOMPUTE(node, true)) \
85 rb = rb_parent(&node->RBFIELD); \
93 new->RBAUGMENTED = old->RBAUGMENTED; \
100 new->RBAUGMENTED = old->RBAUGMENTED; \
111 * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
119 * RBCOMPUTE: name of function that returns the per-node RBTYPE scalar
124 static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit) \
126 RBSTRUCT *child; \
127 RBTYPE max = RBCOMPUTE(node); \
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()
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()
187 __rb_erase_augmented(struct rb_node *node, struct rb_root *root, in __rb_erase_augmented() argument
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()
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()
200 * and node must be black due to 4). We adjust colors locally in __rb_erase_augmented()
203 pc = node->__rb_parent_color; 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()
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()
216 __rb_change_child(node, tmp, parent, root); 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()
234 child2 = successor->rb_right; in __rb_erase_augmented()
236 augment->copy(node, successor); in __rb_erase_augmented()
239 * Case 3: node's successor is leftmost under in __rb_erase_augmented()
240 * node's right child subtree in __rb_erase_augmented()
244 * (x) (y) -> (x) (y) 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()
272 __rb_change_child(node, successor, tmp, root); in __rb_erase_augmented()
275 successor->__rb_parent_color = pc; 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()
286 augment->propagate(tmp, NULL); in __rb_erase_augmented()
291 rb_erase_augmented(struct rb_node *node, struct rb_root *root, in rb_erase_augmented() argument
294 struct rb_node *rebalance = __rb_erase_augmented(node, root, augment); in rb_erase_augmented()
296 __rb_erase_color(rebalance, root, augment->rotate); in rb_erase_augmented()
300 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root, in rb_erase_augmented_cached() argument
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()