1 #ifndef TINC_AVL_TREE_H
2 #define TINC_AVL_TREE_H
5 avl_tree.h -- header file for avl_tree.c
6 Copyright (C) 1998 Michael H. Buselli
7 2000-2005 Ivo Timmermans,
8 2000-2006 Guus Sliepen <guus@tinc-vpn.org>
9 2000-2005 Wessel Dankers <wsl@tinc-vpn.org>
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
21 You should have received a copy of the GNU General Public License along
22 with this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25 Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
27 Modified 2000-11-28 by Wessel Dankers <wsl@tinc-vpn.org> to use counts
28 instead of depths, to add the ->next and ->prev and to generally obfuscate
29 the code. Mail me if you found a bug.
31 Cleaned up and incorporated some of the ideas from the red-black tree
32 library for inclusion into tinc (https://www.tinc-vpn.org/) by
33 Guus Sliepen <guus@tinc-vpn.org>.
42 typedef struct avl_node_t {
44 /* Linked list part */
46 struct avl_node_t *next;
47 struct avl_node_t *prev;
51 struct avl_node_t *parent;
52 struct avl_node_t *left;
53 struct avl_node_t *right;
68 typedef int (*avl_compare_t)(const void *data1, const void *data2);
69 typedef void (*avl_action_t)(const void *data);
70 typedef void (*avl_action_node_t)(const avl_node_t *node);
72 typedef struct avl_tree_t {
74 /* Linked list part */
83 avl_compare_t compare;
88 /* (De)constructors */
90 extern avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete);
91 extern void avl_free_tree(avl_tree_t *tree);
93 extern avl_node_t *avl_alloc_node(void);
94 extern void avl_free_node(avl_tree_t *tree, avl_node_t *node);
96 /* Insertion and deletion */
98 extern avl_node_t *avl_insert(avl_tree_t *tree, void *data);
99 extern avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node);
101 extern void avl_insert_top(avl_tree_t *tree, avl_node_t *node);
102 extern void avl_insert_before(avl_tree_t *tree, avl_node_t *before, avl_node_t *node);
103 extern void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node);
105 extern avl_node_t *avl_unlink(avl_tree_t *tree, void *data);
106 extern void avl_unlink_node(avl_tree_t *tree, avl_node_t *node);
107 extern void avl_delete(avl_tree_t *tree, void *data);
108 extern void avl_delete_node(avl_tree_t *tree, avl_node_t *node);
110 /* Fast tree cleanup */
112 extern void avl_delete_tree(avl_tree_t *tree);
116 extern void *avl_search(const avl_tree_t *tree, const void *data);
117 extern void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result);
118 extern void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data);
119 extern void *avl_search_closest_greater(const avl_tree_t *tree, const void *data);
121 extern avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data);
122 extern avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data, int *result);
123 extern avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, const void *data);
124 extern avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void *data);
128 extern void avl_foreach(const avl_tree_t *tree, avl_action_t action);
129 extern void avl_foreach_node(const avl_tree_t *tree, avl_action_t action);
134 extern unsigned int avl_count(const avl_tree_t *tree);
135 extern avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index);
136 extern unsigned int avl_index(const avl_node_t *node);
139 extern unsigned int avl_depth(const avl_tree_t *tree);