Merge pull request #78 from ffontaine/master
[olsrd.git] / src / common / avl.h
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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 *
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  */