Zephyr API Documentation  3.6.99
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
rb.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2018 Intel Corporation
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
37#ifndef ZEPHYR_INCLUDE_SYS_RB_H_
38#define ZEPHYR_INCLUDE_SYS_RB_H_
39
40#include <stdbool.h>
41#include <stdint.h>
42
43/* Our SDK/toolchains integration seems to be inconsistent about
44 * whether they expose alloca.h or not. On gcc it's a moot point as
45 * it's always builtin.
46 */
47#ifdef __GNUC__
48#ifndef alloca
49#define alloca __builtin_alloca
50#endif
51#else
52#include <alloca.h>
53#endif
54
58struct rbnode {
60 struct rbnode *children[2];
62};
63
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
67 * bit pointers and 121 at 64 bits.
68 */
69#define Z_TBITS(t) ((sizeof(t)) < 8 ? 2 : 3)
70#define Z_PBITS(t) (8 * sizeof(t))
71#define Z_MAX_RBTREE_DEPTH (2 * (Z_PBITS(int *) - Z_TBITS(int *) - 1) + 1)
72
86typedef bool (*rb_lessthan_t)(struct rbnode *a, struct rbnode *b);
87
91struct rbtree {
93 struct rbnode *root;
97 int max_depth;
98#ifdef CONFIG_MISRA_SANE
99 struct rbnode *iter_stack[Z_MAX_RBTREE_DEPTH];
100 unsigned char iter_left[Z_MAX_RBTREE_DEPTH];
101#endif
103};
104
110typedef void (*rb_visit_t)(struct rbnode *node, void *cookie);
111
112struct rbnode *z_rb_child(struct rbnode *node, uint8_t side);
113int z_rb_is_black(struct rbnode *node);
114#ifndef CONFIG_MISRA_SANE
115void z_rb_walk(struct rbnode *node, rb_visit_t visit_fn, void *cookie);
116#endif
117struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side);
118
122void rb_insert(struct rbtree *tree, struct rbnode *node);
123
127void rb_remove(struct rbtree *tree, struct rbnode *node);
128
132static inline struct rbnode *rb_get_min(struct rbtree *tree)
133{
134 return z_rb_get_minmax(tree, 0U);
135}
136
140static inline struct rbnode *rb_get_max(struct rbtree *tree)
141{
142 return z_rb_get_minmax(tree, 1U);
143}
144
154bool rb_contains(struct rbtree *tree, struct rbnode *node);
155
156#ifndef CONFIG_MISRA_SANE
165static inline void rb_walk(struct rbtree *tree, rb_visit_t visit_fn,
166 void *cookie)
167{
168 z_rb_walk(tree->root, visit_fn, cookie);
169}
170#endif
171
172struct _rb_foreach {
173 struct rbnode **stack;
174 uint8_t *is_left;
175 int32_t top;
176};
177
178#ifdef CONFIG_MISRA_SANE
179#define _RB_FOREACH_INIT(tree, node) { \
180 .stack = &(tree)->iter_stack[0], \
181 .is_left = &(tree)->iter_left[0], \
182 .top = -1 \
183}
184#else
185#define _RB_FOREACH_INIT(tree, node) { \
186 .stack = (struct rbnode **) \
187 alloca((tree)->max_depth * sizeof(struct rbnode *)), \
188 .is_left = (uint8_t *)alloca((tree)->max_depth * sizeof(uint8_t)),\
189 .top = -1 \
190}
191#endif
192
193struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f);
194
216#define RB_FOR_EACH(tree, node) \
217 for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node); \
218 (node = z_rb_foreach_next(tree, &__f)); \
219 )
220
231#define RB_FOR_EACH_CONTAINER(tree, node, field) \
232 for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node); \
233 ({struct rbnode *n = z_rb_foreach_next(tree, &__f); \
234 node = n ? CONTAINER_OF(n, __typeof__(*(node)), \
235 field) : NULL; (node); }) != NULL; \
236 )
237
240#endif /* ZEPHYR_INCLUDE_SYS_RB_H_ */
static struct rbnode * rb_get_max(struct rbtree *tree)
Returns the highest-sorted member of the tree.
Definition: rb.h:140
bool(* rb_lessthan_t)(struct rbnode *a, struct rbnode *b)
Red/black tree comparison predicate.
Definition: rb.h:86
void(* rb_visit_t)(struct rbnode *node, void *cookie)
Prototype for node visitor callback.
Definition: rb.h:110
static struct rbnode * rb_get_min(struct rbtree *tree)
Returns the lowest-sorted member of the tree.
Definition: rb.h:132
void rb_insert(struct rbtree *tree, struct rbnode *node)
Insert node into tree.
static void rb_walk(struct rbtree *tree, rb_visit_t visit_fn, void *cookie)
Walk/enumerate a rbtree.
Definition: rb.h:165
void rb_remove(struct rbtree *tree, struct rbnode *node)
Remove node from tree.
bool rb_contains(struct rbtree *tree, struct rbnode *node)
Returns true if the given node is part of the tree.
#define bool
Definition: stdbool.h:13
__INT32_TYPE__ int32_t
Definition: stdint.h:74
__UINT8_TYPE__ uint8_t
Definition: stdint.h:88
Balanced red/black tree node structure.
Definition: rb.h:58
Balanced red/black tree structure.
Definition: rb.h:91
struct rbnode * root
Root node of the tree.
Definition: rb.h:93
rb_lessthan_t lessthan_fn
Comparison function for nodes in the tree.
Definition: rb.h:95