AVL tree

include/structures/avl.h View source View on GitHub

Structs

avl_tree_node

struct avl_tree_node (4 fields) source

§ int height

§ struct avl_tree_node *left

§ struct avl_tree_node *right

§ struct avl_tree_node *parent

avl_tree_node_ops

struct avl_tree_node_ops (2 fields) source

§ int (*cmp)(const struct avl_tree_node *a, const struct avl_tree_node *b)

Compare two embedded nodes. Returns <0, 0, >0. Required.

§ int (*cmp_key)(const struct avl_tree_node *node, const void *key)

Compare a node against an external key

avl_tree

struct avl_tree (2 fields) source

§ struct avl_tree_node *root

§ const struct avl_tree_node_ops *ops

Functions

avl_tree_init

void avl_tree_init(
    struct avl_tree *tree,
    const struct avl_tree_node_ops *ops
)

source

avl_tree_insert

void avl_tree_insert(
    struct avl_tree *tree,
    struct avl_tree_node *node
)

source

avl_tree_remove

void avl_tree_remove(
    struct avl_tree *tree,
    struct avl_tree_node *node
)

source

avl_tree_find

struct avl_tree_node * avl_tree_find(
    const struct avl_tree *tree,
    const void *key
)

source

avl_tree_first

struct avl_tree_node * avl_tree_first(const struct avl_tree *tree)

source

avl_tree_last

struct avl_tree_node * avl_tree_last(const struct avl_tree *tree)

source

avl_tree_next

struct avl_tree_node * avl_tree_next(const struct avl_tree_node *node)

source

avl_tree_prev

struct avl_tree_node * avl_tree_prev(const struct avl_tree_node *node)

source

avl_tree_empty

int avl_tree_empty(const struct avl_tree *tree)

source

avl_init_node

void avl_init_node(struct avl_tree_node *n)

source

avl_tree_validate

int avl_tree_validate(const struct avl_tree *tree)

source

Macros

AVL_NODE_INIT

#define AVL_NODE_INIT

source

Expansion

#define AVL_NODE_INIT \
    (struct avl_tree_node) { \
        .height = 1, .left = NULL, .right = NULL, .parent = NULL \
    }

avl_entry

#define avl_entry(ptr, type, member)

source

Expansion

#define avl_entry(ptr, type, member) container_of(ptr, type, member)

avl_tree_for_each

#define avl_tree_for_each(pos, tree)

source

Expansion

#define avl_tree_for_each(pos, tree) \
    for ((pos) = avl_tree_first(tree); (pos); (pos) = avl_tree_next(pos))

avl_tree_for_each_safe

#define avl_tree_for_each_safe(pos, n, tree)

source

Expansion

#define avl_tree_for_each_safe(pos, n, tree) \
    for ((pos) = avl_tree_first(tree), \
        (n) = (pos) ? avl_tree_next(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? avl_tree_next(pos) : NULL)

avl_tree_for_each_entry

#define avl_tree_for_each_entry(pos, tree, member)

source

Expansion

#define avl_tree_for_each_entry(pos, tree, member) \
    for (typeof(avl_tree_first(tree)) __n = avl_tree_first(tree); \
         __n != NULL && \
         (((pos) = avl_entry(__n, typeof(*(pos)), member)), true); \
         __n = avl_tree_next(__n))

avl_tree_for_each_entry_safe

#define avl_tree_for_each_entry_safe(pos, tmp, tree, member)

source

Expansion

#define avl_tree_for_each_entry_safe(pos, tmp, tree, member) \
    for (typeof(avl_tree_first(tree)) __n = avl_tree_first(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = avl_entry(__n, typeof(*(pos)), member)), \
          (__nx = avl_tree_next(__n)), \
          ((tmp) = __nx ? avl_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)

avl_tree_for_each_reverse

#define avl_tree_for_each_reverse(pos, tree)

source

Expansion

#define avl_tree_for_each_reverse(pos, tree) \
    for ((pos) = avl_tree_last(tree); (pos); (pos) = avl_tree_prev(pos))

avl_tree_for_each_safe_reverse

#define avl_tree_for_each_safe_reverse(pos, n, tree)

source

Expansion

#define avl_tree_for_each_safe_reverse(pos, n, tree) \
    for ((pos) = avl_tree_last(tree), (n) = (pos) ? avl_tree_prev(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? avl_tree_prev(pos) : NULL)

avl_tree_for_each_entry_reverse

#define avl_tree_for_each_entry_reverse(pos, tree, member)

source

Expansion

#define avl_tree_for_each_entry_reverse(pos, tree, member) \
    for (typeof(avl_tree_last(tree)) __n = avl_tree_last(tree); \
         __n != NULL && \
         (((pos) = avl_entry(__n, typeof(*(pos)), member)), true); \
         __n = avl_tree_prev(__n))

avl_tree_for_each_entry_safe_reverse

#define avl_tree_for_each_entry_safe_reverse(pos, tmp, tree, member)

source

Expansion

#define avl_tree_for_each_entry_safe_reverse(pos, tmp, tree, member) \
    for (typeof(avl_tree_last(tree)) __n = avl_tree_last(tree), __nx = NULL; \
         __n != NULL && \
         (((pos) = avl_entry(__n, typeof(*(pos)), member)), \
          (__nx = avl_tree_prev(__n)), \
          ((tmp) = __nx ? avl_entry(__nx, typeof(*(tmp)), member) : NULL), \
          true); \
         __n = __nx)