67 lines
2.1 KiB
C
67 lines
2.1 KiB
C
#ifndef TUPPERWARE_AVL_H
|
|
#define TUPPERWARE_AVL_H
|
|
|
|
#include <stdbool.h>
|
|
#include <stddef.h>
|
|
|
|
struct avl_node {
|
|
struct avl_node *left;
|
|
struct avl_node *right;
|
|
int balance;
|
|
};
|
|
|
|
typedef int (*avl_cmp_f)(const struct avl_node *lhs,
|
|
const struct avl_node *rhs, void *cookie);
|
|
typedef void (*avl_map_f)(struct avl_node *n, void *cookie);
|
|
typedef bool (*avl_filter_f)(struct avl_node *n, void *cookie);
|
|
|
|
struct avl {
|
|
avl_cmp_f cmp;
|
|
void *cookie;
|
|
struct avl_node *root;
|
|
};
|
|
|
|
#define CONTAINER_OF(Type, Field, Ptr) \
|
|
((Type*)((char*)(Ptr) - offsetof(Type, Field)))
|
|
|
|
#define AVL_NODE_INIT_VAL \
|
|
((struct avl_node){ \
|
|
.left = NULL, \
|
|
.right = NULL, \
|
|
.balance = 0, \
|
|
})
|
|
|
|
void avl_init(struct avl *tree, avl_cmp_f cmp, void *cookie);
|
|
void avl_clear(struct avl *tree,
|
|
void (*dtor)(struct avl_node *n, void *cookie), void *cookie);
|
|
|
|
bool avl_insert(struct avl *tree,
|
|
struct avl_node *v, struct avl_node **inserted);
|
|
struct avl_node *avl_insert_or_update(struct avl *tree, struct avl_node *v);
|
|
void avl_insert_multi(struct avl *tree, struct avl_node *v);
|
|
|
|
struct avl_node *avl_remove(struct avl *tree, struct avl_node *v);
|
|
bool avl_remove_at(struct avl *tree, struct avl_node *v);
|
|
|
|
struct avl_node *avl_find(const struct avl *tree, const struct avl_node *v);
|
|
struct avl_node *avl_lower_bound(const struct avl *tree,
|
|
const struct avl_node *v);
|
|
struct avl_node *avl_upper_bound(const struct avl *tree,
|
|
const struct avl_node *v);
|
|
|
|
bool avl_empty(const struct avl *tree);
|
|
size_t avl_size(const struct avl *tree);
|
|
size_t avl_height(const struct avl *tree);
|
|
|
|
void avl_merge(struct avl *tree, struct avl *more);
|
|
void avl_update(struct avl *tree, struct avl *more);
|
|
void avl_merge_all(struct avl *tree, struct avl *more);
|
|
|
|
void avl_prefix_map(struct avl *tree, avl_map_f map, void *cookie);
|
|
void avl_infix_map(struct avl *tree, avl_map_f map, void *cookie);
|
|
void avl_postfix_map(struct avl *tree, avl_map_f map, void *cookie);
|
|
void avl_map_between(const struct avl *tree,
|
|
struct avl_node *inter[2], avl_map_f map, void *cookie);
|
|
|
|
#endif /* !TUPPERWARE_AVL_H */
|