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
53struct 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
78extern "C" {
79#endif
80
88typedef int rbtree_cmp_t(const void *, const void *);
89
91struct rbtree {
95 struct rbnode *root;
97 size_t num_nodes;
98};
99
101#define RBTREE_INIT \
102 { \
103 NULL, NULL, 0 \
104 }
105
113LELY_UTIL_RBTREE_INLINE void rbnode_init(struct rbnode *node, const void *key);
114
121struct rbnode *rbnode_prev(const struct rbnode *node);
122
131struct 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
163LELY_UTIL_RBTREE_INLINE void rbtree_init(
164 struct rbtree *tree, rbtree_cmp_t *cmp);
165
167LELY_UTIL_RBTREE_INLINE int rbtree_empty(const struct rbtree *tree);
168
173LELY_UTIL_RBTREE_INLINE size_t rbtree_size(const struct rbtree *tree);
174
182void rbtree_insert(struct rbtree *tree, struct rbnode *node);
183
189void rbtree_remove(struct rbtree *tree, struct rbnode *node);
190
196int rbtree_contains(const struct rbtree *tree, const struct rbnode *node);
197
205struct rbnode *rbtree_find(const struct rbtree *tree, const void *key);
206
213struct rbnode *rbtree_first(const struct rbtree *tree);
214
221struct rbnode *rbtree_last(const struct rbtree *tree);
222
227LELY_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
236LELY_UTIL_RBTREE_INLINE void
237rbnode_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
247LELY_UTIL_RBTREE_INLINE void
248rbtree_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
258LELY_UTIL_RBTREE_INLINE int
259rbtree_empty(const struct rbtree *tree)
260{
261 return !rbtree_size(tree);
262}
263
264LELY_UTIL_RBTREE_INLINE size_t
265rbtree_size(const struct rbtree *tree)
266{
267 assert(tree);
268
269 return tree->num_nodes;
270}
271
272LELY_UTIL_RBTREE_INLINE struct rbnode *
273rbtree_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_
This header file is part of the Lely libraries; it contains the compiler feature definitions.
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
Definition: rbtree.h:237
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
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
Definition: rbtree.c:306
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
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
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
struct rbnode * rbtree_root(const struct rbtree *tree)
Returns a pointer to the root node in a red-black tree.
Definition: rbtree.h:273
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
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
Definition: rbtree.h:248
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
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
Definition: rbtree.h:265
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
Definition: rbtree.c:187
int rbtree_empty(const struct rbtree *tree)
Returns 1 if the red-black tree is empty, and 0 if not.
Definition: rbtree.h:259
This header file is part of the C11 and POSIX compatibility library; it includes <stddef....
This header file is part of the C11 and POSIX compatibility library; it includes <stdint....
A node in a red-black tree.
Definition: rbtree.h:53
struct rbnode * left
A pointer to the left child node.
Definition: rbtree.h:66
struct rbnode * right
A pointer to the right child node.
Definition: rbtree.h:68
const void * key
A pointer to the key for this node.
Definition: rbtree.h:59
uintptr_t parent
A pointer to the parent node.
Definition: rbtree.h:64
A red-black tree.
Definition: rbtree.h:91
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: rbtree.h:93
size_t num_nodes
The number of nodes stored in the tree.
Definition: rbtree.h:97
struct rbnode * root
A pointer to the root node of the tree.
Definition: rbtree.h:95