33 #ifndef LELY_UTIL_RBTREE_H_
34 #define LELY_UTIL_RBTREE_H_
41 #ifndef LELY_UTIL_RBTREE_INLINE
42 #define LELY_UTIL_RBTREE_INLINE static inline
100 #define RBTREE_INIT \
143 #define rbnode_foreach(first, node) rbnode_foreach_(__COUNTER__, first, node)
145 #define rbnode_foreach(first, node) rbnode_foreach_(__LINE__, first, node)
147 #define rbnode_foreach_(n, first, node) rbnode_foreach__(n, first, node)
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)
226 #define rbtree_foreach(tree, node) rbnode_foreach (rbtree_first(tree), node)
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.
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.
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
int rbtree_cmp_t(const void *, const void *)
The type of a comparison function suitable for use in a red-black tree.
struct rbnode * rbtree_root(const struct rbtree *tree)
Returns a pointer to the root node in a red-black tree.
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
int rbtree_empty(const struct rbtree *tree)
Returns 1 if the red-black tree is empty, and 0 if not.
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
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.
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.
struct rbnode * left
A pointer to the left child node.
struct rbnode * right
A pointer to the right child node.
const void * key
A pointer to the key for this node.
uintptr_t parent
A pointer to the parent node.
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
size_t num_nodes
The number of nodes stored in the tree.
struct rbnode * root
A pointer to the root node of the tree.