128 static void rotate(struct rbnode **stack, int stacksz)  in rotate()  argument
130 	CHECK(stacksz >= 2);  in rotate()
132 	struct rbnode *parent = stack[stacksz - 2];  in rotate()
133 	struct rbnode *child = stack[stacksz - 1];  in rotate()
138 	if (stacksz >= 3) {  in rotate()
139 		struct rbnode *grandparent = stack[stacksz - 3];  in rotate()
147 	stack[stacksz - 2] = child;  in rotate()
148 	stack[stacksz - 1] = parent;  in rotate()
155 static void fix_extra_red(struct rbnode **stack, int stacksz)  in fix_extra_red()  argument
157 	while (stacksz > 1) {  in fix_extra_red()
158 		struct rbnode *node = stack[stacksz - 1];  in fix_extra_red()
159 		struct rbnode *parent = stack[stacksz - 2];  in fix_extra_red()
174 		CHECK(stacksz >= 2);  in fix_extra_red()
176 		struct rbnode *grandparent = stack[stacksz - 3];  in fix_extra_red()
190 			stacksz -= 2;  in fix_extra_red()
201 			rotate(stack, stacksz);  in fix_extra_red()
205 		rotate(stack, stacksz - 1);  in fix_extra_red()
206 		set_color(stack[stacksz - 3], BLACK);  in fix_extra_red()
207 		set_color(stack[stacksz - 2], RED);  in fix_extra_red()
235 	int stacksz = find_and_stack(tree, node, stack);  in rb_insert()  local
237 	struct rbnode *parent = stack[stacksz - 1];  in rb_insert()
244 	stack[stacksz++] = node;  in rb_insert()
245 	fix_extra_red(stack, stacksz);  in rb_insert()
247 	if (stacksz > tree->max_depth) {  in rb_insert()
248 		tree->max_depth = stacksz;  in rb_insert()
266 static void fix_missing_black(struct rbnode **stack, int stacksz,  in fix_missing_black()  argument
270 	while (stacksz > 1) {  in fix_missing_black()
272 		struct rbnode *n = stack[stacksz - 1];  in fix_missing_black()
273 		struct rbnode *parent = stack[stacksz - 2];  in fix_missing_black()
286 			stack[stacksz - 1] = sib;  in fix_missing_black()
287 			rotate(stack, stacksz);  in fix_missing_black()
290 			stack[stacksz++] = n;  in fix_missing_black()
292 			parent = stack[stacksz - 2];  in fix_missing_black()
316 				stacksz--;  in fix_missing_black()
335 			stack[stacksz - 1] = sib;  in fix_missing_black()
336 			stack[stacksz++] = inner;  in fix_missing_black()
337 			rotate(stack, stacksz);  in fix_missing_black()
344 			sib = stack[stacksz - 2];  in fix_missing_black()
346 			stack[stacksz - 2] = n;  in fix_missing_black()
347 			stacksz--;  in fix_missing_black()
358 		stack[stacksz - 1] = sib;  in fix_missing_black()
359 		rotate(stack, stacksz);  in fix_missing_black()
376 	int stacksz = find_and_stack(tree, node, stack);  in rb_remove()  local
378 	if (node != stack[stacksz - 1]) {  in rb_remove()
388 		int stacksz0 = stacksz;  in rb_remove()
392 		hiparent = (stacksz > 1) ? stack[stacksz - 2] : NULL;  in rb_remove()
393 		stack[stacksz++] = node2;  in rb_remove()
396 			stack[stacksz++] = node2;  in rb_remove()
399 		loparent = stack[stacksz - 2];  in rb_remove()
437 		stack[stacksz0 - 1] = stack[stacksz - 1];  in rb_remove()
438 		stack[stacksz - 1] = tmp;  in rb_remove()
456 	if (stacksz < 2) {  in rb_remove()
466 	struct rbnode *parent = stack[stacksz - 2];  in rb_remove()
475 			fix_missing_black(stack, stacksz, node);  in rb_remove()