AVL tree

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

Structs

avl_tree_node

struct avl_tree_node {
    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 {
    int  (*cmp)(const struct avl_tree_node *a, const struct avl_tree_node *b);
    int  (*cmp_key)(const struct avl_tree_node *node, const void *key);
};

avl_tree

struct avl_tree {
    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);

avl_tree_insert

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

avl_tree_remove

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

avl_tree_find

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

avl_tree_first

struct avl_tree_node * avl_tree_first(const struct avl_tree *tree);

avl_tree_last

struct avl_tree_node * avl_tree_last(const struct avl_tree *tree);

avl_tree_next

struct avl_tree_node * avl_tree_next(const struct avl_tree_node *node);

avl_tree_prev

struct avl_tree_node * avl_tree_prev(const struct avl_tree_node *node);

avl_tree_empty

int avl_tree_empty(const struct avl_tree *tree);

Macros

avl_entry

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

avl_tree_for_each

#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) \
    for ((pos) = avl_tree_first(tree), \
        (n) = (pos) ? avl_tree_next(pos) : NULL; \
         (pos); (pos) = (n), (n) = (pos) ? avl_tree_next(pos) : NULL)

---