25 #define LELY_UTIL_RBTREE_INLINE extern inline
120 next = tree->
cmp(node->
key, next->
key) < 0
148 if (node ==
parent->right) {
168 if (node ==
parent->left) {
202 }
else if (!node->
right) {
239 if (node ==
parent->left) {
316 node = cmp < 0 ? node->
left : node->
right;
327 if (node == tree->
root)
350 static inline struct rbnode *
370 return node ? node->
parent & (uintptr_t)1 : 0;
380 node->
parent |= (uintptr_t)1;
382 node->
parent &= ~(uintptr_t)1;
421 else if (node ==
parent->left)
443 else if (node ==
parent->right)
455 tree->
root = new_node;
456 else if (old_node ==
parent->left)
static struct rbnode * rbnode_max(struct rbnode *node)
Returns the rightmost descendant of 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 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.
static void rbtree_ror(struct rbtree *tree, struct rbnode *node)
Rotates node clockwise (right), i.e., it is replaced in the tree by its left child,...
static void rbtree_replace(struct rbtree *tree, struct rbnode *old_node, struct rbnode *new_node)
Replaces old_node by new_node in tree by updating its parent.
static int rbnode_get_color(const struct rbnode *node)
Returns the color of node, or 0 (black) if node is NULL.
int rbtree_contains(const struct rbtree *tree, const struct rbnode *node)
Checks if a node is part of a red-black tree.
static struct rbnode * rbnode_get_parent(const struct rbnode *node)
Returns the parent of node. node MUST NOT be NULL.
static void rbnode_set_color(struct rbnode *node, int color)
Sets the color of node to 0 (black) if color is 0, or to 1 (red) otherwise.
static void rbtree_rol(struct rbtree *tree, struct rbnode *node)
Rotates node counter-clockwise (left), i.e., it is replaced in the tree by its right child,...
static void rbnode_set_parent(struct rbnode *node, const struct rbnode *parent)
Sets the parent of node to parent.
static struct rbnode * rbnode_min(struct rbnode *node)
Returns the leftmost descendant of node.
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.
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 utilities library; it contains the red-black tree declarations.
This is the internal header file of the utilities library.
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.