rbtree.h

Go to the documentation of this file.

 
#ifndef LELY_UTIL_RBTREE_H_
#define LELY_UTIL_RBTREE_H_
 
#include <lely/features.h>
 
#include <stddef.h>
#include <stdint.h>
 
#ifndef LELY_UTIL_RBTREE_INLINE
#define LELY_UTIL_RBTREE_INLINE static inline
#endif
 
struct rbnode {
        const void *key;
        uintptr_t parent;
        struct rbnode *left;
        struct rbnode *right;
};
 
#define RBNODE_INIT \
        { \
                NULL, 0, NULL, NULL \
        }
 
#ifdef __cplusplus
extern "C" {
#endif
 
typedef int rbtree_cmp_t(const void *, const void *);
 
struct rbtree {
        rbtree_cmp_t *cmp;
        struct rbnode *root;
        size_t num_nodes;
};
 
#define RBTREE_INIT \
        { \
                NULL, NULL, 0 \
        }
 
LELY_UTIL_RBTREE_INLINE void rbnode_init(struct rbnode *node, const void *key);
 
struct rbnode *rbnode_prev(const struct rbnode *node);
 
struct rbnode *rbnode_next(const struct rbnode *node);
 
#ifdef __COUNTER__
#define rbnode_foreach(first, node) rbnode_foreach_(__COUNTER__, first, node)
#else
#define rbnode_foreach(first, node) rbnode_foreach_(__LINE__, first, node)
#endif
#define rbnode_foreach_(n, first, node) rbnode_foreach__(n, first, node)
// clang-format off
#define rbnode_foreach__(n, first, node) \
        for (struct rbnode *node = (first), \
                        *_rbnode_next_##n = (node) ? rbnode_next(node) : NULL; \
                        (node); (node) = _rbnode_next_##n, \
                        _rbnode_next_##n = (node) ? rbnode_next(node) : NULL)
// clang-format on
 
LELY_UTIL_RBTREE_INLINE void rbtree_init(
                struct rbtree *tree, rbtree_cmp_t *cmp);
 
LELY_UTIL_RBTREE_INLINE int rbtree_empty(const struct rbtree *tree);
 
LELY_UTIL_RBTREE_INLINE size_t rbtree_size(const struct rbtree *tree);
 
void rbtree_insert(struct rbtree *tree, struct rbnode *node);
 
void rbtree_remove(struct rbtree *tree, struct rbnode *node);
 
struct rbnode *rbtree_find(const struct rbtree *tree, const void *key);
 
struct rbnode *rbtree_first(const struct rbtree *tree);
 
struct rbnode *rbtree_last(const struct rbtree *tree);
 
LELY_UTIL_RBTREE_INLINE struct rbnode *rbtree_root(const struct rbtree *tree);
 
#define rbtree_foreach(tree, node) rbnode_foreach (rbtree_first(tree), node)
 
inline void
rbnode_init(struct rbnode *node, const void *key)
{
        node->key = key;
        node->parent = 0;
        node->left = NULL;
        node->right = NULL;
}
 
inline void
rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
{
        tree->cmp = cmp;
        tree->root = NULL;
        tree->num_nodes = 0;
}
 
inline int
rbtree_empty(const struct rbtree *tree)
{
        return !rbtree_size(tree);
}
 
inline size_t
rbtree_size(const struct rbtree *tree)
{
        return tree->num_nodes;
}
 
inline struct rbnode *
rbtree_root(const struct rbtree *tree)
{
        return tree->root;
}
 
#ifdef __cplusplus
}
#endif
 
#endif // !LELY_UTIL_RBTREE_H_