113 static uint8_t get_side(struct rbnode *parent, struct rbnode *child)  in get_side()  argument
115 	CHECK(get_child(parent, 0U) == child || get_child(parent, 1U) == child);  in get_side()
117 	return (get_child(parent, 1U) == child) ? 1U : 0U;  in get_side()
134 	struct rbnode *parent = stack[stacksz - 2];  in rotate()  local
136 	uint8_t side = get_side(parent, child);  in rotate()
143 		set_child(grandparent, get_side(grandparent, parent), child);  in rotate()
147 	set_child(child, (side == 0U) ? 1U : 0U, parent);  in rotate()
148 	set_child(parent, side, b);  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
161 		struct rbnode *parent = stack[stacksz - 2];  in fix_extra_red()  local
169 		if (is_black(parent)) {  in fix_extra_red()
174 		 * parent is red, as red nodes cannot be the root  in fix_extra_red()
179 		uint8_t side = get_side(grandparent, parent);  in fix_extra_red()
185 			set_color(parent, BLACK);  in fix_extra_red()
189 			 * have a red parent, so continue iterating  in fix_extra_red()
197 		 * make sure that node is on the same side of parent  in fix_extra_red()
198 		 * as parent is of grandparent.  in fix_extra_red()
200 		uint8_t parent_side = get_side(parent, node);  in fix_extra_red()
206 		/* Rotate the grandparent with parent, swapping colors */  in fix_extra_red()
239 	struct rbnode *parent = stack[stacksz - 1];  in rb_insert()  local
241 	uint8_t side = tree->lessthan_fn(node, parent) ? 0U : 1U;  in rb_insert()
243 	set_child(parent, side, node);  in rb_insert()
267  * parent) when finished.
276 		struct rbnode *parent = stack[stacksz - 2];  in fix_missing_black()  local
277 		uint8_t n_side = get_side(parent, n);  in fix_missing_black()
278 		struct rbnode *sib = get_child(parent,  in fix_missing_black()
284 		 * level if needed (after rotate() our parent is the  in fix_missing_black()
291 			set_color(parent, RED);  in fix_missing_black()
296 			parent = stack[stacksz - 2];  in fix_missing_black()
297 			sib = get_child(parent, (n_side == 0U) ? 1U : 0U);  in fix_missing_black()
310 				set_child(parent, n_side, NULL);  in fix_missing_black()
314 			if (is_black(parent)) {  in fix_missing_black()
316 				 * coloring it red, then our parent  in fix_missing_black()
324 				set_color(parent, BLACK);  in fix_missing_black()
356 		 * far/outer slot.  We can rotate sib with our parent  in fix_missing_black()
360 		set_color(sib, get_color(parent));  in fix_missing_black()
361 		set_color(parent, BLACK);  in fix_missing_black()
366 			set_child(parent, n_side, NULL);  in fix_missing_black()
417 		 * may be the root of the tree and not have a parent,  in rb_remove()
420 		 * two nodes also.  And of course we don't have parent  in rb_remove()
473 	struct rbnode *parent = stack[stacksz - 2];  in rb_remove()  local
485 			set_child(parent, get_side(parent, node), NULL);  in rb_remove()
488 		set_child(parent, get_side(parent, node), child);  in rb_remove()
557  * alloca().  The current node is found in stack[top] (and its parent
559  * parent is stored in is_left[] (i.e. if is_left[top] is true, then
587 	/* Otherwise if the node is a left child of its parent, the  in z_rb_foreach_next()
588 	 * next node is the parent (note that the root is stacked  in z_rb_foreach_next()
590 	 * even if node has no parent).  in z_rb_foreach_next()
597 	 * parent was already walked, so walk up the stack looking for  in z_rb_foreach_next()
598 	 * a left child (whose parent is unwalked, and thus next).  in z_rb_foreach_next()