Lely core libraries  2.3.4
rbtree.h
Go to the documentation of this file.
1 
33 #ifndef LELY_UTIL_RBTREE_H_
34 #define LELY_UTIL_RBTREE_H_
35 
36 #include <lely/features.h>
37 
38 #include <assert.h>
39 #include <stddef.h>
40 #include <stdint.h>
41 
42 #ifndef LELY_UTIL_RBTREE_INLINE
43 #define LELY_UTIL_RBTREE_INLINE static inline
44 #endif
45 
53 struct rbnode {
59  const void *key;
64  uintptr_t parent;
66  struct rbnode *left;
68  struct rbnode *right;
69 };
70 
72 #define RBNODE_INIT \
73  { \
74  NULL, 0, NULL, NULL \
75  }
76 
77 #ifdef __cplusplus
78 extern "C" {
79 #endif
80 
88 typedef int rbtree_cmp_t(const void *, const void *);
89 
91 struct rbtree {
95  struct rbnode *root;
97  size_t num_nodes;
98 };
99 
101 #define RBTREE_INIT \
102  { \
103  NULL, NULL, 0 \
104  }
105 
113 LELY_UTIL_RBTREE_INLINE void rbnode_init(struct rbnode *node, const void *key);
114 
121 struct rbnode *rbnode_prev(const struct rbnode *node);
122 
131 struct rbnode *rbnode_next(const struct rbnode *node);
132 
143 #ifdef __COUNTER__
144 #define rbnode_foreach(first, node) rbnode_foreach_(__COUNTER__, first, node)
145 #else
146 #define rbnode_foreach(first, node) rbnode_foreach_(__LINE__, first, node)
147 #endif
148 #define rbnode_foreach_(n, first, node) rbnode_foreach__(n, first, node)
149 // clang-format off
150 #define rbnode_foreach__(n, first, node) \
151  for (struct rbnode *node = (first), \
152  *_rbnode_next_##n = (node) ? rbnode_next(node) : NULL; \
153  (node); (node) = _rbnode_next_##n, \
154  _rbnode_next_##n = (node) ? rbnode_next(node) : NULL)
155 // clang-format on
156 
163 LELY_UTIL_RBTREE_INLINE void rbtree_init(
164  struct rbtree *tree, rbtree_cmp_t *cmp);
165 
167 LELY_UTIL_RBTREE_INLINE int rbtree_empty(const struct rbtree *tree);
168 
173 LELY_UTIL_RBTREE_INLINE size_t rbtree_size(const struct rbtree *tree);
174 
182 void rbtree_insert(struct rbtree *tree, struct rbnode *node);
183 
189 void rbtree_remove(struct rbtree *tree, struct rbnode *node);
190 
196 int rbtree_contains(const struct rbtree *tree, const struct rbnode *node);
197 
205 struct rbnode *rbtree_find(const struct rbtree *tree, const void *key);
206 
213 struct rbnode *rbtree_first(const struct rbtree *tree);
214 
221 struct rbnode *rbtree_last(const struct rbtree *tree);
222 
227 LELY_UTIL_RBTREE_INLINE struct rbnode *rbtree_root(const struct rbtree *tree);
228 
234 #define rbtree_foreach(tree, node) rbnode_foreach (rbtree_first(tree), node)
235 
236 LELY_UTIL_RBTREE_INLINE void
237 rbnode_init(struct rbnode *node, const void *key)
238 {
239  assert(node);
240 
241  node->key = key;
242  node->parent = 0;
243  node->left = NULL;
244  node->right = NULL;
245 }
246 
247 LELY_UTIL_RBTREE_INLINE void
248 rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
249 {
250  assert(tree);
251  assert(cmp);
252 
253  tree->cmp = cmp;
254  tree->root = NULL;
255  tree->num_nodes = 0;
256 }
257 
258 LELY_UTIL_RBTREE_INLINE int
259 rbtree_empty(const struct rbtree *tree)
260 {
261  return !rbtree_size(tree);
262 }
263 
264 LELY_UTIL_RBTREE_INLINE size_t
265 rbtree_size(const struct rbtree *tree)
266 {
267  assert(tree);
268 
269  return tree->num_nodes;
270 }
271 
272 LELY_UTIL_RBTREE_INLINE struct rbnode *
273 rbtree_root(const struct rbtree *tree)
274 {
275  assert(tree);
276 
277  return tree->root;
278 }
279 
280 #ifdef __cplusplus
281 }
282 #endif
283 
284 #endif // !LELY_UTIL_RBTREE_H_
features.h
rbtree_insert
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
rbtree::root
struct rbnode * root
A pointer to the root node of the tree.
Definition: rbtree.h:95
rbnode_next
struct rbnode * rbnode_next(const struct rbnode *node)
Returns a pointer to the next (in-order) node in a red-black tree with respect to node.
Definition: rbtree.c:91
rbtree_contains
int rbtree_contains(const struct rbtree *tree, const struct rbnode *node)
Checks if a node is part of a red-black tree.
Definition: rbtree.c:322
rbtree
A red-black tree.
Definition: rbtree.h:91
rbtree_first
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
Definition: rbtree.c:335
rbtree_find
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
Definition: rbtree.c:306
rbtree_last
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
Definition: rbtree.c:343
rbtree::cmp
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: rbtree.h:93
rbnode::parent
uintptr_t parent
A pointer to the parent node.
Definition: rbtree.h:64
rbtree_cmp_t
int rbtree_cmp_t(const void *, const void *)
The type of a comparison function suitable for use in a red-black tree.
Definition: rbtree.h:88
stdint.h
rbnode
A node in a red-black tree.
Definition: rbtree.h:53
rbtree_root
struct rbnode * rbtree_root(const struct rbtree *tree)
Returns a pointer to the root node in a red-black tree.
Definition: rbtree.h:273
rbtree_init
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
Definition: rbtree.h:248
rbtree::num_nodes
size_t num_nodes
The number of nodes stored in the tree.
Definition: rbtree.h:97
rbtree_empty
int rbtree_empty(const struct rbtree *tree)
Returns 1 if the red-black tree is empty, and 0 if not.
Definition: rbtree.h:259
rbtree_remove
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
Definition: rbtree.c:187
rbnode::key
const void * key
A pointer to the key for this node.
Definition: rbtree.h:59
rbtree_size
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
Definition: rbtree.h:265
stddef.h
rbnode::left
struct rbnode * left
A pointer to the left child node.
Definition: rbtree.h:66
rbnode_init
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
Definition: rbtree.h:237
rbnode::right
struct rbnode * right
A pointer to the right child node.
Definition: rbtree.h:68
rbnode_prev
struct rbnode * rbnode_prev(const struct rbnode *node)
Returns a pointer to the previous (in-order) node in a red-black tree with respect to node.
Definition: rbtree.c:74