2 avl.h -- AVL tree management
4 Copyright (C) 1998 Michael H. Buselli
5 2000-2004 Ivo Timmermans <ivo@tinc-vpn.org>,
6 2000-2004 Guus Sliepen <guus@tinc-vpn.org>
7 2000-2004 Wessel Dankers <wsl@tinc-vpn.org>
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
25 Modified 2000-11-28 by Wessel Dankers <wsl@tinc-vpn.org> to use counts
26 instead of depths, to add the ->next and ->prev and to generally obfuscate
27 the code. Mail me if you found a bug.
29 Cleaned up and incorporated some of the ideas from the red-black tree
30 library for inclusion into tinc (http://www.tinc-vpn.org/) by
31 Guus Sliepen <guus@tinc-vpn.org>.
46 typedef uint32_t avl_count_t;
47 typedef uint16_t avl_depth_t;
49 typedef struct avl_node {
50 struct avl_node *next;
51 struct avl_node *prev;
53 struct avl_node *parent;
54 struct avl_node *left;
55 struct avl_node *right;
68 typedef int (*avl_compare_t)(const void *, const void *);
69 typedef void (*avl_action_t)(void *);
70 typedef void (*avl_node_action_t)(struct avl_node *);
72 typedef struct avl_tree {
73 struct avl_node *head;
74 struct avl_node *tail;
76 struct avl_node *root;
78 avl_compare_t compare;
82 /* (De)constructors */
84 extern struct avl_tree *avl_tree_new(avl_compare_t, avl_action_t);
85 extern void avl_tree_free(struct avl_tree *);
87 extern struct avl_node *avl_node_new(void);
88 extern void avl_node_free(struct avl_tree *tree, struct avl_node *);
90 /* Insertion and deletion */
92 extern struct avl_node *avl_add(struct avl_tree *, void *);
93 extern struct avl_node *avl_add_node(struct avl_tree *, struct avl_node *);
95 extern void avl_add_top(struct avl_tree *, struct avl_node *);
96 extern void avl_add_before(struct avl_tree *, struct avl_node *, struct avl_node *);
97 extern void avl_add_after(struct avl_tree *, struct avl_node *, struct avl_node *);
99 extern struct avl_node *avl_unlink(struct avl_tree *, const void *);
100 extern void avl_unlink_node(struct avl_tree *tree, struct avl_node *);
101 extern bool avl_del(struct avl_tree *, void *);
102 extern void avl_del_node(struct avl_tree *, struct avl_node *);
104 /* Fast tree cleanup */
106 extern void avl_tree_del(struct avl_tree *);
110 extern void *avl_get(const struct avl_tree *, const void *);
111 extern void *avl_get_closest(const struct avl_tree *, const void *, int *);
112 extern void *avl_get_closest_smaller(const struct avl_tree *, const void *);
113 extern void *avl_get_closest_greater(const struct avl_tree *, const void *);
115 extern struct avl_node *avl_get_node(const struct avl_tree *, const void *);
116 extern struct avl_node *avl_get_closest_node(const struct avl_tree *, const void *, int *);
117 extern struct avl_node *avl_get_closest_smaller_node(const struct avl_tree *, const void *);
118 extern struct avl_node *avl_get_closest_greater_node(const struct avl_tree *, const void *);
122 #define avl_foreach(tree, object, action) {avl_node_t *_node, *_next; \
123 for(_node = (tree)->head; _node; _node = _next) { \
124 _next = _node->next; \
125 (object) = _node->data; \
130 #define avl_foreach_node(tree, node, action) {avl_node_t *_next; \
131 for((node) = (tree)->head; (node); (node) = _next) { \
132 _next = (node)->next; \
140 extern avl_count_t avl_count(const struct avl_tree *);
141 extern avl_count_t avl_index(const struct avl_node *);
142 extern void *avl_get_indexed(const struct avl_tree *, avl_count_t);
143 extern struct avl_node *avl_get_indexed_node(const struct avl_tree *, avl_count_t);
146 extern avl_depth_t avl_depth(const struct avl_tree *);