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) 267 #endif // !LELY_UTIL_RBTREE_H_ const void * key
A pointer to the key for this node.
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 rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
uintptr_t parent
A pointer to the parent node.
size_t num_nodes
The number of nodes stored in the tree.
struct rbnode * rbtree_root(const struct rbtree *tree)
Returns a pointer to the root node in a red-black tree.
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of 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.
struct rbnode * left
A pointer to the left child node.
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
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.
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.
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes 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...
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
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.
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
struct rbnode * right
A pointer to the right child node.
A 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.