7  * SPDX-License-Identifier:	GPL-2.0+
19  * Please note - only struct rb_augment_callbacks and the prototypes for
27 	void (*propagate)(struct rb_node *node, struct rb_node *stop);
32 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
35 rb_insert_augmented(struct rb_node *node, struct rb_root *root,  in rb_insert_augmented()  argument
38 	__rb_insert_augmented(node, root, augment->rotate);  in rb_insert_augmented()
47 		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
48 		rbtype augmented = rbcompute(node);			\
49 		if (node->rbaugmented == augmented)			\
51 		node->rbaugmented = augmented;				\
52 		rb = rb_parent(&node->rbfield);				\
60 	new->rbaugmented = old->rbaugmented;				\
67 	new->rbaugmented = old->rbaugmented;				\
68 	old->rbaugmented = rbcompute(old);				\
83 #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
84 #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
85 #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
89 	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;  in rb_set_parent()
95 	rb->__rb_parent_color = (unsigned long)p | color;  in rb_set_parent_color()
100 		  struct rb_node *parent, struct rb_root *root)  in __rb_change_child()  argument
103 		if (parent->rb_left == old)  in __rb_change_child()
104 			parent->rb_left = new;  in __rb_change_child()
106 			parent->rb_right = new;  in __rb_change_child()
108 		root->rb_node = new;  in __rb_change_child()
111 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
115 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,  in __rb_erase_augmented()  argument
118 	struct rb_node *child = node->rb_right, *tmp = node->rb_left;  in __rb_erase_augmented()
124 		 * Case 1: node to erase has no more than 1 child (easy!)  in __rb_erase_augmented()
127 		 * and node must be black due to 4). We adjust colors locally  in __rb_erase_augmented()
130 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
132 		__rb_change_child(node, child, parent, root);  in __rb_erase_augmented()
134 			child->__rb_parent_color = pc;  in __rb_erase_augmented()
140 		/* Still case 1, but this time the child is node->rb_left */  in __rb_erase_augmented()
141 		tmp->__rb_parent_color = pc = node->__rb_parent_color;  in __rb_erase_augmented()
143 		__rb_change_child(node, tmp, parent, root);  in __rb_erase_augmented()
148 		tmp = child->rb_left;  in __rb_erase_augmented()
151 			 * Case 2: node's successor is its right child  in __rb_erase_augmented()
155 			 *  (x) (s)  ->  (x) (c)  in __rb_erase_augmented()
160 			child2 = successor->rb_right;  in __rb_erase_augmented()
161 			augment->copy(node, successor);  in __rb_erase_augmented()
164 			 * Case 3: node's successor is leftmost under  in __rb_erase_augmented()
165 			 * node's right child subtree  in __rb_erase_augmented()
169 			 *  (x) (y)  ->  (x) (y)  in __rb_erase_augmented()
180 				tmp = tmp->rb_left;  in __rb_erase_augmented()
182 			parent->rb_left = child2 = successor->rb_right;  in __rb_erase_augmented()
183 			successor->rb_right = child;  in __rb_erase_augmented()
185 			augment->copy(node, successor);  in __rb_erase_augmented()
186 			augment->propagate(parent, successor);  in __rb_erase_augmented()
189 		successor->rb_left = tmp = node->rb_left;  in __rb_erase_augmented()
192 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
194 		__rb_change_child(node, successor, tmp, root);  in __rb_erase_augmented()
196 			successor->__rb_parent_color = pc;  in __rb_erase_augmented()
200 			unsigned long pc2 = successor->__rb_parent_color;  in __rb_erase_augmented()
201 			successor->__rb_parent_color = pc;  in __rb_erase_augmented()
207 	augment->propagate(tmp, NULL);  in __rb_erase_augmented()
212 rb_erase_augmented(struct rb_node *node, struct rb_root *root,  in rb_erase_augmented()  argument
215 	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);  in rb_erase_augmented()
217 		__rb_erase_color(rebalance, root, augment->rotate);  in rb_erase_augmented()