1 /*
2 * The olsr.org Optimized Link-State Routing daemon (olsrd)
3 *
4 * (c) by the OLSR project
5 *
6 * See our Git repository to find out who worked on this file
7 * and thus is a copyright holder on it.
8 *
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 *
15 * * Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
20 * distribution.
21 * * Neither the name of olsr.org, olsrd nor the names of its
22 * contributors may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
37 *
38 * Visit http://www.olsr.org for more information.
39 *
40 * If you find this software useful feel free to make a donation
41 * to the project. For more information see the website or contact
42 * the copyright holders.
43 *
44 */
45
46 #ifndef _AVL_H
47 #define _AVL_H
48
49 #include <stddef.h>
50 #include "compiler.h"
51 #include "defs.h"
52
53 struct avl_node {
54 struct avl_node *parent;
55 struct avl_node *left;
56 struct avl_node *right;
57 struct avl_node *next;
58 struct avl_node *prev;
59 void *key;
60 signed char balance;
61 unsigned char leader;
62 };
63
64 typedef int (*avl_tree_comp) (const void *, const void *);
65
66 struct avl_tree {
67 struct avl_node *root;
68 struct avl_node *first;
69 struct avl_node *last;
70 unsigned int count;
71 avl_tree_comp comp;
72 };
73
74 #define AVL_DUP 1
75 #define AVL_DUP_NO 0
76
77 void avl_init(struct avl_tree *, avl_tree_comp);
78 struct avl_node *avl_find(struct avl_tree *, const void *);
79 int avl_insert(struct avl_tree *, struct avl_node *, int);
80 void avl_delete(struct avl_tree *, struct avl_node *);
81
82 static INLINE struct avl_node *
avl_walk_first(struct avl_tree * tree)83 avl_walk_first(struct avl_tree *tree)
84 {
85 if (!tree) {
86 return NULL;
87 }
88
89 return tree->first;
90 }
91 static INLINE struct avl_node *
avl_walk_last(struct avl_tree * tree)92 avl_walk_last(struct avl_tree *tree)
93 {
94 if (!tree) {
95 return NULL;
96 }
97
98 return tree->last;
99 }
100 static INLINE struct avl_node *
avl_walk_next(struct avl_node * node)101 avl_walk_next(struct avl_node *node)
102 {
103 if (!node) {
104 return NULL;
105 }
106
107 return node->next;
108 }
109 static INLINE struct avl_node *
avl_walk_prev(struct avl_node * node)110 avl_walk_prev(struct avl_node *node)
111 {
112 if (!node) {
113 return NULL;
114 }
115
116 return node->prev;
117 }
118
119 /* and const versions*/
120 static INLINE const struct avl_node *
avl_walk_first_c(const struct avl_tree * tree)121 avl_walk_first_c(const struct avl_tree *tree)
122 {
123 if (!tree) {
124 return NULL;
125 }
126
127 return tree->first;
128 }
129 static INLINE const struct avl_node *
avl_walk_last_c(const struct avl_tree * tree)130 avl_walk_last_c(const struct avl_tree *tree)
131 {
132 if (!tree) {
133 return NULL;
134 }
135
136 return tree->last;
137 }
138 static INLINE const struct avl_node *
avl_walk_next_c(const struct avl_node * node)139 avl_walk_next_c(const struct avl_node *node)
140 {
141 if (!node) {
142 return NULL;
143 }
144
145 return node->next;
146 }
147 static INLINE const struct avl_node *
avl_walk_prev_c(const struct avl_node * node)148 avl_walk_prev_c(const struct avl_node *node)
149 {
150 if (!node) {
151 return NULL;
152 }
153
154 return node->prev;
155 }
156
157 extern avl_tree_comp avl_comp_default;
158 extern avl_tree_comp avl_comp_prefix_default;
159 extern int avl_comp_ipv4(const void *, const void *);
160 extern int avl_comp_ipv6(const void *, const void *);
161 extern int avl_comp_mac(const void *, const void *);
162
163 /*
164 * Macro to define an INLINE function to map from a list_node offset back to the
165 * base of the datastructure. That way you save an extra data pointer.
166 */
167 #define AVLNODE2STRUCT(funcname, structname, avlnodename) \
168 static INLINE structname * funcname (struct avl_node *ptr)\
169 {\
170 return( \
171 ptr ? \
172 (structname *) (((size_t) ptr) - offsetof(structname, avlnodename)) : \
173 NULL); \
174 }
175
176 #endif /* _AVL_H */
177
178 /*
179 * Local Variables:
180 * c-basic-offset: 2
181 * indent-tabs-mode: nil
182 * End:
183 */
184