33#ifndef LELY_UTIL_RBTREE_H_
34#define LELY_UTIL_RBTREE_H_
42#ifndef LELY_UTIL_RBTREE_INLINE
43#define LELY_UTIL_RBTREE_INLINE static inline
144#define rbnode_foreach(first, node) rbnode_foreach_(__COUNTER__, first, node)
146#define rbnode_foreach(first, node) rbnode_foreach_(__LINE__, first, node)
148#define rbnode_foreach_(n, first, node) rbnode_foreach__(n, first, node)
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)
234#define rbtree_foreach(tree, node) rbnode_foreach (rbtree_first(tree), node)
236LELY_UTIL_RBTREE_INLINE
void
247LELY_UTIL_RBTREE_INLINE
void
258LELY_UTIL_RBTREE_INLINE
int
264LELY_UTIL_RBTREE_INLINE
size_t
272LELY_UTIL_RBTREE_INLINE
struct rbnode *
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 * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in 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_cmp_t(const void *, const void *)
The type of a comparison function suitable for use 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.
struct rbnode * rbtree_root(const struct rbtree *tree)
Returns a pointer to the root node in a red-black tree.
int rbtree_contains(const struct rbtree *tree, const struct rbnode *node)
Checks if a node is part of a red-black tree.
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes 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.
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.
int rbtree_empty(const struct rbtree *tree)
Returns 1 if the red-black tree is empty, and 0 if not.
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.