1/* @title: AVL tree */
2#pragma once
3#include <container_of.h>
4#include <stddef.h>
5#include <stdint.h>
6
7struct avl_tree_node {
8 int height;
9 struct avl_tree_node *left;
10 struct avl_tree_node *right;
11 struct avl_tree_node *parent;
12};
13
14struct avl_tree_node_ops {
15 /* Compare two embedded nodes. Returns <0, 0, >0. Required. */
16 int (*cmp)(const struct avl_tree_node *a, const struct avl_tree_node *b);
17 /* Compare a node against an external key */
18 int (*cmp_key)(const struct avl_tree_node *node, const void *key);
19};
20
21struct avl_tree {
22 struct avl_tree_node *root;
23 const struct avl_tree_node_ops *ops;
24};
25
26void avl_tree_init(struct avl_tree *tree, const struct avl_tree_node_ops *ops);
27
28void avl_tree_insert(struct avl_tree *tree, struct avl_tree_node *node);
29
30void avl_tree_remove(struct avl_tree *tree, struct avl_tree_node *node);
31
32struct avl_tree_node *avl_tree_find(const struct avl_tree *tree,
33 const void *key);
34
35struct avl_tree_node *avl_tree_first(const struct avl_tree *tree);
36struct avl_tree_node *avl_tree_last(const struct avl_tree *tree);
37struct avl_tree_node *avl_tree_next(const struct avl_tree_node *node);
38struct avl_tree_node *avl_tree_prev(const struct avl_tree_node *node);
39
40static inline int avl_tree_empty(const struct avl_tree *tree) {
41 return tree->root == NULL;
42}
43
44#define avl_entry(ptr, type, member) container_of(ptr, type, member)
45
46#define avl_tree_for_each(pos, tree) \
47 for ((pos) = avl_tree_first(tree); (pos); (pos) = avl_tree_next(pos))
48
49#define avl_tree_for_each_safe(pos, n, tree) \
50 for ((pos) = avl_tree_first(tree), \
51 (n) = (pos) ? avl_tree_next(pos) : NULL; \
52 (pos); (pos) = (n), (n) = (pos) ? avl_tree_next(pos) : NULL)
53