1 /*------------------------------------------------------------------------------
2 *
3 * Copyright (c) 2011-2021, EURid vzw. All rights reserved.
4 * The YADIFA TM software product is provided under the BSD 3-clause license:
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * * Neither the name of EURid nor the names of its contributors may be
16 * used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 *
31 *------------------------------------------------------------------------------
32 *
33 */
34
35 /** @defgroup collections Generic collections functions
36 * @ingroup dnscore
37 * @brief A dictionary (map, hash, ...) ptr->ptr implemented as an AVL balanced tree
38 *
39 * A dictionary (map, hash, ...) implemented as an AVL balanced tree
40 * The key is a pointer and is compated with other keys using a used-defined,
41 * per-collection comparison function.
42 *
43 * Pre-defined comparators include:
44 *
45 * PTR_SET_EMPTY (ptr_set_default_node_compare) pointer addresses
46 * PTR_SET_ASCIIZ_EMPTY (ptr_set_asciizp_node_compare) C-strings
47 * PTR_SET_DNSNAME_EMPTY (ptr_set_dnsname_node_compare) FQDNs
48 * PTR_SET_NULLABLE_ASCIIZ_EMPTY (ptr_set_nullable_asciizp_node_compare) C-strings AND NULL
49 * PTR_SET_NULLABLE_DNSNAME_EMPTY (ptr_set_nullable_dnsname_node_compare) FQDNs AND NULL
50 * PTR_SET_PTR_EMPTY (ptr_set_ptr_node_compare) pointer addresses
51 * PTR_SET_HOST_ADDRESS_EMPTY (ptr_set_host_address_node_compare) host_address
52 *
53 * @{
54 */
55
56 #pragma once
57
58 #ifdef __cplusplus
59 extern "C"
60 {
61 #endif
62
63 #include <dnscore/sys_types.h>
64
65 /*
66 * A digest is stored prefixed with its length ([1;255])
67 */
68
69 /*
70 * A structure to hold both children with direct access
71 */
72
73 typedef int ptr_node_compare(const void *node_a, const void *node_b);
74
75 typedef struct ptr_set ptr_set;
76 typedef struct ptr_node ptr_node;
77
78 struct ptr_set
79 {
80 struct ptr_node *root;
81 ptr_node_compare *compare; // compares nodes by passing pointers to the keys (and not the full node)
82 };
83
84 struct ptr_set_children
85 {
86 struct ptr_node* left;
87 struct ptr_node* right;
88 };
89
90 /*
91 * An union to have access to the children with direct or indexed access
92 */
93
94 typedef union ptr_set_children_union ptr_set_children_union;
95
96 union ptr_set_children_union
97 {
98 struct ptr_set_children lr;
99 struct ptr_node * child[2];
100 };
101
102 /*
103 * The node structure CANNOT have a varying size on a given collection
104 * This means that the digest size is a constant in the whole tree
105 */
106
107 struct ptr_node
108 {
109 union ptr_set_children_union children; // 16
110 /**/
111 struct ptr_node* parent; // 8
112 /**/
113 void *key; /* ie: nsec3 item */
114 union
115 {
116 void *value; /* ie: label linked to the nsec3 item */
117 s64 value_s64;
118 u64 value_u64;
119 };
120
121 s8 balance;
122 };
123
124 #define PTR_SET_NODE_SIZE(node) sizeof(ptr_node)
125
126 /*
127 * AVL definition part begins here
128 */
129
130 /*
131 * The maximum depth of a tree.
132 * 40 is enough for storing 433494436 items (worst case)
133 *
134 * Depth 0 is one node.
135 *
136 * Worst case : N is enough for sum[n = 0,N](Fn) where Fn is Fibonacci(n+1)
137 * Best case : N is enough for (2^(N+1))-1
138 */
139 #define AVL_MAX_DEPTH 52 // 139*10^9 items max (worst case)
140
141 /*
142 * The previx that will be put in front of each function name
143 */
144 #define AVL_PREFIX ptr_set_
145
146 /*
147 * The type that hold the node
148 */
149 #define AVL_NODE_TYPE ptr_node
150
151 /*
152 * The tag for the node
153 */
154
155 #define PTR_NODE_TAG 0x45444f4e525450 // PTRNODE
156
157 /*
158 * The type that hold the tree (should be AVL_NODE_TYPE*)
159 */
160 #define AVL_TREE_TYPE ptr_set
161
162 /*
163 * The type that hold the tree (should be AVL_NODE_TYPE*)
164 */
165 #define AVL_CONST_TREE_TYPE const ptr_set
166
167 /*
168 *
169 */
170 #define AVL_TREE_ROOT(__tree__) (__tree__)->root
171 /*
172 * The type used for comparing the nodes.
173 */
174 #define AVL_REFERENCE_TYPE void*
175 #define AVL_REFERENCE_IS_POINTER TRUE
176 #define AVL_REFERENCE_IS_CONST FALSE
177
178 /*
179 * The node has got a pointer to its parent
180 *
181 * 0 : disable
182 * !=0 : enable
183 */
184 #define AVL_HAS_PARENT_POINTER 1
185
186 #ifdef __cplusplus
187 }
188 #endif
189
190 #include <dnscore/avl.h.inc>
191
192 #ifdef __cplusplus
193 extern "C"
194 {
195 #endif
196
197 /*
198 * I recommend setting a define to identify the C part of the template
199 * So it can be used to undefine what is not required anymore for every
200 * C file but that one.
201 *
202 */
203
204 #ifndef _PTR_SET_COLLECTION_C
205
206 #undef AVL_MAX_DEPTH
207 #undef AVL_PREFIX
208 #undef AVL_NODE_TYPE
209 #undef AVL_NODE_TAG
210 #undef AVL_TREE_TYPE
211 #undef AVL_CONST_TREE_TYPE
212 #undef AVL_TREE_ROOT
213 #undef AVL_REFERENCE_TYPE
214 #undef AVL_HAS_PARENT_POINTER
215 #undef AVL_REFERENCE_IS_POINTER
216 #undef AVL_REFERENCE_IS_CONST
217 #undef _AVL_H_INC
218
219 #endif /* _PTR_SET_COLLECTION_C */
220
221 #ifdef __cplusplus
222 }
223 #endif
224
225 #define ptr_set_default_node_compare ptr_set_ptr_node_compare
226
227 /**
228 * ptr_set comparator function.
229 * Compares pointer values.
230 *
231 * @param key_a
232 * @param key_b
233 * @return
234 */
235
236 int ptr_set_ptr_node_compare(const void *key_a, const void *key_b);
237
238 /**
239 * ptr_set comparator function.
240 * Compares C-string values.
241 *
242 * @param key_a
243 * @param key_b
244 * @return
245 */
246
247 int ptr_set_asciizp_node_compare(const void *key_a, const void *key_b);
248
249 /**
250 * ptr_set comparator function.
251 * Compares C-string values, case-insensitive
252 *
253 * @param key_a
254 * @param key_b
255 * @return
256 */
257
258 int ptr_set_asciizcasep_node_compare(const void *key_a, const void *key_b);
259
260
261 /**
262 * ptr_set comparator function.
263 * Compares dnsname values, taking depth into account.
264 *
265 * @param key_a
266 * @param key_b
267 * @return
268 */
269
270 int ptr_set_fqdn_node_compare(const void *key_a, const void *key_b);
271
272 /**
273 * ptr_set comparator function.
274 * Compares dnsname values.
275 *
276 * @param key_a
277 * @param key_b
278 * @return
279 */
280
281 int ptr_set_dnsname_node_compare(const void *key_a, const void *key_b);
282
283 /**
284 * ptr_set comparator function.
285 * Compares dnslabel values.
286 *
287 * @param key_a
288 * @param key_b
289 * @return
290 */
291
292 int ptr_set_dnslabel_node_compare(const void *key_a, const void *key_b);
293
294 // key = asciiz (can be NULL)
295
296 /**
297 * ptr_set comparator function.
298 * Compares C-strings values, NULL is allowed.
299 *
300 * @param key_a
301 * @param key_b
302 * @return
303 */
304
305 int ptr_set_nullable_asciizp_node_compare(const void *key_a, const void *key_b);
306
307 /**
308 * ptr_set comparator function.
309 * Compares dnsname values, NULL is allowed.
310 *
311 * @param key_a
312 * @param key_b
313 * @return
314 */
315
316 int ptr_set_nullable_dnsname_node_compare(const void *key_a, const void *key_b);
317
318 /**
319 * ptr_set comparator function.
320 * Compares host_address values.
321 *
322 * @param key_a
323 * @param key_b
324 * @return
325 */
326
327 int ptr_set_host_address_node_compare(const void *key_a, const void *key_b);
328
329 #define PTR_SET_EMPTY {NULL, ptr_set_default_node_compare}
330 #define PTR_SET_ASCIIZ_EMPTY {NULL, ptr_set_asciizp_node_compare}
331 #define PTR_SET_ASCIIZCASE_EMPTY {NULL, ptr_set_asciizcasep_node_compare}
332 #define PTR_SET_DNSNAME_EMPTY {NULL, ptr_set_dnsname_node_compare}
333 #define PTR_SET_NULLABLE_ASCIIZ_EMPTY {NULL, ptr_set_nullable_asciizp_node_compare}
334 #define PTR_SET_NULLABLE_DNSNAME_EMPTY {NULL, ptr_set_nullable_dnsname_node_compare}
335 #define PTR_SET_PTR_EMPTY {NULL, ptr_set_ptr_node_compare}
336 #define PTR_SET_CUSTOM(comparator___) {NULL, (comparator___)}
337 #define PTR_SET_HOST_ADDRESS_EMPTY {NULL, ptr_set_host_address_node_compare}
338 #define PTR_SET_EMPTY_WITH_COMPARATOR(cmp_func___) {NULL, (cmp_func___)}
339
340 void *ptr_set_iterator_hasnext_next_value(ptr_set_iterator *iterp);
341
342 #define FOREACH_PTR_SET(cast__,var__,ptr_set__) ptr_set_iterator PREPROCESSOR_CONCAT_EVAL(foreach_ptr_set_iter,__LINE__); ptr_set_iterator_init((ptr_set__), &PREPROCESSOR_CONCAT_EVAL(foreach_ptr_set_iter,__LINE__)); for(cast__ var__;((var__) = (cast__)ptr_set_iterator_hasnext_next_value(&PREPROCESSOR_CONCAT_EVAL(foreach_ptr_set_iter,__LINE__))) != NULL;)
343 //#define FOREACH_PTR_SET_KEY_VALUE(castk__,vark__,castv__,varv__,ptr_set__) ptr_set_iterator PREPROCESSOR_CONCAT_EVAL(foreach_ptr_set_iter,__LINE__); ptr_set_iterator_init((ptr_set__), &PREPROCESSOR_CONCAT_EVAL(foreach_ptr_set_iter,__LINE__)); for(varv__ varv__;((varc__) = (cast__)ptr_set_iterator_hasnext_next_key_value(&PREPROCESSOR_CONCAT_EVAL(foreach_ptr_set_iter,__LINE__))) != NULL;)
344
345 struct const_ptr_set_of_one
346 {
347 ptr_set set;
348 ptr_node one;
349 };
350
351 typedef struct const_ptr_set_of_one const_ptr_set_of_one;
352
353 /**
354 *
355 * For these cases you need a set of a single element that is to be used a simple, constant, input,
356 * this is an efficient way to do so.
357 *
358 * Can only be used for reading (find, iterate)
359 * The above implies : cannot be destroyed (as it is supposed to be on the stack and die winding up)
360 *
361 * Any other usage WILL crash the program.
362 *
363 * @param cpsoo
364 * @param key
365 * @param value
366 * @param cmp
367 *
368 * example usage:
369 *
370 * const_ptr_set_of_one fqdn_set;
371 * const_ptr_set_of_one_init(&fqdn_set, fqdn, fqdn, ptr_set_dnsname_node_compare);
372 * my_function_expecting_a_read_only_fqdn_set(&fqdn_set.set);
373 *
374 * // do whatever I want with the fqdn and forget the fqdn_set
375 */
376
const_ptr_set_of_one_init(const_ptr_set_of_one * cpsoo,void * key,void * value,ptr_node_compare * cmp)377 static inline void const_ptr_set_of_one_init(const_ptr_set_of_one *cpsoo, void *key, void *value, ptr_node_compare *cmp)
378 {
379 cpsoo->set.root = &cpsoo->one;
380 cpsoo->set.compare = cmp;
381 ZEROMEMORY(&cpsoo->one, sizeof(ptr_node));
382 cpsoo->one.key = key;
383 cpsoo->one.value = value;
384 }
385
386 /*
387 * AVL definition part ends here
388 */
389
390 /** @} */
391
392