1 /* SPDX-License-Identifier: GPL-2.0+ */
18  * Please note - only struct rb_augment_callbacks and the prototypes for
26 	void (*propagate)(struct rb_node *node, struct rb_node *stop);
31 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
34 rb_insert_augmented(struct rb_node *node, struct rb_root *root,  in rb_insert_augmented()  argument
37 	__rb_insert_augmented(node, root, augment->rotate);  in rb_insert_augmented()
46 		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
47 		rbtype augmented = rbcompute(node);			\
48 		if (node->rbaugmented == augmented)			\
50 		node->rbaugmented = augmented;				\
51 		rb = rb_parent(&node->rbfield);				\
59 	new->rbaugmented = old->rbaugmented;				\
66 	new->rbaugmented = old->rbaugmented;				\
67 	old->rbaugmented = rbcompute(old);				\
82 #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
83 #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
84 #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
88 	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;  in rb_set_parent()
94 	rb->__rb_parent_color = (unsigned long)p | color;  in rb_set_parent_color()
99 		  struct rb_node *parent, struct rb_root *root)  in __rb_change_child()  argument
102 		if (parent->rb_left == old)  in __rb_change_child()
103 			parent->rb_left = new;  in __rb_change_child()
105 			parent->rb_right = new;  in __rb_change_child()
107 		root->rb_node = new;  in __rb_change_child()
110 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
114 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,  in __rb_erase_augmented()  argument
117 	struct rb_node *child = node->rb_right, *tmp = node->rb_left;  in __rb_erase_augmented()
123 		 * Case 1: node to erase has no more than 1 child (easy!)  in __rb_erase_augmented()
126 		 * and node must be black due to 4). We adjust colors locally  in __rb_erase_augmented()
129 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
131 		__rb_change_child(node, child, parent, root);  in __rb_erase_augmented()
133 			child->__rb_parent_color = pc;  in __rb_erase_augmented()
139 		/* Still case 1, but this time the child is node->rb_left */  in __rb_erase_augmented()
140 		tmp->__rb_parent_color = pc = node->__rb_parent_color;  in __rb_erase_augmented()
142 		__rb_change_child(node, tmp, parent, root);  in __rb_erase_augmented()
147 		tmp = child->rb_left;  in __rb_erase_augmented()
150 			 * Case 2: node's successor is its right child  in __rb_erase_augmented()
154 			 *  (x) (s)  ->  (x) (c)  in __rb_erase_augmented()
159 			child2 = successor->rb_right;  in __rb_erase_augmented()
160 			augment->copy(node, successor);  in __rb_erase_augmented()
163 			 * Case 3: node's successor is leftmost under  in __rb_erase_augmented()
164 			 * node's right child subtree  in __rb_erase_augmented()
168 			 *  (x) (y)  ->  (x) (y)  in __rb_erase_augmented()
179 				tmp = tmp->rb_left;  in __rb_erase_augmented()
181 			parent->rb_left = child2 = successor->rb_right;  in __rb_erase_augmented()
182 			successor->rb_right = child;  in __rb_erase_augmented()
184 			augment->copy(node, successor);  in __rb_erase_augmented()
185 			augment->propagate(parent, successor);  in __rb_erase_augmented()
188 		successor->rb_left = tmp = node->rb_left;  in __rb_erase_augmented()
191 		pc = node->__rb_parent_color;  in __rb_erase_augmented()
193 		__rb_change_child(node, successor, tmp, root);  in __rb_erase_augmented()
195 			successor->__rb_parent_color = pc;  in __rb_erase_augmented()
199 			unsigned long pc2 = successor->__rb_parent_color;  in __rb_erase_augmented()
200 			successor->__rb_parent_color = pc;  in __rb_erase_augmented()
206 	augment->propagate(tmp, NULL);  in __rb_erase_augmented()
211 rb_erase_augmented(struct rb_node *node, struct rb_root *root,  in rb_erase_augmented()  argument
214 	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);  in rb_erase_augmented()
216 		__rb_erase_color(rebalance, root, augment->rotate);  in rb_erase_augmented()