7 /* These assertions are very useful when debugging the tree code
72 /* Searches the tree down to a node that is either identical with the
75  * that tree must not be empty and that stack should be allocated to
76  * contain at least tree->max_depth entries!  Returns the number of
79 static int find_and_stack(struct rbtree *tree, struct rbnode *node,  in find_and_stack()  argument
84 	stack[sz++] = tree->root;  in find_and_stack()
87 		uint8_t side = tree->lessthan_fn(node, stack[sz - 1]) ? 0U : 1U;  in find_and_stack()
100 struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side)  in z_rb_get_minmax()  argument
104 	for (n = tree->root; (n != NULL) && (get_child(n, side) != NULL);  in z_rb_get_minmax()
152  * too.  Iteratively fix the tree so it becomes a valid red black tree
194 		/* We can rotate locally to fix the whole tree.  First  in fix_extra_red()
217 void rb_insert(struct rbtree *tree, struct rbnode *node)  in rb_insert()  argument
222 	if (tree->root == NULL) {  in rb_insert()
223 		tree->root = node;  in rb_insert()
224 		tree->max_depth = 1;  in rb_insert()
230 	struct rbnode **stack = &tree->iter_stack[0];  in rb_insert()
232 	struct rbnode *stack[tree->max_depth + 1];  in rb_insert()
235 	int stacksz = find_and_stack(tree, node, stack);  in rb_insert()
239 	uint8_t side = tree->lessthan_fn(node, parent) ? 0U : 1U;  in rb_insert()
247 	if (stacksz > tree->max_depth) {  in rb_insert()
248 		tree->max_depth = stacksz;  in rb_insert()
252 	tree->root = stack[0];  in rb_insert()
253 	CHECK(is_black(tree->root));  in rb_insert()
260  * the tree to preserve red/black rules.  The "null_node" pointer is
262  * tree munging needs a real node for simplicity, so we use it and
283 		 * tree)  in fix_missing_black()
319 				/* Recoloring makes the whole tree OK */  in fix_missing_black()
352 		 * and recolor to produce a valid tree.  in fix_missing_black()
367 void rb_remove(struct rbtree *tree, struct rbnode *node)  in rb_remove()  argument
371 	struct rbnode **stack = &tree->iter_stack[0];  in rb_remove()
373 	struct rbnode *stack[tree->max_depth + 1];  in rb_remove()
376 	int stacksz = find_and_stack(tree, node, stack);  in rb_remove()
384 	 * of 1 would work too) and swap our spot in the tree with  in rb_remove()
401 		/* Now swap the position of node/node2 in the tree.  in rb_remove()
410 		 * may be the root of the tree and not have a parent,  in rb_remove()
420 			tree->root = node2;  in rb_remove()
457 		tree->root = child;  in rb_remove()
461 			tree->max_depth = 0;  in rb_remove()
484 		 * black in a valid tree), then we're done.  in rb_remove()
493 	tree->root = stack[0];  in rb_remove()
517 bool rb_contains(struct rbtree *tree, struct rbnode *node)  in rb_contains()  argument
519 	struct rbnode *n = tree->root;  in rb_contains()
522 		n = get_child(n, tree->lessthan_fn(n, node));  in rb_contains()
557 struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f)  in z_rb_foreach_next()  argument
561 	if (tree->root == NULL) {  in z_rb_foreach_next()
569 		return stack_left_limb(tree->root, f);  in z_rb_foreach_next()
589 	/* If we had no left tree and are a right child then our  in z_rb_foreach_next()