avl.h

Go to the documentation of this file.

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

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

typedef struct a_avl_node
{
    struct a_avl_node *left; 
    struct a_avl_node *right; 
#if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 3)
    a_uptr parent_;
#else /* !A_SIZE_POINTER */
    struct a_avl_node *parent;
    int factor;
#endif /* A_SIZE_POINTER */
} a_avl_node;

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

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

typedef union a_avl
{
    struct a_avl_node *node; 
} a_avl;

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

A_EXTERN a_avl_node *a_avl_head(a_avl const *root);

A_EXTERN a_avl_node *a_avl_tail(a_avl const *root);

A_EXTERN a_avl_node *a_avl_next(a_avl_node *node);

A_EXTERN a_avl_node *a_avl_prev(a_avl_node *node);

A_EXTERN a_avl_node *a_avl_pre_next(a_avl_node *node);

A_EXTERN a_avl_node *a_avl_pre_prev(a_avl_node *node);

A_EXTERN a_avl_node *a_avl_post_head(a_avl const *root);

A_EXTERN a_avl_node *a_avl_post_tail(a_avl const *root);

A_EXTERN a_avl_node *a_avl_post_next(a_avl_node *node);

A_EXTERN a_avl_node *a_avl_post_prev(a_avl_node *node);

A_EXTERN a_avl_node *a_avl_tear(a_avl *root, a_avl_node **next);

A_EXTERN a_avl_node *a_avl_search(a_avl const *root, void const *ctx, int (*cmp)(void const *, void const *));

A_EXTERN a_avl_node *a_avl_insert(a_avl *root, a_avl_node *node, int (*cmp)(void const *, void const *));

A_EXTERN void a_avl_insert_adjust(a_avl *root, a_avl_node *node);

A_EXTERN void a_avl_remove(a_avl *root, a_avl_node *node);
 
#if defined(__cplusplus)
} /* extern "C" */
#endif /* __cplusplus */

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

#define a_avl_foreach(cur, root) \
    for (a_avl_node *cur = a_avl_head(root); cur; cur = a_avl_next(cur))
#define A_AVL_FOREACH(cur, root) \
    for (cur = a_avl_head(root); cur; cur = a_avl_next(cur))

#define a_avl_foreach_reverse(cur, root) \
    for (a_avl_node *cur = a_avl_tail(root); cur; cur = a_avl_prev(cur))
#define A_AVL_FOREACH_REVERSE(cur, root) \
    for (cur = a_avl_tail(root); cur; cur = a_avl_prev(cur))

#define a_avl_pre_foreach(cur, root) \
    for (a_avl_node *cur = (root)->node; cur; cur = a_avl_pre_next(cur))
#define A_AVL_PRE_FOREACH(cur, root) \
    for (cur = (root)->node; cur; cur = a_avl_pre_next(cur))

#define a_avl_pre_foreach_reverse(cur, root) \
    for (a_avl_node *cur = (root)->node; cur; cur = a_avl_pre_prev(cur))
#define A_AVL_PRE_FOREACH_REVERSE(cur, root) \
    for (cur = (root)->node; cur; cur = a_avl_pre_prev(cur))

#define a_avl_post_foreach(cur, root) \
    for (a_avl_node *cur = a_avl_post_head(root); cur; cur = a_avl_post_next(cur))
#define A_AVL_POST_FOREACH(cur, root) \
    for (cur = a_avl_post_head(root); cur; cur = a_avl_post_next(cur))

#define a_avl_post_foreach_reverse(cur, root) \
    for (a_avl_node *cur = a_avl_post_tail(root); cur; cur = a_avl_post_prev(cur))
#define A_AVL_POST_FOREACH_REVERSE(cur, root) \
    for (cur = a_avl_post_tail(root); cur; cur = a_avl_post_prev(cur))

#define a_avl_fortear(cur, next, root) \
    for (a_avl_node *next = A_NULL, *cur = a_avl_tear(root, &next); cur; cur = a_avl_tear(root, &next))
#define A_AVL_FORTEAR(cur, next, root) \
    for ((void)(next = A_NULL), cur = a_avl_tear(root, &next); cur; cur = a_avl_tear(root, &next))

 
#endif /* a/avl.h */