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
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.
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 */
230 /* 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, const 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, const 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, const 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(const 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(const 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, const 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)) {
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)) {
1135 /** Create the shared prefix. */
1136 if (common_len > 0) {
1137 common_str = LDNS_XMALLOC(uint8_t, common_len);
1144 memcpy(common_str, str_to_add, common_len);
1146 /** Make space in the common node array. */
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);
1151 LDNS_FREE(common_str);
1157 * The common node should go direct under the parent node.
1158 * The added and existing nodes go under the common node.
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] -
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;
1183 * Check if one string prefix of other string.
1184 * @param str1: one string.
1185 * @param len1: one string length.
1186 * @param str2: other string.
1187 * @param len2: other string length.
1188 * @return 1 if prefix, 0 otherwise.
1192 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
1193 uint8_t* str2, radix_strlen_t len2)
1196 return 1; /* empty prefix is also a prefix */
1199 return 0; /* len1 is longer so str1 cannot be a prefix */
1201 return (memcmp(str1, str2, len1) == 0);
1206 * Return the number of bytes in common for the two strings.
1207 * @param str1: one string.
1208 * @param len1: one string length.
1209 * @param str2: other string.
1210 * @param len2: other string length.
1211 * @return length of substring that the two strings have in common.
1214 static radix_strlen_t
1215 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
1216 uint8_t* str2, radix_strlen_t len2)
1218 radix_strlen_t i, max = (len1<len2)?len1:len2;
1219 for (i=0; i<max; i++) {
1220 if (str1[i] != str2[i]) {
1229 * Find the next element in the subtree of this node.
1230 * @param node: node.
1231 * @return: node with next element.
1234 static ldns_radix_node_t*
1235 ldns_radix_next_in_subtree(ldns_radix_node_t* node)
1238 ldns_radix_node_t* next;
1239 /** Try every subnode. */
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;
1246 /** Dive into subtree. */
1247 next = ldns_radix_next_in_subtree(node->array[i].edge);
1258 * Find the previous element in the array of this node, from index.
1259 * @param node: node.
1260 * @param index: index.
1261 * @return previous node from index.
1264 static ldns_radix_node_t*
1265 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
1270 if (node->array[i].edge) {
1271 ldns_radix_node_t* prev =
1272 ldns_radix_last_in_subtree_incl_self(node);
1283 * Find last node in subtree, or this node (if have data).
1284 * @param node: node.
1285 * @return last node in subtree, or this node, or NULL.
1288 static ldns_radix_node_t*
1289 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
1291 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
1294 } else if (node->data) {
1302 * Find last node in subtree.
1303 * @param node: node.
1304 * @return last node in subtree.
1307 static ldns_radix_node_t*
1308 ldns_radix_last_in_subtree(ldns_radix_node_t* node)
1311 /** Look for the most right leaf node. */
1312 for (i=(int)(node->len)-1; i >= 0; i--) {
1313 if (node->array[i].edge) {
1314 /** Keep looking for the most right leaf node. */
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);
1323 /** Could this be the most right leaf node? */
1324 if (node->array[i].edge->data) {
1325 return node->array[i].edge;
1334 * Fix tree after deleting element.
1335 * @param tree: tree.
1336 * @param node: node with deleted element.
1340 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
1344 /** Thou should not delete nodes with data attached. */
1346 } else if (node->len == 1 && node->parent) {
1347 /** Node with one child is fold back into. */
1348 ldns_radix_cleanup_onechild(node);
1350 } else if (node->len == 0) {
1352 ldns_radix_node_t* parent = node->parent;
1354 /** The root is a leaf node. */
1355 ldns_radix_node_free(node, NULL);
1359 /** Cleanup leaf node and continue with parent. */
1360 ldns_radix_cleanup_leaf(node);
1364 * Node cannot be deleted, because it has edge nodes
1365 * and no parent to fix up to.
1376 * Clean up a node with one child.
1377 * @param node: node with one child.
1381 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
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;
1389 /** Node has one child, merge the child node into the parent node. */
1390 assert(parent_index < parent->len);
1391 join_len = parent->array[parent_index].len + node->array[0].len + 1;
1393 join_str = LDNS_XMALLOC(uint8_t, join_len);
1396 * Cleanup failed due to out of memory.
1397 * This tree is now inefficient, with the empty node still
1398 * existing, but it is still valid.
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 +
1407 memmove(join_str + parent->array[parent_index].len+1,
1408 node->array[0].str, node->array[0].len);
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);
1422 * Clean up a leaf node.
1423 * @param node: leaf node.
1427 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
1429 uint8_t parent_index = node->parent_index;
1430 ldns_radix_node_t* parent = node->parent;
1431 /** Delete lead node and fix parent array. */
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;
1438 /** Fix array in parent. */
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);
1444 ldns_radix_node_array_free_end(parent);
1451 * Free a radix node.
1452 * @param node: node.
1453 * @param arg: user argument.
1457 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
1464 for (i=0; i < node->len; i++) {
1465 LDNS_FREE(node->array[i].str);
1469 LDNS_FREE(node->array);
1476 * Free select edge array.
1477 * @param node: node.
1481 ldns_radix_node_array_free(ldns_radix_node_t* node)
1485 LDNS_FREE(node->array);
1493 * Free front of select edge array.
1494 * @param node: node.
1498 ldns_radix_node_array_free_front(ldns_radix_node_t* node)
1501 /** Remove until a non NULL entry. */
1502 while (n < node->len && node->array[n].edge == NULL) {
1508 if (n == node->len) {
1509 ldns_radix_node_array_free(node);
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));
1518 for (i=0; i < node->len; i++) {
1519 if (node->array[i].edge) {
1520 node->array[i].edge->parent_index = i;
1523 ldns_radix_array_reduce(node);
1529 * Free front of select edge array.
1530 * @param node: node.
1534 ldns_radix_node_array_free_end(ldns_radix_node_t* node)
1537 /** Shorten array. */
1538 while (n < node->len && node->array[node->len-1-n].edge == NULL) {
1544 if (n == node->len) {
1545 ldns_radix_node_array_free(node);
1548 assert(n < node->len);
1550 ldns_radix_array_reduce(node);
1556 * Reduce the capacity of the array if needed.
1557 * @param node: node.
1561 ldns_radix_array_reduce(ldns_radix_node_t* node)
1563 if (node->len <= node->capacity/2 && node->len != node->capacity) {
1564 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
1569 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
1570 LDNS_FREE(node->array);
1572 node->capacity = node->len;
1579 * Return this element if it exists, the previous otherwise.
1580 * @param node: from this node.
1581 * @param result: result node.
1585 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
1590 *result = ldns_radix_prev(node);