rbt.h

Go to the documentation of this file.

 
#ifndef LIBA_RBT_H
#define LIBA_RBT_H
 
#include "a.h"

 
/* clang-format off */
#define A_RBT_ROOT {A_NULL}
/* clang-format on */

typedef struct a_rbt_node
{
    struct a_rbt_node *left; 
    struct a_rbt_node *right; 
#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
    a_uptr parent_;
#else /* !A_SIZE_POINTER */
    struct a_rbt_node *parent;
    unsigned int color;
#endif /* A_SIZE_POINTER */
} a_rbt_node;

A_INTERN a_rbt_node *a_rbt_parent(a_rbt_node const *node)
{
#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
    return a_cast_r(a_rbt_node *, node->parent_ & ~a_uptr_c(1));
#else /* !A_SIZE_POINTER */
    return node->parent;
#endif /* A_SIZE_POINTER */
}

A_INTERN a_rbt_node *a_rbt_init(a_rbt_node *node, a_rbt_node *parent)
{
#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
    node->parent_ = a_cast_r(a_uptr, parent);
#else /* !A_SIZE_POINTER */
    node->parent = parent;
    node->color = 0;
#endif /* A_SIZE_POINTER */
    node->right = A_NULL;
    node->left = A_NULL;
    return node;
}

typedef union a_rbt
{
    struct a_rbt_node *node; 
} a_rbt;

A_INTERN void a_rbt_root(a_rbt *root) { root->node = A_NULL; }
 
#if defined(__cplusplus)
extern "C" {
#endif /* __cplusplus */

A_EXTERN a_rbt_node *a_rbt_head(a_rbt const *root);

A_EXTERN a_rbt_node *a_rbt_tail(a_rbt const *root);

A_EXTERN a_rbt_node *a_rbt_next(a_rbt_node *node);

A_EXTERN a_rbt_node *a_rbt_prev(a_rbt_node *node);

A_EXTERN a_rbt_node *a_rbt_pre_next(a_rbt_node *node);

A_EXTERN a_rbt_node *a_rbt_pre_prev(a_rbt_node *node);

A_EXTERN a_rbt_node *a_rbt_post_head(a_rbt const *root);

A_EXTERN a_rbt_node *a_rbt_post_tail(a_rbt const *root);

A_EXTERN a_rbt_node *a_rbt_post_next(a_rbt_node *node);

A_EXTERN a_rbt_node *a_rbt_post_prev(a_rbt_node *node);

A_EXTERN a_rbt_node *a_rbt_tear(a_rbt *root, a_rbt_node **next);

A_EXTERN a_rbt_node *a_rbt_search(a_rbt const *root, void const *ctx, int (*cmp)(void const *, void const *));

A_EXTERN a_rbt_node *a_rbt_insert(a_rbt *root, a_rbt_node *node, int (*cmp)(void const *, void const *));

A_EXTERN void a_rbt_insert_adjust(a_rbt *root, a_rbt_node *node);

A_EXTERN void a_rbt_remove(a_rbt *root, a_rbt_node *node);
 
#if defined(__cplusplus)
} /* extern "C" */
#endif /* __cplusplus */

#define a_rbt_entry(ptr, type, member) a_container_of(ptr, type, member)

#define a_rbt_foreach(cur, root) \
    for (a_rbt_node *cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))
#define A_RBT_FOREACH(cur, root) \
    for (cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))

#define a_rbt_foreach_reverse(cur, root) \
    for (a_rbt_node *cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))
#define A_RBT_FOREACH_REVERSE(cur, root) \
    for (cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))

#define a_rbt_pre_foreach(cur, root) \
    for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_next(cur))
#define A_RBT_PRE_FOREACH(cur, root) \
    for (cur = (root)->node; cur; cur = a_rbt_pre_next(cur))

#define a_rbt_pre_foreach_reverse(cur, root) \
    for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))
#define A_RBT_PRE_FOREACH_REVERSE(cur, root) \
    for (cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))

#define a_rbt_post_foreach(cur, root) \
    for (a_rbt_node *cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))
#define A_RBT_POST_FOREACH(cur, root) \
    for (cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))

#define a_rbt_post_foreach_reverse(cur, root) \
    for (a_rbt_node *cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))
#define A_RBT_POST_FOREACH_REVERSE(cur, root) \
    for (cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))

#define a_rbt_fortear(cur, next, root) \
    for (a_rbt_node *next = A_NULL, *cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))
#define A_RBT_FORTEAR(cur, next, root) \
    for ((void)(next = A_NULL), cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))

 
#endif /* a/rbt.h */