74  * should be, leaving all nodes found in the resulting stack.  Note
75  * that tree must not be empty and that stack should be allocated to
77  * entries pushed onto the stack.
80 			  struct rbnode **stack)  in find_and_stack()  argument
84 	stack[sz] = tree->root;  in find_and_stack()
87 	while (stack[sz - 1] != node) {  in find_and_stack()
88 		uint8_t side = tree->lessthan_fn(node, stack[sz - 1]) ? 0U : 1U;  in find_and_stack()
89 		struct rbnode *ch = get_child(stack[sz - 1], side);  in find_and_stack()
92 			stack[sz] = ch;  in find_and_stack()
121  * stack, modifying the stack accordingly. Does not change the color
130 static void rotate(struct rbnode **stack, int stacksz)  in rotate()  argument
134 	struct rbnode *parent = stack[stacksz - 2];  in rotate()
135 	struct rbnode *child = stack[stacksz - 1];  in rotate()
141 		struct rbnode *grandparent = stack[stacksz - 3];  in rotate()
149 	stack[stacksz - 2] = child;  in rotate()
150 	stack[stacksz - 1] = parent;  in rotate()
153 /* The node at the top of the provided stack is red, and its parent is
157 static void fix_extra_red(struct rbnode **stack, int stacksz)  in fix_extra_red()  argument
160 		struct rbnode *node = stack[stacksz - 1];  in fix_extra_red()
161 		struct rbnode *parent = stack[stacksz - 2];  in fix_extra_red()
178 		struct rbnode *grandparent = stack[stacksz - 3];  in fix_extra_red()
203 			rotate(stack, stacksz);  in fix_extra_red()
207 		rotate(stack, stacksz - 1);  in fix_extra_red()
208 		set_color(stack[stacksz - 3], BLACK);  in fix_extra_red()
209 		set_color(stack[stacksz - 2], RED);  in fix_extra_red()
216 	set_color(stack[0], BLACK);  in fix_extra_red()
232 	struct rbnode **stack = &tree->iter_stack[0];  in rb_insert()  local
234 	struct rbnode *stack[tree->max_depth + 1];  in rb_insert()  local
237 	int stacksz = find_and_stack(tree, node, stack);  in rb_insert()
239 	struct rbnode *parent = stack[stacksz - 1];  in rb_insert()
246 	stack[stacksz] = node;  in rb_insert()
248 	fix_extra_red(stack, stacksz);  in rb_insert()
255 	tree->root = stack[0];  in rb_insert()
259 /* Called for a node N (at the top of the stack) which after a
269 static void fix_missing_black(struct rbnode **stack, int stacksz,  in fix_missing_black()  argument
275 		struct rbnode *n = stack[stacksz - 1];  in fix_missing_black()
276 		struct rbnode *parent = stack[stacksz - 2];  in fix_missing_black()
289 			stack[stacksz - 1] = sib;  in fix_missing_black()
290 			rotate(stack, stacksz);  in fix_missing_black()
293 			stack[stacksz] = n;  in fix_missing_black()
296 			parent = stack[stacksz - 2];  in fix_missing_black()
339 			stack[stacksz - 1] = sib;  in fix_missing_black()
340 			stack[stacksz] = inner;  in fix_missing_black()
342 			rotate(stack, stacksz);  in fix_missing_black()
346 			/* Restore stack state to have N on the top  in fix_missing_black()
349 			sib = stack[stacksz - 2];  in fix_missing_black()
351 			stack[stacksz - 2] = n;  in fix_missing_black()
363 		stack[stacksz - 1] = sib;  in fix_missing_black()
364 		rotate(stack, stacksz);  in fix_missing_black()
376 	struct rbnode **stack = &tree->iter_stack[0];  in rb_remove()  local
378 	struct rbnode *stack[tree->max_depth + 1];  in rb_remove()  local
381 	int stacksz = find_and_stack(tree, node, stack);  in rb_remove()
383 	if (node != stack[stacksz - 1]) {  in rb_remove()
397 		hiparent = (stacksz > 1) ? stack[stacksz - 2] : NULL;  in rb_remove()
398 		stack[stacksz] = node2;  in rb_remove()
402 			stack[stacksz] = node2;  in rb_remove()
406 		loparent = stack[stacksz - 2];  in rb_remove()
421 		 * pointers, so the stack tracking this structure  in rb_remove()
443 		tmp = stack[stacksz0 - 1];  in rb_remove()
444 		stack[stacksz0 - 1] = stack[stacksz - 1];  in rb_remove()
445 		stack[stacksz - 1] = tmp;  in rb_remove()
473 	struct rbnode *parent = stack[stacksz - 2];  in rb_remove()
482 			fix_missing_black(stack, stacksz, node);  in rb_remove()
500 	tree->root = stack[0];  in rb_remove()
535 /* Pushes the node and its chain of left-side children onto the stack
544 	f->stack[f->top] = n;  in stack_left_limb()
549 		f->stack[f->top] = n;  in stack_left_limb()
553 	return f->stack[f->top];  in stack_left_limb()
556 /* The foreach tracking works via a dynamic stack allocated via
557  * alloca().  The current node is found in stack[top] (and its parent
558  * is thus stack[top-1]).  The side of each stacked node from its
560  * node/stack[top] is the left child of stack[top-1]).  The special
561  * case of top == -1 indicates that the stack is uninitialized and we
562  * need to push an initial stack starting at the root.
573 	 * root as our first node, initializing the stack on the way.  in z_rb_foreach_next()
582 	n = get_child(f->stack[f->top], 1U);  in z_rb_foreach_next()
593 		return f->stack[--f->top];  in z_rb_foreach_next()
597 	 * parent was already walked, so walk up the stack looking for  in z_rb_foreach_next()
605 	return (f->top >= 0) ? f->stack[f->top] : NULL;  in z_rb_foreach_next()