1 /*
2 * ivykis, an event handling library
3 * Copyright (C) 2010 Lennert Buytenhek
4 * Dedicated to Marija Kulikova.
5 *
6 * This library is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License version
8 * 2.1 as published by the Free Software Foundation.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser General Public License version 2.1 for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License version 2.1 along with this library; if not, write to the
17 * Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 */
20
21 #ifndef __IV_AVL_H
22 #define __IV_AVL_H
23
24 #ifdef __cplusplus
25 extern "C" {
26 #endif
27
28 #include <inttypes.h>
29
30 struct iv_avl_node {
31 struct iv_avl_node *left;
32 struct iv_avl_node *right;
33 struct iv_avl_node *parent;
34 uint8_t height;
35 };
36
37 struct iv_avl_tree {
38 int (*compare)(const struct iv_avl_node *a,
39 const struct iv_avl_node *b);
40
41 struct iv_avl_node *root;
42 };
43
44 #define IV_AVL_TREE_INIT(comp) \
45 { .compare = comp, .root = NULL }
46
47 #define INIT_IV_AVL_TREE(tree, comp) \
48 do { \
49 (tree)->compare = (comp); \
50 (tree)->root = NULL; \
51 } while (0)
52
53 int iv_avl_tree_insert(struct iv_avl_tree *tree, struct iv_avl_node *an);
54 void iv_avl_tree_delete(struct iv_avl_tree *tree, struct iv_avl_node *an);
55 struct iv_avl_node *iv_avl_tree_next(struct iv_avl_node *an);
56 struct iv_avl_node *iv_avl_tree_prev(struct iv_avl_node *an);
57
iv_avl_tree_empty(const struct iv_avl_tree * tree)58 static inline int iv_avl_tree_empty(const struct iv_avl_tree *tree)
59 {
60 return tree->root == NULL;
61 }
62
63 static inline struct iv_avl_node *
iv_avl_tree_min(const struct iv_avl_tree * tree)64 iv_avl_tree_min(const struct iv_avl_tree *tree)
65 {
66 if (tree->root != NULL) {
67 struct iv_avl_node *an;
68
69 an = tree->root;
70 while (an->left != NULL)
71 an = an->left;
72
73 return an;
74 }
75
76 return NULL;
77 }
78
79 static inline struct iv_avl_node *
iv_avl_tree_max(const struct iv_avl_tree * tree)80 iv_avl_tree_max(const struct iv_avl_tree *tree)
81 {
82 if (tree->root != NULL) {
83 struct iv_avl_node *an;
84
85 an = tree->root;
86 while (an->right != NULL)
87 an = an->right;
88
89 return an;
90 }
91
92 return NULL;
93 }
94
95 #define iv_avl_tree_for_each(an, tree) \
96 for (an = iv_avl_tree_min(tree); an != NULL; an = iv_avl_tree_next(an))
97
iv_avl_tree_next_safe(struct iv_avl_node * an)98 static inline struct iv_avl_node *iv_avl_tree_next_safe(struct iv_avl_node *an)
99 {
100 return an != NULL ? iv_avl_tree_next(an) : NULL;
101 }
102
103 #define iv_avl_tree_for_each_safe(an, an2, tree) \
104 for (an = iv_avl_tree_min(tree), an2 = iv_avl_tree_next_safe(an); \
105 an != NULL; an = an2, an2 = iv_avl_tree_next_safe(an))
106
107 #ifdef __cplusplus
108 }
109 #endif
110
111
112 #endif
113