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()
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()
200 		uint8_t parent_side = get_side(parent, node);  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()
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()
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()
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()
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()