15340022aSzrj /*
25340022aSzrj * radix.c -- generic radix tree
35340022aSzrj *
45340022aSzrj * Taken from NSD4, modified for ldns
55340022aSzrj *
65340022aSzrj * Copyright (c) 2012, NLnet Labs. All rights reserved.
75340022aSzrj *
85340022aSzrj * This software is open source.
95340022aSzrj *
105340022aSzrj * Redistribution and use in source and binary forms, with or without
115340022aSzrj * modification, are permitted provided that the following conditions
125340022aSzrj * are met:
135340022aSzrj *
145340022aSzrj * Redistributions of source code must retain the above copyright notice,
155340022aSzrj * this list of conditions and the following disclaimer.
165340022aSzrj *
175340022aSzrj * Redistributions in binary form must reproduce the above copyright notice,
185340022aSzrj * this list of conditions and the following disclaimer in the documentation
195340022aSzrj * and/or other materials provided with the distribution.
205340022aSzrj *
215340022aSzrj * Neither the name of the NLNET LABS nor the names of its contributors may
225340022aSzrj * be used to endorse or promote products derived from this software without
235340022aSzrj * specific prior written permission.
245340022aSzrj *
255340022aSzrj * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
265340022aSzrj * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
275340022aSzrj * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
285340022aSzrj * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
295340022aSzrj * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
305340022aSzrj * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
315340022aSzrj * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
325340022aSzrj * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
335340022aSzrj * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
345340022aSzrj * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
355340022aSzrj * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
365340022aSzrj *
375340022aSzrj */
385340022aSzrj
395340022aSzrj /**
405340022aSzrj * \file
415340022aSzrj * Implementation of a radix tree.
425340022aSzrj */
435340022aSzrj
445340022aSzrj #include <ldns/config.h>
455340022aSzrj #include <ldns/radix.h>
465340022aSzrj #include <ldns/util.h>
475340022aSzrj #include <stdlib.h>
485340022aSzrj
495340022aSzrj /** Helper functions */
505340022aSzrj static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
515340022aSzrj radix_strlen_t len);
525340022aSzrj static int ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
535340022aSzrj radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos);
545340022aSzrj static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte);
555340022aSzrj static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need);
565340022aSzrj static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
575340022aSzrj radix_strlen_t pos, radix_strlen_t len);
585340022aSzrj static int ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
595340022aSzrj uint8_t* longer_str, radix_strlen_t longer_len, uint8_t** split_str,
605340022aSzrj radix_strlen_t* split_len);
615340022aSzrj static int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
625340022aSzrj radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add);
635340022aSzrj static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
645340022aSzrj uint8_t* str2, radix_strlen_t len2);
655340022aSzrj static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
665340022aSzrj uint8_t* str2, radix_strlen_t len2);
675340022aSzrj static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node);
685340022aSzrj static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node,
695340022aSzrj uint8_t index);
705340022aSzrj static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self(
715340022aSzrj ldns_radix_node_t* node);
725340022aSzrj static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node);
735340022aSzrj static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node);
745340022aSzrj static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node);
755340022aSzrj static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node);
765340022aSzrj static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg);
775340022aSzrj static void ldns_radix_node_array_free(ldns_radix_node_t* node);
785340022aSzrj static void ldns_radix_node_array_free_front(ldns_radix_node_t* node);
795340022aSzrj static void ldns_radix_node_array_free_end(ldns_radix_node_t* node);
805340022aSzrj static void ldns_radix_array_reduce(ldns_radix_node_t* node);
815340022aSzrj static void ldns_radix_self_or_prev(ldns_radix_node_t* node,
825340022aSzrj ldns_radix_node_t** result);
835340022aSzrj
845340022aSzrj
855340022aSzrj /**
865340022aSzrj * Create a new radix node.
875340022aSzrj *
885340022aSzrj */
895340022aSzrj static ldns_radix_node_t*
ldns_radix_new_node(void * data,uint8_t * key,radix_strlen_t len)905340022aSzrj ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
915340022aSzrj {
925340022aSzrj ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
935340022aSzrj if (!node) {
945340022aSzrj return NULL;
955340022aSzrj }
965340022aSzrj node->data = data;
975340022aSzrj node->key = key;
985340022aSzrj node->klen = len;
995340022aSzrj node->parent = NULL;
1005340022aSzrj node->parent_index = 0;
1015340022aSzrj node->len = 0;
1025340022aSzrj node->offset = 0;
1035340022aSzrj node->capacity = 0;
1045340022aSzrj node->array = NULL;
1055340022aSzrj return node;
1065340022aSzrj }
1075340022aSzrj
1085340022aSzrj
1095340022aSzrj /**
1105340022aSzrj * Create a new radix tree.
1115340022aSzrj *
1125340022aSzrj */
1135340022aSzrj ldns_radix_t *
ldns_radix_create(void)1145340022aSzrj ldns_radix_create(void)
1155340022aSzrj {
1165340022aSzrj ldns_radix_t* tree;
1175340022aSzrj
1185340022aSzrj /** Allocate memory for it */
1195340022aSzrj tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
1205340022aSzrj if (!tree) {
1215340022aSzrj return NULL;
1225340022aSzrj }
1235340022aSzrj /** Initialize it */
1245340022aSzrj ldns_radix_init(tree);
1255340022aSzrj return tree;
1265340022aSzrj }
1275340022aSzrj
1285340022aSzrj
1295340022aSzrj /**
1305340022aSzrj * Initialize radix tree.
1315340022aSzrj *
1325340022aSzrj */
1335340022aSzrj void
ldns_radix_init(ldns_radix_t * tree)1345340022aSzrj ldns_radix_init(ldns_radix_t* tree)
1355340022aSzrj {
1365340022aSzrj /** Initialize it */
1375340022aSzrj if (tree) {
1385340022aSzrj tree->root = NULL;
1395340022aSzrj tree->count = 0;
1405340022aSzrj }
1415340022aSzrj return;
1425340022aSzrj }
1435340022aSzrj
1445340022aSzrj
1455340022aSzrj /**
1465340022aSzrj * Free radix tree.
1475340022aSzrj *
1485340022aSzrj */
1495340022aSzrj void
ldns_radix_free(ldns_radix_t * tree)1505340022aSzrj ldns_radix_free(ldns_radix_t* tree)
1515340022aSzrj {
1525340022aSzrj if (tree) {
1535340022aSzrj if (tree->root) {
1545340022aSzrj ldns_radix_traverse_postorder(tree->root,
1555340022aSzrj ldns_radix_node_free, NULL);
1565340022aSzrj }
1575340022aSzrj LDNS_FREE(tree);
1585340022aSzrj }
1595340022aSzrj return;
1605340022aSzrj }
1615340022aSzrj
1625340022aSzrj
1635340022aSzrj /**
1645340022aSzrj * Insert data into the tree.
1655340022aSzrj *
1665340022aSzrj */
1675340022aSzrj ldns_status
ldns_radix_insert(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len,void * data)1685340022aSzrj ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
1695340022aSzrj void* data)
1705340022aSzrj {
1715340022aSzrj radix_strlen_t pos = 0;
1725340022aSzrj ldns_radix_node_t* add = NULL;
1735340022aSzrj ldns_radix_node_t* prefix = NULL;
1745340022aSzrj
1755340022aSzrj if (!tree || !key || !data) {
1765340022aSzrj return LDNS_STATUS_NULL;
1775340022aSzrj }
1785340022aSzrj add = ldns_radix_new_node(data, key, len);
1795340022aSzrj if (!add) {
1805340022aSzrj return LDNS_STATUS_MEM_ERR;
1815340022aSzrj }
1825340022aSzrj /** Search the trie until we can make no further process. */
1835340022aSzrj if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
1845340022aSzrj /** No prefix found */
1855340022aSzrj assert(tree->root == NULL);
1865340022aSzrj if (len == 0) {
1875340022aSzrj /**
1885340022aSzrj * Example 1: The root:
1895340022aSzrj * | [0]
1905340022aSzrj **/
1915340022aSzrj tree->root = add;
1925340022aSzrj } else {
1935340022aSzrj /** Example 2: 'dns':
1945340022aSzrj * | [0]
1955340022aSzrj * --| [d+ns] dns
1965340022aSzrj **/
1975340022aSzrj prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
1985340022aSzrj if (!prefix) {
1995340022aSzrj LDNS_FREE(add);
2005340022aSzrj return LDNS_STATUS_MEM_ERR;
2015340022aSzrj }
2025340022aSzrj /** Find some space in the array for the first byte */
2035340022aSzrj if (!ldns_radix_array_space(prefix, key[0])) {
2045340022aSzrj LDNS_FREE(add);
2055340022aSzrj LDNS_FREE(prefix->array);
2065340022aSzrj LDNS_FREE(prefix);
2075340022aSzrj return LDNS_STATUS_MEM_ERR;
2085340022aSzrj }
2095340022aSzrj /** Set relational pointers */
2105340022aSzrj add->parent = prefix;
2115340022aSzrj add->parent_index = 0;
2125340022aSzrj prefix->array[0].edge = add;
2135340022aSzrj if (len > 1) {
2145340022aSzrj /** Store the remainder of the prefix */
2155340022aSzrj if (!ldns_radix_prefix_remainder(1, key,
2165340022aSzrj len, &prefix->array[0].str,
2175340022aSzrj &prefix->array[0].len)) {
2185340022aSzrj LDNS_FREE(add);
2195340022aSzrj LDNS_FREE(prefix->array);
2205340022aSzrj LDNS_FREE(prefix);
2215340022aSzrj return LDNS_STATUS_MEM_ERR;
2225340022aSzrj }
2235340022aSzrj }
2245340022aSzrj tree->root = prefix;
2255340022aSzrj }
2265340022aSzrj } else if (pos == len) {
2275340022aSzrj /** Exact match found */
228819dec71SDaniel Fojt LDNS_FREE(add);
2295340022aSzrj if (prefix->data) {
2305340022aSzrj /* Element already exists */
2315340022aSzrj return LDNS_STATUS_EXISTS_ERR;
2325340022aSzrj }
2335340022aSzrj prefix->data = data;
2345340022aSzrj prefix->key = key;
2355340022aSzrj prefix->klen = len; /* redundant */
2365340022aSzrj } else {
2375340022aSzrj /** Prefix found */
2385340022aSzrj uint8_t byte = key[pos];
2395340022aSzrj assert(pos < len);
2405340022aSzrj if (byte < prefix->offset ||
2415340022aSzrj (byte - prefix->offset) >= prefix->len) {
2425340022aSzrj /** Find some space in the array for the byte. */
2435340022aSzrj /**
2445340022aSzrj * Example 3: 'ldns'
2455340022aSzrj * | [0]
2465340022aSzrj * --| [d+ns] dns
2475340022aSzrj * --| [l+dns] ldns
2485340022aSzrj **/
2495340022aSzrj if (!ldns_radix_array_space(prefix, byte)) {
2505340022aSzrj LDNS_FREE(add);
2515340022aSzrj return LDNS_STATUS_MEM_ERR;
2525340022aSzrj }
2535340022aSzrj assert(byte >= prefix->offset);
2545340022aSzrj assert((byte - prefix->offset) <= prefix->len);
2555340022aSzrj byte -= prefix->offset;
2565340022aSzrj if (pos+1 < len) {
2575340022aSzrj /** Create remainder of the string. */
2585340022aSzrj if (!ldns_radix_str_create(
2595340022aSzrj &prefix->array[byte], key, pos+1,
2605340022aSzrj len)) {
2615340022aSzrj LDNS_FREE(add);
2625340022aSzrj return LDNS_STATUS_MEM_ERR;
2635340022aSzrj }
2645340022aSzrj }
2655340022aSzrj /** Add new node. */
2665340022aSzrj add->parent = prefix;
2675340022aSzrj add->parent_index = byte;
2685340022aSzrj prefix->array[byte].edge = add;
2695340022aSzrj } else if (prefix->array[byte-prefix->offset].edge == NULL) {
2705340022aSzrj /** Use existing element. */
2715340022aSzrj /**
2725340022aSzrj * Example 4: 'edns'
2735340022aSzrj * | [0]
2745340022aSzrj * --| [d+ns] dns
2755340022aSzrj * --| [e+dns] edns
2765340022aSzrj * --| [l+dns] ldns
2775340022aSzrj **/
2785340022aSzrj byte -= prefix->offset;
2795340022aSzrj if (pos+1 < len) {
2805340022aSzrj /** Create remainder of the string. */
2815340022aSzrj if (!ldns_radix_str_create(
2825340022aSzrj &prefix->array[byte], key, pos+1,
2835340022aSzrj len)) {
2845340022aSzrj LDNS_FREE(add);
2855340022aSzrj return LDNS_STATUS_MEM_ERR;
2865340022aSzrj }
2875340022aSzrj }
2885340022aSzrj /** Add new node. */
2895340022aSzrj add->parent = prefix;
2905340022aSzrj add->parent_index = byte;
2915340022aSzrj prefix->array[byte].edge = add;
2925340022aSzrj } else {
2935340022aSzrj /**
2945340022aSzrj * Use existing element, but it has a shared prefix,
2955340022aSzrj * we need a split.
2965340022aSzrj */
2975340022aSzrj if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)],
2985340022aSzrj key, pos+1, len, add)) {
2995340022aSzrj LDNS_FREE(add);
3005340022aSzrj return LDNS_STATUS_MEM_ERR;
3015340022aSzrj }
3025340022aSzrj }
3035340022aSzrj }
3045340022aSzrj
3055340022aSzrj tree->count ++;
3065340022aSzrj return LDNS_STATUS_OK;
3075340022aSzrj }
3085340022aSzrj
3095340022aSzrj
3105340022aSzrj /**
3115340022aSzrj * Delete data from the tree.
3125340022aSzrj *
3135340022aSzrj */
ldns_radix_delete(ldns_radix_t * tree,const uint8_t * key,radix_strlen_t len)3145340022aSzrj void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len)
3155340022aSzrj {
3165340022aSzrj ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
3175340022aSzrj void* data = NULL;
3185340022aSzrj if (del) {
3195340022aSzrj tree->count--;
3205340022aSzrj data = del->data;
3215340022aSzrj del->data = NULL;
3225340022aSzrj ldns_radix_del_fix(tree, del);
3235340022aSzrj return data;
3245340022aSzrj }
3255340022aSzrj return NULL;
3265340022aSzrj }
3275340022aSzrj
3285340022aSzrj
3295340022aSzrj /**
3305340022aSzrj * Search data in the tree.
3315340022aSzrj *
3325340022aSzrj */
3335340022aSzrj ldns_radix_node_t*
ldns_radix_search(ldns_radix_t * tree,const uint8_t * key,radix_strlen_t len)3345340022aSzrj ldns_radix_search(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len)
3355340022aSzrj {
3365340022aSzrj ldns_radix_node_t* node = NULL;
3375340022aSzrj radix_strlen_t pos = 0;
3385340022aSzrj uint8_t byte = 0;
3395340022aSzrj
3405340022aSzrj if (!tree || !key) {
3415340022aSzrj return NULL;
3425340022aSzrj }
3435340022aSzrj node = tree->root;
3445340022aSzrj while (node) {
3455340022aSzrj if (pos == len) {
3465340022aSzrj return node->data?node:NULL;
3475340022aSzrj }
3485340022aSzrj byte = key[pos];
3495340022aSzrj if (byte < node->offset) {
3505340022aSzrj return NULL;
3515340022aSzrj }
3525340022aSzrj byte -= node->offset;
3535340022aSzrj if (byte >= node->len) {
3545340022aSzrj return NULL;
3555340022aSzrj }
3565340022aSzrj pos++;
3575340022aSzrj if (node->array[byte].len > 0) {
3585340022aSzrj /** Must match additional string. */
3595340022aSzrj if (pos + node->array[byte].len > len) {
3605340022aSzrj return NULL;
3615340022aSzrj }
3625340022aSzrj if (memcmp(&key[pos], node->array[byte].str,
3635340022aSzrj node->array[byte].len) != 0) {
3645340022aSzrj return NULL;
3655340022aSzrj }
3665340022aSzrj pos += node->array[byte].len;
3675340022aSzrj }
3685340022aSzrj node = node->array[byte].edge;
3695340022aSzrj }
3705340022aSzrj return NULL;
3715340022aSzrj }
3725340022aSzrj
3735340022aSzrj
3745340022aSzrj /**
3755340022aSzrj * Search data in the tree, and if not found, find the closest smaller
3765340022aSzrj * element in the tree.
3775340022aSzrj *
3785340022aSzrj */
3795340022aSzrj int
ldns_radix_find_less_equal(ldns_radix_t * tree,const uint8_t * key,radix_strlen_t len,ldns_radix_node_t ** result)3805340022aSzrj ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key,
3815340022aSzrj radix_strlen_t len, ldns_radix_node_t** result)
3825340022aSzrj {
3835340022aSzrj ldns_radix_node_t* node = NULL;
3845340022aSzrj radix_strlen_t pos = 0;
3855340022aSzrj uint8_t byte;
3865340022aSzrj int memcmp_res = 0;
3875340022aSzrj
3885340022aSzrj if (!tree || !tree->root || !key) {
3895340022aSzrj *result = NULL;
3905340022aSzrj return 0;
3915340022aSzrj }
3925340022aSzrj
3935340022aSzrj node = tree->root;
3945340022aSzrj while (pos < len) {
3955340022aSzrj byte = key[pos];
3965340022aSzrj if (byte < node->offset) {
3975340022aSzrj /**
3985340022aSzrj * No exact match. The lesser is in this or the
3995340022aSzrj * previous node.
4005340022aSzrj */
4015340022aSzrj ldns_radix_self_or_prev(node, result);
4025340022aSzrj return 0;
4035340022aSzrj }
4045340022aSzrj byte -= node->offset;
4055340022aSzrj if (byte >= node->len) {
4065340022aSzrj /**
4075340022aSzrj * No exact match. The lesser is in this node or the
4085340022aSzrj * last of this array, or something before this node.
4095340022aSzrj */
4105340022aSzrj *result = ldns_radix_last_in_subtree_incl_self(node);
4115340022aSzrj if (*result == NULL) {
4125340022aSzrj *result = ldns_radix_prev(node);
4135340022aSzrj }
4145340022aSzrj return 0;
4155340022aSzrj }
4165340022aSzrj pos++;
4175340022aSzrj if (!node->array[byte].edge) {
4185340022aSzrj /**
4195340022aSzrj * No exact match. Find the previous in the array
4205340022aSzrj * from this index.
4215340022aSzrj */
4225340022aSzrj *result = ldns_radix_prev_from_index(node, byte);
4235340022aSzrj if (*result == NULL) {
4245340022aSzrj ldns_radix_self_or_prev(node, result);
4255340022aSzrj }
4265340022aSzrj return 0;
4275340022aSzrj }
4285340022aSzrj if (node->array[byte].len != 0) {
4295340022aSzrj /** Must match additional string. */
4305340022aSzrj if (pos + node->array[byte].len > len) {
4315340022aSzrj /** Additional string is longer than key. */
4325340022aSzrj if (memcmp(&key[pos], node->array[byte].str,
4335340022aSzrj len-pos) <= 0) {
4345340022aSzrj /** Key is before this node. */
4355340022aSzrj *result = ldns_radix_prev(
4365340022aSzrj node->array[byte].edge);
4375340022aSzrj } else {
4385340022aSzrj /** Key is after additional string. */
4395340022aSzrj *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
4405340022aSzrj if (*result == NULL) {
4415340022aSzrj *result = ldns_radix_prev(node->array[byte].edge);
4425340022aSzrj }
4435340022aSzrj }
4445340022aSzrj return 0;
4455340022aSzrj }
4465340022aSzrj memcmp_res = memcmp(&key[pos], node->array[byte].str,
4475340022aSzrj node->array[byte].len);
4485340022aSzrj if (memcmp_res < 0) {
4495340022aSzrj *result = ldns_radix_prev(
4505340022aSzrj node->array[byte].edge);
4515340022aSzrj return 0;
4525340022aSzrj } else if (memcmp_res > 0) {
4535340022aSzrj *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
4545340022aSzrj if (*result == NULL) {
4555340022aSzrj *result = ldns_radix_prev(node->array[byte].edge);
4565340022aSzrj }
4575340022aSzrj return 0;
4585340022aSzrj }
4595340022aSzrj
4605340022aSzrj pos += node->array[byte].len;
4615340022aSzrj }
4625340022aSzrj node = node->array[byte].edge;
4635340022aSzrj }
4645340022aSzrj if (node->data) {
4655340022aSzrj /** Exact match. */
4665340022aSzrj *result = node;
4675340022aSzrj return 1;
4685340022aSzrj }
4695340022aSzrj /** There is a node which is an exact match, but has no element. */
4705340022aSzrj *result = ldns_radix_prev(node);
4715340022aSzrj return 0;
4725340022aSzrj }
4735340022aSzrj
4745340022aSzrj
4755340022aSzrj /**
4765340022aSzrj * Get the first element in the tree.
4775340022aSzrj *
4785340022aSzrj */
4795340022aSzrj ldns_radix_node_t*
ldns_radix_first(const ldns_radix_t * tree)4805340022aSzrj ldns_radix_first(const ldns_radix_t* tree)
4815340022aSzrj {
4825340022aSzrj ldns_radix_node_t* first = NULL;
4835340022aSzrj if (!tree || !tree->root) {
4845340022aSzrj return NULL;
4855340022aSzrj }
4865340022aSzrj first = tree->root;
4875340022aSzrj if (first->data) {
4885340022aSzrj return first;
4895340022aSzrj }
4905340022aSzrj return ldns_radix_next(first);
4915340022aSzrj }
4925340022aSzrj
4935340022aSzrj
4945340022aSzrj /**
4955340022aSzrj * Get the last element in the tree.
4965340022aSzrj *
4975340022aSzrj */
4985340022aSzrj ldns_radix_node_t*
ldns_radix_last(const ldns_radix_t * tree)4995340022aSzrj ldns_radix_last(const ldns_radix_t* tree)
5005340022aSzrj {
5015340022aSzrj if (!tree || !tree->root) {
5025340022aSzrj return NULL;
5035340022aSzrj }
5045340022aSzrj return ldns_radix_last_in_subtree_incl_self(tree->root);
5055340022aSzrj }
5065340022aSzrj
5075340022aSzrj
5085340022aSzrj /**
5095340022aSzrj * Next element.
5105340022aSzrj *
5115340022aSzrj */
5125340022aSzrj ldns_radix_node_t*
ldns_radix_next(ldns_radix_node_t * node)5135340022aSzrj ldns_radix_next(ldns_radix_node_t* node)
5145340022aSzrj {
5155340022aSzrj if (!node) {
5165340022aSzrj return NULL;
5175340022aSzrj }
5185340022aSzrj if (node->len) {
5195340022aSzrj /** Go down: most-left child is the next. */
5205340022aSzrj ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
5215340022aSzrj if (next) {
5225340022aSzrj return next;
5235340022aSzrj }
5245340022aSzrj }
5255340022aSzrj /** No elements in subtree, get to parent and go down next branch. */
5265340022aSzrj while (node->parent) {
5275340022aSzrj uint8_t index = node->parent_index;
5285340022aSzrj node = node->parent;
5295340022aSzrj index++;
5305340022aSzrj for (; index < node->len; index++) {
5315340022aSzrj if (node->array[index].edge) {
5325340022aSzrj ldns_radix_node_t* next;
5335340022aSzrj /** Node itself. */
5345340022aSzrj if (node->array[index].edge->data) {
5355340022aSzrj return node->array[index].edge;
5365340022aSzrj }
5375340022aSzrj /** Dive into subtree. */
5385340022aSzrj next = ldns_radix_next_in_subtree(node);
5395340022aSzrj if (next) {
5405340022aSzrj return next;
5415340022aSzrj }
5425340022aSzrj }
5435340022aSzrj }
5445340022aSzrj }
5455340022aSzrj return NULL;
5465340022aSzrj }
5475340022aSzrj
5485340022aSzrj
5495340022aSzrj /**
5505340022aSzrj * Previous element.
5515340022aSzrj *
5525340022aSzrj */
5535340022aSzrj ldns_radix_node_t*
ldns_radix_prev(ldns_radix_node_t * node)5545340022aSzrj ldns_radix_prev(ldns_radix_node_t* node)
5555340022aSzrj {
5565340022aSzrj if (!node) {
5575340022aSzrj return NULL;
5585340022aSzrj }
5595340022aSzrj
5605340022aSzrj /** Get to parent and go down previous branch. */
5615340022aSzrj while (node->parent) {
5625340022aSzrj uint8_t index = node->parent_index;
5635340022aSzrj ldns_radix_node_t* prev;
5645340022aSzrj node = node->parent;
5655340022aSzrj assert(node->len > 0);
5665340022aSzrj prev = ldns_radix_prev_from_index(node, index);
5675340022aSzrj if (prev) {
5685340022aSzrj return prev;
5695340022aSzrj }
5705340022aSzrj if (node->data) {
5715340022aSzrj return node;
5725340022aSzrj }
5735340022aSzrj }
5745340022aSzrj return NULL;
5755340022aSzrj }
5765340022aSzrj
5775340022aSzrj
5785340022aSzrj /**
5795340022aSzrj * Print node.
5805340022aSzrj *
5815340022aSzrj */
5825340022aSzrj static void
ldns_radix_node_print(FILE * fd,ldns_radix_node_t * node,uint8_t i,uint8_t * str,radix_strlen_t len,unsigned d)5835340022aSzrj ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node,
5845340022aSzrj uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d)
5855340022aSzrj {
5865340022aSzrj uint8_t j;
5875340022aSzrj if (!node) {
5885340022aSzrj return;
5895340022aSzrj }
5905340022aSzrj for (j = 0; j < d; j++) {
5915340022aSzrj fprintf(fd, "--");
5925340022aSzrj }
5935340022aSzrj if (str) {
5945340022aSzrj radix_strlen_t l;
5955340022aSzrj fprintf(fd, "| [%u+", (unsigned) i);
5965340022aSzrj for (l=0; l < len; l++) {
5975340022aSzrj fprintf(fd, "%c", (char) str[l]);
5985340022aSzrj }
5995340022aSzrj fprintf(fd, "]%u", (unsigned) len);
6005340022aSzrj } else {
6015340022aSzrj fprintf(fd, "| [%u]", (unsigned) i);
6025340022aSzrj }
6035340022aSzrj
6045340022aSzrj if (node->data) {
6055340022aSzrj fprintf(fd, " %s", (char*) node->data);
6065340022aSzrj }
6075340022aSzrj fprintf(fd, "\n");
6085340022aSzrj
6095340022aSzrj for (j = 0; j < node->len; j++) {
6105340022aSzrj if (node->array[j].edge) {
6115340022aSzrj ldns_radix_node_print(fd, node->array[j].edge, j,
6125340022aSzrj node->array[j].str, node->array[j].len, d+1);
6135340022aSzrj }
6145340022aSzrj }
6155340022aSzrj return;
6165340022aSzrj }
6175340022aSzrj
6185340022aSzrj
6195340022aSzrj /**
6205340022aSzrj * Print radix tree.
6215340022aSzrj *
6225340022aSzrj */
6235340022aSzrj void
ldns_radix_printf(FILE * fd,const ldns_radix_t * tree)6245340022aSzrj ldns_radix_printf(FILE* fd, const ldns_radix_t* tree)
6255340022aSzrj {
6265340022aSzrj if (!fd || !tree) {
6275340022aSzrj return;
6285340022aSzrj }
6295340022aSzrj if (!tree->root) {
6305340022aSzrj fprintf(fd, "; empty radix tree\n");
6315340022aSzrj return;
6325340022aSzrj }
6335340022aSzrj ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0);
6345340022aSzrj return;
6355340022aSzrj }
6365340022aSzrj
6375340022aSzrj
6385340022aSzrj /**
6395340022aSzrj * Join two radix trees.
6405340022aSzrj *
6415340022aSzrj */
6425340022aSzrj ldns_status
ldns_radix_join(ldns_radix_t * tree1,ldns_radix_t * tree2)6435340022aSzrj ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2)
6445340022aSzrj {
6455340022aSzrj ldns_radix_node_t* cur_node, *next_node;
6465340022aSzrj ldns_status status;
6475340022aSzrj if (!tree2 || !tree2->root) {
6485340022aSzrj return LDNS_STATUS_OK;
6495340022aSzrj }
6505340022aSzrj /** Add all elements from tree2 into tree1. */
6515340022aSzrj
6525340022aSzrj cur_node = ldns_radix_first(tree2);
6535340022aSzrj while (cur_node) {
6545340022aSzrj status = LDNS_STATUS_NO_DATA;
6555340022aSzrj /** Insert current node into tree1 */
6565340022aSzrj if (cur_node->data) {
6575340022aSzrj status = ldns_radix_insert(tree1, cur_node->key,
6585340022aSzrj cur_node->klen, cur_node->data);
6595340022aSzrj /** Exist errors may occur */
6605340022aSzrj if (status != LDNS_STATUS_OK &&
6615340022aSzrj status != LDNS_STATUS_EXISTS_ERR) {
6625340022aSzrj return status;
6635340022aSzrj }
6645340022aSzrj }
6655340022aSzrj next_node = ldns_radix_next(cur_node);
6665340022aSzrj if (status == LDNS_STATUS_OK) {
6675340022aSzrj (void) ldns_radix_delete(tree2, cur_node->key,
6685340022aSzrj cur_node->klen);
6695340022aSzrj }
6705340022aSzrj cur_node = next_node;
6715340022aSzrj }
6725340022aSzrj
6735340022aSzrj return LDNS_STATUS_OK;
6745340022aSzrj }
6755340022aSzrj
6765340022aSzrj
6775340022aSzrj /**
6785340022aSzrj * Split a radix tree intwo.
6795340022aSzrj *
6805340022aSzrj */
6815340022aSzrj ldns_status
ldns_radix_split(ldns_radix_t * tree1,size_t num,ldns_radix_t ** tree2)6825340022aSzrj ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2)
6835340022aSzrj {
6845340022aSzrj size_t count = 0;
6855340022aSzrj ldns_radix_node_t* cur_node;
6865340022aSzrj ldns_status status = LDNS_STATUS_OK;
6875340022aSzrj if (!tree1 || !tree1->root || num == 0) {
6885340022aSzrj return LDNS_STATUS_OK;
6895340022aSzrj }
6905340022aSzrj if (!tree2) {
6915340022aSzrj return LDNS_STATUS_NULL;
6925340022aSzrj }
6935340022aSzrj if (!*tree2) {
6945340022aSzrj *tree2 = ldns_radix_create();
6955340022aSzrj if (!*tree2) {
6965340022aSzrj return LDNS_STATUS_MEM_ERR;
6975340022aSzrj }
6985340022aSzrj }
6995340022aSzrj cur_node = ldns_radix_first(tree1);
7005340022aSzrj while (count < num && cur_node) {
7015340022aSzrj if (cur_node->data) {
7025340022aSzrj /** Delete current node from tree1. */
7035340022aSzrj uint8_t* cur_key = cur_node->key;
7045340022aSzrj radix_strlen_t cur_len = cur_node->klen;
7055340022aSzrj void* cur_data = ldns_radix_delete(tree1, cur_key,
7065340022aSzrj cur_len);
7075340022aSzrj /** Insert current node into tree2/ */
7085340022aSzrj if (!cur_data) {
7095340022aSzrj return LDNS_STATUS_NO_DATA;
7105340022aSzrj }
7115340022aSzrj status = ldns_radix_insert(*tree2, cur_key, cur_len,
7125340022aSzrj cur_data);
7135340022aSzrj if (status != LDNS_STATUS_OK &&
7145340022aSzrj status != LDNS_STATUS_EXISTS_ERR) {
7155340022aSzrj return status;
7165340022aSzrj }
7175340022aSzrj /*
7185340022aSzrj if (status == LDNS_STATUS_OK) {
7195340022aSzrj cur_node->key = NULL;
7205340022aSzrj cur_node->klen = 0;
7215340022aSzrj }
7225340022aSzrj */
7235340022aSzrj /** Update count; get first element from tree1 again. */
7245340022aSzrj count++;
7255340022aSzrj cur_node = ldns_radix_first(tree1);
7265340022aSzrj } else {
7275340022aSzrj cur_node = ldns_radix_next(cur_node);
7285340022aSzrj }
7295340022aSzrj }
7305340022aSzrj return LDNS_STATUS_OK;
7315340022aSzrj }
7325340022aSzrj
7335340022aSzrj
7345340022aSzrj /**
7355340022aSzrj * Call function for all nodes in the tree, such that leaf nodes are
7365340022aSzrj * called before parent nodes.
7375340022aSzrj *
7385340022aSzrj */
7395340022aSzrj void
ldns_radix_traverse_postorder(ldns_radix_node_t * node,void (* func)(ldns_radix_node_t *,void *),void * arg)7405340022aSzrj ldns_radix_traverse_postorder(ldns_radix_node_t* node,
7415340022aSzrj void (*func)(ldns_radix_node_t*, void*), void* arg)
7425340022aSzrj {
7435340022aSzrj uint8_t i;
7445340022aSzrj if (!node) {
7455340022aSzrj return;
7465340022aSzrj }
7475340022aSzrj for (i=0; i < node->len; i++) {
7485340022aSzrj ldns_radix_traverse_postorder(node->array[i].edge,
7495340022aSzrj func, arg);
7505340022aSzrj }
7515340022aSzrj /** Call user function */
7525340022aSzrj (*func)(node, arg);
7535340022aSzrj return;
7545340022aSzrj }
7555340022aSzrj
7565340022aSzrj
7575340022aSzrj /** Static helper functions */
7585340022aSzrj
7595340022aSzrj /**
7605340022aSzrj * Find a prefix of the key.
7615340022aSzrj * @param tree: tree.
7625340022aSzrj * @param key: key.
7635340022aSzrj * @param len: length of key.
7645340022aSzrj * @param result: the longest prefix, the entry itself if *pos==len,
7655340022aSzrj * otherwise an array entry.
7665340022aSzrj * @param pos: position in string where next unmatched byte is.
7675340022aSzrj * If *pos==len, an exact match is found.
7685340022aSzrj * If *pos== 0, a "" match was found.
7695340022aSzrj * @return 0 (false) if no prefix found.
7705340022aSzrj *
7715340022aSzrj */
7725340022aSzrj static int
ldns_radix_find_prefix(ldns_radix_t * tree,uint8_t * key,radix_strlen_t len,ldns_radix_node_t ** result,radix_strlen_t * respos)7735340022aSzrj ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
7745340022aSzrj radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos)
7755340022aSzrj {
7765340022aSzrj /** Start searching at the root node */
7775340022aSzrj ldns_radix_node_t* n = tree->root;
7785340022aSzrj radix_strlen_t pos = 0;
7795340022aSzrj uint8_t byte;
7805340022aSzrj *respos = 0;
7815340022aSzrj *result = n;
7825340022aSzrj if (!n) {
7835340022aSzrj /** No root, no prefix found */
7845340022aSzrj return 0;
7855340022aSzrj }
7865340022aSzrj /** For each node, look if we can make further progress */
7875340022aSzrj while (n) {
7885340022aSzrj if (pos == len) {
7895340022aSzrj /** Exact match */
7905340022aSzrj return 1;
7915340022aSzrj }
7925340022aSzrj byte = key[pos];
7935340022aSzrj if (byte < n->offset) {
7945340022aSzrj /** key < node */
7955340022aSzrj return 1;
7965340022aSzrj }
7975340022aSzrj byte -= n->offset;
7985340022aSzrj if (byte >= n->len) {
7995340022aSzrj /** key > node */
8005340022aSzrj return 1;
8015340022aSzrj }
8025340022aSzrj /** So far, the trie matches */
8035340022aSzrj pos++;
8045340022aSzrj if (n->array[byte].len != 0) {
8055340022aSzrj /** Must match additional string */
8065340022aSzrj if (pos + n->array[byte].len > len) {
8075340022aSzrj return 1; /* no match at child node */
8085340022aSzrj }
8095340022aSzrj if (memcmp(&key[pos], n->array[byte].str,
8105340022aSzrj n->array[byte].len) != 0) {
8115340022aSzrj return 1; /* no match at child node */
8125340022aSzrj }
8135340022aSzrj pos += n->array[byte].len;
8145340022aSzrj }
8155340022aSzrj /** Continue searching prefix at this child node */
8165340022aSzrj n = n->array[byte].edge;
8175340022aSzrj if (!n) {
8185340022aSzrj return 1;
8195340022aSzrj }
8205340022aSzrj /** Update the prefix node */
8215340022aSzrj *respos = pos;
8225340022aSzrj *result = n;
8235340022aSzrj }
8245340022aSzrj /** Done */
8255340022aSzrj return 1;
8265340022aSzrj }
8275340022aSzrj
8285340022aSzrj
8295340022aSzrj /**
8305340022aSzrj * Make space in the node's array for another byte.
8315340022aSzrj * @param node: node.
8325340022aSzrj * @param byte: byte.
8335340022aSzrj * @return 1 if successful, 0 otherwise.
8345340022aSzrj *
8355340022aSzrj */
8365340022aSzrj static int
ldns_radix_array_space(ldns_radix_node_t * node,uint8_t byte)8375340022aSzrj ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
8385340022aSzrj {
8395340022aSzrj /** Is there an array? */
8405340022aSzrj if (!node->array) {
8415340022aSzrj assert(node->capacity == 0);
8425340022aSzrj /** No array, create new array */
8435340022aSzrj node->array = LDNS_MALLOC(ldns_radix_array_t);
8445340022aSzrj if (!node->array) {
8455340022aSzrj return 0;
8465340022aSzrj }
8475340022aSzrj memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
8485340022aSzrj node->len = 1;
8495340022aSzrj node->capacity = 1;
8505340022aSzrj node->offset = byte;
8515340022aSzrj return 1;
8525340022aSzrj }
8535340022aSzrj /** Array exist */
8545340022aSzrj assert(node->array != NULL);
8555340022aSzrj assert(node->capacity > 0);
8565340022aSzrj
8575340022aSzrj if (node->len == 0) {
8585340022aSzrj /** Unused array */
8595340022aSzrj node->len = 1;
8605340022aSzrj node->offset = byte;
8615340022aSzrj } else if (byte < node->offset) {
8625340022aSzrj /** Byte is below the offset */
8635340022aSzrj uint8_t index;
8645340022aSzrj uint16_t need = node->offset - byte;
8655340022aSzrj /** Is there enough capacity? */
8665340022aSzrj if (node->len + need > node->capacity) {
8675340022aSzrj /** Not enough capacity, grow array */
8685340022aSzrj if (!ldns_radix_array_grow(node,
8695340022aSzrj (unsigned) (node->len + need))) {
8705340022aSzrj return 0; /* failed to grow array */
8715340022aSzrj }
8725340022aSzrj }
8735340022aSzrj /** Move items to the end */
8745340022aSzrj memmove(&node->array[need], &node->array[0],
8755340022aSzrj node->len*sizeof(ldns_radix_array_t));
8765340022aSzrj /** Fix parent index */
8775340022aSzrj for (index = 0; index < node->len; index++) {
8785340022aSzrj if (node->array[index+need].edge) {
8795340022aSzrj node->array[index+need].edge->parent_index =
8805340022aSzrj index + need;
8815340022aSzrj }
8825340022aSzrj }
8835340022aSzrj /** Zero the first */
8845340022aSzrj memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));
8855340022aSzrj node->len += need;
8865340022aSzrj node->offset = byte;
8875340022aSzrj } else if (byte - node->offset >= node->len) {
8885340022aSzrj /** Byte does not fit in array */
8895340022aSzrj uint16_t need = (byte - node->offset) - node->len + 1;
8905340022aSzrj /** Is there enough capacity? */
8915340022aSzrj if (node->len + need > node->capacity) {
8925340022aSzrj /** Not enough capacity, grow array */
8935340022aSzrj if (!ldns_radix_array_grow(node,
8945340022aSzrj (unsigned) (node->len + need))) {
8955340022aSzrj return 0; /* failed to grow array */
8965340022aSzrj }
8975340022aSzrj }
8985340022aSzrj /** Zero the added items */
8995340022aSzrj memset(&node->array[node->len], 0,
9005340022aSzrj need*sizeof(ldns_radix_array_t));
9015340022aSzrj node->len += need;
9025340022aSzrj }
9035340022aSzrj return 1;
9045340022aSzrj }
9055340022aSzrj
9065340022aSzrj
9075340022aSzrj /**
9085340022aSzrj * Grow the array.
9095340022aSzrj * @param node: node.
9105340022aSzrj * @param need: number of elements the array at least need to grow.
9115340022aSzrj * Can't be bigger than 256.
9125340022aSzrj * @return: 0 if failed, 1 if was successful.
9135340022aSzrj *
9145340022aSzrj */
9155340022aSzrj static int
ldns_radix_array_grow(ldns_radix_node_t * node,unsigned need)9165340022aSzrj ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
9175340022aSzrj {
9185340022aSzrj unsigned size = ((unsigned)node->capacity)*2;
9195340022aSzrj ldns_radix_array_t* a = NULL;
9205340022aSzrj if (need > size) {
9215340022aSzrj size = need;
9225340022aSzrj }
9235340022aSzrj if (size > 256) {
9245340022aSzrj size = 256;
9255340022aSzrj }
9265340022aSzrj a = LDNS_XMALLOC(ldns_radix_array_t, size);
9275340022aSzrj if (!a) {
9285340022aSzrj return 0;
9295340022aSzrj }
9305340022aSzrj assert(node->len <= node->capacity);
9315340022aSzrj assert(node->capacity < size);
9325340022aSzrj memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));
9335340022aSzrj LDNS_FREE(node->array);
9345340022aSzrj node->array = a;
9355340022aSzrj node->capacity = size;
9365340022aSzrj return 1;
9375340022aSzrj }
9385340022aSzrj
9395340022aSzrj
9405340022aSzrj /**
9415340022aSzrj * Create a prefix in the array string.
9425340022aSzrj * @param array: array.
9435340022aSzrj * @param key: key.
9445340022aSzrj * @param pos: start position in key.
9455340022aSzrj * @param len: length of key.
9465340022aSzrj * @return 0 if failed, 1 if was successful.
9475340022aSzrj *
9485340022aSzrj */
9495340022aSzrj static int
ldns_radix_str_create(ldns_radix_array_t * array,uint8_t * key,radix_strlen_t pos,radix_strlen_t len)9505340022aSzrj ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
9515340022aSzrj radix_strlen_t pos, radix_strlen_t len)
9525340022aSzrj {
9535340022aSzrj array->str = LDNS_XMALLOC(uint8_t, (len-pos));
9545340022aSzrj if (!array->str) {
9555340022aSzrj return 0;
9565340022aSzrj }
9575340022aSzrj memmove(array->str, key+pos, len-pos);
9585340022aSzrj array->len = (len-pos);
9595340022aSzrj return 1;
9605340022aSzrj }
9615340022aSzrj
9625340022aSzrj
9635340022aSzrj /**
9645340022aSzrj * Allocate remainder from prefixes for a split.
9655340022aSzrj * @param prefixlen: length of prefix.
9665340022aSzrj * @param longer_str: the longer string.
9675340022aSzrj * @param longer_len: the longer string length.
9685340022aSzrj * @param split_str: the split string.
9695340022aSzrj * @param split_len: the split string length.
9705340022aSzrj * @return 0 if failed, 1 if successful.
9715340022aSzrj *
9725340022aSzrj */
9735340022aSzrj static int
ldns_radix_prefix_remainder(radix_strlen_t prefix_len,uint8_t * longer_str,radix_strlen_t longer_len,uint8_t ** split_str,radix_strlen_t * split_len)9745340022aSzrj ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
9755340022aSzrj uint8_t* longer_str, radix_strlen_t longer_len,
9765340022aSzrj uint8_t** split_str, radix_strlen_t* split_len)
9775340022aSzrj {
9785340022aSzrj *split_len = longer_len - prefix_len;
9795340022aSzrj *split_str = LDNS_XMALLOC(uint8_t, (*split_len));
9805340022aSzrj if (!*split_str) {
9815340022aSzrj return 0;
9825340022aSzrj }
9835340022aSzrj memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len);
9845340022aSzrj return 1;
9855340022aSzrj }
9865340022aSzrj
9875340022aSzrj
9885340022aSzrj /**
9895340022aSzrj * Create a split when two nodes have a shared prefix.
9905340022aSzrj * @param array: array.
9915340022aSzrj * @param key: key.
9925340022aSzrj * @param pos: start position in key.
9935340022aSzrj * @param len: length of the key.
9945340022aSzrj * @param add: node to be added.
9955340022aSzrj * @return 0 if failed, 1 if was successful.
9965340022aSzrj *
9975340022aSzrj */
9985340022aSzrj static int
ldns_radix_array_split(ldns_radix_array_t * array,uint8_t * key,radix_strlen_t pos,radix_strlen_t len,ldns_radix_node_t * add)9995340022aSzrj ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
10005340022aSzrj radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add)
10015340022aSzrj {
10025340022aSzrj uint8_t* str_to_add = key + pos;
10035340022aSzrj radix_strlen_t strlen_to_add = len - pos;
10045340022aSzrj
10055340022aSzrj if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add,
10065340022aSzrj array->str, array->len)) {
10075340022aSzrj /** The string to add is a prefix of the existing string */
10085340022aSzrj uint8_t* split_str = NULL, *dup_str = NULL;
10095340022aSzrj radix_strlen_t split_len = 0;
10105340022aSzrj /**
10115340022aSzrj * Example 5: 'ld'
10125340022aSzrj * | [0]
10135340022aSzrj * --| [d+ns] dns
10145340022aSzrj * --| [e+dns] edns
10155340022aSzrj * --| [l+d] ld
10165340022aSzrj * ----| [n+s] ldns
10175340022aSzrj **/
10185340022aSzrj assert(strlen_to_add < array->len);
10195340022aSzrj /** Store the remainder in the split string */
10205340022aSzrj if (array->len - strlen_to_add > 1) {
10215340022aSzrj if (!ldns_radix_prefix_remainder(strlen_to_add+1,
10225340022aSzrj array->str, array->len, &split_str,
10235340022aSzrj &split_len)) {
10245340022aSzrj return 0;
10255340022aSzrj }
10265340022aSzrj }
10275340022aSzrj /** Duplicate the string to add */
10285340022aSzrj if (strlen_to_add != 0) {
10295340022aSzrj dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add);
10305340022aSzrj if (!dup_str) {
10315340022aSzrj LDNS_FREE(split_str);
10325340022aSzrj return 0;
10335340022aSzrj }
10345340022aSzrj memcpy(dup_str, str_to_add, strlen_to_add);
10355340022aSzrj }
10365340022aSzrj /** Make space in array for the new node */
10375340022aSzrj if (!ldns_radix_array_space(add,
10385340022aSzrj array->str[strlen_to_add])) {
10395340022aSzrj LDNS_FREE(split_str);
10405340022aSzrj LDNS_FREE(dup_str);
10415340022aSzrj return 0;
10425340022aSzrj }
10435340022aSzrj /**
10445340022aSzrj * The added node should go direct under the existing parent.
10455340022aSzrj * The existing node should go under the added node.
10465340022aSzrj */
10475340022aSzrj add->parent = array->edge->parent;
10485340022aSzrj add->parent_index = array->edge->parent_index;
10495340022aSzrj add->array[0].edge = array->edge;
10505340022aSzrj add->array[0].str = split_str;
10515340022aSzrj add->array[0].len = split_len;
10525340022aSzrj array->edge->parent = add;
10535340022aSzrj array->edge->parent_index = 0;
10545340022aSzrj LDNS_FREE(array->str);
10555340022aSzrj array->edge = add;
10565340022aSzrj array->str = dup_str;
10575340022aSzrj array->len = strlen_to_add;
10585340022aSzrj } else if (ldns_radix_str_is_prefix(array->str, array->len,
10595340022aSzrj str_to_add, strlen_to_add)) {
10605340022aSzrj /** The existing string is a prefix of the string to add */
10615340022aSzrj /**
10625340022aSzrj * Example 6: 'dns-ng'
10635340022aSzrj * | [0]
10645340022aSzrj * --| [d+ns] dns
10655340022aSzrj * ----| [-+ng] dns-ng
10665340022aSzrj * --| [e+dns] edns
10675340022aSzrj * --| [l+d] ld
10685340022aSzrj * ----| [n+s] ldns
10695340022aSzrj **/
10705340022aSzrj uint8_t* split_str = NULL;
10715340022aSzrj radix_strlen_t split_len = 0;
10725340022aSzrj assert(array->len < strlen_to_add);
10735340022aSzrj if (strlen_to_add - array->len > 1) {
10745340022aSzrj if (!ldns_radix_prefix_remainder(array->len+1,
10755340022aSzrj str_to_add, strlen_to_add, &split_str,
10765340022aSzrj &split_len)) {
10775340022aSzrj return 0;
10785340022aSzrj }
10795340022aSzrj }
10805340022aSzrj /** Make space in array for the new node */
10815340022aSzrj if (!ldns_radix_array_space(array->edge,
10825340022aSzrj str_to_add[array->len])) {
10835340022aSzrj LDNS_FREE(split_str);
10845340022aSzrj return 0;
10855340022aSzrj }
10865340022aSzrj /**
10875340022aSzrj * The added node should go direct under the existing node.
10885340022aSzrj */
10895340022aSzrj add->parent = array->edge;
10905340022aSzrj add->parent_index = str_to_add[array->len] -
10915340022aSzrj array->edge->offset;
10925340022aSzrj array->edge->array[add->parent_index].edge = add;
10935340022aSzrj array->edge->array[add->parent_index].str = split_str;
10945340022aSzrj array->edge->array[add->parent_index].len = split_len;
10955340022aSzrj } else {
10965340022aSzrj /** Create a new split node. */
10975340022aSzrj /**
10985340022aSzrj * Example 7: 'dndns'
10995340022aSzrj * | [0]
11005340022aSzrj * --| [d+n]
11015340022aSzrj * ----| [d+ns] dndns
11025340022aSzrj * ----| [s] dns
11035340022aSzrj * ------| [-+ng] dns-ng
11045340022aSzrj * --| [e+dns] edns
11055340022aSzrj * --| [l+d] ld
11065340022aSzrj * ----| [n+s] ldns
11075340022aSzrj **/
11085340022aSzrj ldns_radix_node_t* common = NULL;
11095340022aSzrj uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL;
11105340022aSzrj radix_strlen_t common_len = 0, l1 = 0, l2 = 0;
11115340022aSzrj common_len = ldns_radix_str_common(array->str, array->len,
11125340022aSzrj str_to_add, strlen_to_add);
11135340022aSzrj assert(common_len < array->len);
11145340022aSzrj assert(common_len < strlen_to_add);
11155340022aSzrj /** Create the new common node. */
11165340022aSzrj common = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
11175340022aSzrj if (!common) {
11185340022aSzrj return 0;
11195340022aSzrj }
11205340022aSzrj if (array->len - common_len > 1) {
11215340022aSzrj if (!ldns_radix_prefix_remainder(common_len+1,
11225340022aSzrj array->str, array->len, &s1, &l1)) {
1123819dec71SDaniel Fojt LDNS_FREE(common);
11245340022aSzrj return 0;
11255340022aSzrj }
11265340022aSzrj }
11275340022aSzrj if (strlen_to_add - common_len > 1) {
11285340022aSzrj if (!ldns_radix_prefix_remainder(common_len+1,
11295340022aSzrj str_to_add, strlen_to_add, &s2, &l2)) {
1130819dec71SDaniel Fojt LDNS_FREE(common);
1131819dec71SDaniel Fojt LDNS_FREE(s1);
11325340022aSzrj return 0;
11335340022aSzrj }
11345340022aSzrj }
11355340022aSzrj /** Create the shared prefix. */
11365340022aSzrj if (common_len > 0) {
11375340022aSzrj common_str = LDNS_XMALLOC(uint8_t, common_len);
11385340022aSzrj if (!common_str) {
11395340022aSzrj LDNS_FREE(common);
11405340022aSzrj LDNS_FREE(s1);
11415340022aSzrj LDNS_FREE(s2);
11425340022aSzrj return 0;
11435340022aSzrj }
11445340022aSzrj memcpy(common_str, str_to_add, common_len);
11455340022aSzrj }
11465340022aSzrj /** Make space in the common node array. */
11475340022aSzrj if (!ldns_radix_array_space(common, array->str[common_len]) ||
11485340022aSzrj !ldns_radix_array_space(common, str_to_add[common_len])) {
11495340022aSzrj LDNS_FREE(common->array);
11505340022aSzrj LDNS_FREE(common);
11515340022aSzrj LDNS_FREE(common_str);
11525340022aSzrj LDNS_FREE(s1);
11535340022aSzrj LDNS_FREE(s2);
11545340022aSzrj return 0;
11555340022aSzrj }
11565340022aSzrj /**
11575340022aSzrj * The common node should go direct under the parent node.
11585340022aSzrj * The added and existing nodes go under the common node.
11595340022aSzrj */
11605340022aSzrj common->parent = array->edge->parent;
11615340022aSzrj common->parent_index = array->edge->parent_index;
11625340022aSzrj array->edge->parent = common;
11635340022aSzrj array->edge->parent_index = array->str[common_len] -
11645340022aSzrj common->offset;
11655340022aSzrj add->parent = common;
11665340022aSzrj add->parent_index = str_to_add[common_len] - common->offset;
11675340022aSzrj common->array[array->edge->parent_index].edge = array->edge;
11685340022aSzrj common->array[array->edge->parent_index].str = s1;
11695340022aSzrj common->array[array->edge->parent_index].len = l1;
11705340022aSzrj common->array[add->parent_index].edge = add;
11715340022aSzrj common->array[add->parent_index].str = s2;
11725340022aSzrj common->array[add->parent_index].len = l2;
11735340022aSzrj LDNS_FREE(array->str);
11745340022aSzrj array->edge = common;
11755340022aSzrj array->str = common_str;
11765340022aSzrj array->len = common_len;
11775340022aSzrj }
11785340022aSzrj return 1;
11795340022aSzrj }
11805340022aSzrj
11815340022aSzrj
11825340022aSzrj /**
11835340022aSzrj * Check if one string prefix of other string.
11845340022aSzrj * @param str1: one string.
11855340022aSzrj * @param len1: one string length.
11865340022aSzrj * @param str2: other string.
11875340022aSzrj * @param len2: other string length.
11885340022aSzrj * @return 1 if prefix, 0 otherwise.
11895340022aSzrj *
11905340022aSzrj */
11915340022aSzrj static int
ldns_radix_str_is_prefix(uint8_t * str1,radix_strlen_t len1,uint8_t * str2,radix_strlen_t len2)11925340022aSzrj ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
11935340022aSzrj uint8_t* str2, radix_strlen_t len2)
11945340022aSzrj {
11955340022aSzrj if (len1 == 0) {
11965340022aSzrj return 1; /* empty prefix is also a prefix */
11975340022aSzrj }
11985340022aSzrj if (len1 > len2) {
11995340022aSzrj return 0; /* len1 is longer so str1 cannot be a prefix */
12005340022aSzrj }
12015340022aSzrj return (memcmp(str1, str2, len1) == 0);
12025340022aSzrj }
12035340022aSzrj
12045340022aSzrj
12055340022aSzrj /**
12065340022aSzrj * Return the number of bytes in common for the two strings.
12075340022aSzrj * @param str1: one string.
12085340022aSzrj * @param len1: one string length.
12095340022aSzrj * @param str2: other string.
12105340022aSzrj * @param len2: other string length.
12115340022aSzrj * @return length of substring that the two strings have in common.
12125340022aSzrj *
12135340022aSzrj */
12145340022aSzrj static radix_strlen_t
ldns_radix_str_common(uint8_t * str1,radix_strlen_t len1,uint8_t * str2,radix_strlen_t len2)12155340022aSzrj ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
12165340022aSzrj uint8_t* str2, radix_strlen_t len2)
12175340022aSzrj {
12185340022aSzrj radix_strlen_t i, max = (len1<len2)?len1:len2;
12195340022aSzrj for (i=0; i<max; i++) {
12205340022aSzrj if (str1[i] != str2[i]) {
12215340022aSzrj return i;
12225340022aSzrj }
12235340022aSzrj }
12245340022aSzrj return max;
12255340022aSzrj }
12265340022aSzrj
12275340022aSzrj
12285340022aSzrj /**
12295340022aSzrj * Find the next element in the subtree of this node.
12305340022aSzrj * @param node: node.
12315340022aSzrj * @return: node with next element.
12325340022aSzrj *
12335340022aSzrj */
12345340022aSzrj static ldns_radix_node_t*
ldns_radix_next_in_subtree(ldns_radix_node_t * node)12355340022aSzrj ldns_radix_next_in_subtree(ldns_radix_node_t* node)
12365340022aSzrj {
12375340022aSzrj uint16_t i;
12385340022aSzrj ldns_radix_node_t* next;
12395340022aSzrj /** Try every subnode. */
12405340022aSzrj for (i = 0; i < node->len; i++) {
12415340022aSzrj if (node->array[i].edge) {
12425340022aSzrj /** Node itself. */
12435340022aSzrj if (node->array[i].edge->data) {
12445340022aSzrj return node->array[i].edge;
12455340022aSzrj }
12465340022aSzrj /** Dive into subtree. */
12475340022aSzrj next = ldns_radix_next_in_subtree(node->array[i].edge);
12485340022aSzrj if (next) {
12495340022aSzrj return next;
12505340022aSzrj }
12515340022aSzrj }
12525340022aSzrj }
12535340022aSzrj return NULL;
12545340022aSzrj }
12555340022aSzrj
12565340022aSzrj
12575340022aSzrj /**
12585340022aSzrj * Find the previous element in the array of this node, from index.
12595340022aSzrj * @param node: node.
12605340022aSzrj * @param index: index.
12615340022aSzrj * @return previous node from index.
12625340022aSzrj *
12635340022aSzrj */
12645340022aSzrj static ldns_radix_node_t*
ldns_radix_prev_from_index(ldns_radix_node_t * node,uint8_t index)12655340022aSzrj ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
12665340022aSzrj {
12675340022aSzrj uint8_t i = index;
12685340022aSzrj while (i > 0) {
12695340022aSzrj i--;
12705340022aSzrj if (node->array[i].edge) {
12715340022aSzrj ldns_radix_node_t* prev =
12725340022aSzrj ldns_radix_last_in_subtree_incl_self(node);
12735340022aSzrj if (prev) {
12745340022aSzrj return prev;
12755340022aSzrj }
12765340022aSzrj }
12775340022aSzrj }
12785340022aSzrj return NULL;
12795340022aSzrj }
12805340022aSzrj
12815340022aSzrj
12825340022aSzrj /**
12835340022aSzrj * Find last node in subtree, or this node (if have data).
12845340022aSzrj * @param node: node.
12855340022aSzrj * @return last node in subtree, or this node, or NULL.
12865340022aSzrj *
12875340022aSzrj */
12885340022aSzrj static ldns_radix_node_t*
ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t * node)12895340022aSzrj ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
12905340022aSzrj {
12915340022aSzrj ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
12925340022aSzrj if (last) {
12935340022aSzrj return last;
12945340022aSzrj } else if (node->data) {
12955340022aSzrj return node;
12965340022aSzrj }
12975340022aSzrj return NULL;
12985340022aSzrj }
12995340022aSzrj
13005340022aSzrj
13015340022aSzrj /**
13025340022aSzrj * Find last node in subtree.
13035340022aSzrj * @param node: node.
13045340022aSzrj * @return last node in subtree.
13055340022aSzrj *
13065340022aSzrj */
13075340022aSzrj static ldns_radix_node_t*
ldns_radix_last_in_subtree(ldns_radix_node_t * node)13085340022aSzrj ldns_radix_last_in_subtree(ldns_radix_node_t* node)
13095340022aSzrj {
13105340022aSzrj int i;
13115340022aSzrj /** Look for the most right leaf node. */
13125340022aSzrj for (i=(int)(node->len)-1; i >= 0; i--) {
13135340022aSzrj if (node->array[i].edge) {
13145340022aSzrj /** Keep looking for the most right leaf node. */
13155340022aSzrj if (node->array[i].edge->len > 0) {
13165340022aSzrj ldns_radix_node_t* last =
13175340022aSzrj ldns_radix_last_in_subtree(
13185340022aSzrj node->array[i].edge);
13195340022aSzrj if (last) {
13205340022aSzrj return last;
13215340022aSzrj }
13225340022aSzrj }
13235340022aSzrj /** Could this be the most right leaf node? */
13245340022aSzrj if (node->array[i].edge->data) {
13255340022aSzrj return node->array[i].edge;
13265340022aSzrj }
13275340022aSzrj }
13285340022aSzrj }
13295340022aSzrj return NULL;
13305340022aSzrj }
13315340022aSzrj
13325340022aSzrj
13335340022aSzrj /**
13345340022aSzrj * Fix tree after deleting element.
13355340022aSzrj * @param tree: tree.
13365340022aSzrj * @param node: node with deleted element.
13375340022aSzrj *
13385340022aSzrj */
13395340022aSzrj static void
ldns_radix_del_fix(ldns_radix_t * tree,ldns_radix_node_t * node)13405340022aSzrj ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
13415340022aSzrj {
13425340022aSzrj while (node) {
13435340022aSzrj if (node->data) {
13445340022aSzrj /** Thou should not delete nodes with data attached. */
13455340022aSzrj return;
13465340022aSzrj } else if (node->len == 1 && node->parent) {
13475340022aSzrj /** Node with one child is fold back into. */
13485340022aSzrj ldns_radix_cleanup_onechild(node);
13495340022aSzrj return;
13505340022aSzrj } else if (node->len == 0) {
13515340022aSzrj /** Leaf node. */
13525340022aSzrj ldns_radix_node_t* parent = node->parent;
13535340022aSzrj if (!parent) {
13545340022aSzrj /** The root is a leaf node. */
13555340022aSzrj ldns_radix_node_free(node, NULL);
13565340022aSzrj tree->root = NULL;
13575340022aSzrj return;
13585340022aSzrj }
13595340022aSzrj /** Cleanup leaf node and continue with parent. */
13605340022aSzrj ldns_radix_cleanup_leaf(node);
13615340022aSzrj node = parent;
13625340022aSzrj } else {
13635340022aSzrj /**
13645340022aSzrj * Node cannot be deleted, because it has edge nodes
13655340022aSzrj * and no parent to fix up to.
13665340022aSzrj */
13675340022aSzrj return;
13685340022aSzrj }
13695340022aSzrj }
13705340022aSzrj /** Not reached. */
13715340022aSzrj return;
13725340022aSzrj }
13735340022aSzrj
13745340022aSzrj
13755340022aSzrj /**
13765340022aSzrj * Clean up a node with one child.
13775340022aSzrj * @param node: node with one child.
13785340022aSzrj *
13795340022aSzrj */
13805340022aSzrj static void
ldns_radix_cleanup_onechild(ldns_radix_node_t * node)13815340022aSzrj ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
13825340022aSzrj {
13835340022aSzrj uint8_t* join_str;
13845340022aSzrj radix_strlen_t join_len;
13855340022aSzrj uint8_t parent_index = node->parent_index;
13865340022aSzrj ldns_radix_node_t* child = node->array[0].edge;
13875340022aSzrj ldns_radix_node_t* parent = node->parent;
13885340022aSzrj
13895340022aSzrj /** Node has one child, merge the child node into the parent node. */
13905340022aSzrj assert(parent_index < parent->len);
13915340022aSzrj join_len = parent->array[parent_index].len + node->array[0].len + 1;
13925340022aSzrj
13935340022aSzrj join_str = LDNS_XMALLOC(uint8_t, join_len);
13945340022aSzrj if (!join_str) {
13955340022aSzrj /**
13965340022aSzrj * Cleanup failed due to out of memory.
13975340022aSzrj * This tree is now inefficient, with the empty node still
13985340022aSzrj * existing, but it is still valid.
13995340022aSzrj */
14005340022aSzrj return;
14015340022aSzrj }
14025340022aSzrj
14035340022aSzrj memcpy(join_str, parent->array[parent_index].str,
14045340022aSzrj parent->array[parent_index].len);
14055340022aSzrj join_str[parent->array[parent_index].len] = child->parent_index +
14065340022aSzrj node->offset;
14075340022aSzrj memmove(join_str + parent->array[parent_index].len+1,
14085340022aSzrj node->array[0].str, node->array[0].len);
14095340022aSzrj
14105340022aSzrj LDNS_FREE(parent->array[parent_index].str);
14115340022aSzrj parent->array[parent_index].str = join_str;
14125340022aSzrj parent->array[parent_index].len = join_len;
14135340022aSzrj parent->array[parent_index].edge = child;
14145340022aSzrj child->parent = parent;
14155340022aSzrj child->parent_index = parent_index;
14165340022aSzrj ldns_radix_node_free(node, NULL);
14175340022aSzrj return;
14185340022aSzrj }
14195340022aSzrj
14205340022aSzrj
14215340022aSzrj /**
14225340022aSzrj * Clean up a leaf node.
14235340022aSzrj * @param node: leaf node.
14245340022aSzrj *
14255340022aSzrj */
14265340022aSzrj static void
ldns_radix_cleanup_leaf(ldns_radix_node_t * node)14275340022aSzrj ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
14285340022aSzrj {
14295340022aSzrj uint8_t parent_index = node->parent_index;
14305340022aSzrj ldns_radix_node_t* parent = node->parent;
14315340022aSzrj /** Delete lead node and fix parent array. */
14325340022aSzrj assert(parent_index < parent->len);
14335340022aSzrj ldns_radix_node_free(node, NULL);
14345340022aSzrj LDNS_FREE(parent->array[parent_index].str);
14355340022aSzrj parent->array[parent_index].str = NULL;
14365340022aSzrj parent->array[parent_index].len = 0;
14375340022aSzrj parent->array[parent_index].edge = NULL;
14385340022aSzrj /** Fix array in parent. */
14395340022aSzrj if (parent->len == 1) {
14405340022aSzrj ldns_radix_node_array_free(parent);
14415340022aSzrj } else if (parent_index == 0) {
14425340022aSzrj ldns_radix_node_array_free_front(parent);
14435340022aSzrj } else {
14445340022aSzrj ldns_radix_node_array_free_end(parent);
14455340022aSzrj }
14465340022aSzrj return;
14475340022aSzrj }
14485340022aSzrj
14495340022aSzrj
14505340022aSzrj /**
14515340022aSzrj * Free a radix node.
14525340022aSzrj * @param node: node.
14535340022aSzrj * @param arg: user argument.
14545340022aSzrj *
14555340022aSzrj */
14565340022aSzrj static void
ldns_radix_node_free(ldns_radix_node_t * node,void * arg)14575340022aSzrj ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
14585340022aSzrj {
14595340022aSzrj uint16_t i;
14605340022aSzrj (void) arg;
14615340022aSzrj if (!node) {
14625340022aSzrj return;
14635340022aSzrj }
14645340022aSzrj for (i=0; i < node->len; i++) {
14655340022aSzrj LDNS_FREE(node->array[i].str);
14665340022aSzrj }
14675340022aSzrj node->key = NULL;
14685340022aSzrj node->klen = 0;
14695340022aSzrj LDNS_FREE(node->array);
14705340022aSzrj LDNS_FREE(node);
14715340022aSzrj return;
14725340022aSzrj }
14735340022aSzrj
14745340022aSzrj
14755340022aSzrj /**
14765340022aSzrj * Free select edge array.
14775340022aSzrj * @param node: node.
14785340022aSzrj *
14795340022aSzrj */
14805340022aSzrj static void
ldns_radix_node_array_free(ldns_radix_node_t * node)14815340022aSzrj ldns_radix_node_array_free(ldns_radix_node_t* node)
14825340022aSzrj {
14835340022aSzrj node->offset = 0;
14845340022aSzrj node->len = 0;
14855340022aSzrj LDNS_FREE(node->array);
14865340022aSzrj node->array = NULL;
14875340022aSzrj node->capacity = 0;
14885340022aSzrj return;
14895340022aSzrj }
14905340022aSzrj
14915340022aSzrj
14925340022aSzrj /**
14935340022aSzrj * Free front of select edge array.
14945340022aSzrj * @param node: node.
14955340022aSzrj *
14965340022aSzrj */
14975340022aSzrj static void
ldns_radix_node_array_free_front(ldns_radix_node_t * node)14985340022aSzrj ldns_radix_node_array_free_front(ldns_radix_node_t* node)
14995340022aSzrj {
15005340022aSzrj uint16_t i, n = 0;
15015340022aSzrj /** Remove until a non NULL entry. */
15025340022aSzrj while (n < node->len && node->array[n].edge == NULL) {
15035340022aSzrj n++;
15045340022aSzrj }
15055340022aSzrj if (n == 0) {
15065340022aSzrj return;
15075340022aSzrj }
15085340022aSzrj if (n == node->len) {
15095340022aSzrj ldns_radix_node_array_free(node);
15105340022aSzrj return;
15115340022aSzrj }
15125340022aSzrj assert(n < node->len);
15135340022aSzrj assert((int) n <= (255 - (int) node->offset));
15145340022aSzrj memmove(&node->array[0], &node->array[n],
15155340022aSzrj (node->len - n)*sizeof(ldns_radix_array_t));
15165340022aSzrj node->offset += n;
15175340022aSzrj node->len -= n;
15185340022aSzrj for (i=0; i < node->len; i++) {
15195340022aSzrj if (node->array[i].edge) {
15205340022aSzrj node->array[i].edge->parent_index = i;
15215340022aSzrj }
15225340022aSzrj }
15235340022aSzrj ldns_radix_array_reduce(node);
15245340022aSzrj return;
15255340022aSzrj }
15265340022aSzrj
15275340022aSzrj
15285340022aSzrj /**
15295340022aSzrj * Free front of select edge array.
15305340022aSzrj * @param node: node.
15315340022aSzrj *
15325340022aSzrj */
15335340022aSzrj static void
ldns_radix_node_array_free_end(ldns_radix_node_t * node)15345340022aSzrj ldns_radix_node_array_free_end(ldns_radix_node_t* node)
15355340022aSzrj {
15365340022aSzrj uint16_t n = 0;
15375340022aSzrj /** Shorten array. */
15385340022aSzrj while (n < node->len && node->array[node->len-1-n].edge == NULL) {
15395340022aSzrj n++;
15405340022aSzrj }
15415340022aSzrj if (n == 0) {
15425340022aSzrj return;
15435340022aSzrj }
15445340022aSzrj if (n == node->len) {
15455340022aSzrj ldns_radix_node_array_free(node);
15465340022aSzrj return;
15475340022aSzrj }
15485340022aSzrj assert(n < node->len);
15495340022aSzrj node->len -= n;
15505340022aSzrj ldns_radix_array_reduce(node);
15515340022aSzrj return;
15525340022aSzrj }
15535340022aSzrj
15545340022aSzrj
15555340022aSzrj /**
15565340022aSzrj * Reduce the capacity of the array if needed.
15575340022aSzrj * @param node: node.
15585340022aSzrj *
15595340022aSzrj */
15605340022aSzrj static void
ldns_radix_array_reduce(ldns_radix_node_t * node)15615340022aSzrj ldns_radix_array_reduce(ldns_radix_node_t* node)
15625340022aSzrj {
15635340022aSzrj if (node->len <= node->capacity/2 && node->len != node->capacity) {
15645340022aSzrj ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
15655340022aSzrj node->len);
15665340022aSzrj if (!a) {
15675340022aSzrj return;
15685340022aSzrj }
15695340022aSzrj memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
15705340022aSzrj LDNS_FREE(node->array);
15715340022aSzrj node->array = a;
15725340022aSzrj node->capacity = node->len;
15735340022aSzrj }
15745340022aSzrj return;
15755340022aSzrj }
15765340022aSzrj
15775340022aSzrj
15785340022aSzrj /**
15795340022aSzrj * Return this element if it exists, the previous otherwise.
15805340022aSzrj * @param node: from this node.
15815340022aSzrj * @param result: result node.
15825340022aSzrj *
15835340022aSzrj */
15845340022aSzrj static void
ldns_radix_self_or_prev(ldns_radix_node_t * node,ldns_radix_node_t ** result)15855340022aSzrj ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
15865340022aSzrj {
15875340022aSzrj if (node->data) {
15885340022aSzrj *result = node;
15895340022aSzrj } else {
15905340022aSzrj *result = ldns_radix_prev(node);
15915340022aSzrj }
15925340022aSzrj return;
15935340022aSzrj }
1594