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
55 			   struct rb_root_cached *root, bool newleft,  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()
64 rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_add_augmented_cached()  argument
68 	struct rb_node **link = &tree->rb_root.rb_node;  in rb_add_augmented_cached()
74 		if (less(node, parent)) {  in rb_add_augmented_cached()
75 			link = &parent->rb_left;  in rb_add_augmented_cached()
77 			link = &parent->rb_right;  in rb_add_augmented_cached()
82 	rb_link_node(node, parent, link);  in rb_add_augmented_cached()
83 	augment->propagate(parent, NULL); /* suboptimal */  in rb_add_augmented_cached()
84 	rb_insert_augmented_cached(node, tree, leftmost, augment);  in rb_add_augmented_cached()
86 	return leftmost ? node : NULL;  in rb_add_augmented_cached()
106 		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
107 		if (RBCOMPUTE(node, true))				\
109 		rb = rb_parent(&node->RBFIELD);				\
117 	new->RBAUGMENTED = old->RBAUGMENTED;				\
124 	new->RBAUGMENTED = old->RBAUGMENTED;				\
135  * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
143  * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
148 static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
151 	RBTYPE max = RBCOMPUTE(node);					      \
152 	if (node->RBFIELD.rb_left) {					      \
153 		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
154 		if (child->RBAUGMENTED > max)				      \
155 			max = child->RBAUGMENTED;			      \
157 	if (node->RBFIELD.rb_right) {					      \
158 		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
159 		if (child->RBAUGMENTED > max)				      \
160 			max = child->RBAUGMENTED;			      \
162 	if (exit && node->RBAUGMENTED == max)				      \
164 	node->RBAUGMENTED = max;					      \
179 #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
180 #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
181 #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
185 	rb->__rb_parent_color = rb_color(rb) + (unsigned long)p;  in rb_set_parent()
191 	rb->__rb_parent_color = (unsigned long)p + color;  in rb_set_parent_color()
196 		  struct rb_node *parent, struct rb_root *root)  in __rb_change_child()  argument
199 		if (parent->rb_left == old)  in __rb_change_child()
200 			WRITE_ONCE(parent->rb_left, new);  in __rb_change_child()
202 			WRITE_ONCE(parent->rb_right, new);  in __rb_change_child()
204 		WRITE_ONCE(root->rb_node, new);  in __rb_change_child()
209 		      struct rb_node *parent, struct rb_root *root)  in __rb_change_child_rcu()  argument
212 		if (parent->rb_left == old)  in __rb_change_child_rcu()
213 			rcu_assign_pointer(parent->rb_left, new);  in __rb_change_child_rcu()
215 			rcu_assign_pointer(parent->rb_right, new);  in __rb_change_child_rcu()
217 		rcu_assign_pointer(root->rb_node, new);  in __rb_change_child_rcu()
220 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
224 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,  in __rb_erase_augmented()  argument
227 	struct rb_node *child = node->rb_right;  in __rb_erase_augmented()
228 	struct rb_node *tmp = node->rb_left;  in __rb_erase_augmented()
234 		 * Case 1: node to erase has no more than 1 child (easy!)  in __rb_erase_augmented()
237 		 * and node must be black due to 4). We adjust colors locally  in __rb_erase_augmented()
240 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
242 		__rb_change_child(node, child, parent, root);  in __rb_erase_augmented()
244 			child->__rb_parent_color = pc;  in __rb_erase_augmented()
250 		/* Still case 1, but this time the child is node->rb_left */  in __rb_erase_augmented()
251 		tmp->__rb_parent_color = pc = node->__rb_parent_color;  in __rb_erase_augmented()
253 		__rb_change_child(node, tmp, parent, root);  in __rb_erase_augmented()
259 		tmp = child->rb_left;  in __rb_erase_augmented()
262 			 * Case 2: node's successor is its right child  in __rb_erase_augmented()
266 			 *  (x) (s)  ->  (x) (c)  in __rb_erase_augmented()
271 			child2 = successor->rb_right;  in __rb_erase_augmented()
273 			augment->copy(node, successor);  in __rb_erase_augmented()
276 			 * Case 3: node's successor is leftmost under  in __rb_erase_augmented()
277 			 * node's right child subtree  in __rb_erase_augmented()
281 			 *  (x) (y)  ->  (x) (y)  in __rb_erase_augmented()
292 				tmp = tmp->rb_left;  in __rb_erase_augmented()
294 			child2 = successor->rb_right;  in __rb_erase_augmented()
295 			WRITE_ONCE(parent->rb_left, child2);  in __rb_erase_augmented()
296 			WRITE_ONCE(successor->rb_right, child);  in __rb_erase_augmented()
299 			augment->copy(node, successor);  in __rb_erase_augmented()
300 			augment->propagate(parent, successor);  in __rb_erase_augmented()
303 		tmp = node->rb_left;  in __rb_erase_augmented()
304 		WRITE_ONCE(successor->rb_left, tmp);  in __rb_erase_augmented()
307 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
309 		__rb_change_child(node, successor, tmp, root);  in __rb_erase_augmented()
317 		successor->__rb_parent_color = pc;  in __rb_erase_augmented()
321 	augment->propagate(tmp, NULL);  in __rb_erase_augmented()
326 rb_erase_augmented(struct rb_node *node, struct rb_root *root,  in rb_erase_augmented()  argument
329 	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);  in rb_erase_augmented()
331 		__rb_erase_color(rebalance, root, augment->rotate);  in rb_erase_augmented()
335 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,  in rb_erase_augmented_cached()  argument
338 	if (root->rb_leftmost == node)  in rb_erase_augmented_cached()
339 		root->rb_leftmost = rb_next(node);  in rb_erase_augmented_cached()
340 	rb_erase_augmented(node, &root->rb_root, augment);  in rb_erase_augmented_cached()