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.
50 	__rb_insert_augmented(node, root, augment->rotate);  in rb_insert_augmented()
59 		root->rb_leftmost = node;  in rb_insert_augmented_cached()
60 	rb_insert_augmented(node, &root->rb_root, augment);  in rb_insert_augmented_cached()
83 		rb = rb_parent(&node->RBFIELD);				\
91 	new->RBAUGMENTED = old->RBAUGMENTED;				\
98 	new->RBAUGMENTED = old->RBAUGMENTED;				\
117  * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
124 	RBSTRUCT *child;						      \
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()
170 		  struct rb_node *parent, struct rb_root *root)  in __rb_change_child()  argument
172 	if (parent) {  in __rb_change_child()
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()
183 		      struct rb_node *parent, struct rb_root *root)  in __rb_change_child_rcu()  argument
185 	if (parent) {  in __rb_change_child_rcu()
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()
194 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
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()
203 	struct rb_node *parent, *rebalance;  in __rb_erase_augmented()  local
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()
214 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
215 		parent = __rb_parent(pc);  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()
221 			rebalance = __rb_is_black(pc) ? parent : NULL;  in __rb_erase_augmented()
222 		tmp = parent;  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()
226 		parent = __rb_parent(pc);  in __rb_erase_augmented()
227 		__rb_change_child(node, tmp, parent, root);  in __rb_erase_augmented()
229 		tmp = parent;  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()
244 			parent = successor;  in __rb_erase_augmented()
245 			child2 = successor->rb_right;  in __rb_erase_augmented()
247 			augment->copy(node, successor);  in __rb_erase_augmented()
251 			 * node's right child subtree  in __rb_erase_augmented()
255 			 *  (x) (y)  ->  (x) (y)  in __rb_erase_augmented()
264 				parent = successor;  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()
286 			rb_set_parent_color(child2, parent, RB_BLACK);  in __rb_erase_augmented()
289 			rebalance = rb_is_black(successor) ? parent : NULL;  in __rb_erase_augmented()
291 		successor->__rb_parent_color = pc;  in __rb_erase_augmented()
295 	augment->propagate(tmp, NULL);  in __rb_erase_augmented()
305 		__rb_erase_color(rebalance, root, augment->rotate);  in rb_erase_augmented()
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()