]> git.meshlink.io Git - meshlink/blob - lib/avl_tree.h
Releasing 1.0.19.
[meshlink] / lib / avl_tree.h
1 /*
2     avl_tree.h -- header file for avl_tree.c
3     Copyright (C) 1998 Michael H. Buselli
4                   2000-2005 Ivo Timmermans,
5                   2000-2006 Guus Sliepen <guus@tinc-vpn.org>
6                   2000-2005 Wessel Dankers <wsl@tinc-vpn.org>
7
8     This program is free software; you can redistribute it and/or modify
9     it under the terms of the GNU General Public License as published by
10     the Free Software Foundation; either version 2 of the License, or
11     (at your option) any later version.
12
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16     GNU General Public License for more details.
17
18     You should have received a copy of the GNU General Public License along
19     with this program; if not, write to the Free Software Foundation, Inc.,
20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21
22     Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
23
24     Modified 2000-11-28 by Wessel Dankers <wsl@tinc-vpn.org> to use counts
25     instead of depths, to add the ->next and ->prev and to generally obfuscate
26     the code. Mail me if you found a bug.
27
28     Cleaned up and incorporated some of the ideas from the red-black tree
29     library for inclusion into tinc (http://www.tinc-vpn.org/) by
30     Guus Sliepen <guus@tinc-vpn.org>.
31 */
32
33
34 #ifndef __AVL_TREE_H__
35 #define __AVL_TREE_H__
36
37 #ifndef AVL_DEPTH
38 #ifndef AVL_COUNT
39 #define AVL_DEPTH
40 #endif
41 #endif
42
43 typedef struct avl_node_t {
44
45         /* Linked list part */
46
47         struct avl_node_t *next;
48         struct avl_node_t *prev;
49
50         /* Tree part */
51
52         struct avl_node_t *parent;
53         struct avl_node_t *left;
54         struct avl_node_t *right;
55
56 #ifdef AVL_COUNT
57         unsigned int count;
58 #endif
59 #ifdef AVL_DEPTH
60         unsigned char depth;
61 #endif
62
63         /* Payload */
64
65         void *data;
66
67 } avl_node_t;
68
69 typedef int (*avl_compare_t)(const void *, const void *);
70 typedef void (*avl_action_t)(const void *);
71 typedef void (*avl_action_node_t)(const avl_node_t *);
72
73 typedef struct avl_tree_t {
74
75         /* Linked list part */
76
77         avl_node_t *head;
78         avl_node_t *tail;
79
80         /* Tree part */
81
82         avl_node_t *root;
83
84         avl_compare_t compare;
85         avl_action_t delete;
86
87 } avl_tree_t;
88
89 /* (De)constructors */
90
91 extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_action_t);
92 extern void avl_free_tree(avl_tree_t *);
93
94 extern avl_node_t *avl_alloc_node(void);
95 extern void avl_free_node(avl_tree_t *tree, avl_node_t *);
96
97 /* Insertion and deletion */
98
99 extern avl_node_t *avl_insert(avl_tree_t *, void *);
100 extern avl_node_t *avl_insert_node(avl_tree_t *, avl_node_t *);
101
102 extern void avl_insert_top(avl_tree_t *, avl_node_t *);
103 extern void avl_insert_before(avl_tree_t *, avl_node_t *, avl_node_t *);
104 extern void avl_insert_after(avl_tree_t *, avl_node_t *, avl_node_t *);
105
106 extern avl_node_t *avl_unlink(avl_tree_t *, void *);
107 extern void avl_unlink_node(avl_tree_t *tree, avl_node_t *);
108 extern void avl_delete(avl_tree_t *, void *);
109 extern void avl_delete_node(avl_tree_t *, avl_node_t *);
110
111 /* Fast tree cleanup */
112
113 extern void avl_delete_tree(avl_tree_t *);
114
115 /* Searching */
116
117 extern void *avl_search(const avl_tree_t *, const void *);
118 extern void *avl_search_closest(const avl_tree_t *, const void *, int *);
119 extern void *avl_search_closest_smaller(const avl_tree_t *, const void *);
120 extern void *avl_search_closest_greater(const avl_tree_t *, const void *);
121
122 extern avl_node_t *avl_search_node(const avl_tree_t *, const void *);
123 extern avl_node_t *avl_search_closest_node(const avl_tree_t *, const void *, int *);
124 extern avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *, const void *);
125 extern avl_node_t *avl_search_closest_greater_node(const avl_tree_t *, const void *);
126
127 /* Tree walking */
128
129 extern void avl_foreach(const avl_tree_t *, avl_action_t);
130 extern void avl_foreach_node(const avl_tree_t *, avl_action_t);
131
132 /* Indexing */
133
134 #ifdef AVL_COUNT
135 extern unsigned int avl_count(const avl_tree_t *);
136 extern avl_node_t *avl_get_node(const avl_tree_t *, unsigned int);
137 extern unsigned int avl_index(const avl_node_t *);
138 #endif
139 #ifdef AVL_DEPTH
140 extern unsigned int avl_depth(const avl_tree_t *);
141 #endif
142
143 #endif                                                  /* __AVL_TREE_H__ */