/*
* radix.c -- generic radix tree
*
* Taken from NSD4, modified for ldns
*
* Copyright (c) 2012, NLnet Labs. All rights reserved.
*
* This software is open source.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the NLNET LABS nor the names of its contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
/**
* \file
* Implementation of a radix tree.
*/
#include <ldns/config.h>
#include <ldns/radix.h>
#include <ldns/util.h>
#include <stdlib.h>
/** Helper functions */
static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
radix_strlen_t len);
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* pos);
static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte);
static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need);
static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
radix_strlen_t pos, radix_strlen_t len);
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);
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);
static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
uint8_t* str2, radix_strlen_t len2);
static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
uint8_t* str2, radix_strlen_t len2);
static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node);
static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node,
uint8_t index);
static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self(
ldns_radix_node_t* node);
static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node);
static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node);
static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node);
static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node);
static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg);
static void ldns_radix_node_array_free(ldns_radix_node_t* node);
static void ldns_radix_node_array_free_front(ldns_radix_node_t* node);
static void ldns_radix_node_array_free_end(ldns_radix_node_t* node);
static void ldns_radix_array_reduce(ldns_radix_node_t* node);
static void ldns_radix_self_or_prev(ldns_radix_node_t* node,
ldns_radix_node_t** result);
/**
* Create a new radix node.
*
*/
static ldns_radix_node_t*
ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
{
ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
if (!node) {
return NULL;
}
node->data = data;
node->key = key;
node->klen = len;
node->parent = NULL;
node->parent_index = 0;
node->len = 0;
node->offset = 0;
node->capacity = 0;
node->array = NULL;
return node;
}
/**
* Create a new radix tree.
*
*/
ldns_radix_t *
ldns_radix_create(void)
{
ldns_radix_t* tree;
/** Allocate memory for it */
tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
if (!tree) {
return NULL;
}
/** Initialize it */
ldns_radix_init(tree);
return tree;
}
/**
* Initialize radix tree.
*
*/
void
ldns_radix_init(ldns_radix_t* tree)
{
/** Initialize it */
if (tree) {
tree->root = NULL;
tree->count = 0;
}
return;
}
/**
* Free radix tree.
*
*/
void
ldns_radix_free(ldns_radix_t* tree)
{
if (tree) {
if (tree->root) {
ldns_radix_traverse_postorder(tree->root,
ldns_radix_node_free, NULL);
}
LDNS_FREE(tree);
}
return;
}
/**
* Insert data into the tree.
*
*/
ldns_status
ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
void* data)
{
radix_strlen_t pos = 0;
ldns_radix_node_t* add = NULL;
ldns_radix_node_t* prefix = NULL;
if (!tree || !key || !data) {
return LDNS_STATUS_NULL;
}
add = ldns_radix_new_node(data, key, len);
if (!add) {
return LDNS_STATUS_MEM_ERR;
}
/** Search the trie until we can make no further process. */
if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
/** No prefix found */
assert(tree->root == NULL);
if (len == 0) {
/**
* Example 1: The root:
* | [0]
**/
tree->root = add;
} else {
/** Example 2: 'dns':
* | [0]
* --| [d+ns] dns
**/
prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
if (!prefix) {
LDNS_FREE(add);
return LDNS_STATUS_MEM_ERR;
}
/** Find some space in the array for the first byte */
if (!ldns_radix_array_space(prefix, key[0])) {
LDNS_FREE(add);
LDNS_FREE(prefix->array);
LDNS_FREE(prefix);
return LDNS_STATUS_MEM_ERR;
}
/** Set relational pointers */
add->parent = prefix;
add->parent_index = 0;
prefix->array[0].edge = add;
if (len > 1) {
/** Store the remainder of the prefix */
if (!ldns_radix_prefix_remainder(1, key,
len, &prefix->array[0].str,
&prefix->array[0].len)) {
LDNS_FREE(add);
LDNS_FREE(prefix->array);
LDNS_FREE(prefix);
return LDNS_STATUS_MEM_ERR;
}
}
tree->root = prefix;
}
} else if (pos == len) {
/** Exact match found */
if (prefix->data) {
/* Element already exists */
LDNS_FREE(add);
return LDNS_STATUS_EXISTS_ERR;
}
prefix->data = data;
prefix->key = key;
prefix->klen = len; /* redundant */
} else {
/** Prefix found */
uint8_t byte = key[pos];
assert(pos < len);
if (byte < prefix->offset ||
(byte - prefix->offset) >= prefix->len) {
/** Find some space in the array for the byte. */
/**
* Example 3: 'ldns'
* | [0]
* --| [d+ns] dns
* --| [l+dns] ldns
**/
if (!ldns_radix_array_space(prefix, byte)) {
LDNS_FREE(add);
return LDNS_STATUS_MEM_ERR;
}
assert(byte >= prefix->offset);
assert((byte - prefix->offset) <= prefix->len);
byte -= prefix->offset;
if (pos+1 < len) {
/** Create remainder of the string. */
if (!ldns_radix_str_create(
&prefix->array[byte], key, pos+1,
len)) {
LDNS_FREE(add);
return LDNS_STATUS_MEM_ERR;
}
}
/** Add new node. */
add->parent = prefix;
add->parent_index = byte;
prefix->array[byte].edge = add;
} else if (prefix->array[byte-prefix->offset].edge == NULL) {
/** Use existing element. */
/**
* Example 4: 'edns'
* | [0]
* --| [d+ns] dns
* --| [e+dns] edns
* --| [l+dns] ldns
**/
byte -= prefix->offset;
if (pos+1 < len) {
/** Create remainder of the string. */
if (!ldns_radix_str_create(
&prefix->array[byte], key, pos+1,
len)) {
LDNS_FREE(add);
return LDNS_STATUS_MEM_ERR;
}
}
/** Add new node. */
add->parent = prefix;
add->parent_index = byte;
prefix->array[byte].edge = add;
} else {
/**
* Use existing element, but it has a shared prefix,
* we need a split.
*/
if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)],
key, pos+1, len, add)) {
LDNS_FREE(add);
return LDNS_STATUS_MEM_ERR;
}
}
}
tree->count ++;
return LDNS_STATUS_OK;
}
/**
* Delete data from the tree.
*
*/
void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len)
{
ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
void* data = NULL;
if (del) {
tree->count--;
data = del->data;
del->data = NULL;
ldns_radix_del_fix(tree, del);
return data;
}
return NULL;
}
/**
* Search data in the tree.
*
*/
ldns_radix_node_t*
ldns_radix_search(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len)
{
ldns_radix_node_t* node = NULL;
radix_strlen_t pos = 0;
uint8_t byte = 0;
if (!tree || !key) {
return NULL;
}
node = tree->root;
while (node) {
if (pos == len) {
return node->data?node:NULL;
}
byte = key[pos];
if (byte < node->offset) {
return NULL;
}
byte -= node->offset;
if (byte >= node->len) {
return NULL;
}
pos++;
if (node->array[byte].len > 0) {
/** Must match additional string. */
if (pos + node->array[byte].len > len) {
return NULL;
}
if (memcmp(&key[pos], node->array[byte].str,
node->array[byte].len) != 0) {
return NULL;
}
pos += node->array[byte].len;
}
node = node->array[byte].edge;
}
return NULL;
}
/**
* Search data in the tree, and if not found, find the closest smaller
* element in the tree.
*
*/
int
ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key,
radix_strlen_t len, ldns_radix_node_t** result)
{
ldns_radix_node_t* node = NULL;
radix_strlen_t pos = 0;
uint8_t byte;
int memcmp_res = 0;
if (!tree || !tree->root || !key) {
*result = NULL;
return 0;
}
node = tree->root;
while (pos < len) {
byte = key[pos];
if (byte < node->offset) {
/**
* No exact match. The lesser is in this or the
* previous node.
*/
ldns_radix_self_or_prev(node, result);
return 0;
}
byte -= node->offset;
if (byte >= node->len) {
/**
* No exact match. The lesser is in this node or the
* last of this array, or something before this node.
*/
*result = ldns_radix_last_in_subtree_incl_self(node);
if (*result == NULL) {
*result = ldns_radix_prev(node);
}
return 0;
}
pos++;
if (!node->array[byte].edge) {
/**
* No exact match. Find the previous in the array
* from this index.
*/
*result = ldns_radix_prev_from_index(node, byte);
if (*result == NULL) {
ldns_radix_self_or_prev(node, result);
}
return 0;
}
if (node->array[byte].len != 0) {
/** Must match additional string. */
if (pos + node->array[byte].len > len) {
/** Additional string is longer than key. */
if (memcmp(&key[pos], node->array[byte].str,
len-pos) <= 0) {
/** Key is before this node. */
*result = ldns_radix_prev(
node->array[byte].edge);
} else {
/** Key is after additional string. */
*result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
if (*result == NULL) {
*result = ldns_radix_prev(node->array[byte].edge);
}
}
return 0;
}
memcmp_res = memcmp(&key[pos], node->array[byte].str,
node->array[byte].len);
if (memcmp_res < 0) {
*result = ldns_radix_prev(
node->array[byte].edge);
return 0;
} else if (memcmp_res > 0) {
*result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
if (*result == NULL) {
*result = ldns_radix_prev(node->array[byte].edge);
}
return 0;
}
pos += node->array[byte].len;
}
node = node->array[byte].edge;
}
if (node->data) {
/** Exact match. */
*result = node;
return 1;
}
/** There is a node which is an exact match, but has no element. */
*result = ldns_radix_prev(node);
return 0;
}
/**
* Get the first element in the tree.
*
*/
ldns_radix_node_t*
ldns_radix_first(const ldns_radix_t* tree)
{
ldns_radix_node_t* first = NULL;
if (!tree || !tree->root) {
return NULL;
}
first = tree->root;
if (first->data) {
return first;
}
return ldns_radix_next(first);
}
/**
* Get the last element in the tree.
*
*/
ldns_radix_node_t*
ldns_radix_last(const ldns_radix_t* tree)
{
if (!tree || !tree->root) {
return NULL;
}
return ldns_radix_last_in_subtree_incl_self(tree->root);
}
/**
* Next element.
*
*/
ldns_radix_node_t*
ldns_radix_next(ldns_radix_node_t* node)
{
if (!node) {
return NULL;
}
if (node->len) {
/** Go down: most-left child is the next. */
ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
if (next) {
return next;
}
}
/** No elements in subtree, get to parent and go down next branch. */
while (node->parent) {
uint8_t index = node->parent_index;
node = node->parent;
index++;
for (; index < node->len; index++) {
if (node->array[index].edge) {
ldns_radix_node_t* next;
/** Node itself. */
if (node->array[index].edge->data) {
return node->array[index].edge;
}
/** Dive into subtree. */
next = ldns_radix_next_in_subtree(node);
if (next) {
return next;
}
}
}
}
return NULL;
}
/**
* Previous element.
*
*/
ldns_radix_node_t*
ldns_radix_prev(ldns_radix_node_t* node)
{
if (!node) {
return NULL;
}
/** Get to parent and go down previous branch. */
while (node->parent) {
uint8_t index = node->parent_index;
ldns_radix_node_t* prev;
node = node->parent;
assert(node->len > 0);
prev = ldns_radix_prev_from_index(node, index);
if (prev) {
return prev;
}
if (node->data) {
return node;
}
}
return NULL;
}
/**
* Print node.
*
*/
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)
{
uint8_t j;
if (!node) {
return;
}
for (j = 0; j < d; j++) {
fprintf(fd, "--");
}
if (str) {
radix_strlen_t l;
fprintf(fd, "| [%u+", (unsigned) i);
for (l=0; l < len; l++) {
fprintf(fd, "%c", (char) str[l]);
}
fprintf(fd, "]%u", (unsigned) len);
} else {
fprintf(fd, "| [%u]", (unsigned) i);
}
if (node->data) {
fprintf(fd, " %s", (char*) node->data);
}
fprintf(fd, "\n");
for (j = 0; j < node->len; j++) {
if (node->array[j].edge) {
ldns_radix_node_print(fd, node->array[j].edge, j,
node->array[j].str, node->array[j].len, d+1);
}
}
return;
}
/**
* Print radix tree.
*
*/
void
ldns_radix_printf(FILE* fd, const ldns_radix_t* tree)
{
if (!fd || !tree) {
return;
}
if (!tree->root) {
fprintf(fd, "; empty radix tree\n");
return;
}
ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0);
return;
}
/**
* Join two radix trees.
*
*/
ldns_status
ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2)
{
ldns_radix_node_t* cur_node, *next_node;
ldns_status status;
if (!tree2 || !tree2->root) {
return LDNS_STATUS_OK;
}
/** Add all elements from tree2 into tree1. */
cur_node = ldns_radix_first(tree2);
while (cur_node) {
status = LDNS_STATUS_NO_DATA;
/** Insert current node into tree1 */
if (cur_node->data) {
status = ldns_radix_insert(tree1, cur_node->key,
cur_node->klen, cur_node->data);
/** Exist errors may occur */
if (status != LDNS_STATUS_OK &&
status != LDNS_STATUS_EXISTS_ERR) {
return status;
}
}
next_node = ldns_radix_next(cur_node);
if (status == LDNS_STATUS_OK) {
(void) ldns_radix_delete(tree2, cur_node->key,
cur_node->klen);
}
cur_node = next_node;
}
return LDNS_STATUS_OK;
}
/**
* Split a radix tree intwo.
*
*/
ldns_status
ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2)
{
size_t count = 0;
ldns_radix_node_t* cur_node;
ldns_status status = LDNS_STATUS_OK;
if (!tree1 || !tree1->root || num == 0) {
return LDNS_STATUS_OK;
}
if (!tree2) {
return LDNS_STATUS_NULL;
}
if (!*tree2) {
*tree2 = ldns_radix_create();
if (!*tree2) {
return LDNS_STATUS_MEM_ERR;
}
}
cur_node = ldns_radix_first(tree1);
while (count < num && cur_node) {
if (cur_node->data) {
/** Delete current node from tree1. */
uint8_t* cur_key = cur_node->key;
radix_strlen_t cur_len = cur_node->klen;
void* cur_data = ldns_radix_delete(tree1, cur_key,
cur_len);
/** Insert current node into tree2/ */
if (!cur_data) {
return LDNS_STATUS_NO_DATA;
}
status = ldns_radix_insert(*tree2, cur_key, cur_len,
cur_data);
if (status != LDNS_STATUS_OK &&
status != LDNS_STATUS_EXISTS_ERR) {
return status;
}
/*
if (status == LDNS_STATUS_OK) {
cur_node->key = NULL;
cur_node->klen = 0;
}
*/
/** Update count; get first element from tree1 again. */
count++;
cur_node = ldns_radix_first(tree1);
} else {
cur_node = ldns_radix_next(cur_node);
}
}
return LDNS_STATUS_OK;
}
/**
* Call function for all nodes in the tree, such that leaf nodes are
* called before parent nodes.
*
*/
void
ldns_radix_traverse_postorder(ldns_radix_node_t* node,
void (*func)(ldns_radix_node_t*, void*), void* arg)
{
uint8_t i;
if (!node) {
return;
}
for (i=0; i < node->len; i++) {
ldns_radix_traverse_postorder(node->array[i].edge,
func, arg);
}
/** Call user function */
(*func)(node, arg);
return;
}
/** Static helper functions */
/**
* Find a prefix of the key.
* @param tree: tree.
* @param key: key.
* @param len: length of key.
* @param result: the longest prefix, the entry itself if *pos==len,
* otherwise an array entry.
* @param pos: position in string where next unmatched byte is.
* If *pos==len, an exact match is found.
* If *pos== 0, a "" match was found.
* @return 0 (false) if no prefix found.
*
*/
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)
{
/** Start searching at the root node */
ldns_radix_node_t* n = tree->root;
radix_strlen_t pos = 0;
uint8_t byte;
*respos = 0;
*result = n;
if (!n) {
/** No root, no prefix found */
return 0;
}
/** For each node, look if we can make further progress */
while (n) {
if (pos == len) {
/** Exact match */
return 1;
}
byte = key[pos];
if (byte < n->offset) {
/** key < node */
return 1;
}
byte -= n->offset;
if (byte >= n->len) {
/** key > node */
return 1;
}
/** So far, the trie matches */
pos++;
if (n->array[byte].len != 0) {
/** Must match additional string */
if (pos + n->array[byte].len > len) {
return 1; /* no match at child node */
}
if (memcmp(&key[pos], n->array[byte].str,
n->array[byte].len) != 0) {
return 1; /* no match at child node */
}
pos += n->array[byte].len;
}
/** Continue searching prefix at this child node */
n = n->array[byte].edge;
if (!n) {
return 1;
}
/** Update the prefix node */
*respos = pos;
*result = n;
}
/** Done */
return 1;
}
/**
* Make space in the node's array for another byte.
* @param node: node.
* @param byte: byte.
* @return 1 if successful, 0 otherwise.
*
*/
static int
ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
{
/** Is there an array? */
if (!node->array) {
assert(node->capacity == 0);
/** No array, create new array */
node->array = LDNS_MALLOC(ldns_radix_array_t);
if (!node->array) {
return 0;
}
memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
node->len = 1;
node->capacity = 1;
node->offset = byte;
return 1;
}
/** Array exist */
assert(node->array != NULL);
assert(node->capacity > 0);
if (node->len == 0) {
/** Unused array */
node->len = 1;
node->offset = byte;
} else if (byte < node->offset) {
/** Byte is below the offset */
uint8_t index;
uint16_t need = node->offset - byte;
/** Is there enough capacity? */
if (node->len + need > node->capacity) {
/** Not enough capacity, grow array */
if (!ldns_radix_array_grow(node,
(unsigned) (node->len + need))) {
return 0; /* failed to grow array */
}
}
/** Move items to the end */
memmove(&node->array[need], &node->array[0],
node->len*sizeof(ldns_radix_array_t));
/** Fix parent index */
for (index = 0; index < node->len; index++) {
if (node->array[index+need].edge) {
node->array[index+need].edge->parent_index =
index + need;
}
}
/** Zero the first */
memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));
node->len += need;
node->offset = byte;
} else if (byte - node->offset >= node->len) {
/** Byte does not fit in array */
uint16_t need = (byte - node->offset) - node->len + 1;
/** Is there enough capacity? */
if (node->len + need > node->capacity) {
/** Not enough capacity, grow array */
if (!ldns_radix_array_grow(node,
(unsigned) (node->len + need))) {
return 0; /* failed to grow array */
}
}
/** Zero the added items */
memset(&node->array[node->len], 0,
need*sizeof(ldns_radix_array_t));
node->len += need;
}
return 1;
}
/**
* Grow the array.
* @param node: node.
* @param need: number of elements the array at least need to grow.
* Can't be bigger than 256.
* @return: 0 if failed, 1 if was successful.
*
*/
static int
ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
{
unsigned size = ((unsigned)node->capacity)*2;
ldns_radix_array_t* a = NULL;
if (need > size) {
size = need;
}
if (size > 256) {
size = 256;
}
a = LDNS_XMALLOC(ldns_radix_array_t, size);
if (!a) {
return 0;
}
assert(node->len <= node->capacity);
assert(node->capacity < size);
memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));
LDNS_FREE(node->array);
node->array = a;
node->capacity = size;
return 1;
}
/**
* Create a prefix in the array string.
* @param array: array.
* @param key: key.
* @param pos: start position in key.
* @param len: length of key.
* @return 0 if failed, 1 if was successful.
*
*/
static int
ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
radix_strlen_t pos, radix_strlen_t len)
{
array->str = LDNS_XMALLOC(uint8_t, (len-pos));
if (!array->str) {
return 0;
}
memmove(array->str, key+pos, len-pos);
array->len = (len-pos);
return 1;
}
/**
* Allocate remainder from prefixes for a split.
* @param prefixlen: length of prefix.
* @param longer_str: the longer string.
* @param longer_len: the longer string length.
* @param split_str: the split string.
* @param split_len: the split string length.
* @return 0 if failed, 1 if successful.
*
*/
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)
{
*split_len = longer_len - prefix_len;
*split_str = LDNS_XMALLOC(uint8_t, (*split_len));
if (!*split_str) {
return 0;
}
memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len);
return 1;
}
/**
* Create a split when two nodes have a shared prefix.
* @param array: array.
* @param key: key.
* @param pos: start position in key.
* @param len: length of the key.
* @param add: node to be added.
* @return 0 if failed, 1 if was successful.
*
*/
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)
{
uint8_t* str_to_add = key + pos;
radix_strlen_t strlen_to_add = len - pos;
if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add,
array->str, array->len)) {
/** The string to add is a prefix of the existing string */
uint8_t* split_str = NULL, *dup_str = NULL;
radix_strlen_t split_len = 0;
/**
* Example 5: 'ld'
* | [0]
* --| [d+ns] dns
* --| [e+dns] edns
* --| [l+d] ld
* ----| [n+s] ldns
**/
assert(strlen_to_add < array->len);
/** Store the remainder in the split string */
if (array->len - strlen_to_add > 1) {
if (!ldns_radix_prefix_remainder(strlen_to_add+1,
array->str, array->len, &split_str,
&split_len)) {
return 0;
}
}
/** Duplicate the string to add */
if (strlen_to_add != 0) {
dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add);
if (!dup_str) {
LDNS_FREE(split_str);
return 0;
}
memcpy(dup_str, str_to_add, strlen_to_add);
}
/** Make space in array for the new node */
if (!ldns_radix_array_space(add,
array->str[strlen_to_add])) {
LDNS_FREE(split_str);
LDNS_FREE(dup_str);
return 0;
}
/**
* The added node should go direct under the existing parent.
* The existing node should go under the added node.
*/
add->parent = array->edge->parent;
add->parent_index = array->edge->parent_index;
add->array[0].edge = array->edge;
add->array[0].str = split_str;
add->array[0].len = split_len;
array->edge->parent = add;
array->edge->parent_index = 0;
LDNS_FREE(array->str);
array->edge = add;
array->str = dup_str;
array->len = strlen_to_add;
} else if (ldns_radix_str_is_prefix(array->str, array->len,
str_to_add, strlen_to_add)) {
/** The existing string is a prefix of the string to add */
/**
* Example 6: 'dns-ng'
* | [0]
* --| [d+ns] dns
* ----| [-+ng] dns-ng
* --| [e+dns] edns
* --| [l+d] ld
* ----| [n+s] ldns
**/
uint8_t* split_str = NULL;
radix_strlen_t split_len = 0;
assert(array->len < strlen_to_add);
if (strlen_to_add - array->len > 1) {
if (!ldns_radix_prefix_remainder(array->len+1,
str_to_add, strlen_to_add, &split_str,
&split_len)) {
return 0;
}
}
/** Make space in array for the new node */
if (!ldns_radix_array_space(array->edge,
str_to_add[array->len])) {
LDNS_FREE(split_str);
return 0;
}
/**
* The added node should go direct under the existing node.
*/
add->parent = array->edge;
add->parent_index = str_to_add[array->len] -
array->edge->offset;
array->edge->array[add->parent_index].edge = add;
array->edge->array[add->parent_index].str = split_str;
array->edge->array[add->parent_index].len = split_len;
} else {
/** Create a new split node. */
/**
* Example 7: 'dndns'
* | [0]
* --| [d+n]
* ----| [d+ns] dndns
* ----| [s] dns
* ------| [-+ng] dns-ng
* --| [e+dns] edns
* --| [l+d] ld
* ----| [n+s] ldns
**/
ldns_radix_node_t* common = NULL;
uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL;
radix_strlen_t common_len = 0, l1 = 0, l2 = 0;
common_len = ldns_radix_str_common(array->str, array->len,
str_to_add, strlen_to_add);
assert(common_len < array->len);
assert(common_len < strlen_to_add);
/** Create the new common node. */
common = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
if (!common) {
return 0;
}
if (array->len - common_len > 1) {
if (!ldns_radix_prefix_remainder(common_len+1,
array->str, array->len, &s1, &l1)) {
return 0;
}
}
if (strlen_to_add - common_len > 1) {
if (!ldns_radix_prefix_remainder(common_len+1,
str_to_add, strlen_to_add, &s2, &l2)) {
return 0;
}
}
/** Create the shared prefix. */
if (common_len > 0) {
common_str = LDNS_XMALLOC(uint8_t, common_len);
if (!common_str) {
LDNS_FREE(common);
LDNS_FREE(s1);
LDNS_FREE(s2);
return 0;
}
memcpy(common_str, str_to_add, common_len);
}
/** Make space in the common node array. */
if (!ldns_radix_array_space(common, array->str[common_len]) ||
!ldns_radix_array_space(common, str_to_add[common_len])) {
LDNS_FREE(common->array);
LDNS_FREE(common);
LDNS_FREE(common_str);
LDNS_FREE(s1);
LDNS_FREE(s2);
return 0;
}
/**
* The common node should go direct under the parent node.
* The added and existing nodes go under the common node.
*/
common->parent = array->edge->parent;
common->parent_index = array->edge->parent_index;
array->edge->parent = common;
array->edge->parent_index = array->str[common_len] -
common->offset;
add->parent = common;
add->parent_index = str_to_add[common_len] - common->offset;
common->array[array->edge->parent_index].edge = array->edge;
common->array[array->edge->parent_index].str = s1;
common->array[array->edge->parent_index].len = l1;
common->array[add->parent_index].edge = add;
common->array[add->parent_index].str = s2;
common->array[add->parent_index].len = l2;
LDNS_FREE(array->str);
array->edge = common;
array->str = common_str;
array->len = common_len;
}
return 1;
}
/**
* Check if one string prefix of other string.
* @param str1: one string.
* @param len1: one string length.
* @param str2: other string.
* @param len2: other string length.
* @return 1 if prefix, 0 otherwise.
*
*/
static int
ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
uint8_t* str2, radix_strlen_t len2)
{
if (len1 == 0) {
return 1; /* empty prefix is also a prefix */
}
if (len1 > len2) {
return 0; /* len1 is longer so str1 cannot be a prefix */
}
return (memcmp(str1, str2, len1) == 0);
}
/**
* Return the number of bytes in common for the two strings.
* @param str1: one string.
* @param len1: one string length.
* @param str2: other string.
* @param len2: other string length.
* @return length of substring that the two strings have in common.
*
*/
static radix_strlen_t
ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
uint8_t* str2, radix_strlen_t len2)
{
radix_strlen_t i, max = (len1<len2)?len1:len2;
for (i=0; i<max; i++) {
if (str1[i] != str2[i]) {
return i;
}
}
return max;
}
/**
* Find the next element in the subtree of this node.
* @param node: node.
* @return: node with next element.
*
*/
static ldns_radix_node_t*
ldns_radix_next_in_subtree(ldns_radix_node_t* node)
{
uint16_t i;
ldns_radix_node_t* next;
/** Try every subnode. */
for (i = 0; i < node->len; i++) {
if (node->array[i].edge) {
/** Node itself. */
if (node->array[i].edge->data) {
return node->array[i].edge;
}
/** Dive into subtree. */
next = ldns_radix_next_in_subtree(node->array[i].edge);
if (next) {
return next;
}
}
}
return NULL;
}
/**
* Find the previous element in the array of this node, from index.
* @param node: node.
* @param index: index.
* @return previous node from index.
*
*/
static ldns_radix_node_t*
ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
{
uint8_t i = index;
while (i > 0) {
i--;
if (node->array[i].edge) {
ldns_radix_node_t* prev =
ldns_radix_last_in_subtree_incl_self(node);
if (prev) {
return prev;
}
}
}
return NULL;
}
/**
* Find last node in subtree, or this node (if have data).
* @param node: node.
* @return last node in subtree, or this node, or NULL.
*
*/
static ldns_radix_node_t*
ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
{
ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
if (last) {
return last;
} else if (node->data) {
return node;
}
return NULL;
}
/**
* Find last node in subtree.
* @param node: node.
* @return last node in subtree.
*
*/
static ldns_radix_node_t*
ldns_radix_last_in_subtree(ldns_radix_node_t* node)
{
int i;
/** Look for the most right leaf node. */
for (i=(int)(node->len)-1; i >= 0; i--) {
if (node->array[i].edge) {
/** Keep looking for the most right leaf node. */
if (node->array[i].edge->len > 0) {
ldns_radix_node_t* last =
ldns_radix_last_in_subtree(
node->array[i].edge);
if (last) {
return last;
}
}
/** Could this be the most right leaf node? */
if (node->array[i].edge->data) {
return node->array[i].edge;
}
}
}
return NULL;
}
/**
* Fix tree after deleting element.
* @param tree: tree.
* @param node: node with deleted element.
*
*/
static void
ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
{
while (node) {
if (node->data) {
/** Thou should not delete nodes with data attached. */
return;
} else if (node->len == 1 && node->parent) {
/** Node with one child is fold back into. */
ldns_radix_cleanup_onechild(node);
return;
} else if (node->len == 0) {
/** Leaf node. */
ldns_radix_node_t* parent = node->parent;
if (!parent) {
/** The root is a leaf node. */
ldns_radix_node_free(node, NULL);
tree->root = NULL;
return;
}
/** Cleanup leaf node and continue with parent. */
ldns_radix_cleanup_leaf(node);
node = parent;
} else {
/**
* Node cannot be deleted, because it has edge nodes
* and no parent to fix up to.
*/
return;
}
}
/** Not reached. */
return;
}
/**
* Clean up a node with one child.
* @param node: node with one child.
*
*/
static void
ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
{
uint8_t* join_str;
radix_strlen_t join_len;
uint8_t parent_index = node->parent_index;
ldns_radix_node_t* child = node->array[0].edge;
ldns_radix_node_t* parent = node->parent;
/** Node has one child, merge the child node into the parent node. */
assert(parent_index < parent->len);
join_len = parent->array[parent_index].len + node->array[0].len + 1;
join_str = LDNS_XMALLOC(uint8_t, join_len);
if (!join_str) {
/**
* Cleanup failed due to out of memory.
* This tree is now inefficient, with the empty node still
* existing, but it is still valid.
*/
return;
}
memcpy(join_str, parent->array[parent_index].str,
parent->array[parent_index].len);
join_str[parent->array[parent_index].len] = child->parent_index +
node->offset;
memmove(join_str + parent->array[parent_index].len+1,
node->array[0].str, node->array[0].len);
LDNS_FREE(parent->array[parent_index].str);
parent->array[parent_index].str = join_str;
parent->array[parent_index].len = join_len;
parent->array[parent_index].edge = child;
child->parent = parent;
child->parent_index = parent_index;
ldns_radix_node_free(node, NULL);
return;
}
/**
* Clean up a leaf node.
* @param node: leaf node.
*
*/
static void
ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
{
uint8_t parent_index = node->parent_index;
ldns_radix_node_t* parent = node->parent;
/** Delete lead node and fix parent array. */
assert(parent_index < parent->len);
ldns_radix_node_free(node, NULL);
LDNS_FREE(parent->array[parent_index].str);
parent->array[parent_index].str = NULL;
parent->array[parent_index].len = 0;
parent->array[parent_index].edge = NULL;
/** Fix array in parent. */
if (parent->len == 1) {
ldns_radix_node_array_free(parent);
} else if (parent_index == 0) {
ldns_radix_node_array_free_front(parent);
} else {
ldns_radix_node_array_free_end(parent);
}
return;
}
/**
* Free a radix node.
* @param node: node.
* @param arg: user argument.
*
*/
static void
ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
{
uint16_t i;
(void) arg;
if (!node) {
return;
}
for (i=0; i < node->len; i++) {
LDNS_FREE(node->array[i].str);
}
node->key = NULL;
node->klen = 0;
LDNS_FREE(node->array);
LDNS_FREE(node);
return;
}
/**
* Free select edge array.
* @param node: node.
*
*/
static void
ldns_radix_node_array_free(ldns_radix_node_t* node)
{
node->offset = 0;
node->len = 0;
LDNS_FREE(node->array);
node->array = NULL;
node->capacity = 0;
return;
}
/**
* Free front of select edge array.
* @param node: node.
*
*/
static void
ldns_radix_node_array_free_front(ldns_radix_node_t* node)
{
uint16_t i, n = 0;
/** Remove until a non NULL entry. */
while (n < node->len && node->array[n].edge == NULL) {
n++;
}
if (n == 0) {
return;
}
if (n == node->len) {
ldns_radix_node_array_free(node);
return;
}
assert(n < node->len);
assert((int) n <= (255 - (int) node->offset));
memmove(&node->array[0], &node->array[n],
(node->len - n)*sizeof(ldns_radix_array_t));
node->offset += n;
node->len -= n;
for (i=0; i < node->len; i++) {
if (node->array[i].edge) {
node->array[i].edge->parent_index = i;
}
}
ldns_radix_array_reduce(node);
return;
}
/**
* Free front of select edge array.
* @param node: node.
*
*/
static void
ldns_radix_node_array_free_end(ldns_radix_node_t* node)
{
uint16_t n = 0;
/** Shorten array. */
while (n < node->len && node->array[node->len-1-n].edge == NULL) {
n++;
}
if (n == 0) {
return;
}
if (n == node->len) {
ldns_radix_node_array_free(node);
return;
}
assert(n < node->len);
node->len -= n;
ldns_radix_array_reduce(node);
return;
}
/**
* Reduce the capacity of the array if needed.
* @param node: node.
*
*/
static void
ldns_radix_array_reduce(ldns_radix_node_t* node)
{
if (node->len <= node->capacity/2 && node->len != node->capacity) {
ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
node->len);
if (!a) {
return;
}
memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
LDNS_FREE(node->array);
node->array = a;
node->capacity = node->len;
}
return;
}
/**
* Return this element if it exists, the previous otherwise.
* @param node: from this node.
* @param result: result node.
*
*/
static void
ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
{
if (node->data) {
*result = node;
} else {
*result = ldns_radix_prev(node);
}
return;
}