79 static int find_and_stack(struct rbtree *tree, struct rbnode *node,  in find_and_stack()  argument
86 	while (stack[sz - 1] != node) {  in find_and_stack()
87 		uint8_t side = tree->lessthan_fn(node, stack[sz - 1]) ? 0U : 1U;  in find_and_stack()
158 		struct rbnode *node = stack[stacksz - 1];  in fix_extra_red()  local
162 		CHECK((get_child(node, 0U) == NULL) ||  in fix_extra_red()
163 		      is_black(get_child(node, 0U)));  in fix_extra_red()
164 		CHECK((get_child(node, 1U) == NULL) ||  in fix_extra_red()
165 		      is_black(get_child(node, 1U)));  in fix_extra_red()
198 		uint8_t parent_side = get_side(parent, node);  in fix_extra_red()
202 			node = stack[stacksz - 1];  in fix_extra_red()
218 void rb_insert(struct rbtree *tree, struct rbnode *node)  in rb_insert()  argument
220 	set_child(node, 0U, NULL);  in rb_insert()
221 	set_child(node, 1U, NULL);  in rb_insert()
224 		tree->root = node;  in rb_insert()
226 		set_color(node, BLACK);  in rb_insert()
236 	int stacksz = find_and_stack(tree, node, stack);  in rb_insert()
240 	uint8_t side = tree->lessthan_fn(node, parent) ? 0U : 1U;  in rb_insert()
242 	set_child(parent, side, node);  in rb_insert()
243 	set_color(node, RED);  in rb_insert()
245 	stack[stacksz++] = node;  in rb_insert()
368 void rb_remove(struct rbtree *tree, struct rbnode *node)  in rb_remove()  argument
377 	int stacksz = find_and_stack(tree, node, stack);  in rb_remove()
379 	if (node != stack[stacksz - 1]) {  in rb_remove()
388 	if ((get_child(node, 0U) != NULL) && (get_child(node, 1U) != NULL)) {  in rb_remove()
391 		struct rbnode *node2 = get_child(node, 0U);  in rb_remove()
419 			set_child(hiparent, get_side(hiparent, node), node2);  in rb_remove()
424 		if (loparent == node) {  in rb_remove()
425 			set_child(node, 0U, get_child(node2, 0U));  in rb_remove()
426 			set_child(node2, 0U, node);  in rb_remove()
428 			set_child(loparent, get_side(loparent, node2), node);  in rb_remove()
429 			tmp = get_child(node, 0U);  in rb_remove()
430 			set_child(node, 0U, get_child(node2, 0U));  in rb_remove()
434 		set_child(node2, 1U, get_child(node, 1U));  in rb_remove()
435 		set_child(node, 1U, NULL);  in rb_remove()
441 		enum rb_color ctmp = get_color(node);  in rb_remove()
443 		set_color(node, get_color(node2));  in rb_remove()
447 	CHECK((get_child(node, 0U) == NULL) ||  in rb_remove()
448 	      (get_child(node, 1U) == NULL));  in rb_remove()
450 	struct rbnode *child = get_child(node, 0U);  in rb_remove()
453 		child = get_child(node, 1U);  in rb_remove()
475 		if (is_black(node)) {  in rb_remove()
476 			fix_missing_black(stack, stacksz, node);  in rb_remove()
479 			set_child(parent, get_side(parent, node), NULL);  in rb_remove()
482 		set_child(parent, get_side(parent, node), child);  in rb_remove()
487 		__ASSERT(is_black(node) || is_black(child), "both nodes red?!");  in rb_remove()
488 		if (is_red(node) || is_red(child)) {  in rb_remove()
498 void z_rb_walk(struct rbnode *node, rb_visit_t visit_fn, void *cookie)  in z_rb_walk()  argument
500 	if (node != NULL) {  in z_rb_walk()
501 		z_rb_walk(get_child(node, 0U), visit_fn, cookie);  in z_rb_walk()
502 		visit_fn(node, cookie);  in z_rb_walk()
503 		z_rb_walk(get_child(node, 1U), visit_fn, cookie);  in z_rb_walk()
508 struct rbnode *z_rb_child(struct rbnode *node, uint8_t side)  in z_rb_child()  argument
510 	return get_child(node, side);  in z_rb_child()
513 int z_rb_is_black(struct rbnode *node)  in z_rb_is_black()  argument
515 	return is_black(node);  in z_rb_is_black()
518 bool rb_contains(struct rbtree *tree, struct rbnode *node)  in rb_contains()  argument
522 	while ((n != NULL) && (n != node)) {  in rb_contains()
523 		n = get_child(n, tree->lessthan_fn(n, node));  in rb_contains()
526 	return n == node;  in rb_contains()