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_NODE_INIT \
45 (struct avl_tree_node) { \
46 .height = 1, .left = NULL, .right = NULL, .parent = NULL \
47 }
48
49static inline void avl_init_node(struct avl_tree_node *n) {
50 n->height = 1;
51 n->left = n->right = n->parent = NULL;
52}
53
54#define avl_entry(ptr, type, member) container_of(ptr, type, member)
55
56#define avl_tree_for_each(pos, tree) \
57 for ((pos) = avl_tree_first(tree); (pos); (pos) = avl_tree_next(pos))
58
59#define avl_tree_for_each_safe(pos, n, tree) \
60 for ((pos) = avl_tree_first(tree), \
61 (n) = (pos) ? avl_tree_next(pos) : NULL; \
62 (pos); (pos) = (n), (n) = (pos) ? avl_tree_next(pos) : NULL)
63
64#define avl_tree_for_each_entry(pos, type, member, tree) \
65 for (pos = avl_entry(avl_tree_first(tree), type, member); \
66 (pos) != NULL && &pos->member != NULL; \
67 pos = avl_entry(avl_tree_next(&pos->member), type, member))
68
69#define avl_tree_for_each_entry_safe(pos, tmp, type, member, tree) \
70 for (pos = avl_entry(avl_tree_first(tree), type, member), \
71 tmp = (pos) ? avl_entry(avl_tree_next(&pos->member), type, member) \
72 : NULL; \
73 (pos) != NULL && &pos->member != NULL; pos = tmp, \
74 tmp = (pos) ? avl_entry(avl_tree_next(&pos->member), type, member) \
75 : NULL)
76
77#define avl_tree_for_each_reverse(pos, tree) \
78 for ((pos) = avl_tree_last(tree); (pos); (pos) = avl_tree_prev(pos))
79
80#define avl_tree_for_each_safe_reverse(pos, n, tree) \
81 for ((pos) = avl_tree_last(tree), (n) = (pos) ? avl_tree_prev(pos) : NULL; \
82 (pos); (pos) = (n), (n) = (pos) ? avl_tree_prev(pos) : NULL)
83
84#define avl_tree_for_each_entry_reverse(pos, type, member, tree) \
85 for (pos = avl_entry(avl_tree_last(tree), type, member); \
86 (pos) != NULL && &pos->member != NULL; \
87 pos = avl_entry(avl_tree_prev(&pos->member), type, member))
88
89#define avl_tree_for_each_entry_safe_reverse(pos, tmp, type, member, tree) \
90 for (pos = avl_entry(avl_tree_last(tree), type, member), \
91 tmp = (pos) ? avl_entry(avl_tree_prev(&pos->member), type, member) \
92 : NULL; \
93 (pos) != NULL && &pos->member != NULL; pos = tmp, \
94 tmp = (pos) ? avl_entry(avl_tree_prev(&pos->member), type, member) \
95 : NULL)
96