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()
88 		uint8_t side = tree->lessthan_fn(node, stack[sz - 1]) ? 0U : 1U;  in find_and_stack()
102 struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side)  in z_rb_get_minmax()  argument
106 	for (n = tree->root; (n != NULL) && (get_child(n, side) != NULL);  in z_rb_get_minmax()
154  * too.  Iteratively fix the tree so it becomes a valid red black tree
196 		/* We can rotate locally to fix the whole tree.  First  in fix_extra_red()
219 void rb_insert(struct rbtree *tree, struct rbnode *node)  in rb_insert()  argument
224 	if (tree->root == NULL) {  in rb_insert()
225 		tree->root = node;  in rb_insert()
226 		tree->max_depth = 1;  in rb_insert()
232 	struct rbnode **stack = &tree->iter_stack[0];  in rb_insert()
234 	struct rbnode *stack[tree->max_depth + 1];  in rb_insert()
237 	int stacksz = find_and_stack(tree, node, stack);  in rb_insert()
241 	uint8_t side = tree->lessthan_fn(node, parent) ? 0U : 1U;  in rb_insert()
250 	if (stacksz > tree->max_depth) {  in rb_insert()
251 		tree->max_depth = stacksz;  in rb_insert()
255 	tree->root = stack[0];  in rb_insert()
256 	CHECK(is_black(tree->root));  in rb_insert()
263  * the tree to preserve red/black rules.  The "null_node" pointer is
265  * tree munging needs a real node for simplicity, so we use it and
286 		 * tree)  in fix_missing_black()
323 				/* Recoloring makes the whole tree OK */  in fix_missing_black()
357 		 * and recolor to produce a valid tree.  in fix_missing_black()
372 void rb_remove(struct rbtree *tree, struct rbnode *node)  in rb_remove()  argument
376 	struct rbnode **stack = &tree->iter_stack[0];  in rb_remove()
378 	struct rbnode *stack[tree->max_depth + 1];  in rb_remove()
381 	int stacksz = find_and_stack(tree, node, stack);  in rb_remove()
389 	 * of 1 would work too) and swap our spot in the tree with  in rb_remove()
408 		/* Now swap the position of node/node2 in the tree.  in rb_remove()
417 		 * may be the root of the tree and not have a parent,  in rb_remove()
427 			tree->root = node2;  in rb_remove()
464 		tree->root = child;  in rb_remove()
468 			tree->max_depth = 0;  in rb_remove()
491 		 * black in a valid tree), then we're done.  in rb_remove()
500 	tree->root = stack[0];  in rb_remove()
524 bool rb_contains(struct rbtree *tree, struct rbnode *node)  in rb_contains()  argument
526 	struct rbnode *n = tree->root;  in rb_contains()
529 		n = get_child(n, tree->lessthan_fn(n, node));  in rb_contains()
564 struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f)  in z_rb_foreach_next()  argument
568 	if (tree->root == NULL) {  in z_rb_foreach_next()
576 		return stack_left_limb(tree->root, f);  in z_rb_foreach_next()
596 	/* If we had no left tree and are a right child then our  in z_rb_foreach_next()