72 /* Searches the tree down to a node that is either identical with the
73  * "node" argument or has an empty/leaf child pointer where "node"
79 static int find_and_stack(struct rbtree *tree, struct rbnode *node,  in find_and_stack()  argument
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()
122  * of either node.  That is, it effects the following transition (or
153 /* The node at the top of the provided stack is red, and its parent is
160 		struct rbnode *node = stack[stacksz - 1];  in fix_extra_red()  local
164 		CHECK((get_child(node, 0U) == NULL) ||  in fix_extra_red()
165 		      is_black(get_child(node, 0U)));  in fix_extra_red()
166 		CHECK((get_child(node, 1U) == NULL) ||  in fix_extra_red()
167 		      is_black(get_child(node, 1U)));  in fix_extra_red()
197 		 * make sure that node is on the same side of parent  in fix_extra_red()
200 		uint8_t parent_side = get_side(parent, node);  in fix_extra_red()
213 	/* If we exit the loop, it's because our node is now the root,  in fix_extra_red()
219 void rb_insert(struct rbtree *tree, struct rbnode *node)  in rb_insert()  argument
221 	set_child(node, 0U, NULL);  in rb_insert()
222 	set_child(node, 1U, NULL);  in rb_insert()
225 		tree->root = node;  in rb_insert()
227 		set_color(node, BLACK);  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()
243 	set_child(parent, side, node);  in rb_insert()
244 	set_color(node, RED);  in rb_insert()
246 	stack[stacksz] = node;  in rb_insert()
259 /* Called for a node N (at the top of the stack) which after a
264  * for situations where we are removing a childless black node.  The
265  * tree munging needs a real node for simplicity, so we use it and
372 void rb_remove(struct rbtree *tree, struct rbnode *node)  in rb_remove()  argument
381 	int stacksz = find_and_stack(tree, node, stack);  in rb_remove()
383 	if (node != stack[stacksz - 1]) {  in rb_remove()
387 	/* We can only remove a node with zero or one child, if we  in rb_remove()
392 	if ((get_child(node, 0U) != NULL) && (get_child(node, 1U) != NULL)) {  in rb_remove()
395 		struct rbnode *node2 = get_child(node, 0U);  in rb_remove()
408 		/* Now swap the position of node/node2 in the tree.  in rb_remove()
416 		 * them from their parents, but: (1) the upper node  in rb_remove()
418 		 * and (2) the lower node may be a direct child of the  in rb_remove()
419 		 * upper node.  Remember to swap the color bits of the  in rb_remove()
425 			set_child(hiparent, get_side(hiparent, node), node2);  in rb_remove()
430 		if (loparent == node) {  in rb_remove()
431 			set_child(node, 0U, get_child(node2, 0U));  in rb_remove()
432 			set_child(node2, 0U, node);  in rb_remove()
434 			set_child(loparent, get_side(loparent, node2), node);  in rb_remove()
435 			tmp = get_child(node, 0U);  in rb_remove()
436 			set_child(node, 0U, get_child(node2, 0U));  in rb_remove()
440 		set_child(node2, 1U, get_child(node, 1U));  in rb_remove()
441 		set_child(node, 1U, NULL);  in rb_remove()
447 		enum rb_color ctmp = get_color(node);  in rb_remove()
449 		set_color(node, get_color(node2));  in rb_remove()
453 	CHECK((get_child(node, 0U) == NULL) ||  in rb_remove()
454 	      (get_child(node, 1U) == NULL));  in rb_remove()
456 	struct rbnode *child = get_child(node, 0U);  in rb_remove()
459 		child = get_child(node, 1U);  in rb_remove()
475 	/* Special case: if the node to be removed is childless, then  in rb_remove()
481 		if (is_black(node)) {  in rb_remove()
482 			fix_missing_black(stack, stacksz, node);  in rb_remove()
485 			set_child(parent, get_side(parent, node), NULL);  in rb_remove()
488 		set_child(parent, get_side(parent, node), child);  in rb_remove()
493 		__ASSERT(is_black(node) || is_black(child), "both nodes red?!");  in rb_remove()
494 		if (is_red(node) || is_red(child)) {  in rb_remove()
504 void z_rb_walk(struct rbnode *node, rb_visit_t visit_fn, void *cookie)  in z_rb_walk()  argument
506 	if (node != NULL) {  in z_rb_walk()
507 		z_rb_walk(get_child(node, 0U), visit_fn, cookie);  in z_rb_walk()
508 		visit_fn(node, cookie);  in z_rb_walk()
509 		z_rb_walk(get_child(node, 1U), visit_fn, cookie);  in z_rb_walk()
514 struct rbnode *z_rb_child(struct rbnode *node, uint8_t side)  in z_rb_child()  argument
516 	return get_child(node, side);  in z_rb_child()
519 int z_rb_is_black(struct rbnode *node)  in z_rb_is_black()  argument
521 	return is_black(node);  in z_rb_is_black()
524 bool rb_contains(struct rbtree *tree, struct rbnode *node)  in rb_contains()  argument
528 	while ((n != NULL) && (n != node)) {  in rb_contains()
529 		n = get_child(n, tree->lessthan_fn(n, node));  in rb_contains()
532 	return n == node;  in rb_contains()
535 /* Pushes the node and its chain of left-side children onto the stack
536  * in the foreach struct, returning the last node, which is the next
537  * node to iterate.  By construction node will always be a right child
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
573 	 * root as our first node, initializing the stack on the way.  in z_rb_foreach_next()
579 	/* The next child from a given node is the leftmost child of  in z_rb_foreach_next()
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()