radix.c
Go to the documentation of this file.
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
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 */
38
44#include <ldns/config.h>
45#include <ldns/radix.h>
46#include <ldns/util.h>
47#include <stdlib.h>
48
50static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
51 radix_strlen_t len);
52static 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);
54static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte);
55static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need);
56static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
57 radix_strlen_t pos, radix_strlen_t len);
58static 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);
61static 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);
63static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
64 uint8_t* str2, radix_strlen_t len2);
65static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
66 uint8_t* str2, radix_strlen_t len2);
67static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node);
68static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node,
69 uint8_t index);
70static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self(
71 ldns_radix_node_t* node);
72static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node);
73static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node);
74static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node);
75static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node);
76static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg);
77static void ldns_radix_node_array_free(ldns_radix_node_t* node);
78static void ldns_radix_node_array_free_front(ldns_radix_node_t* node);
79static void ldns_radix_node_array_free_end(ldns_radix_node_t* node);
80static void ldns_radix_array_reduce(ldns_radix_node_t* node);
81static void ldns_radix_self_or_prev(ldns_radix_node_t* node,
82 ldns_radix_node_t** result);
83
84
89static ldns_radix_node_t*
90ldns_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
113ldns_radix_t *
114ldns_radix_create(void)
115{
116 ldns_radix_t* tree;
117
119 tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
120 if (!tree) {
121 return NULL;
122 }
124 ldns_radix_init(tree);
125 return tree;
126}
127
128
133void
134ldns_radix_init(ldns_radix_t* tree)
135{
137 if (tree) {
138 tree->root = NULL;
139 tree->count = 0;
140 }
141 return;
142}
143
144
149void
150ldns_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
167ldns_status
168ldns_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 }
183 if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
185 assert(tree->root == NULL);
186 if (len == 0) {
191 tree->root = add;
192 } else {
197 prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
198 if (!prefix) {
199 LDNS_FREE(add);
200 return LDNS_STATUS_MEM_ERR;
201 }
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 }
210 add->parent = prefix;
211 add->parent_index = 0;
212 prefix->array[0].edge = add;
213 if (len > 1) {
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) {
228 LDNS_FREE(add);
229 if (prefix->data) {
230 /* Element already exists */
231 return LDNS_STATUS_EXISTS_ERR;
232 }
233 prefix->data = data;
234 prefix->key = key;
235 prefix->klen = len; /* redundant */
236 } else {
238 uint8_t byte = key[pos];
239 assert(pos < len);
240 if (byte < prefix->offset ||
241 (byte - prefix->offset) >= prefix->len) {
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) {
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 }
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) {
278 byte -= prefix->offset;
279 if (pos+1 < len) {
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 }
289 add->parent = prefix;
290 add->parent_index = byte;
291 prefix->array[byte].edge = add;
292 } else {
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
314void* ldns_radix_delete(ldns_radix_t* tree, const 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
333ldns_radix_node_t*
334ldns_radix_search(ldns_radix_t* tree, const 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) {
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
379int
380ldns_radix_find_less_equal(ldns_radix_t* tree, const 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) {
401 ldns_radix_self_or_prev(node, result);
402 return 0;
403 }
404 byte -= node->offset;
405 if (byte >= node->len) {
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) {
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) {
430 if (pos + node->array[byte].len > len) {
432 if (memcmp(&key[pos], node->array[byte].str,
433 len-pos) <= 0) {
435 *result = ldns_radix_prev(
436 node->array[byte].edge);
437 } else {
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) {
466 *result = node;
467 return 1;
468 }
470 *result = ldns_radix_prev(node);
471 return 0;
472}
473
474
479ldns_radix_node_t*
480ldns_radix_first(const 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
498ldns_radix_node_t*
499ldns_radix_last(const 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
512ldns_radix_node_t*
513ldns_radix_next(ldns_radix_node_t* node)
514{
515 if (!node) {
516 return NULL;
517 }
518 if (node->len) {
520 ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
521 if (next) {
522 return next;
523 }
524 }
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;
534 if (node->array[index].edge->data) {
535 return node->array[index].edge;
536 }
538 next = ldns_radix_next_in_subtree(node);
539 if (next) {
540 return next;
541 }
542 }
543 }
544 }
545 return NULL;
546}
547
548
553ldns_radix_node_t*
554ldns_radix_prev(ldns_radix_node_t* node)
555{
556 if (!node) {
557 return NULL;
558 }
559
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
582static void
583ldns_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
623void
624ldns_radix_printf(FILE* fd, const 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
642ldns_status
643ldns_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 }
652 cur_node = ldns_radix_first(tree2);
653 while (cur_node) {
654 status = LDNS_STATUS_NO_DATA;
656 if (cur_node->data) {
657 status = ldns_radix_insert(tree1, cur_node->key,
658 cur_node->klen, cur_node->data);
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
681ldns_status
682ldns_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) {
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);
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*/
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
739void
740ldns_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 }
752 (*func)(node, arg);
753 return;
754}
755
756
772static int
773ldns_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{
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) {
784 return 0;
785 }
787 while (n) {
788 if (pos == len) {
790 return 1;
791 }
792 byte = key[pos];
793 if (byte < n->offset) {
795 return 1;
796 }
797 byte -= n->offset;
798 if (byte >= n->len) {
800 return 1;
801 }
803 pos++;
804 if (n->array[byte].len != 0) {
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 }
816 n = n->array[byte].edge;
817 if (!n) {
818 return 1;
819 }
821 *respos = pos;
822 *result = n;
823 }
825 return 1;
826}
827
828
836static int
837ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
838{
840 if (!node->array) {
841 assert(node->capacity == 0);
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 }
854 assert(node->array != NULL);
855 assert(node->capacity > 0);
856
857 if (node->len == 0) {
859 node->len = 1;
860 node->offset = byte;
861 } else if (byte < node->offset) {
863 uint8_t index;
864 uint16_t need = node->offset - byte;
866 if (node->len + need > node->capacity) {
868 if (!ldns_radix_array_grow(node,
869 (unsigned) (node->len + need))) {
870 return 0; /* failed to grow array */
871 }
872 }
874 memmove(&node->array[need], &node->array[0],
875 node->len*sizeof(ldns_radix_array_t));
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 }
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) {
889 uint16_t need = (byte - node->offset) - node->len + 1;
891 if (node->len + need > node->capacity) {
893 if (!ldns_radix_array_grow(node,
894 (unsigned) (node->len + need))) {
895 return 0; /* failed to grow array */
896 }
897 }
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
915static int
916ldns_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
949static int
950ldns_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
973static int
974ldns_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
998static int
999ldns_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)) {
1008 uint8_t* split_str = NULL, *dup_str = NULL;
1009 radix_strlen_t split_len = 0;
1018 assert(strlen_to_add < array->len);
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 }
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 }
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 }
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)) {
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 }
1081 if (!ldns_radix_array_space(array->edge,
1082 str_to_add[array->len])) {
1083 LDNS_FREE(split_str);
1084 return 0;
1085 }
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 {
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);
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 LDNS_FREE(common);
1124 return 0;
1125 }
1126 }
1127 if (strlen_to_add - common_len > 1) {
1128 if (!ldns_radix_prefix_remainder(common_len+1,
1129 str_to_add, strlen_to_add, &s2, &l2)) {
1130 LDNS_FREE(common);
1131 LDNS_FREE(s1);
1132 return 0;
1133 }
1134 }
1136 if (common_len > 0) {
1137 common_str = LDNS_XMALLOC(uint8_t, common_len);
1138 if (!common_str) {
1139 LDNS_FREE(common);
1140 LDNS_FREE(s1);
1141 LDNS_FREE(s2);
1142 return 0;
1143 }
1144 memcpy(common_str, str_to_add, common_len);
1145 }
1147 if (!ldns_radix_array_space(common, array->str[common_len]) ||
1148 !ldns_radix_array_space(common, str_to_add[common_len])) {
1149 LDNS_FREE(common->array);
1150 LDNS_FREE(common);
1151 LDNS_FREE(common_str);
1152 LDNS_FREE(s1);
1153 LDNS_FREE(s2);
1154 return 0;
1155 }
1160 common->parent = array->edge->parent;
1161 common->parent_index = array->edge->parent_index;
1162 array->edge->parent = common;
1163 array->edge->parent_index = array->str[common_len] -
1164 common->offset;
1165 add->parent = common;
1166 add->parent_index = str_to_add[common_len] - common->offset;
1167 common->array[array->edge->parent_index].edge = array->edge;
1168 common->array[array->edge->parent_index].str = s1;
1169 common->array[array->edge->parent_index].len = l1;
1170 common->array[add->parent_index].edge = add;
1171 common->array[add->parent_index].str = s2;
1172 common->array[add->parent_index].len = l2;
1173 LDNS_FREE(array->str);
1174 array->edge = common;
1175 array->str = common_str;
1176 array->len = common_len;
1177 }
1178 return 1;
1179}
1180
1181
1191static int
1192ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
1193 uint8_t* str2, radix_strlen_t len2)
1194{
1195 if (len1 == 0) {
1196 return 1; /* empty prefix is also a prefix */
1197 }
1198 if (len1 > len2) {
1199 return 0; /* len1 is longer so str1 cannot be a prefix */
1200 }
1201 return (memcmp(str1, str2, len1) == 0);
1202}
1203
1204
1214static radix_strlen_t
1215ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
1216 uint8_t* str2, radix_strlen_t len2)
1217{
1218 radix_strlen_t i, max = (len1<len2)?len1:len2;
1219 for (i=0; i<max; i++) {
1220 if (str1[i] != str2[i]) {
1221 return i;
1222 }
1223 }
1224 return max;
1225}
1226
1227
1234static ldns_radix_node_t*
1235ldns_radix_next_in_subtree(ldns_radix_node_t* node)
1236{
1237 uint16_t i;
1238 ldns_radix_node_t* next;
1240 for (i = 0; i < node->len; i++) {
1241 if (node->array[i].edge) {
1243 if (node->array[i].edge->data) {
1244 return node->array[i].edge;
1245 }
1247 next = ldns_radix_next_in_subtree(node->array[i].edge);
1248 if (next) {
1249 return next;
1250 }
1251 }
1252 }
1253 return NULL;
1254}
1255
1256
1264static ldns_radix_node_t*
1265ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
1266{
1267 uint8_t i = index;
1268 while (i > 0) {
1269 i--;
1270 if (node->array[i].edge) {
1271 ldns_radix_node_t* prev =
1272 ldns_radix_last_in_subtree_incl_self(node);
1273 if (prev) {
1274 return prev;
1275 }
1276 }
1277 }
1278 return NULL;
1279}
1280
1281
1288static ldns_radix_node_t*
1289ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
1290{
1291 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
1292 if (last) {
1293 return last;
1294 } else if (node->data) {
1295 return node;
1296 }
1297 return NULL;
1298}
1299
1300
1307static ldns_radix_node_t*
1308ldns_radix_last_in_subtree(ldns_radix_node_t* node)
1309{
1310 int i;
1312 for (i=(int)(node->len)-1; i >= 0; i--) {
1313 if (node->array[i].edge) {
1315 if (node->array[i].edge->len > 0) {
1316 ldns_radix_node_t* last =
1317 ldns_radix_last_in_subtree(
1318 node->array[i].edge);
1319 if (last) {
1320 return last;
1321 }
1322 }
1324 if (node->array[i].edge->data) {
1325 return node->array[i].edge;
1326 }
1327 }
1328 }
1329 return NULL;
1330}
1331
1332
1339static void
1340ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
1341{
1342 while (node) {
1343 if (node->data) {
1345 return;
1346 } else if (node->len == 1 && node->parent) {
1348 ldns_radix_cleanup_onechild(node);
1349 return;
1350 } else if (node->len == 0) {
1352 ldns_radix_node_t* parent = node->parent;
1353 if (!parent) {
1355 ldns_radix_node_free(node, NULL);
1356 tree->root = NULL;
1357 return;
1358 }
1360 ldns_radix_cleanup_leaf(node);
1361 node = parent;
1362 } else {
1367 return;
1368 }
1369 }
1371 return;
1372}
1373
1374
1380static void
1381ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
1382{
1383 uint8_t* join_str;
1384 radix_strlen_t join_len;
1385 uint8_t parent_index = node->parent_index;
1386 ldns_radix_node_t* child = node->array[0].edge;
1387 ldns_radix_node_t* parent = node->parent;
1388
1390 assert(parent_index < parent->len);
1391 join_len = parent->array[parent_index].len + node->array[0].len + 1;
1392
1393 join_str = LDNS_XMALLOC(uint8_t, join_len);
1394 if (!join_str) {
1400 return;
1401 }
1402
1403 memcpy(join_str, parent->array[parent_index].str,
1404 parent->array[parent_index].len);
1405 join_str[parent->array[parent_index].len] = child->parent_index +
1406 node->offset;
1407 memmove(join_str + parent->array[parent_index].len+1,
1408 node->array[0].str, node->array[0].len);
1409
1410 LDNS_FREE(parent->array[parent_index].str);
1411 parent->array[parent_index].str = join_str;
1412 parent->array[parent_index].len = join_len;
1413 parent->array[parent_index].edge = child;
1414 child->parent = parent;
1415 child->parent_index = parent_index;
1416 ldns_radix_node_free(node, NULL);
1417 return;
1418}
1419
1420
1426static void
1427ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
1428{
1429 uint8_t parent_index = node->parent_index;
1430 ldns_radix_node_t* parent = node->parent;
1432 assert(parent_index < parent->len);
1433 ldns_radix_node_free(node, NULL);
1434 LDNS_FREE(parent->array[parent_index].str);
1435 parent->array[parent_index].str = NULL;
1436 parent->array[parent_index].len = 0;
1437 parent->array[parent_index].edge = NULL;
1439 if (parent->len == 1) {
1440 ldns_radix_node_array_free(parent);
1441 } else if (parent_index == 0) {
1442 ldns_radix_node_array_free_front(parent);
1443 } else {
1444 ldns_radix_node_array_free_end(parent);
1445 }
1446 return;
1447}
1448
1449
1456static void
1457ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
1458{
1459 uint16_t i;
1460 (void) arg;
1461 if (!node) {
1462 return;
1463 }
1464 for (i=0; i < node->len; i++) {
1465 LDNS_FREE(node->array[i].str);
1466 }
1467 node->key = NULL;
1468 node->klen = 0;
1469 LDNS_FREE(node->array);
1470 LDNS_FREE(node);
1471 return;
1472}
1473
1474
1480static void
1481ldns_radix_node_array_free(ldns_radix_node_t* node)
1482{
1483 node->offset = 0;
1484 node->len = 0;
1485 LDNS_FREE(node->array);
1486 node->array = NULL;
1487 node->capacity = 0;
1488 return;
1489}
1490
1491
1497static void
1498ldns_radix_node_array_free_front(ldns_radix_node_t* node)
1499{
1500 uint16_t i, n = 0;
1502 while (n < node->len && node->array[n].edge == NULL) {
1503 n++;
1504 }
1505 if (n == 0) {
1506 return;
1507 }
1508 if (n == node->len) {
1509 ldns_radix_node_array_free(node);
1510 return;
1511 }
1512 assert(n < node->len);
1513 assert((int) n <= (255 - (int) node->offset));
1514 memmove(&node->array[0], &node->array[n],
1515 (node->len - n)*sizeof(ldns_radix_array_t));
1516 node->offset += n;
1517 node->len -= n;
1518 for (i=0; i < node->len; i++) {
1519 if (node->array[i].edge) {
1520 node->array[i].edge->parent_index = i;
1521 }
1522 }
1523 ldns_radix_array_reduce(node);
1524 return;
1525}
1526
1527
1533static void
1534ldns_radix_node_array_free_end(ldns_radix_node_t* node)
1535{
1536 uint16_t n = 0;
1538 while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1539 n++;
1540 }
1541 if (n == 0) {
1542 return;
1543 }
1544 if (n == node->len) {
1545 ldns_radix_node_array_free(node);
1546 return;
1547 }
1548 assert(n < node->len);
1549 node->len -= n;
1550 ldns_radix_array_reduce(node);
1551 return;
1552}
1553
1554
1560static void
1561ldns_radix_array_reduce(ldns_radix_node_t* node)
1562{
1563 if (node->len <= node->capacity/2 && node->len != node->capacity) {
1564 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
1565 node->len);
1566 if (!a) {
1567 return;
1568 }
1569 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
1570 LDNS_FREE(node->array);
1571 node->array = a;
1572 node->capacity = node->len;
1573 }
1574 return;
1575}
1576
1577
1584static void
1585ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
1586{
1587 if (node->data) {
1588 *result = node;
1589 } else {
1590 *result = ldns_radix_prev(node);
1591 }
1592 return;
1593}
LDNS_STATUS_EXISTS_ERR
@ LDNS_STATUS_EXISTS_ERR
Definition error.h:121
LDNS_STATUS_NO_DATA
@ LDNS_STATUS_NO_DATA
Definition error.h:77
LDNS_STATUS_NULL
@ LDNS_STATUS_NULL
Definition error.h:51
LDNS_STATUS_MEM_ERR
@ LDNS_STATUS_MEM_ERR
Definition error.h:34
LDNS_STATUS_OK
@ LDNS_STATUS_OK
Definition error.h:26
ldns_status
enum ldns_enum_status ldns_status
Definition error.h:148
ldns_radix_create
ldns_radix_t * ldns_radix_create(void)
Create a new radix tree.
Definition radix.c:114
ldns_radix_init
void ldns_radix_init(ldns_radix_t *tree)
Initialize radix tree.
Definition radix.c:134
ldns_radix_next
ldns_radix_node_t * ldns_radix_next(ldns_radix_node_t *node)
Next element.
Definition radix.c:513
ldns_radix_traverse_postorder
void ldns_radix_traverse_postorder(ldns_radix_node_t *node, void(*func)(ldns_radix_node_t *, void *), void *arg)
Call function for all nodes in the tree, such that leaf nodes are called before parent nodes.
Definition radix.c:740
ldns_radix_join
ldns_status ldns_radix_join(ldns_radix_t *tree1, ldns_radix_t *tree2)
Join two radix trees.
Definition radix.c:643
ldns_radix_first
ldns_radix_node_t * ldns_radix_first(const ldns_radix_t *tree)
Get the first element in the tree.
Definition radix.c:480
ldns_radix_delete
void * ldns_radix_delete(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Delete data from the tree.
Definition radix.c:314
ldns_radix_free
void ldns_radix_free(ldns_radix_t *tree)
Free radix tree.
Definition radix.c:150
ldns_radix_split
ldns_status ldns_radix_split(ldns_radix_t *tree1, size_t num, ldns_radix_t **tree2)
Split a radix tree intwo.
Definition radix.c:682
ldns_radix_search
ldns_radix_node_t * ldns_radix_search(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Search data in the tree.
Definition radix.c:334
ldns_radix_last
ldns_radix_node_t * ldns_radix_last(const ldns_radix_t *tree)
Get the last element in the tree.
Definition radix.c:499
ldns_radix_insert
ldns_status ldns_radix_insert(ldns_radix_t *tree, uint8_t *key, radix_strlen_t len, void *data)
Insert data into the tree.
Definition radix.c:168
ldns_radix_find_less_equal
int ldns_radix_find_less_equal(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len, ldns_radix_node_t **result)
Search data in the tree, and if not found, find the closest smaller element in the tree.
Definition radix.c:380
ldns_radix_printf
void ldns_radix_printf(FILE *fd, const ldns_radix_t *tree)
Print radix tree.
Definition radix.c:624
ldns_radix_prev
ldns_radix_node_t * ldns_radix_prev(ldns_radix_node_t *node)
Previous element.
Definition radix.c:554
radix.h
Radix tree.
radix_strlen_t
uint16_t radix_strlen_t
Definition radix.h:52
ldns_radix_array_t
Radix node select edge array.
Definition radix.h:58
ldns_radix_array_t::edge
ldns_radix_node_t * edge
Node that deals with byte+str.
Definition radix.h:64
ldns_radix_array_t::len
radix_strlen_t len
Length of additional string for this edge.
Definition radix.h:62
ldns_radix_array_t::str
uint8_t * str
Additional string after the selection byte for this edge.
Definition radix.h:60
ldns_radix_node_t
A node in a radix tree.
Definition radix.h:68
ldns_radix_node_t::parent
ldns_radix_node_t * parent
Parent node.
Definition radix.h:76
ldns_radix_node_t::offset
uint16_t offset
Offset of the array.
Definition radix.h:82
ldns_radix_node_t::klen
radix_strlen_t klen
Key length corresponding to this node.
Definition radix.h:72
ldns_radix_node_t::array
ldns_radix_array_t * array
Select edge array.
Definition radix.h:86
ldns_radix_node_t::len
uint16_t len
Length of the array.
Definition radix.h:80
ldns_radix_node_t::capacity
uint16_t capacity
Capacity of the array.
Definition radix.h:84
ldns_radix_node_t::data
void * data
Data corresponding to this node.
Definition radix.h:74
ldns_radix_node_t::parent_index
uint8_t parent_index
Index in the parent node select edge array.
Definition radix.h:78
ldns_radix_node_t::key
uint8_t * key
Key corresponding to this node.
Definition radix.h:70
ldns_radix_t
An entire radix tree.
Definition radix.h:90
ldns_radix_t::root
ldns_radix_node_t * root
Root.
Definition radix.h:92
ldns_radix_t::count
size_t count
Number of nodes in tree.
Definition radix.h:94
LDNS_FREE
#define LDNS_FREE(ptr)
Definition util.h:60
LDNS_MALLOC
#define LDNS_MALLOC(type)
Memory management macros.
Definition util.h:49
LDNS_XMALLOC
#define LDNS_XMALLOC(type, count)
Definition util.h:51