Lely core libraries  2.2.5
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 <stddef.h>
39 #include <stdint.h>
40 
41 #ifndef LELY_UTIL_RBTREE_INLINE
42 #define LELY_UTIL_RBTREE_INLINE static inline
43 #endif
44 
52 struct rbnode {
58  const void *key;
63  uintptr_t parent;
65  struct rbnode *left;
67  struct rbnode *right;
68 };
69 
71 #define RBNODE_INIT \
72  { \
73  NULL, 0, NULL, NULL \
74  }
75 
76 #ifdef __cplusplus
77 extern "C" {
78 #endif
79 
87 typedef int rbtree_cmp_t(const void *, const void *);
88 
90 struct rbtree {
94  struct rbnode *root;
96  size_t num_nodes;
97 };
98 
100 #define RBTREE_INIT \
101  { \
102  NULL, NULL, 0 \
103  }
104 
112 LELY_UTIL_RBTREE_INLINE void rbnode_init(struct rbnode *node, const void *key);
113 
120 struct rbnode *rbnode_prev(const struct rbnode *node);
121 
130 struct rbnode *rbnode_next(const struct rbnode *node);
131 
142 #ifdef __COUNTER__
143 #define rbnode_foreach(first, node) rbnode_foreach_(__COUNTER__, first, node)
144 #else
145 #define rbnode_foreach(first, node) rbnode_foreach_(__LINE__, first, node)
146 #endif
147 #define rbnode_foreach_(n, first, node) rbnode_foreach__(n, first, node)
148 // clang-format off
149 #define rbnode_foreach__(n, first, node) \
150  for (struct rbnode *node = (first), \
151  *_rbnode_next_##n = (node) ? rbnode_next(node) : NULL; \
152  (node); (node) = _rbnode_next_##n, \
153  _rbnode_next_##n = (node) ? rbnode_next(node) : NULL)
154 // clang-format on
155 
162 LELY_UTIL_RBTREE_INLINE void rbtree_init(
163  struct rbtree *tree, rbtree_cmp_t *cmp);
164 
166 LELY_UTIL_RBTREE_INLINE int rbtree_empty(const struct rbtree *tree);
167 
172 LELY_UTIL_RBTREE_INLINE size_t rbtree_size(const struct rbtree *tree);
173 
181 void rbtree_insert(struct rbtree *tree, struct rbnode *node);
182 
188 void rbtree_remove(struct rbtree *tree, struct rbnode *node);
189 
197 struct rbnode *rbtree_find(const struct rbtree *tree, const void *key);
198 
205 struct rbnode *rbtree_first(const struct rbtree *tree);
206 
213 struct rbnode *rbtree_last(const struct rbtree *tree);
214 
219 LELY_UTIL_RBTREE_INLINE struct rbnode *rbtree_root(const struct rbtree *tree);
220 
226 #define rbtree_foreach(tree, node) rbnode_foreach (rbtree_first(tree), node)
227 
228 inline void
229 rbnode_init(struct rbnode *node, const void *key)
230 {
231  node->key = key;
232  node->parent = 0;
233  node->left = NULL;
234  node->right = NULL;
235 }
236 
237 inline void
238 rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
239 {
240  tree->cmp = cmp;
241  tree->root = NULL;
242  tree->num_nodes = 0;
243 }
244 
245 inline int
246 rbtree_empty(const struct rbtree *tree)
247 {
248  return !rbtree_size(tree);
249 }
250 
251 inline size_t
252 rbtree_size(const struct rbtree *tree)
253 {
254  return tree->num_nodes;
255 }
256 
257 inline struct rbnode *
258 rbtree_root(const struct rbtree *tree)
259 {
260  return tree->root;
261 }
262 
263 #ifdef __cplusplus
264 }
265 #endif
266 
267 #endif // !LELY_UTIL_RBTREE_H_
const void * key
A pointer to the key for this node.
Definition: rbtree.h:58
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
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
Definition: rbtree.h:229
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: rbtree.h:92
uintptr_t parent
A pointer to the parent node.
Definition: rbtree.h:63
size_t num_nodes
The number of nodes stored in the tree.
Definition: rbtree.h:96
struct rbnode * rbtree_root(const struct rbtree *tree)
Returns a pointer to the root node in a red-black tree.
Definition: rbtree.h:258
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
Definition: rbtree.h:252
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
Definition: rbtree.c:330
struct rbnode * left
A pointer to the left child node.
Definition: rbtree.h:65
A red-black tree.
Definition: rbtree.h:90
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
Definition: rbtree.c:306
This header file is part of the C11 and POSIX compatibility library; it includes <stddef.h> and defines any missing functionality.
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
Definition: rbtree.c:187
This header file is part of the C11 and POSIX compatibility library; it includes <stdint.h> and defines any missing functionality.
struct rbnode * root
A pointer to the root node of the tree.
Definition: rbtree.h:94
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
Definition: rbtree.h:238
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
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
This header file is part of the Lely libraries; it contains the compiler feature definitions.
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:87
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
Definition: rbtree.c:322
struct rbnode * right
A pointer to the right child node.
Definition: rbtree.h:67
A node in a red-black tree.
Definition: rbtree.h:52
int rbtree_empty(const struct rbtree *tree)
Returns 1 if the red-black tree is empty, and 0 if not.
Definition: rbtree.h:246