]> git.meshlink.io Git - meshlink/blob - lib/avl_tree.h
Always close all sockets in terminate_connection().
[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,2001 Ivo Timmermans <itimmermans@bigfoot.com>,
5                   2000,2001 Guus Sliepen <guus@sliepen.warande.net>
6                   2000,2001 Wessel Dankers <wsl@nl.linux.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
19     along with this program; if not, write to the Free Software
20     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21
22     Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
23
24     Modified 2000-11-28 by Wessel Dankers <wsl@nl.linux.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://tinc.nl.linux.org/) by
30     Guus Sliepen <guus@sliepen.warande.net>.
31
32     $Id: avl_tree.h,v 1.1.2.4 2001/02/06 10:13:22 guus Exp $
33 */
34
35
36 #ifndef __AVL_TREE_H__
37 #define __AVL_TREE_H__
38
39 #ifndef AVL_DEPTH
40  #ifndef AVL_COUNT
41   #define AVL_DEPTH
42  #endif
43 #endif
44
45 typedef struct avl_node_t {
46
47   /* Linked list part */
48
49   struct avl_node_t *next;
50   struct avl_node_t *prev;
51
52   /* Tree part */
53
54   struct avl_node_t *parent;
55   struct avl_node_t *left;
56   struct avl_node_t *right;
57
58 #ifdef AVL_COUNT
59   unsigned int count;
60 #endif
61 #ifdef AVL_DEPTH
62   unsigned char depth;
63 #endif
64
65   /* Payload */
66
67   void *data;
68
69 } avl_node_t;
70
71 typedef int (*avl_compare_t) (const void *, const void *);
72 typedef void (*avl_action_t) (const void *);
73 typedef void (*avl_action_node_t) (const avl_node_t *);
74
75 typedef struct avl_tree_t {
76
77   /* Linked list part */
78
79   avl_node_t *head;
80   avl_node_t *tail;
81
82   /* Tree part */
83
84   avl_node_t *root;
85
86   avl_compare_t compare;
87   avl_action_t delete;
88
89 } avl_tree_t;
90
91 /* (De)constructors */
92
93 extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_action_t);
94 extern void avl_free_tree(avl_tree_t *);
95
96 extern avl_node_t *avl_alloc_node(void);
97 extern void avl_free_node(avl_tree_t *tree, avl_node_t *);
98
99 /* Insertion and deletion */
100
101 extern avl_node_t *avl_insert(avl_tree_t *, void *);
102 extern avl_node_t *avl_insert_node(avl_tree_t *, avl_node_t *);
103
104 extern void avl_insert_top(avl_tree_t *, avl_node_t *);
105 extern void avl_insert_before(avl_tree_t *, avl_node_t *, avl_node_t *);
106 extern void avl_insert_after(avl_tree_t *, avl_node_t *, avl_node_t *);
107
108 extern avl_node_t *avl_unlink(avl_tree_t *, void *);
109 extern void avl_unlink_node(avl_tree_t *tree, avl_node_t *);
110 extern void avl_delete(avl_tree_t *, void *);
111 extern void avl_delete_node(avl_tree_t *, avl_node_t *);
112
113 /* Fast tree cleanup */
114
115 extern void avl_delete_tree(avl_tree_t *);
116
117 /* Searching */
118
119 extern void *avl_search(const avl_tree_t *, const void *);
120 extern void *avl_search_closest(const avl_tree_t *, const void *, int *);
121 extern void *avl_search_closest_smaller(const avl_tree_t *, const void *);
122 extern void *avl_search_closest_greater(const avl_tree_t *, const void *);
123
124 extern avl_node_t *avl_search_node(const avl_tree_t *, const void *);
125 extern avl_node_t *avl_search_closest_node(const avl_tree_t *, const void *, int *);
126 extern avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *, const void *);
127 extern avl_node_t *avl_search_closest_greater_node(const avl_tree_t *, const void *);
128
129 /* Tree walking */
130
131 extern void avl_foreach(avl_tree_t *, avl_action_t);
132 extern void avl_foreach_node(avl_tree_t *, avl_action_t);
133
134 /* Indexing */
135
136 #ifdef AVL_COUNT
137 extern unsigned int avl_count(avl_tree_t *);
138 extern avl_node_t *avl_get_node(const avl_tree_t *, unsigned int);
139 extern unsigned int avl_index(const avl_node_t *);
140 #endif
141 #ifdef AVL_DEPTH
142 extern unsigned int avl_depth(avl_tree_t *);
143 #endif
144
145 #endif /* __AVL_TREE_H__ */