2 * radix.c -- generic radix tree
4 * Taken from NSD4, modified for ldns
6 * Copyright (c) 2012, NLnet Labs. All rights reserved.
8 * This software is open source.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
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.
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.
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.
41 * Implementation of a radix tree.
44 #include <ldns/config.h>
45 #include <ldns/radix.h>
46 #include <ldns/util.h>
49 /** Helper functions */
50 static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
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,
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);
86 * Create a new radix node.
89 static ldns_radix_node_t*
90 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
92 ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
100 node->parent_index = 0;
110 * Create a new radix tree.
114 ldns_radix_create(void)
118 /** Allocate memory for it */
119 tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
124 ldns_radix_init(tree);
130 * Initialize radix tree.
134 ldns_radix_init(ldns_radix_t* tree)
150 ldns_radix_free(ldns_radix_t* tree)
154 ldns_radix_traverse_postorder(tree->root,
155 ldns_radix_node_free, NULL);
164 * Insert data into the tree.
168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
171 radix_strlen_t pos = 0;
172 ldns_radix_node_t* add = NULL;
173 ldns_radix_node_t* prefix = NULL;
175 if (!tree || !key || !data) {
176 return LDNS_STATUS_NULL;
178 add = ldns_radix_new_node(data, key, len);
180 return LDNS_STATUS_MEM_ERR;
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);
188 * Example 1: The root:
193 /** Example 2: 'dns':
197 prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
200 return LDNS_STATUS_MEM_ERR;
202 /** Find some space in the array for the first byte */
203 if (!ldns_radix_array_space(prefix, key[0])) {
205 LDNS_FREE(prefix->array);
207 return LDNS_STATUS_MEM_ERR;
209 /** Set relational pointers */
210 add->parent = prefix;
211 add->parent_index = 0;
212 prefix->array[0].edge = add;
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)) {
219 LDNS_FREE(prefix->array);
221 return LDNS_STATUS_MEM_ERR;
226 } else if (pos == len) {
227 /** Exact match found */
229 /* Element already exists */
231 return LDNS_STATUS_EXISTS_ERR;
235 prefix->klen = len; /* redundant */
238 uint8_t byte = key[pos];
240 if (byte < prefix->offset ||
241 (byte - prefix->offset) >= prefix->len) {
242 /** Find some space in the array for the byte. */
249 if (!ldns_radix_array_space(prefix, byte)) {
251 return LDNS_STATUS_MEM_ERR;
253 assert(byte >= prefix->offset);
254 assert((byte - prefix->offset) <= prefix->len);
255 byte -= prefix->offset;
257 /** Create remainder of the string. */
258 if (!ldns_radix_str_create(
259 &prefix->array[byte], key, pos+1,
262 return LDNS_STATUS_MEM_ERR;
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. */
278 byte -= prefix->offset;
280 /** Create remainder of the string. */
281 if (!ldns_radix_str_create(
282 &prefix->array[byte], key, pos+1,
285 return LDNS_STATUS_MEM_ERR;
289 add->parent = prefix;
290 add->parent_index = byte;
291 prefix->array[byte].edge = add;
294 * Use existing element, but it has a shared prefix,
297 if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)],
298 key, pos+1, len, add)) {
300 return LDNS_STATUS_MEM_ERR;
306 return LDNS_STATUS_OK;
311 * Delete data from the tree.
314 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
316 ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
322 ldns_radix_del_fix(tree, del);
330 * Search data in the tree.
334 ldns_radix_search(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
336 ldns_radix_node_t* node = NULL;
337 radix_strlen_t pos = 0;
346 return node->data?node:NULL;
349 if (byte < node->offset) {
352 byte -= node->offset;
353 if (byte >= node->len) {
357 if (node->array[byte].len > 0) {
358 /** Must match additional string. */
359 if (pos + node->array[byte].len > len) {
362 if (memcmp(&key[pos], node->array[byte].str,
363 node->array[byte].len) != 0) {
366 pos += node->array[byte].len;
368 node = node->array[byte].edge;
375 * Search data in the tree, and if not found, find the closest smaller
376 * element in the tree.
380 ldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key,
381 radix_strlen_t len, ldns_radix_node_t** result)
383 ldns_radix_node_t* node = NULL;
384 radix_strlen_t pos = 0;
388 if (!tree || !tree->root || !key) {
396 if (byte < node->offset) {
398 * No exact match. The lesser is in this or the
401 ldns_radix_self_or_prev(node, result);
404 byte -= node->offset;
405 if (byte >= node->len) {
407 * No exact match. The lesser is in this node or the
408 * last of this array, or something before this node.
410 *result = ldns_radix_last_in_subtree_incl_self(node);
411 if (*result == NULL) {
412 *result = ldns_radix_prev(node);
417 if (!node->array[byte].edge) {
419 * No exact match. Find the previous in the array
422 *result = ldns_radix_prev_from_index(node, byte);
423 if (*result == NULL) {
424 ldns_radix_self_or_prev(node, result);
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,
434 /** Key is before this node. */
435 *result = ldns_radix_prev(
436 node->array[byte].edge);
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);
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);
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);
460 pos += node->array[byte].len;
462 node = node->array[byte].edge;
469 /** There is a node which is an exact match, but has no element. */
470 *result = ldns_radix_prev(node);
476 * Get the first element in the tree.
480 ldns_radix_first(ldns_radix_t* tree)
482 ldns_radix_node_t* first = NULL;
483 if (!tree || !tree->root) {
490 return ldns_radix_next(first);
495 * Get the last element in the tree.
499 ldns_radix_last(ldns_radix_t* tree)
501 if (!tree || !tree->root) {
504 return ldns_radix_last_in_subtree_incl_self(tree->root);
513 ldns_radix_next(ldns_radix_node_t* node)
519 /** Go down: most-left child is the next. */
520 ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
525 /** No elements in subtree, get to parent and go down next branch. */
526 while (node->parent) {
527 uint8_t index = node->parent_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;
537 /** Dive into subtree. */
538 next = ldns_radix_next_in_subtree(node);
554 ldns_radix_prev(ldns_radix_node_t* node)
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;
565 assert(node->len > 0);
566 prev = ldns_radix_prev_from_index(node, index);
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)
590 for (j = 0; j < d; j++) {
595 fprintf(fd, "| [%u+", (unsigned) i);
596 for (l=0; l < len; l++) {
597 fprintf(fd, "%c", (char) str[l]);
599 fprintf(fd, "]%u", (unsigned) len);
601 fprintf(fd, "| [%u]", (unsigned) i);
605 fprintf(fd, " %s", (char*) node->data);
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);
624 ldns_radix_printf(FILE* fd, ldns_radix_t* tree)
630 fprintf(fd, "; empty radix tree\n");
633 ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0);
639 * Join two radix trees.
643 ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2)
645 ldns_radix_node_t* cur_node, *next_node;
647 if (!tree2 || !tree2->root) {
648 return LDNS_STATUS_OK;
650 /** Add all elements from tree2 into tree1. */
652 cur_node = ldns_radix_first(tree2);
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) {
665 next_node = ldns_radix_next(cur_node);
666 if (status == LDNS_STATUS_OK) {
667 (void) ldns_radix_delete(tree2, cur_node->key,
670 cur_node = next_node;
673 return LDNS_STATUS_OK;
678 * Split a radix tree intwo.
682 ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2)
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;
691 return LDNS_STATUS_NULL;
694 *tree2 = ldns_radix_create();
696 return LDNS_STATUS_MEM_ERR;
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,
707 /** Insert current node into tree2/ */
709 return LDNS_STATUS_NO_DATA;
711 status = ldns_radix_insert(*tree2, cur_key, cur_len,
713 if (status != LDNS_STATUS_OK &&
714 status != LDNS_STATUS_EXISTS_ERR) {
718 if (status == LDNS_STATUS_OK) {
719 cur_node->key = NULL;
723 /** Update count; get first element from tree1 again. */
725 cur_node = ldns_radix_first(tree1);
727 cur_node = ldns_radix_next(cur_node);
730 return LDNS_STATUS_OK;
735 * Call function for all nodes in the tree, such that leaf nodes are
736 * called before parent nodes.
740 ldns_radix_traverse_postorder(ldns_radix_node_t* node,
741 void (*func)(ldns_radix_node_t*, void*), void* arg)
747 for (i=0; i < node->len; i++) {
748 ldns_radix_traverse_postorder(node->array[i].edge,
751 /** Call user function */
757 /** Static helper functions */
760 * Find a prefix of the 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.
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)
776 /** Start searching at the root node */
777 ldns_radix_node_t* n = tree->root;
778 radix_strlen_t pos = 0;
783 /** No root, no prefix found */
786 /** For each node, look if we can make further progress */
793 if (byte < n->offset) {
798 if (byte >= n->len) {
802 /** So far, the trie matches */
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 */
809 if (memcmp(&key[pos], n->array[byte].str,
810 n->array[byte].len) != 0) {
811 return 1; /* no match at child node */
813 pos += n->array[byte].len;
815 /** Continue searching prefix at this child node */
816 n = n->array[byte].edge;
820 /** Update the prefix node */
830 * Make space in the node's array for another byte.
833 * @return 1 if successful, 0 otherwise.
837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
839 /** Is there an array? */
841 assert(node->capacity == 0);
842 /** No array, create new array */
843 node->array = LDNS_MALLOC(ldns_radix_array_t);
847 memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
854 assert(node->array != NULL);
855 assert(node->capacity > 0);
857 if (node->len == 0) {
861 } else if (byte < node->offset) {
862 /** Byte is below the offset */
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 */
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 =
883 /** Zero the first */
884 memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));
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 */
898 /** Zero the added items */
899 memset(&node->array[node->len], 0,
900 need*sizeof(ldns_radix_array_t));
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.
916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
918 unsigned size = ((unsigned)node->capacity)*2;
919 ldns_radix_array_t* a = NULL;
926 a = LDNS_XMALLOC(ldns_radix_array_t, size);
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);
935 node->capacity = size;
941 * Create a prefix in the array string.
942 * @param array: array.
944 * @param pos: start position in key.
945 * @param len: length of key.
946 * @return 0 if failed, 1 if was successful.
950 ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
951 radix_strlen_t pos, radix_strlen_t len)
953 array->str = LDNS_XMALLOC(uint8_t, (len-pos));
957 memmove(array->str, key+pos, len-pos);
958 array->len = (len-pos);
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.
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)
978 *split_len = longer_len - prefix_len;
979 *split_str = LDNS_XMALLOC(uint8_t, (*split_len));
983 memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len);
989 * Create a split when two nodes have a shared prefix.
990 * @param array: array.
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.
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)
1002 uint8_t* str_to_add = key + pos;
1003 radix_strlen_t strlen_to_add = len - pos;
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;
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,
1027 /** Duplicate the string to add */
1028 if (strlen_to_add != 0) {
1029 dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add);
1031 LDNS_FREE(split_str);
1034 memcpy(dup_str, str_to_add, strlen_to_add);
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);
1044 * The added node should go direct under the existing parent.
1045 * The existing node should go under the added node.
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);
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 */
1062 * Example 6: 'dns-ng'
1065 * ----| [-+ng] dns-ng
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,
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);
1087 * The added node should go direct under the existing node.
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;
1096 /** Create a new split node. */
1098 * Example 7: 'dndns'
1101 * ----| [d+ns] dndns
1103 * ------| [-+ng] dns-ng
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);
1120 if (array->len - common_len > 1) {
1121 if (!ldns_radix_prefix_remainder(common_len+1,
1122 array->str, array->len, &s1, &l1)) {
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)) {
1132 /** Create the shared prefix. */
1133 if (common_len > 0) {
1134 common_str = LDNS_XMALLOC(uint8_t, common_len);
1141 memcpy(common_str, str_to_add, common_len);
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);
1148 LDNS_FREE(common_str);
1154 * The common node should go direct under the parent node.
1155 * The added and existing nodes go under the common node.
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] -
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;
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.
1189 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
1190 uint8_t* str2, radix_strlen_t len2)
1193 return 1; /* empty prefix is also a prefix */
1196 return 0; /* len1 is longer so str1 cannot be a prefix */
1198 return (memcmp(str1, str2, len1) == 0);
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.
1211 static radix_strlen_t
1212 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
1213 uint8_t* str2, radix_strlen_t len2)
1215 radix_strlen_t i, max = (len1<len2)?len1:len2;
1216 for (i=0; i<max; i++) {
1217 if (str1[i] != str2[i]) {
1226 * Find the next element in the subtree of this node.
1227 * @param node: node.
1228 * @return: node with next element.
1231 static ldns_radix_node_t*
1232 ldns_radix_next_in_subtree(ldns_radix_node_t* node)
1235 ldns_radix_node_t* next;
1236 /** Try every subnode. */
1237 for (i = 0; i < node->len; i++) {
1238 if (node->array[i].edge) {
1240 if (node->array[i].edge->data) {
1241 return node->array[i].edge;
1243 /** Dive into subtree. */
1244 next = ldns_radix_next_in_subtree(node->array[i].edge);
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.
1261 static ldns_radix_node_t*
1262 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
1267 if (node->array[i].edge) {
1268 ldns_radix_node_t* prev =
1269 ldns_radix_last_in_subtree_incl_self(node);
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.
1285 static ldns_radix_node_t*
1286 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
1288 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
1291 } else if (node->data) {
1299 * Find last node in subtree.
1300 * @param node: node.
1301 * @return last node in subtree.
1304 static ldns_radix_node_t*
1305 ldns_radix_last_in_subtree(ldns_radix_node_t* node)
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);
1320 /** Could this be the most right leaf node? */
1321 if (node->array[i].edge->data) {
1322 return node->array[i].edge;
1331 * Fix tree after deleting element.
1332 * @param tree: tree.
1333 * @param node: node with deleted element.
1337 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
1341 /** Thou should not delete nodes with data attached. */
1343 } else if (node->len == 1 && node->parent) {
1344 /** Node with one child is fold back into. */
1345 ldns_radix_cleanup_onechild(node);
1347 } else if (node->len == 0) {
1349 ldns_radix_node_t* parent = node->parent;
1351 /** The root is a leaf node. */
1352 ldns_radix_node_free(node, NULL);
1356 /** Cleanup leaf node and continue with parent. */
1357 ldns_radix_cleanup_leaf(node);
1361 * Node cannot be deleted, because it has edge nodes
1362 * and no parent to fix up to.
1373 * Clean up a node with one child.
1374 * @param node: node with one child.
1378 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
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;
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;
1390 join_str = LDNS_XMALLOC(uint8_t, join_len);
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.
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 +
1404 memmove(join_str + parent->array[parent_index].len+1,
1405 node->array[0].str, node->array[0].len);
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);
1419 * Clean up a leaf node.
1420 * @param node: leaf node.
1424 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
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);
1441 ldns_radix_node_array_free_end(parent);
1448 * Free a radix node.
1449 * @param node: node.
1450 * @param arg: user argument.
1454 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
1461 for (i=0; i < node->len; i++) {
1462 LDNS_FREE(node->array[i].str);
1466 LDNS_FREE(node->array);
1473 * Free select edge array.
1474 * @param node: node.
1478 ldns_radix_node_array_free(ldns_radix_node_t* node)
1482 LDNS_FREE(node->array);
1490 * Free front of select edge array.
1491 * @param node: node.
1495 ldns_radix_node_array_free_front(ldns_radix_node_t* node)
1498 /** Remove until a non NULL entry. */
1499 while (n < node->len && node->array[n].edge == NULL) {
1505 if (n == node->len) {
1506 ldns_radix_node_array_free(node);
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));
1515 for (i=0; i < node->len; i++) {
1516 if (node->array[i].edge) {
1517 node->array[i].edge->parent_index = i;
1520 ldns_radix_array_reduce(node);
1526 * Free front of select edge array.
1527 * @param node: node.
1531 ldns_radix_node_array_free_end(ldns_radix_node_t* node)
1534 /** Shorten array. */
1535 while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1541 if (n == node->len) {
1542 ldns_radix_node_array_free(node);
1545 assert(n < node->len);
1547 ldns_radix_array_reduce(node);
1553 * Reduce the capacity of the array if needed.
1554 * @param node: node.
1558 ldns_radix_array_reduce(ldns_radix_node_t* node)
1560 if (node->len <= node->capacity/2 && node->len != node->capacity) {
1561 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
1566 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
1567 LDNS_FREE(node->array);
1569 node->capacity = node->len;
1576 * Return this element if it exists, the previous otherwise.
1577 * @param node: from this node.
1578 * @param result: result node.
1582 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
1587 *result = ldns_radix_prev(node);