1 /*
2 * radix.c -- generic radix tree
3 *
4 * Taken from NSD4, modified for ldns
5 *
6 * Copyright (c) 2012, NLnet Labs. All rights reserved.
7 *
8 * This software is open source.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 *
17 * Redistributions in binary form must reproduce the above copyright notice,
18 * this list of conditions and the following disclaimer in the documentation
19 * and/or other materials provided with the distribution.
20 *
21 * Neither the name of the NLNET LABS nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
23 * 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 LIMITED
27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 *
37 */
38
39 /**
40 * \file
41 * Implementation of a radix tree.
42 */
43
44 #include <ldns/config.h>
45 #include <ldns/radix.h>
46 #include <ldns/util.h>
47 #include <stdlib.h>
48
49 /** Helper functions */
50 static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
51 radix_strlen_t len);
52 static int ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
53 radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos);
54 static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte);
55 static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need);
56 static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
57 radix_strlen_t pos, radix_strlen_t len);
58 static int ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
59 uint8_t* longer_str, radix_strlen_t longer_len, uint8_t** split_str,
60 radix_strlen_t* split_len);
61 static int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
62 radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add);
63 static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
64 uint8_t* str2, radix_strlen_t len2);
65 static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
66 uint8_t* str2, radix_strlen_t len2);
67 static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node);
68 static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node,
69 uint8_t index);
70 static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self(
71 ldns_radix_node_t* node);
72 static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node);
73 static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node);
74 static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node);
75 static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node);
76 static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg);
77 static void ldns_radix_node_array_free(ldns_radix_node_t* node);
78 static void ldns_radix_node_array_free_front(ldns_radix_node_t* node);
79 static void ldns_radix_node_array_free_end(ldns_radix_node_t* node);
80 static void ldns_radix_array_reduce(ldns_radix_node_t* node);
81 static void ldns_radix_self_or_prev(ldns_radix_node_t* node,
82 ldns_radix_node_t** result);
83
84
85 /**
86 * Create a new radix node.
87 *
88 */
89 static ldns_radix_node_t*
ldns_radix_new_node(void * data,uint8_t * key,radix_strlen_t len)90 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
91 {
92 ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
93 if (!node) {
94 return NULL;
95 }
96 node->data = data;
97 node->key = key;
98 node->klen = len;
99 node->parent = NULL;
100 node->parent_index = 0;
101 node->len = 0;
102 node->offset = 0;
103 node->capacity = 0;
104 node->array = NULL;
105 return node;
106 }
107
108
109 /**
110 * Create a new radix tree.
111 *
112 */
113 ldns_radix_t *
ldns_radix_create(void)114 ldns_radix_create(void)
115 {
116 ldns_radix_t* tree;
117
118 /** Allocate memory for it */
119 tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
120 if (!tree) {
121 return NULL;
122 }
123 /** Initialize it */
124 ldns_radix_init(tree);
125 return tree;
126 }
127
128
129 /**
130 * Initialize radix tree.
131 *
132 */
133 void
ldns_radix_init(ldns_radix_t * tree)134 ldns_radix_init(ldns_radix_t* tree)
135 {
136 /** Initialize it */
137 if (tree) {
138 tree->root = NULL;
139 tree->count = 0;
140 }
141 return;
142 }
143
144
145 /**
146 * Free radix tree.
147 *
148 */
149 void
ldns_radix_free(ldns_radix_t * tree)150 ldns_radix_free(ldns_radix_t* tree)
151 {
152 if (tree) {
153 if (tree->root) {
154 ldns_radix_traverse_postorder(tree->root,
155 ldns_radix_node_free, NULL);
156 }
157 LDNS_FREE(tree);
158 }
159 return;
160 }
161
162
163 /**
164 * Insert data into the tree.
165 *
166 */
167 ldns_status
ldns_radix_insert(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len,void * data)168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
169 void* data)
170 {
171 radix_strlen_t pos = 0;
172 ldns_radix_node_t* add = NULL;
173 ldns_radix_node_t* prefix = NULL;
174
175 if (!tree || !key || !data) {
176 return LDNS_STATUS_NULL;
177 }
178 add = ldns_radix_new_node(data, key, len);
179 if (!add) {
180 return LDNS_STATUS_MEM_ERR;
181 }
182 /** Search the trie until we can make no further process. */
183 if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
184 /** No prefix found */
185 assert(tree->root == NULL);
186 if (len == 0) {
187 /**
188 * Example 1: The root:
189 * | [0]
190 **/
191 tree->root = add;
192 } else {
193 /** Example 2: 'dns':
194 * | [0]
195 * --| [d+ns] dns
196 **/
197 prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
198 if (!prefix) {
199 LDNS_FREE(add);
200 return LDNS_STATUS_MEM_ERR;
201 }
202 /** Find some space in the array for the first byte */
203 if (!ldns_radix_array_space(prefix, key[0])) {
204 LDNS_FREE(add);
205 LDNS_FREE(prefix->array);
206 LDNS_FREE(prefix);
207 return LDNS_STATUS_MEM_ERR;
208 }
209 /** Set relational pointers */
210 add->parent = prefix;
211 add->parent_index = 0;
212 prefix->array[0].edge = add;
213 if (len > 1) {
214 /** Store the remainder of the prefix */
215 if (!ldns_radix_prefix_remainder(1, key,
216 len, &prefix->array[0].str,
217 &prefix->array[0].len)) {
218 LDNS_FREE(add);
219 LDNS_FREE(prefix->array);
220 LDNS_FREE(prefix);
221 return LDNS_STATUS_MEM_ERR;
222 }
223 }
224 tree->root = prefix;
225 }
226 } else if (pos == len) {
227 /** Exact match found */
228 if (prefix->data) {
229 /* Element already exists */
230 LDNS_FREE(add);
231 return LDNS_STATUS_EXISTS_ERR;
232 }
233 prefix->data = data;
234 prefix->key = key;
235 prefix->klen = len; /* redundant */
236 } else {
237 /** Prefix found */
238 uint8_t byte = key[pos];
239 assert(pos < len);
240 if (byte < prefix->offset ||
241 (byte - prefix->offset) >= prefix->len) {
242 /** Find some space in the array for the byte. */
243 /**
244 * Example 3: 'ldns'
245 * | [0]
246 * --| [d+ns] dns
247 * --| [l+dns] ldns
248 **/
249 if (!ldns_radix_array_space(prefix, byte)) {
250 LDNS_FREE(add);
251 return LDNS_STATUS_MEM_ERR;
252 }
253 assert(byte >= prefix->offset);
254 assert((byte - prefix->offset) <= prefix->len);
255 byte -= prefix->offset;
256 if (pos+1 < len) {
257 /** Create remainder of the string. */
258 if (!ldns_radix_str_create(
259 &prefix->array[byte], key, pos+1,
260 len)) {
261 LDNS_FREE(add);
262 return LDNS_STATUS_MEM_ERR;
263 }
264 }
265 /** Add new node. */
266 add->parent = prefix;
267 add->parent_index = byte;
268 prefix->array[byte].edge = add;
269 } else if (prefix->array[byte-prefix->offset].edge == NULL) {
270 /** Use existing element. */
271 /**
272 * Example 4: 'edns'
273 * | [0]
274 * --| [d+ns] dns
275 * --| [e+dns] edns
276 * --| [l+dns] ldns
277 **/
278 byte -= prefix->offset;
279 if (pos+1 < len) {
280 /** Create remainder of the string. */
281 if (!ldns_radix_str_create(
282 &prefix->array[byte], key, pos+1,
283 len)) {
284 LDNS_FREE(add);
285 return LDNS_STATUS_MEM_ERR;
286 }
287 }
288 /** Add new node. */
289 add->parent = prefix;
290 add->parent_index = byte;
291 prefix->array[byte].edge = add;
292 } else {
293 /**
294 * Use existing element, but it has a shared prefix,
295 * we need a split.
296 */
297 if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)],
298 key, pos+1, len, add)) {
299 LDNS_FREE(add);
300 return LDNS_STATUS_MEM_ERR;
301 }
302 }
303 }
304
305 tree->count ++;
306 return LDNS_STATUS_OK;
307 }
308
309
310 /**
311 * Delete data from the tree.
312 *
313 */
ldns_radix_delete(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len)314 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
315 {
316 ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
317 void* data = NULL;
318 if (del) {
319 tree->count--;
320 data = del->data;
321 del->data = NULL;
322 ldns_radix_del_fix(tree, del);
323 return data;
324 }
325 return NULL;
326 }
327
328
329 /**
330 * Search data in the tree.
331 *
332 */
333 ldns_radix_node_t*
ldns_radix_search(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len)334 ldns_radix_search(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
335 {
336 ldns_radix_node_t* node = NULL;
337 radix_strlen_t pos = 0;
338 uint8_t byte = 0;
339
340 if (!tree || !key) {
341 return NULL;
342 }
343 node = tree->root;
344 while (node) {
345 if (pos == len) {
346 return node->data?node:NULL;
347 }
348 byte = key[pos];
349 if (byte < node->offset) {
350 return NULL;
351 }
352 byte -= node->offset;
353 if (byte >= node->len) {
354 return NULL;
355 }
356 pos++;
357 if (node->array[byte].len > 0) {
358 /** Must match additional string. */
359 if (pos + node->array[byte].len > len) {
360 return NULL;
361 }
362 if (memcmp(&key[pos], node->array[byte].str,
363 node->array[byte].len) != 0) {
364 return NULL;
365 }
366 pos += node->array[byte].len;
367 }
368 node = node->array[byte].edge;
369 }
370 return NULL;
371 }
372
373
374 /**
375 * Search data in the tree, and if not found, find the closest smaller
376 * element in the tree.
377 *
378 */
379 int
ldns_radix_find_less_equal(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len,ldns_radix_node_t ** result)380 ldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key,
381 radix_strlen_t len, ldns_radix_node_t** result)
382 {
383 ldns_radix_node_t* node = NULL;
384 radix_strlen_t pos = 0;
385 uint8_t byte;
386 int memcmp_res = 0;
387
388 if (!tree || !tree->root || !key) {
389 *result = NULL;
390 return 0;
391 }
392
393 node = tree->root;
394 while (pos < len) {
395 byte = key[pos];
396 if (byte < node->offset) {
397 /**
398 * No exact match. The lesser is in this or the
399 * previous node.
400 */
401 ldns_radix_self_or_prev(node, result);
402 return 0;
403 }
404 byte -= node->offset;
405 if (byte >= node->len) {
406 /**
407 * No exact match. The lesser is in this node or the
408 * last of this array, or something before this node.
409 */
410 *result = ldns_radix_last_in_subtree_incl_self(node);
411 if (*result == NULL) {
412 *result = ldns_radix_prev(node);
413 }
414 return 0;
415 }
416 pos++;
417 if (!node->array[byte].edge) {
418 /**
419 * No exact match. Find the previous in the array
420 * from this index.
421 */
422 *result = ldns_radix_prev_from_index(node, byte);
423 if (*result == NULL) {
424 ldns_radix_self_or_prev(node, result);
425 }
426 return 0;
427 }
428 if (node->array[byte].len != 0) {
429 /** Must match additional string. */
430 if (pos + node->array[byte].len > len) {
431 /** Additional string is longer than key. */
432 if (memcmp(&key[pos], node->array[byte].str,
433 len-pos) <= 0) {
434 /** Key is before this node. */
435 *result = ldns_radix_prev(
436 node->array[byte].edge);
437 } else {
438 /** Key is after additional string. */
439 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
440 if (*result == NULL) {
441 *result = ldns_radix_prev(node->array[byte].edge);
442 }
443 }
444 return 0;
445 }
446 memcmp_res = memcmp(&key[pos], node->array[byte].str,
447 node->array[byte].len);
448 if (memcmp_res < 0) {
449 *result = ldns_radix_prev(
450 node->array[byte].edge);
451 return 0;
452 } else if (memcmp_res > 0) {
453 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
454 if (*result == NULL) {
455 *result = ldns_radix_prev(node->array[byte].edge);
456 }
457 return 0;
458 }
459
460 pos += node->array[byte].len;
461 }
462 node = node->array[byte].edge;
463 }
464 if (node->data) {
465 /** Exact match. */
466 *result = node;
467 return 1;
468 }
469 /** There is a node which is an exact match, but has no element. */
470 *result = ldns_radix_prev(node);
471 return 0;
472 }
473
474
475 /**
476 * Get the first element in the tree.
477 *
478 */
479 ldns_radix_node_t*
ldns_radix_first(ldns_radix_t * tree)480 ldns_radix_first(ldns_radix_t* tree)
481 {
482 ldns_radix_node_t* first = NULL;
483 if (!tree || !tree->root) {
484 return NULL;
485 }
486 first = tree->root;
487 if (first->data) {
488 return first;
489 }
490 return ldns_radix_next(first);
491 }
492
493
494 /**
495 * Get the last element in the tree.
496 *
497 */
498 ldns_radix_node_t*
ldns_radix_last(ldns_radix_t * tree)499 ldns_radix_last(ldns_radix_t* tree)
500 {
501 if (!tree || !tree->root) {
502 return NULL;
503 }
504 return ldns_radix_last_in_subtree_incl_self(tree->root);
505 }
506
507
508 /**
509 * Next element.
510 *
511 */
512 ldns_radix_node_t*
ldns_radix_next(ldns_radix_node_t * node)513 ldns_radix_next(ldns_radix_node_t* node)
514 {
515 if (!node) {
516 return NULL;
517 }
518 if (node->len) {
519 /** Go down: most-left child is the next. */
520 ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
521 if (next) {
522 return next;
523 }
524 }
525 /** No elements in subtree, get to parent and go down next branch. */
526 while (node->parent) {
527 uint8_t index = node->parent_index;
528 node = node->parent;
529 index++;
530 for (; index < node->len; index++) {
531 if (node->array[index].edge) {
532 ldns_radix_node_t* next;
533 /** Node itself. */
534 if (node->array[index].edge->data) {
535 return node->array[index].edge;
536 }
537 /** Dive into subtree. */
538 next = ldns_radix_next_in_subtree(node);
539 if (next) {
540 return next;
541 }
542 }
543 }
544 }
545 return NULL;
546 }
547
548
549 /**
550 * Previous element.
551 *
552 */
553 ldns_radix_node_t*
ldns_radix_prev(ldns_radix_node_t * node)554 ldns_radix_prev(ldns_radix_node_t* node)
555 {
556 if (!node) {
557 return NULL;
558 }
559
560 /** Get to parent and go down previous branch. */
561 while (node->parent) {
562 uint8_t index = node->parent_index;
563 ldns_radix_node_t* prev;
564 node = node->parent;
565 assert(node->len > 0);
566 prev = ldns_radix_prev_from_index(node, index);
567 if (prev) {
568 return prev;
569 }
570 if (node->data) {
571 return node;
572 }
573 }
574 return NULL;
575 }
576
577
578 /**
579 * Print node.
580 *
581 */
582 static void
ldns_radix_node_print(FILE * fd,ldns_radix_node_t * node,uint8_t i,uint8_t * str,radix_strlen_t len,unsigned d)583 ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node,
584 uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d)
585 {
586 uint8_t j;
587 if (!node) {
588 return;
589 }
590 for (j = 0; j < d; j++) {
591 fprintf(fd, "--");
592 }
593 if (str) {
594 radix_strlen_t l;
595 fprintf(fd, "| [%u+", (unsigned) i);
596 for (l=0; l < len; l++) {
597 fprintf(fd, "%c", (char) str[l]);
598 }
599 fprintf(fd, "]%u", (unsigned) len);
600 } else {
601 fprintf(fd, "| [%u]", (unsigned) i);
602 }
603
604 if (node->data) {
605 fprintf(fd, " %s", (char*) node->data);
606 }
607 fprintf(fd, "\n");
608
609 for (j = 0; j < node->len; j++) {
610 if (node->array[j].edge) {
611 ldns_radix_node_print(fd, node->array[j].edge, j,
612 node->array[j].str, node->array[j].len, d+1);
613 }
614 }
615 return;
616 }
617
618
619 /**
620 * Print radix tree.
621 *
622 */
623 void
ldns_radix_printf(FILE * fd,ldns_radix_t * tree)624 ldns_radix_printf(FILE* fd, ldns_radix_t* tree)
625 {
626 if (!fd || !tree) {
627 return;
628 }
629 if (!tree->root) {
630 fprintf(fd, "; empty radix tree\n");
631 return;
632 }
633 ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0);
634 return;
635 }
636
637
638 /**
639 * Join two radix trees.
640 *
641 */
642 ldns_status
ldns_radix_join(ldns_radix_t * tree1,ldns_radix_t * tree2)643 ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2)
644 {
645 ldns_radix_node_t* cur_node, *next_node;
646 ldns_status status;
647 if (!tree2 || !tree2->root) {
648 return LDNS_STATUS_OK;
649 }
650 /** Add all elements from tree2 into tree1. */
651
652 cur_node = ldns_radix_first(tree2);
653 while (cur_node) {
654 status = LDNS_STATUS_NO_DATA;
655 /** Insert current node into tree1 */
656 if (cur_node->data) {
657 status = ldns_radix_insert(tree1, cur_node->key,
658 cur_node->klen, cur_node->data);
659 /** Exist errors may occur */
660 if (status != LDNS_STATUS_OK &&
661 status != LDNS_STATUS_EXISTS_ERR) {
662 return status;
663 }
664 }
665 next_node = ldns_radix_next(cur_node);
666 if (status == LDNS_STATUS_OK) {
667 (void) ldns_radix_delete(tree2, cur_node->key,
668 cur_node->klen);
669 }
670 cur_node = next_node;
671 }
672
673 return LDNS_STATUS_OK;
674 }
675
676
677 /**
678 * Split a radix tree intwo.
679 *
680 */
681 ldns_status
ldns_radix_split(ldns_radix_t * tree1,size_t num,ldns_radix_t ** tree2)682 ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2)
683 {
684 size_t count = 0;
685 ldns_radix_node_t* cur_node;
686 ldns_status status = LDNS_STATUS_OK;
687 if (!tree1 || !tree1->root || num == 0) {
688 return LDNS_STATUS_OK;
689 }
690 if (!tree2) {
691 return LDNS_STATUS_NULL;
692 }
693 if (!*tree2) {
694 *tree2 = ldns_radix_create();
695 if (!*tree2) {
696 return LDNS_STATUS_MEM_ERR;
697 }
698 }
699 cur_node = ldns_radix_first(tree1);
700 while (count < num && cur_node) {
701 if (cur_node->data) {
702 /** Delete current node from tree1. */
703 uint8_t* cur_key = cur_node->key;
704 radix_strlen_t cur_len = cur_node->klen;
705 void* cur_data = ldns_radix_delete(tree1, cur_key,
706 cur_len);
707 /** Insert current node into tree2/ */
708 if (!cur_data) {
709 return LDNS_STATUS_NO_DATA;
710 }
711 status = ldns_radix_insert(*tree2, cur_key, cur_len,
712 cur_data);
713 if (status != LDNS_STATUS_OK &&
714 status != LDNS_STATUS_EXISTS_ERR) {
715 return status;
716 }
717 /*
718 if (status == LDNS_STATUS_OK) {
719 cur_node->key = NULL;
720 cur_node->klen = 0;
721 }
722 */
723 /** Update count; get first element from tree1 again. */
724 count++;
725 cur_node = ldns_radix_first(tree1);
726 } else {
727 cur_node = ldns_radix_next(cur_node);
728 }
729 }
730 return LDNS_STATUS_OK;
731 }
732
733
734 /**
735 * Call function for all nodes in the tree, such that leaf nodes are
736 * called before parent nodes.
737 *
738 */
739 void
ldns_radix_traverse_postorder(ldns_radix_node_t * node,void (* func)(ldns_radix_node_t *,void *),void * arg)740 ldns_radix_traverse_postorder(ldns_radix_node_t* node,
741 void (*func)(ldns_radix_node_t*, void*), void* arg)
742 {
743 uint8_t i;
744 if (!node) {
745 return;
746 }
747 for (i=0; i < node->len; i++) {
748 ldns_radix_traverse_postorder(node->array[i].edge,
749 func, arg);
750 }
751 /** Call user function */
752 (*func)(node, arg);
753 return;
754 }
755
756
757 /** Static helper functions */
758
759 /**
760 * Find a prefix of the key.
761 * @param tree: tree.
762 * @param key: key.
763 * @param len: length of key.
764 * @param result: the longest prefix, the entry itself if *pos==len,
765 * otherwise an array entry.
766 * @param pos: position in string where next unmatched byte is.
767 * If *pos==len, an exact match is found.
768 * If *pos== 0, a "" match was found.
769 * @return 0 (false) if no prefix found.
770 *
771 */
772 static int
ldns_radix_find_prefix(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len,ldns_radix_node_t ** result,radix_strlen_t * respos)773 ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
774 radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos)
775 {
776 /** Start searching at the root node */
777 ldns_radix_node_t* n = tree->root;
778 radix_strlen_t pos = 0;
779 uint8_t byte;
780 *respos = 0;
781 *result = n;
782 if (!n) {
783 /** No root, no prefix found */
784 return 0;
785 }
786 /** For each node, look if we can make further progress */
787 while (n) {
788 if (pos == len) {
789 /** Exact match */
790 return 1;
791 }
792 byte = key[pos];
793 if (byte < n->offset) {
794 /** key < node */
795 return 1;
796 }
797 byte -= n->offset;
798 if (byte >= n->len) {
799 /** key > node */
800 return 1;
801 }
802 /** So far, the trie matches */
803 pos++;
804 if (n->array[byte].len != 0) {
805 /** Must match additional string */
806 if (pos + n->array[byte].len > len) {
807 return 1; /* no match at child node */
808 }
809 if (memcmp(&key[pos], n->array[byte].str,
810 n->array[byte].len) != 0) {
811 return 1; /* no match at child node */
812 }
813 pos += n->array[byte].len;
814 }
815 /** Continue searching prefix at this child node */
816 n = n->array[byte].edge;
817 if (!n) {
818 return 1;
819 }
820 /** Update the prefix node */
821 *respos = pos;
822 *result = n;
823 }
824 /** Done */
825 return 1;
826 }
827
828
829 /**
830 * Make space in the node's array for another byte.
831 * @param node: node.
832 * @param byte: byte.
833 * @return 1 if successful, 0 otherwise.
834 *
835 */
836 static int
ldns_radix_array_space(ldns_radix_node_t * node,uint8_t byte)837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
838 {
839 /** Is there an array? */
840 if (!node->array) {
841 assert(node->capacity == 0);
842 /** No array, create new array */
843 node->array = LDNS_MALLOC(ldns_radix_array_t);
844 if (!node->array) {
845 return 0;
846 }
847 memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
848 node->len = 1;
849 node->capacity = 1;
850 node->offset = byte;
851 return 1;
852 }
853 /** Array exist */
854 assert(node->array != NULL);
855 assert(node->capacity > 0);
856
857 if (node->len == 0) {
858 /** Unused array */
859 node->len = 1;
860 node->offset = byte;
861 } else if (byte < node->offset) {
862 /** Byte is below the offset */
863 uint8_t index;
864 uint16_t need = node->offset - byte;
865 /** Is there enough capacity? */
866 if (node->len + need > node->capacity) {
867 /** Not enough capacity, grow array */
868 if (!ldns_radix_array_grow(node,
869 (unsigned) (node->len + need))) {
870 return 0; /* failed to grow array */
871 }
872 }
873 /** Move items to the end */
874 memmove(&node->array[need], &node->array[0],
875 node->len*sizeof(ldns_radix_array_t));
876 /** Fix parent index */
877 for (index = 0; index < node->len; index++) {
878 if (node->array[index+need].edge) {
879 node->array[index+need].edge->parent_index =
880 index + need;
881 }
882 }
883 /** Zero the first */
884 memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));
885 node->len += need;
886 node->offset = byte;
887 } else if (byte - node->offset >= node->len) {
888 /** Byte does not fit in array */
889 uint16_t need = (byte - node->offset) - node->len + 1;
890 /** Is there enough capacity? */
891 if (node->len + need > node->capacity) {
892 /** Not enough capacity, grow array */
893 if (!ldns_radix_array_grow(node,
894 (unsigned) (node->len + need))) {
895 return 0; /* failed to grow array */
896 }
897 }
898 /** Zero the added items */
899 memset(&node->array[node->len], 0,
900 need*sizeof(ldns_radix_array_t));
901 node->len += need;
902 }
903 return 1;
904 }
905
906
907 /**
908 * Grow the array.
909 * @param node: node.
910 * @param need: number of elements the array at least need to grow.
911 * Can't be bigger than 256.
912 * @return: 0 if failed, 1 if was successful.
913 *
914 */
915 static int
ldns_radix_array_grow(ldns_radix_node_t * node,unsigned need)916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
917 {
918 unsigned size = ((unsigned)node->capacity)*2;
919 ldns_radix_array_t* a = NULL;
920 if (need > size) {
921 size = need;
922 }
923 if (size > 256) {
924 size = 256;
925 }
926 a = LDNS_XMALLOC(ldns_radix_array_t, size);
927 if (!a) {
928 return 0;
929 }
930 assert(node->len <= node->capacity);
931 assert(node->capacity < size);
932 memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));
933 LDNS_FREE(node->array);
934 node->array = a;
935 node->capacity = size;
936 return 1;
937 }
938
939
940 /**
941 * Create a prefix in the array string.
942 * @param array: array.
943 * @param key: key.
944 * @param pos: start position in key.
945 * @param len: length of key.
946 * @return 0 if failed, 1 if was successful.
947 *
948 */
949 static int
ldns_radix_str_create(ldns_radix_array_t * array,uint8_t * key,radix_strlen_t pos,radix_strlen_t len)950 ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
951 radix_strlen_t pos, radix_strlen_t len)
952 {
953 array->str = LDNS_XMALLOC(uint8_t, (len-pos));
954 if (!array->str) {
955 return 0;
956 }
957 memmove(array->str, key+pos, len-pos);
958 array->len = (len-pos);
959 return 1;
960 }
961
962
963 /**
964 * Allocate remainder from prefixes for a split.
965 * @param prefixlen: length of prefix.
966 * @param longer_str: the longer string.
967 * @param longer_len: the longer string length.
968 * @param split_str: the split string.
969 * @param split_len: the split string length.
970 * @return 0 if failed, 1 if successful.
971 *
972 */
973 static int
ldns_radix_prefix_remainder(radix_strlen_t prefix_len,uint8_t * longer_str,radix_strlen_t longer_len,uint8_t ** split_str,radix_strlen_t * split_len)974 ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
975 uint8_t* longer_str, radix_strlen_t longer_len,
976 uint8_t** split_str, radix_strlen_t* split_len)
977 {
978 *split_len = longer_len - prefix_len;
979 *split_str = LDNS_XMALLOC(uint8_t, (*split_len));
980 if (!*split_str) {
981 return 0;
982 }
983 memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len);
984 return 1;
985 }
986
987
988 /**
989 * Create a split when two nodes have a shared prefix.
990 * @param array: array.
991 * @param key: key.
992 * @param pos: start position in key.
993 * @param len: length of the key.
994 * @param add: node to be added.
995 * @return 0 if failed, 1 if was successful.
996 *
997 */
998 static int
ldns_radix_array_split(ldns_radix_array_t * array,uint8_t * key,radix_strlen_t pos,radix_strlen_t len,ldns_radix_node_t * add)999 ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
1000 radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add)
1001 {
1002 uint8_t* str_to_add = key + pos;
1003 radix_strlen_t strlen_to_add = len - pos;
1004
1005 if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add,
1006 array->str, array->len)) {
1007 /** The string to add is a prefix of the existing string */
1008 uint8_t* split_str = NULL, *dup_str = NULL;
1009 radix_strlen_t split_len = 0;
1010 /**
1011 * Example 5: 'ld'
1012 * | [0]
1013 * --| [d+ns] dns
1014 * --| [e+dns] edns
1015 * --| [l+d] ld
1016 * ----| [n+s] ldns
1017 **/
1018 assert(strlen_to_add < array->len);
1019 /** Store the remainder in the split string */
1020 if (array->len - strlen_to_add > 1) {
1021 if (!ldns_radix_prefix_remainder(strlen_to_add+1,
1022 array->str, array->len, &split_str,
1023 &split_len)) {
1024 return 0;
1025 }
1026 }
1027 /** Duplicate the string to add */
1028 if (strlen_to_add != 0) {
1029 dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add);
1030 if (!dup_str) {
1031 LDNS_FREE(split_str);
1032 return 0;
1033 }
1034 memcpy(dup_str, str_to_add, strlen_to_add);
1035 }
1036 /** Make space in array for the new node */
1037 if (!ldns_radix_array_space(add,
1038 array->str[strlen_to_add])) {
1039 LDNS_FREE(split_str);
1040 LDNS_FREE(dup_str);
1041 return 0;
1042 }
1043 /**
1044 * The added node should go direct under the existing parent.
1045 * The existing node should go under the added node.
1046 */
1047 add->parent = array->edge->parent;
1048 add->parent_index = array->edge->parent_index;
1049 add->array[0].edge = array->edge;
1050 add->array[0].str = split_str;
1051 add->array[0].len = split_len;
1052 array->edge->parent = add;
1053 array->edge->parent_index = 0;
1054 LDNS_FREE(array->str);
1055 array->edge = add;
1056 array->str = dup_str;
1057 array->len = strlen_to_add;
1058 } else if (ldns_radix_str_is_prefix(array->str, array->len,
1059 str_to_add, strlen_to_add)) {
1060 /** The existing string is a prefix of the string to add */
1061 /**
1062 * Example 6: 'dns-ng'
1063 * | [0]
1064 * --| [d+ns] dns
1065 * ----| [-+ng] dns-ng
1066 * --| [e+dns] edns
1067 * --| [l+d] ld
1068 * ----| [n+s] ldns
1069 **/
1070 uint8_t* split_str = NULL;
1071 radix_strlen_t split_len = 0;
1072 assert(array->len < strlen_to_add);
1073 if (strlen_to_add - array->len > 1) {
1074 if (!ldns_radix_prefix_remainder(array->len+1,
1075 str_to_add, strlen_to_add, &split_str,
1076 &split_len)) {
1077 return 0;
1078 }
1079 }
1080 /** Make space in array for the new node */
1081 if (!ldns_radix_array_space(array->edge,
1082 str_to_add[array->len])) {
1083 LDNS_FREE(split_str);
1084 return 0;
1085 }
1086 /**
1087 * The added node should go direct under the existing node.
1088 */
1089 add->parent = array->edge;
1090 add->parent_index = str_to_add[array->len] -
1091 array->edge->offset;
1092 array->edge->array[add->parent_index].edge = add;
1093 array->edge->array[add->parent_index].str = split_str;
1094 array->edge->array[add->parent_index].len = split_len;
1095 } else {
1096 /** Create a new split node. */
1097 /**
1098 * Example 7: 'dndns'
1099 * | [0]
1100 * --| [d+n]
1101 * ----| [d+ns] dndns
1102 * ----| [s] dns
1103 * ------| [-+ng] dns-ng
1104 * --| [e+dns] edns
1105 * --| [l+d] ld
1106 * ----| [n+s] ldns
1107 **/
1108 ldns_radix_node_t* common = NULL;
1109 uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL;
1110 radix_strlen_t common_len = 0, l1 = 0, l2 = 0;
1111 common_len = ldns_radix_str_common(array->str, array->len,
1112 str_to_add, strlen_to_add);
1113 assert(common_len < array->len);
1114 assert(common_len < strlen_to_add);
1115 /** Create the new common node. */
1116 common = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
1117 if (!common) {
1118 return 0;
1119 }
1120 if (array->len - common_len > 1) {
1121 if (!ldns_radix_prefix_remainder(common_len+1,
1122 array->str, array->len, &s1, &l1)) {
1123 return 0;
1124 }
1125 }
1126 if (strlen_to_add - common_len > 1) {
1127 if (!ldns_radix_prefix_remainder(common_len+1,
1128 str_to_add, strlen_to_add, &s2, &l2)) {
1129 return 0;
1130 }
1131 }
1132 /** Create the shared prefix. */
1133 if (common_len > 0) {
1134 common_str = LDNS_XMALLOC(uint8_t, common_len);
1135 if (!common_str) {
1136 LDNS_FREE(common);
1137 LDNS_FREE(s1);
1138 LDNS_FREE(s2);
1139 return 0;
1140 }
1141 memcpy(common_str, str_to_add, common_len);
1142 }
1143 /** Make space in the common node array. */
1144 if (!ldns_radix_array_space(common, array->str[common_len]) ||
1145 !ldns_radix_array_space(common, str_to_add[common_len])) {
1146 LDNS_FREE(common->array);
1147 LDNS_FREE(common);
1148 LDNS_FREE(common_str);
1149 LDNS_FREE(s1);
1150 LDNS_FREE(s2);
1151 return 0;
1152 }
1153 /**
1154 * The common node should go direct under the parent node.
1155 * The added and existing nodes go under the common node.
1156 */
1157 common->parent = array->edge->parent;
1158 common->parent_index = array->edge->parent_index;
1159 array->edge->parent = common;
1160 array->edge->parent_index = array->str[common_len] -
1161 common->offset;
1162 add->parent = common;
1163 add->parent_index = str_to_add[common_len] - common->offset;
1164 common->array[array->edge->parent_index].edge = array->edge;
1165 common->array[array->edge->parent_index].str = s1;
1166 common->array[array->edge->parent_index].len = l1;
1167 common->array[add->parent_index].edge = add;
1168 common->array[add->parent_index].str = s2;
1169 common->array[add->parent_index].len = l2;
1170 LDNS_FREE(array->str);
1171 array->edge = common;
1172 array->str = common_str;
1173 array->len = common_len;
1174 }
1175 return 1;
1176 }
1177
1178
1179 /**
1180 * Check if one string prefix of other string.
1181 * @param str1: one string.
1182 * @param len1: one string length.
1183 * @param str2: other string.
1184 * @param len2: other string length.
1185 * @return 1 if prefix, 0 otherwise.
1186 *
1187 */
1188 static int
ldns_radix_str_is_prefix(uint8_t * str1,radix_strlen_t len1,uint8_t * str2,radix_strlen_t len2)1189 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
1190 uint8_t* str2, radix_strlen_t len2)
1191 {
1192 if (len1 == 0) {
1193 return 1; /* empty prefix is also a prefix */
1194 }
1195 if (len1 > len2) {
1196 return 0; /* len1 is longer so str1 cannot be a prefix */
1197 }
1198 return (memcmp(str1, str2, len1) == 0);
1199 }
1200
1201
1202 /**
1203 * Return the number of bytes in common for the two strings.
1204 * @param str1: one string.
1205 * @param len1: one string length.
1206 * @param str2: other string.
1207 * @param len2: other string length.
1208 * @return length of substring that the two strings have in common.
1209 *
1210 */
1211 static radix_strlen_t
ldns_radix_str_common(uint8_t * str1,radix_strlen_t len1,uint8_t * str2,radix_strlen_t len2)1212 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
1213 uint8_t* str2, radix_strlen_t len2)
1214 {
1215 radix_strlen_t i, max = (len1<len2)?len1:len2;
1216 for (i=0; i<max; i++) {
1217 if (str1[i] != str2[i]) {
1218 return i;
1219 }
1220 }
1221 return max;
1222 }
1223
1224
1225 /**
1226 * Find the next element in the subtree of this node.
1227 * @param node: node.
1228 * @return: node with next element.
1229 *
1230 */
1231 static ldns_radix_node_t*
ldns_radix_next_in_subtree(ldns_radix_node_t * node)1232 ldns_radix_next_in_subtree(ldns_radix_node_t* node)
1233 {
1234 uint16_t i;
1235 ldns_radix_node_t* next;
1236 /** Try every subnode. */
1237 for (i = 0; i < node->len; i++) {
1238 if (node->array[i].edge) {
1239 /** Node itself. */
1240 if (node->array[i].edge->data) {
1241 return node->array[i].edge;
1242 }
1243 /** Dive into subtree. */
1244 next = ldns_radix_next_in_subtree(node->array[i].edge);
1245 if (next) {
1246 return next;
1247 }
1248 }
1249 }
1250 return NULL;
1251 }
1252
1253
1254 /**
1255 * Find the previous element in the array of this node, from index.
1256 * @param node: node.
1257 * @param index: index.
1258 * @return previous node from index.
1259 *
1260 */
1261 static ldns_radix_node_t*
ldns_radix_prev_from_index(ldns_radix_node_t * node,uint8_t index)1262 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
1263 {
1264 uint8_t i = index;
1265 while (i > 0) {
1266 i--;
1267 if (node->array[i].edge) {
1268 ldns_radix_node_t* prev =
1269 ldns_radix_last_in_subtree_incl_self(node);
1270 if (prev) {
1271 return prev;
1272 }
1273 }
1274 }
1275 return NULL;
1276 }
1277
1278
1279 /**
1280 * Find last node in subtree, or this node (if have data).
1281 * @param node: node.
1282 * @return last node in subtree, or this node, or NULL.
1283 *
1284 */
1285 static ldns_radix_node_t*
ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t * node)1286 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
1287 {
1288 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
1289 if (last) {
1290 return last;
1291 } else if (node->data) {
1292 return node;
1293 }
1294 return NULL;
1295 }
1296
1297
1298 /**
1299 * Find last node in subtree.
1300 * @param node: node.
1301 * @return last node in subtree.
1302 *
1303 */
1304 static ldns_radix_node_t*
ldns_radix_last_in_subtree(ldns_radix_node_t * node)1305 ldns_radix_last_in_subtree(ldns_radix_node_t* node)
1306 {
1307 int i;
1308 /** Look for the most right leaf node. */
1309 for (i=(int)(node->len)-1; i >= 0; i--) {
1310 if (node->array[i].edge) {
1311 /** Keep looking for the most right leaf node. */
1312 if (node->array[i].edge->len > 0) {
1313 ldns_radix_node_t* last =
1314 ldns_radix_last_in_subtree(
1315 node->array[i].edge);
1316 if (last) {
1317 return last;
1318 }
1319 }
1320 /** Could this be the most right leaf node? */
1321 if (node->array[i].edge->data) {
1322 return node->array[i].edge;
1323 }
1324 }
1325 }
1326 return NULL;
1327 }
1328
1329
1330 /**
1331 * Fix tree after deleting element.
1332 * @param tree: tree.
1333 * @param node: node with deleted element.
1334 *
1335 */
1336 static void
ldns_radix_del_fix(ldns_radix_t * tree,ldns_radix_node_t * node)1337 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
1338 {
1339 while (node) {
1340 if (node->data) {
1341 /** Thou should not delete nodes with data attached. */
1342 return;
1343 } else if (node->len == 1 && node->parent) {
1344 /** Node with one child is fold back into. */
1345 ldns_radix_cleanup_onechild(node);
1346 return;
1347 } else if (node->len == 0) {
1348 /** Leaf node. */
1349 ldns_radix_node_t* parent = node->parent;
1350 if (!parent) {
1351 /** The root is a leaf node. */
1352 ldns_radix_node_free(node, NULL);
1353 tree->root = NULL;
1354 return;
1355 }
1356 /** Cleanup leaf node and continue with parent. */
1357 ldns_radix_cleanup_leaf(node);
1358 node = parent;
1359 } else {
1360 /**
1361 * Node cannot be deleted, because it has edge nodes
1362 * and no parent to fix up to.
1363 */
1364 return;
1365 }
1366 }
1367 /** Not reached. */
1368 return;
1369 }
1370
1371
1372 /**
1373 * Clean up a node with one child.
1374 * @param node: node with one child.
1375 *
1376 */
1377 static void
ldns_radix_cleanup_onechild(ldns_radix_node_t * node)1378 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
1379 {
1380 uint8_t* join_str;
1381 radix_strlen_t join_len;
1382 uint8_t parent_index = node->parent_index;
1383 ldns_radix_node_t* child = node->array[0].edge;
1384 ldns_radix_node_t* parent = node->parent;
1385
1386 /** Node has one child, merge the child node into the parent node. */
1387 assert(parent_index < parent->len);
1388 join_len = parent->array[parent_index].len + node->array[0].len + 1;
1389
1390 join_str = LDNS_XMALLOC(uint8_t, join_len);
1391 if (!join_str) {
1392 /**
1393 * Cleanup failed due to out of memory.
1394 * This tree is now inefficient, with the empty node still
1395 * existing, but it is still valid.
1396 */
1397 return;
1398 }
1399
1400 memcpy(join_str, parent->array[parent_index].str,
1401 parent->array[parent_index].len);
1402 join_str[parent->array[parent_index].len] = child->parent_index +
1403 node->offset;
1404 memmove(join_str + parent->array[parent_index].len+1,
1405 node->array[0].str, node->array[0].len);
1406
1407 LDNS_FREE(parent->array[parent_index].str);
1408 parent->array[parent_index].str = join_str;
1409 parent->array[parent_index].len = join_len;
1410 parent->array[parent_index].edge = child;
1411 child->parent = parent;
1412 child->parent_index = parent_index;
1413 ldns_radix_node_free(node, NULL);
1414 return;
1415 }
1416
1417
1418 /**
1419 * Clean up a leaf node.
1420 * @param node: leaf node.
1421 *
1422 */
1423 static void
ldns_radix_cleanup_leaf(ldns_radix_node_t * node)1424 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
1425 {
1426 uint8_t parent_index = node->parent_index;
1427 ldns_radix_node_t* parent = node->parent;
1428 /** Delete lead node and fix parent array. */
1429 assert(parent_index < parent->len);
1430 ldns_radix_node_free(node, NULL);
1431 LDNS_FREE(parent->array[parent_index].str);
1432 parent->array[parent_index].str = NULL;
1433 parent->array[parent_index].len = 0;
1434 parent->array[parent_index].edge = NULL;
1435 /** Fix array in parent. */
1436 if (parent->len == 1) {
1437 ldns_radix_node_array_free(parent);
1438 } else if (parent_index == 0) {
1439 ldns_radix_node_array_free_front(parent);
1440 } else {
1441 ldns_radix_node_array_free_end(parent);
1442 }
1443 return;
1444 }
1445
1446
1447 /**
1448 * Free a radix node.
1449 * @param node: node.
1450 * @param arg: user argument.
1451 *
1452 */
1453 static void
ldns_radix_node_free(ldns_radix_node_t * node,void * arg)1454 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
1455 {
1456 uint16_t i;
1457 (void) arg;
1458 if (!node) {
1459 return;
1460 }
1461 for (i=0; i < node->len; i++) {
1462 LDNS_FREE(node->array[i].str);
1463 }
1464 node->key = NULL;
1465 node->klen = 0;
1466 LDNS_FREE(node->array);
1467 LDNS_FREE(node);
1468 return;
1469 }
1470
1471
1472 /**
1473 * Free select edge array.
1474 * @param node: node.
1475 *
1476 */
1477 static void
ldns_radix_node_array_free(ldns_radix_node_t * node)1478 ldns_radix_node_array_free(ldns_radix_node_t* node)
1479 {
1480 node->offset = 0;
1481 node->len = 0;
1482 LDNS_FREE(node->array);
1483 node->array = NULL;
1484 node->capacity = 0;
1485 return;
1486 }
1487
1488
1489 /**
1490 * Free front of select edge array.
1491 * @param node: node.
1492 *
1493 */
1494 static void
ldns_radix_node_array_free_front(ldns_radix_node_t * node)1495 ldns_radix_node_array_free_front(ldns_radix_node_t* node)
1496 {
1497 uint16_t i, n = 0;
1498 /** Remove until a non NULL entry. */
1499 while (n < node->len && node->array[n].edge == NULL) {
1500 n++;
1501 }
1502 if (n == 0) {
1503 return;
1504 }
1505 if (n == node->len) {
1506 ldns_radix_node_array_free(node);
1507 return;
1508 }
1509 assert(n < node->len);
1510 assert((int) n <= (255 - (int) node->offset));
1511 memmove(&node->array[0], &node->array[n],
1512 (node->len - n)*sizeof(ldns_radix_array_t));
1513 node->offset += n;
1514 node->len -= n;
1515 for (i=0; i < node->len; i++) {
1516 if (node->array[i].edge) {
1517 node->array[i].edge->parent_index = i;
1518 }
1519 }
1520 ldns_radix_array_reduce(node);
1521 return;
1522 }
1523
1524
1525 /**
1526 * Free front of select edge array.
1527 * @param node: node.
1528 *
1529 */
1530 static void
ldns_radix_node_array_free_end(ldns_radix_node_t * node)1531 ldns_radix_node_array_free_end(ldns_radix_node_t* node)
1532 {
1533 uint16_t n = 0;
1534 /** Shorten array. */
1535 while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1536 n++;
1537 }
1538 if (n == 0) {
1539 return;
1540 }
1541 if (n == node->len) {
1542 ldns_radix_node_array_free(node);
1543 return;
1544 }
1545 assert(n < node->len);
1546 node->len -= n;
1547 ldns_radix_array_reduce(node);
1548 return;
1549 }
1550
1551
1552 /**
1553 * Reduce the capacity of the array if needed.
1554 * @param node: node.
1555 *
1556 */
1557 static void
ldns_radix_array_reduce(ldns_radix_node_t * node)1558 ldns_radix_array_reduce(ldns_radix_node_t* node)
1559 {
1560 if (node->len <= node->capacity/2 && node->len != node->capacity) {
1561 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
1562 node->len);
1563 if (!a) {
1564 return;
1565 }
1566 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
1567 LDNS_FREE(node->array);
1568 node->array = a;
1569 node->capacity = node->len;
1570 }
1571 return;
1572 }
1573
1574
1575 /**
1576 * Return this element if it exists, the previous otherwise.
1577 * @param node: from this node.
1578 * @param result: result node.
1579 *
1580 */
1581 static void
ldns_radix_self_or_prev(ldns_radix_node_t * node,ldns_radix_node_t ** result)1582 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
1583 {
1584 if (node->data) {
1585 *result = node;
1586 } else {
1587 *result = ldns_radix_prev(node);
1588 }
1589 return;
1590 }
1591