Lines Matching +full:exact +full:- +full:len
2 * radix.c -- generic radix tree
51 radix_strlen_t len);
53 radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos);
57 radix_strlen_t pos, radix_strlen_t len);
62 radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add);
90 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len) in ldns_radix_new_node() argument
96 node->data = data; in ldns_radix_new_node()
97 node->key = key; in ldns_radix_new_node()
98 node->klen = len; in ldns_radix_new_node()
99 node->parent = NULL; in ldns_radix_new_node()
100 node->parent_index = 0; in ldns_radix_new_node()
101 node->len = 0; in ldns_radix_new_node()
102 node->offset = 0; in ldns_radix_new_node()
103 node->capacity = 0; in ldns_radix_new_node()
104 node->array = NULL; in ldns_radix_new_node()
138 tree->root = NULL; in ldns_radix_init()
139 tree->count = 0; in ldns_radix_init()
153 if (tree->root) { in ldns_radix_free()
154 ldns_radix_traverse_postorder(tree->root, in ldns_radix_free()
168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len, in ldns_radix_insert() argument
178 add = ldns_radix_new_node(data, key, len); in ldns_radix_insert()
183 if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) { in ldns_radix_insert()
185 assert(tree->root == NULL); in ldns_radix_insert()
186 if (len == 0) { in ldns_radix_insert()
191 tree->root = add; in ldns_radix_insert()
195 * --| [d+ns] dns in ldns_radix_insert()
205 LDNS_FREE(prefix->array); in ldns_radix_insert()
210 add->parent = prefix; in ldns_radix_insert()
211 add->parent_index = 0; in ldns_radix_insert()
212 prefix->array[0].edge = add; in ldns_radix_insert()
213 if (len > 1) { in ldns_radix_insert()
216 len, &prefix->array[0].str, in ldns_radix_insert()
217 &prefix->array[0].len)) { in ldns_radix_insert()
219 LDNS_FREE(prefix->array); in ldns_radix_insert()
224 tree->root = prefix; in ldns_radix_insert()
226 } else if (pos == len) { in ldns_radix_insert()
227 /** Exact match found */ in ldns_radix_insert()
229 if (prefix->data) { in ldns_radix_insert()
233 prefix->data = data; in ldns_radix_insert()
234 prefix->key = key; in ldns_radix_insert()
235 prefix->klen = len; /* redundant */ in ldns_radix_insert()
239 assert(pos < len); in ldns_radix_insert()
240 if (byte < prefix->offset || in ldns_radix_insert()
241 (byte - prefix->offset) >= prefix->len) { in ldns_radix_insert()
246 * --| [d+ns] dns in ldns_radix_insert()
247 * --| [l+dns] ldns in ldns_radix_insert()
253 assert(byte >= prefix->offset); in ldns_radix_insert()
254 assert((byte - prefix->offset) <= prefix->len); in ldns_radix_insert()
255 byte -= prefix->offset; in ldns_radix_insert()
256 if (pos+1 < len) { in ldns_radix_insert()
259 &prefix->array[byte], key, pos+1, in ldns_radix_insert()
260 len)) { in ldns_radix_insert()
266 add->parent = prefix; in ldns_radix_insert()
267 add->parent_index = byte; in ldns_radix_insert()
268 prefix->array[byte].edge = add; in ldns_radix_insert()
269 } else if (prefix->array[byte-prefix->offset].edge == NULL) { in ldns_radix_insert()
274 * --| [d+ns] dns in ldns_radix_insert()
275 * --| [e+dns] edns in ldns_radix_insert()
276 * --| [l+dns] ldns in ldns_radix_insert()
278 byte -= prefix->offset; in ldns_radix_insert()
279 if (pos+1 < len) { in ldns_radix_insert()
282 &prefix->array[byte], key, pos+1, in ldns_radix_insert()
283 len)) { in ldns_radix_insert()
289 add->parent = prefix; in ldns_radix_insert()
290 add->parent_index = byte; in ldns_radix_insert()
291 prefix->array[byte].edge = add; in ldns_radix_insert()
297 if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)], in ldns_radix_insert()
298 key, pos+1, len, add)) { in ldns_radix_insert()
305 tree->count ++; in ldns_radix_insert()
314 void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len) in ldns_radix_delete() argument
316 ldns_radix_node_t* del = ldns_radix_search(tree, key, len); in ldns_radix_delete()
319 tree->count--; in ldns_radix_delete()
320 data = del->data; in ldns_radix_delete()
321 del->data = NULL; in ldns_radix_delete()
334 ldns_radix_search(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len) in ldns_radix_search() argument
343 node = tree->root; in ldns_radix_search()
345 if (pos == len) { in ldns_radix_search()
346 return node->data?node:NULL; in ldns_radix_search()
349 if (byte < node->offset) { in ldns_radix_search()
352 byte -= node->offset; in ldns_radix_search()
353 if (byte >= node->len) { in ldns_radix_search()
357 if (node->array[byte].len > 0) { in ldns_radix_search()
359 if (pos + node->array[byte].len > len) { in ldns_radix_search()
362 if (memcmp(&key[pos], node->array[byte].str, in ldns_radix_search()
363 node->array[byte].len) != 0) { in ldns_radix_search()
366 pos += node->array[byte].len; in ldns_radix_search()
368 node = node->array[byte].edge; in ldns_radix_search()
381 radix_strlen_t len, ldns_radix_node_t** result) in ldns_radix_find_less_equal() argument
388 if (!tree || !tree->root || !key) { in ldns_radix_find_less_equal()
393 node = tree->root; in ldns_radix_find_less_equal()
394 while (pos < len) { in ldns_radix_find_less_equal()
396 if (byte < node->offset) { in ldns_radix_find_less_equal()
398 * No exact match. The lesser is in this or the in ldns_radix_find_less_equal()
404 byte -= node->offset; in ldns_radix_find_less_equal()
405 if (byte >= node->len) { in ldns_radix_find_less_equal()
407 * No exact match. The lesser is in this node or the in ldns_radix_find_less_equal()
417 if (!node->array[byte].edge) { in ldns_radix_find_less_equal()
419 * No exact match. Find the previous in the array in ldns_radix_find_less_equal()
428 if (node->array[byte].len != 0) { in ldns_radix_find_less_equal()
430 if (pos + node->array[byte].len > len) { in ldns_radix_find_less_equal()
432 if (memcmp(&key[pos], node->array[byte].str, in ldns_radix_find_less_equal()
433 len-pos) <= 0) { in ldns_radix_find_less_equal()
436 node->array[byte].edge); in ldns_radix_find_less_equal()
439 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge); in ldns_radix_find_less_equal()
441 *result = ldns_radix_prev(node->array[byte].edge); in ldns_radix_find_less_equal()
446 memcmp_res = memcmp(&key[pos], node->array[byte].str, in ldns_radix_find_less_equal()
447 node->array[byte].len); in ldns_radix_find_less_equal()
450 node->array[byte].edge); in ldns_radix_find_less_equal()
453 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge); in ldns_radix_find_less_equal()
455 *result = ldns_radix_prev(node->array[byte].edge); in ldns_radix_find_less_equal()
460 pos += node->array[byte].len; in ldns_radix_find_less_equal()
462 node = node->array[byte].edge; in ldns_radix_find_less_equal()
464 if (node->data) { in ldns_radix_find_less_equal()
465 /** Exact match. */ in ldns_radix_find_less_equal()
469 /** There is a node which is an exact match, but has no element. */ in ldns_radix_find_less_equal()
483 if (!tree || !tree->root) { in ldns_radix_first()
486 first = tree->root; in ldns_radix_first()
487 if (first->data) { in ldns_radix_first()
501 if (!tree || !tree->root) { in ldns_radix_last()
504 return ldns_radix_last_in_subtree_incl_self(tree->root); in ldns_radix_last()
518 if (node->len) { in ldns_radix_next()
519 /** Go down: most-left child is the next. */ in ldns_radix_next()
526 while (node->parent) { in ldns_radix_next()
527 uint8_t index = node->parent_index; in ldns_radix_next()
528 node = node->parent; in ldns_radix_next()
530 for (; index < node->len; index++) { in ldns_radix_next()
531 if (node->array[index].edge) { in ldns_radix_next()
534 if (node->array[index].edge->data) { in ldns_radix_next()
535 return node->array[index].edge; in ldns_radix_next()
561 while (node->parent) { in ldns_radix_prev()
562 uint8_t index = node->parent_index; in ldns_radix_prev()
564 node = node->parent; in ldns_radix_prev()
565 assert(node->len > 0); in ldns_radix_prev()
570 if (node->data) { in ldns_radix_prev()
584 uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d) in ldns_radix_node_print() argument
591 fprintf(fd, "--"); in ldns_radix_node_print()
596 for (l=0; l < len; l++) { in ldns_radix_node_print()
599 fprintf(fd, "]%u", (unsigned) len); in ldns_radix_node_print()
604 if (node->data) { in ldns_radix_node_print()
605 fprintf(fd, " %s", (char*) node->data); in ldns_radix_node_print()
609 for (j = 0; j < node->len; j++) { in ldns_radix_node_print()
610 if (node->array[j].edge) { in ldns_radix_node_print()
611 ldns_radix_node_print(fd, node->array[j].edge, j, in ldns_radix_node_print()
612 node->array[j].str, node->array[j].len, d+1); in ldns_radix_node_print()
629 if (!tree->root) { in ldns_radix_printf()
633 ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0); in ldns_radix_printf()
647 if (!tree2 || !tree2->root) { in ldns_radix_join()
656 if (cur_node->data) { in ldns_radix_join()
657 status = ldns_radix_insert(tree1, cur_node->key, in ldns_radix_join()
658 cur_node->klen, cur_node->data); in ldns_radix_join()
667 (void) ldns_radix_delete(tree2, cur_node->key, in ldns_radix_join()
668 cur_node->klen); in ldns_radix_join()
687 if (!tree1 || !tree1->root || num == 0) { in ldns_radix_split()
701 if (cur_node->data) { in ldns_radix_split()
703 uint8_t* cur_key = cur_node->key; in ldns_radix_split()
704 radix_strlen_t cur_len = cur_node->klen; in ldns_radix_split()
719 cur_node->key = NULL; in ldns_radix_split()
720 cur_node->klen = 0; in ldns_radix_split()
747 for (i=0; i < node->len; i++) { in ldns_radix_traverse_postorder()
748 ldns_radix_traverse_postorder(node->array[i].edge, in ldns_radix_traverse_postorder()
763 * @param len: length of key.
764 * @param result: the longest prefix, the entry itself if *pos==len,
767 * If *pos==len, an exact match is found.
774 radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos) in ldns_radix_find_prefix() argument
777 ldns_radix_node_t* n = tree->root; in ldns_radix_find_prefix()
788 if (pos == len) { in ldns_radix_find_prefix()
789 /** Exact match */ in ldns_radix_find_prefix()
793 if (byte < n->offset) { in ldns_radix_find_prefix()
797 byte -= n->offset; in ldns_radix_find_prefix()
798 if (byte >= n->len) { in ldns_radix_find_prefix()
804 if (n->array[byte].len != 0) { in ldns_radix_find_prefix()
806 if (pos + n->array[byte].len > len) { in ldns_radix_find_prefix()
809 if (memcmp(&key[pos], n->array[byte].str, in ldns_radix_find_prefix()
810 n->array[byte].len) != 0) { in ldns_radix_find_prefix()
813 pos += n->array[byte].len; in ldns_radix_find_prefix()
816 n = n->array[byte].edge; in ldns_radix_find_prefix()
840 if (!node->array) { in ldns_radix_array_space()
841 assert(node->capacity == 0); in ldns_radix_array_space()
843 node->array = LDNS_MALLOC(ldns_radix_array_t); in ldns_radix_array_space()
844 if (!node->array) { in ldns_radix_array_space()
847 memset(&node->array[0], 0, sizeof(ldns_radix_array_t)); in ldns_radix_array_space()
848 node->len = 1; in ldns_radix_array_space()
849 node->capacity = 1; in ldns_radix_array_space()
850 node->offset = byte; in ldns_radix_array_space()
854 assert(node->array != NULL); in ldns_radix_array_space()
855 assert(node->capacity > 0); in ldns_radix_array_space()
857 if (node->len == 0) { in ldns_radix_array_space()
859 node->len = 1; in ldns_radix_array_space()
860 node->offset = byte; in ldns_radix_array_space()
861 } else if (byte < node->offset) { in ldns_radix_array_space()
864 uint16_t need = node->offset - byte; in ldns_radix_array_space()
866 if (node->len + need > node->capacity) { in ldns_radix_array_space()
869 (unsigned) (node->len + need))) { in ldns_radix_array_space()
874 memmove(&node->array[need], &node->array[0], in ldns_radix_array_space()
875 node->len*sizeof(ldns_radix_array_t)); in ldns_radix_array_space()
877 for (index = 0; index < node->len; index++) { in ldns_radix_array_space()
878 if (node->array[index+need].edge) { in ldns_radix_array_space()
879 node->array[index+need].edge->parent_index = in ldns_radix_array_space()
884 memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t)); in ldns_radix_array_space()
885 node->len += need; in ldns_radix_array_space()
886 node->offset = byte; in ldns_radix_array_space()
887 } else if (byte - node->offset >= node->len) { in ldns_radix_array_space()
889 uint16_t need = (byte - node->offset) - node->len + 1; in ldns_radix_array_space()
891 if (node->len + need > node->capacity) { in ldns_radix_array_space()
894 (unsigned) (node->len + need))) { in ldns_radix_array_space()
899 memset(&node->array[node->len], 0, in ldns_radix_array_space()
901 node->len += need; in ldns_radix_array_space()
918 unsigned size = ((unsigned)node->capacity)*2; in ldns_radix_array_grow()
930 assert(node->len <= node->capacity); in ldns_radix_array_grow()
931 assert(node->capacity < size); in ldns_radix_array_grow()
932 memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t)); in ldns_radix_array_grow()
933 LDNS_FREE(node->array); in ldns_radix_array_grow()
934 node->array = a; in ldns_radix_array_grow()
935 node->capacity = size; in ldns_radix_array_grow()
945 * @param len: length of key.
951 radix_strlen_t pos, radix_strlen_t len) in ldns_radix_str_create() argument
953 array->str = LDNS_XMALLOC(uint8_t, (len-pos)); in ldns_radix_str_create()
954 if (!array->str) { in ldns_radix_str_create()
957 memmove(array->str, key+pos, len-pos); in ldns_radix_str_create()
958 array->len = (len-pos); in ldns_radix_str_create()
978 *split_len = longer_len - prefix_len; in ldns_radix_prefix_remainder()
983 memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len); in ldns_radix_prefix_remainder()
993 * @param len: length of the key.
1000 radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add) in ldns_radix_array_split() argument
1003 radix_strlen_t strlen_to_add = len - pos; in ldns_radix_array_split()
1006 array->str, array->len)) { in ldns_radix_array_split()
1013 * --| [d+ns] dns in ldns_radix_array_split()
1014 * --| [e+dns] edns in ldns_radix_array_split()
1015 * --| [l+d] ld in ldns_radix_array_split()
1016 * ----| [n+s] ldns in ldns_radix_array_split()
1018 assert(strlen_to_add < array->len); in ldns_radix_array_split()
1020 if (array->len - strlen_to_add > 1) { in ldns_radix_array_split()
1022 array->str, array->len, &split_str, in ldns_radix_array_split()
1038 array->str[strlen_to_add])) { in ldns_radix_array_split()
1047 add->parent = array->edge->parent; in ldns_radix_array_split()
1048 add->parent_index = array->edge->parent_index; in ldns_radix_array_split()
1049 add->array[0].edge = array->edge; in ldns_radix_array_split()
1050 add->array[0].str = split_str; in ldns_radix_array_split()
1051 add->array[0].len = split_len; in ldns_radix_array_split()
1052 array->edge->parent = add; in ldns_radix_array_split()
1053 array->edge->parent_index = 0; in ldns_radix_array_split()
1054 LDNS_FREE(array->str); in ldns_radix_array_split()
1055 array->edge = add; in ldns_radix_array_split()
1056 array->str = dup_str; in ldns_radix_array_split()
1057 array->len = strlen_to_add; in ldns_radix_array_split()
1058 } else if (ldns_radix_str_is_prefix(array->str, array->len, in ldns_radix_array_split()
1062 * Example 6: 'dns-ng' in ldns_radix_array_split()
1064 * --| [d+ns] dns in ldns_radix_array_split()
1065 * ----| [-+ng] dns-ng in ldns_radix_array_split()
1066 * --| [e+dns] edns in ldns_radix_array_split()
1067 * --| [l+d] ld in ldns_radix_array_split()
1068 * ----| [n+s] ldns in ldns_radix_array_split()
1072 assert(array->len < strlen_to_add); in ldns_radix_array_split()
1073 if (strlen_to_add - array->len > 1) { in ldns_radix_array_split()
1074 if (!ldns_radix_prefix_remainder(array->len+1, in ldns_radix_array_split()
1081 if (!ldns_radix_array_space(array->edge, in ldns_radix_array_split()
1082 str_to_add[array->len])) { in ldns_radix_array_split()
1089 add->parent = array->edge; in ldns_radix_array_split()
1090 add->parent_index = str_to_add[array->len] - in ldns_radix_array_split()
1091 array->edge->offset; in ldns_radix_array_split()
1092 array->edge->array[add->parent_index].edge = add; in ldns_radix_array_split()
1093 array->edge->array[add->parent_index].str = split_str; in ldns_radix_array_split()
1094 array->edge->array[add->parent_index].len = split_len; in ldns_radix_array_split()
1100 * --| [d+n] in ldns_radix_array_split()
1101 * ----| [d+ns] dndns in ldns_radix_array_split()
1102 * ----| [s] dns in ldns_radix_array_split()
1103 * ------| [-+ng] dns-ng in ldns_radix_array_split()
1104 * --| [e+dns] edns in ldns_radix_array_split()
1105 * --| [l+d] ld in ldns_radix_array_split()
1106 * ----| [n+s] ldns in ldns_radix_array_split()
1111 common_len = ldns_radix_str_common(array->str, array->len, in ldns_radix_array_split()
1113 assert(common_len < array->len); in ldns_radix_array_split()
1120 if (array->len - common_len > 1) { in ldns_radix_array_split()
1122 array->str, array->len, &s1, &l1)) { in ldns_radix_array_split()
1127 if (strlen_to_add - common_len > 1) { in ldns_radix_array_split()
1147 if (!ldns_radix_array_space(common, array->str[common_len]) || in ldns_radix_array_split()
1149 LDNS_FREE(common->array); in ldns_radix_array_split()
1160 common->parent = array->edge->parent; in ldns_radix_array_split()
1161 common->parent_index = array->edge->parent_index; in ldns_radix_array_split()
1162 array->edge->parent = common; in ldns_radix_array_split()
1163 array->edge->parent_index = array->str[common_len] - in ldns_radix_array_split()
1164 common->offset; in ldns_radix_array_split()
1165 add->parent = common; in ldns_radix_array_split()
1166 add->parent_index = str_to_add[common_len] - common->offset; in ldns_radix_array_split()
1167 common->array[array->edge->parent_index].edge = array->edge; in ldns_radix_array_split()
1168 common->array[array->edge->parent_index].str = s1; in ldns_radix_array_split()
1169 common->array[array->edge->parent_index].len = l1; in ldns_radix_array_split()
1170 common->array[add->parent_index].edge = add; in ldns_radix_array_split()
1171 common->array[add->parent_index].str = s2; in ldns_radix_array_split()
1172 common->array[add->parent_index].len = l2; in ldns_radix_array_split()
1173 LDNS_FREE(array->str); in ldns_radix_array_split()
1174 array->edge = common; in ldns_radix_array_split()
1175 array->str = common_str; in ldns_radix_array_split()
1176 array->len = common_len; in ldns_radix_array_split()
1240 for (i = 0; i < node->len; i++) { in ldns_radix_next_in_subtree()
1241 if (node->array[i].edge) { in ldns_radix_next_in_subtree()
1243 if (node->array[i].edge->data) { in ldns_radix_next_in_subtree()
1244 return node->array[i].edge; in ldns_radix_next_in_subtree()
1247 next = ldns_radix_next_in_subtree(node->array[i].edge); in ldns_radix_next_in_subtree()
1269 i--; in ldns_radix_prev_from_index()
1270 if (node->array[i].edge) { in ldns_radix_prev_from_index()
1294 } else if (node->data) { in ldns_radix_last_in_subtree_incl_self()
1312 for (i=(int)(node->len)-1; i >= 0; i--) { in ldns_radix_last_in_subtree()
1313 if (node->array[i].edge) { in ldns_radix_last_in_subtree()
1315 if (node->array[i].edge->len > 0) { in ldns_radix_last_in_subtree()
1318 node->array[i].edge); in ldns_radix_last_in_subtree()
1324 if (node->array[i].edge->data) { in ldns_radix_last_in_subtree()
1325 return node->array[i].edge; in ldns_radix_last_in_subtree()
1343 if (node->data) { in ldns_radix_del_fix()
1346 } else if (node->len == 1 && node->parent) { in ldns_radix_del_fix()
1350 } else if (node->len == 0) { in ldns_radix_del_fix()
1352 ldns_radix_node_t* parent = node->parent; in ldns_radix_del_fix()
1356 tree->root = NULL; in ldns_radix_del_fix()
1385 uint8_t parent_index = node->parent_index; in ldns_radix_cleanup_onechild()
1386 ldns_radix_node_t* child = node->array[0].edge; in ldns_radix_cleanup_onechild()
1387 ldns_radix_node_t* parent = node->parent; in ldns_radix_cleanup_onechild()
1390 assert(parent_index < parent->len); in ldns_radix_cleanup_onechild()
1391 join_len = parent->array[parent_index].len + node->array[0].len + 1; in ldns_radix_cleanup_onechild()
1403 memcpy(join_str, parent->array[parent_index].str, in ldns_radix_cleanup_onechild()
1404 parent->array[parent_index].len); in ldns_radix_cleanup_onechild()
1405 join_str[parent->array[parent_index].len] = child->parent_index + in ldns_radix_cleanup_onechild()
1406 node->offset; in ldns_radix_cleanup_onechild()
1407 memmove(join_str + parent->array[parent_index].len+1, in ldns_radix_cleanup_onechild()
1408 node->array[0].str, node->array[0].len); in ldns_radix_cleanup_onechild()
1410 LDNS_FREE(parent->array[parent_index].str); in ldns_radix_cleanup_onechild()
1411 parent->array[parent_index].str = join_str; in ldns_radix_cleanup_onechild()
1412 parent->array[parent_index].len = join_len; in ldns_radix_cleanup_onechild()
1413 parent->array[parent_index].edge = child; in ldns_radix_cleanup_onechild()
1414 child->parent = parent; in ldns_radix_cleanup_onechild()
1415 child->parent_index = parent_index; in ldns_radix_cleanup_onechild()
1429 uint8_t parent_index = node->parent_index; in ldns_radix_cleanup_leaf()
1430 ldns_radix_node_t* parent = node->parent; in ldns_radix_cleanup_leaf()
1432 assert(parent_index < parent->len); in ldns_radix_cleanup_leaf()
1434 LDNS_FREE(parent->array[parent_index].str); in ldns_radix_cleanup_leaf()
1435 parent->array[parent_index].str = NULL; in ldns_radix_cleanup_leaf()
1436 parent->array[parent_index].len = 0; in ldns_radix_cleanup_leaf()
1437 parent->array[parent_index].edge = NULL; in ldns_radix_cleanup_leaf()
1439 if (parent->len == 1) { in ldns_radix_cleanup_leaf()
1464 for (i=0; i < node->len; i++) { in ldns_radix_node_free()
1465 LDNS_FREE(node->array[i].str); in ldns_radix_node_free()
1467 node->key = NULL; in ldns_radix_node_free()
1468 node->klen = 0; in ldns_radix_node_free()
1469 LDNS_FREE(node->array); in ldns_radix_node_free()
1483 node->offset = 0; in ldns_radix_node_array_free()
1484 node->len = 0; in ldns_radix_node_array_free()
1485 LDNS_FREE(node->array); in ldns_radix_node_array_free()
1486 node->array = NULL; in ldns_radix_node_array_free()
1487 node->capacity = 0; in ldns_radix_node_array_free()
1502 while (n < node->len && node->array[n].edge == NULL) { in ldns_radix_node_array_free_front()
1508 if (n == node->len) { in ldns_radix_node_array_free_front()
1512 assert(n < node->len); in ldns_radix_node_array_free_front()
1513 assert((int) n <= (255 - (int) node->offset)); in ldns_radix_node_array_free_front()
1514 memmove(&node->array[0], &node->array[n], in ldns_radix_node_array_free_front()
1515 (node->len - n)*sizeof(ldns_radix_array_t)); in ldns_radix_node_array_free_front()
1516 node->offset += n; in ldns_radix_node_array_free_front()
1517 node->len -= n; in ldns_radix_node_array_free_front()
1518 for (i=0; i < node->len; i++) { in ldns_radix_node_array_free_front()
1519 if (node->array[i].edge) { in ldns_radix_node_array_free_front()
1520 node->array[i].edge->parent_index = i; in ldns_radix_node_array_free_front()
1538 while (n < node->len && node->array[node->len-1-n].edge == NULL) { in ldns_radix_node_array_free_end()
1544 if (n == node->len) { in ldns_radix_node_array_free_end()
1548 assert(n < node->len); in ldns_radix_node_array_free_end()
1549 node->len -= n; in ldns_radix_node_array_free_end()
1563 if (node->len <= node->capacity/2 && node->len != node->capacity) { in ldns_radix_array_reduce()
1565 node->len); in ldns_radix_array_reduce()
1569 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len); in ldns_radix_array_reduce()
1570 LDNS_FREE(node->array); in ldns_radix_array_reduce()
1571 node->array = a; in ldns_radix_array_reduce()
1572 node->capacity = node->len; in ldns_radix_array_reduce()
1587 if (node->data) { in ldns_radix_self_or_prev()