Lines Matching +full:child +full:- +full:node
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
20 * Please note - only struct rb_augment_callbacks and the prototypes for
24 * See Documentation/core-api/rbtree.rst for documentation and samples.
28 void (*propagate)(struct rb_node *node, struct rb_node *stop);
33 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
40 * leading to the inserted node, then call rb_link_node() as usual and
47 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented() argument
50 __rb_insert_augmented(node, root, augment->rotate); in rb_insert_augmented()
54 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached() argument
59 root->rb_leftmost = node; in rb_insert_augmented_cached()
60 rb_insert_augmented(node, &root->rb_root, augment); in rb_insert_augmented_cached()
80 RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \
81 if (RBCOMPUTE(node, true)) \
83 rb = rb_parent(&node->RBFIELD); \
91 new->RBAUGMENTED = old->RBAUGMENTED; \
98 new->RBAUGMENTED = old->RBAUGMENTED; \
109 * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
117 * RBCOMPUTE: name of function that returns the per-node RBTYPE scalar
122 static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit) \
124 RBSTRUCT *child; \
125 RBTYPE max = RBCOMPUTE(node); \
126 if (node->RBFIELD.rb_left) { \
127 child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
128 if (child->RBAUGMENTED > max) \
129 max = child->RBAUGMENTED; \
131 if (node->RBFIELD.rb_right) { \
132 child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
133 if (child->RBAUGMENTED > max) \
134 max = child->RBAUGMENTED; \
136 if (exit && node->RBAUGMENTED == max) \
138 node->RBAUGMENTED = max; \
153 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
154 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
155 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
159 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; in rb_set_parent()
165 rb->__rb_parent_color = (unsigned long)p | color; in rb_set_parent_color()
173 if (parent->rb_left == old) in __rb_change_child()
174 WRITE_ONCE(parent->rb_left, new); in __rb_change_child()
176 WRITE_ONCE(parent->rb_right, new); in __rb_change_child()
178 WRITE_ONCE(root->rb_node, new); in __rb_change_child()
186 if (parent->rb_left == old) in __rb_change_child_rcu()
187 rcu_assign_pointer(parent->rb_left, new); in __rb_change_child_rcu()
189 rcu_assign_pointer(parent->rb_right, new); in __rb_change_child_rcu()
191 rcu_assign_pointer(root->rb_node, new); in __rb_change_child_rcu()
198 __rb_erase_augmented(struct rb_node *node, struct rb_root *root, in __rb_erase_augmented() argument
201 struct rb_node *child = node->rb_right; in __rb_erase_augmented() local
202 struct rb_node *tmp = node->rb_left; in __rb_erase_augmented()
208 * Case 1: node to erase has no more than 1 child (easy!) in __rb_erase_augmented()
210 * Note that if there is one child it must be red due to 5) in __rb_erase_augmented()
211 * and node must be black due to 4). We adjust colors locally in __rb_erase_augmented()
214 pc = node->__rb_parent_color; in __rb_erase_augmented()
216 __rb_change_child(node, child, parent, root); in __rb_erase_augmented()
217 if (child) { in __rb_erase_augmented()
218 child->__rb_parent_color = pc; in __rb_erase_augmented()
223 } else if (!child) { in __rb_erase_augmented()
224 /* Still case 1, but this time the child is node->rb_left */ in __rb_erase_augmented()
225 tmp->__rb_parent_color = pc = node->__rb_parent_color; in __rb_erase_augmented()
227 __rb_change_child(node, tmp, parent, root); in __rb_erase_augmented()
231 struct rb_node *successor = child, *child2; in __rb_erase_augmented()
233 tmp = child->rb_left; in __rb_erase_augmented()
236 * Case 2: node's successor is its right child in __rb_erase_augmented()
240 * (x) (s) -> (x) (c) in __rb_erase_augmented()
245 child2 = successor->rb_right; in __rb_erase_augmented()
247 augment->copy(node, successor); in __rb_erase_augmented()
250 * Case 3: node's successor is leftmost under in __rb_erase_augmented()
251 * node's right child subtree in __rb_erase_augmented()
255 * (x) (y) -> (x) (y) in __rb_erase_augmented()
266 tmp = tmp->rb_left; in __rb_erase_augmented()
268 child2 = successor->rb_right; in __rb_erase_augmented()
269 WRITE_ONCE(parent->rb_left, child2); in __rb_erase_augmented()
270 WRITE_ONCE(successor->rb_right, child); in __rb_erase_augmented()
271 rb_set_parent(child, successor); in __rb_erase_augmented()
273 augment->copy(node, successor); in __rb_erase_augmented()
274 augment->propagate(parent, successor); in __rb_erase_augmented()
277 tmp = node->rb_left; in __rb_erase_augmented()
278 WRITE_ONCE(successor->rb_left, tmp); in __rb_erase_augmented()
281 pc = node->__rb_parent_color; in __rb_erase_augmented()
283 __rb_change_child(node, successor, tmp, root); in __rb_erase_augmented()
291 successor->__rb_parent_color = pc; in __rb_erase_augmented()
295 augment->propagate(tmp, NULL); in __rb_erase_augmented()
300 rb_erase_augmented(struct rb_node *node, struct rb_root *root, in rb_erase_augmented() argument
303 struct rb_node *rebalance = __rb_erase_augmented(node, root, augment); in rb_erase_augmented()
305 __rb_erase_color(rebalance, root, augment->rotate); in rb_erase_augmented()
309 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root, in rb_erase_augmented_cached() argument
312 if (root->rb_leftmost == node) in rb_erase_augmented_cached()
313 root->rb_leftmost = rb_next(node); in rb_erase_augmented_cached()
314 rb_erase_augmented(node, &root->rb_root, augment); in rb_erase_augmented_cached()