9  * @defgroup rbtree_apis Balanced Red/Black Tree
12  * @brief Balanced Red/Black Tree implementation
14  * This implements an intrusive balanced tree that guarantees
29  * stored in the node, the upper structure of the tree being generated
30  * dynamically via a stack as the tree is recursed. So the overall
56  * @brief Balanced red/black tree node structure
64 /* Theoretical maximum depth of tree based on pointer size. If memory
65  * is filled with 2-pointer nodes, and the tree can be twice as a
66  * packed binary tree, plus root...  Works out to 59 entries for 32
75  * @brief Red/black tree comparison predicate
78  * than B according to the tree's sorting criteria, false otherwise.
81  * "A", where "B" is the existing node within the tree against which
89  * @brief Balanced red/black tree structure
92 	/** Root node of the tree */
94 	/** Comparison function for nodes in the tree */
117 struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side);
120  * @brief Insert node into tree
122 void rb_insert(struct rbtree *tree, struct rbnode *node);
125  * @brief Remove node from tree
127 void rb_remove(struct rbtree *tree, struct rbnode *node);
130  * @brief Returns the lowest-sorted member of the tree
132 static inline struct rbnode *rb_get_min(struct rbtree *tree)  in rb_get_min()  argument
134 	return z_rb_get_minmax(tree, 0U);  in rb_get_min()
138  * @brief Returns the highest-sorted member of the tree
140 static inline struct rbnode *rb_get_max(struct rbtree *tree)  in rb_get_max()  argument
142 	return z_rb_get_minmax(tree, 1U);  in rb_get_max()
146  * @brief Returns true if the given node is part of the tree
149  * (though the tree's lessthan callback might!), it just tests it for
150  * equality with items in the tree.  So it's feasible to use this to
154 bool rb_contains(struct rbtree *tree, struct rbnode *node);
165 static inline void rb_walk(struct rbtree *tree, rb_visit_t visit_fn,  in rb_walk()  argument
168 	z_rb_walk(tree->root, visit_fn, cookie);  in rb_walk()
179 #define _RB_FOREACH_INIT(tree, node) {					\  argument
180 	.stack   = &(tree)->iter_stack[0],				\
181 	.is_left = &(tree)->iter_left[0],				\
185 #define _RB_FOREACH_INIT(tree, node) {					\  argument
187 			alloca((tree)->max_depth * sizeof(struct rbnode *)), \
188 	.is_left = (uint8_t *)alloca((tree)->max_depth * sizeof(uint8_t)),\
193 struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f);
196  * @brief Walk a tree in-order without recursing
201  * non-recursive "foreach" loop that can iterate directly on the tree,
205  * the tree.  Changes to the tree structure during the loop will
212  * @param tree A pointer to a struct rbtree to walk
216 #define RB_FOR_EACH(tree, node) \  argument
217 	for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node);	\
218 	     (node = z_rb_foreach_next(tree, &__f));			\
227  * @param tree A pointer to a struct rbtree to walk
231 #define RB_FOR_EACH_CONTAINER(tree, node, field)		           \  argument
232 	for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node);	   \
233 			({struct rbnode *n = z_rb_foreach_next(tree, &__f); \