/*
* radtree -- generic radix tree for binary strings.
*
* Copyright (c) 2010, NLnet Labs. See LICENSE for license.
*/
#include "config.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include "radtree.h"
#include "util.h"
#include "region-allocator.h"
#include <stdio.h>
#include <ctype.h>
struct radtree* radix_tree_create(struct region* region)
{
struct radtree* rt = (struct radtree*)region_alloc(region, sizeof(*rt));
if(!rt) return NULL;
rt->region = region;
radix_tree_init(rt);
return rt;
}
void radix_tree_init(struct radtree* rt)
{
rt->root = NULL;
rt->count = 0;
}
/** delete radnodes in postorder recursion */
static void radnode_del_postorder(struct region* region, struct radnode* n)
{
unsigned i;
if(!n) return;
for(i=0; i<n->len; i++) {
radnode_del_postorder(region, n->array[i].node);
region_recycle(region, n->array[i].str, n->array[i].len);
}
region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
region_recycle(region, n, sizeof(*n));
}
void radix_tree_clear(struct radtree* rt)
{
radnode_del_postorder(rt->region, rt->root);
rt->root = NULL;
rt->count = 0;
}
void radix_tree_delete(struct radtree* rt)
{
if(!rt) return;
radix_tree_clear(rt);
region_recycle(rt->region, rt, sizeof(*rt));
}
/** return last elem-containing node in this subtree (excl self) */
static struct radnode*
radnode_last_in_subtree(struct radnode* n)
{
int idx;
/* try last entry in array first */
for(idx=((int)n->len)-1; idx >= 0; idx--) {
if(n->array[idx].node) {
/* does it have entries in its subtrees? */
if(n->array[idx].node->len > 0) {
struct radnode* s = radnode_last_in_subtree(
n->array[idx].node);
if(s) return s;
}
/* no, does it have an entry itself? */
if(n->array[idx].node->elem)
return n->array[idx].node;
}
}
return NULL;
}
/** last in subtree, incl self */
static struct radnode*
radnode_last_in_subtree_incl_self(struct radnode* n)
{
struct radnode* s = radnode_last_in_subtree(n);
if(s) return s;
if(n->elem) return n;
return NULL;
}
/** return first elem-containing node in this subtree (excl self) */
static struct radnode*
radnode_first_in_subtree(struct radnode* n)
{
unsigned idx;
struct radnode* s;
/* try every subnode */
for(idx=0; idx<n->len; idx++) {
if(n->array[idx].node) {
/* does it have elem itself? */
if(n->array[idx].node->elem)
return n->array[idx].node;
/* try its subtrees */
if((s=radnode_first_in_subtree(n->array[idx].node))!=0)
return s;
}
}
return NULL;
}
/** Find an entry in arrays from idx-1 to 0 */
static struct radnode*
radnode_find_prev_from_idx(struct radnode* n, unsigned from)
{
unsigned idx = from;
while(idx > 0) {
idx --;
if(n->array[idx].node) {
struct radnode* s = radnode_last_in_subtree_incl_self(
n->array[idx].node);
if(s) return s;
}
}
return NULL;
}
/**
* Find a prefix of the key, in whole-nodes.
* Finds the longest prefix that corresponds to a whole radnode entry.
* There may be a slightly longer prefix in one of the array elements.
* @param result: the longest prefix, the entry itself if *respos==len,
* otherwise an array entry, residx.
* @param respos: pos in string where next unmatched byte is, if == len an
* exact match has been found. If == 0 then a "" match was found.
* @return false if no prefix found, not even the root "" prefix.
*/
static int radix_find_prefix_node(struct radtree* rt, uint8_t* k,
radstrlen_type len, struct radnode** result, radstrlen_type* respos)
{
struct radnode* n = rt->root;
radstrlen_type pos = 0;
uint8_t byte;
*respos = 0;
*result = n;
if(!n) return 0;
while(n) {
if(pos == len) {
return 1;
}
byte = k[pos];
if(byte < n->offset) {
return 1;
}
byte -= n->offset;
if(byte >= n->len) {
return 1;
}
pos++;
if(n->array[byte].len != 0) {
/* must match additional string */
if(pos+n->array[byte].len > len) {
return 1;
}
if(memcmp(&k[pos], n->array[byte].str,
n->array[byte].len) != 0) {
return 1;
}
pos += n->array[byte].len;
}
n = n->array[byte].node;
if(!n) return 1;
*respos = pos;
*result = n;
}
/* cannot reach because of returns when !n above */
/* ENOTREACH */
return 1;
}
/** grow array to at least the given size, offset unchanged */
static int
radnode_array_grow(struct region* region, struct radnode* n, unsigned want)
{
unsigned ns = ((unsigned)n->capacity)*2;
struct radsel* a;
assert(want <= 256); /* cannot be more, range of uint8 */
if(want > ns)
ns = want;
if(ns > 256) ns = 256;
/* we do not use realloc, because we want to keep the old array
* in case alloc fails, so that the tree is still usable */
a = (struct radsel*)region_alloc_array(region, ns, sizeof(struct radsel));
if(!a) return 0;
assert(n->len <= n->capacity);
assert(n->capacity < ns);
memcpy(&a[0], &n->array[0], n->len*sizeof(struct radsel));
region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
n->array = a;
n->capacity = ns;
return 1;
}
/** make space in radnode array for another byte */
static int
radnode_array_space(struct region* region, struct radnode* n, uint8_t byte)
{
/* is there an array? */
if(!n->array || n->capacity == 0) {
n->array = (struct radsel*)region_alloc(region,
sizeof(struct radsel));
if(!n->array) return 0;
memset(&n->array[0], 0, sizeof(struct radsel));
n->len = 1;
n->capacity = 1;
n->offset = byte;
/* is the array unused? */
} else if(n->len == 0 && n->capacity != 0) {
n->len = 1;
n->offset = byte;
memset(&n->array[0], 0, sizeof(struct radsel));
/* is it below the offset? */
} else if(byte < n->offset) {
/* is capacity enough? */
unsigned idx;
unsigned need = n->offset-byte;
if(n->len+need > n->capacity) {
/* grow array */
if(!radnode_array_grow(region, n, n->len+need))
return 0;
}
/* reshuffle items to end */
memmove(&n->array[need], &n->array[0],
n->len*sizeof(struct radsel));
/* fixup pidx */
for(idx = 0; idx < n->len; idx++) {
if(n->array[idx+need].node)
n->array[idx+need].node->pidx = idx+need;
}
/* zero the first */
memset(&n->array[0], 0, need*sizeof(struct radsel));
n->len += need;
n->offset = byte;
/* is it above the max? */
} else if(byte-n->offset >= n->len) {
/* is capacity enough? */
unsigned need = (byte-n->offset) - n->len + 1;
/* grow array */
if(n->len + need > n->capacity) {
if(!radnode_array_grow(region, n, n->len+need))
return 0;
}
/* zero added entries */
memset(&n->array[n->len], 0, need*sizeof(struct radsel));
/* grow length */
n->len += need;
}
return 1;
}
/** create a prefix in the array strs */
static int
radsel_str_create(struct region* region, struct radsel* r, uint8_t* k,
radstrlen_type pos, radstrlen_type len)
{
r->str = (uint8_t*)region_alloc(region, sizeof(uint8_t)*(len-pos));
if(!r->str)
return 0; /* out of memory */
memmove(r->str, k+pos, len-pos);
r->len = len-pos;
return 1;
}
/** see if one byte string p is a prefix of another x (equality is true) */
static int
bstr_is_prefix(uint8_t* p, radstrlen_type plen, uint8_t* x,
radstrlen_type xlen)
{
/* if plen is zero, it is an (empty) prefix */
if(plen == 0)
return 1;
/* if so, p must be shorter */
if(plen > xlen)
return 0;
return (memcmp(p, x, plen) == 0);
}
/** number of bytes in common for the two strings */
static radstrlen_type
bstr_common(uint8_t* x, radstrlen_type xlen, uint8_t* y, radstrlen_type ylen)
{
unsigned i, max = ((xlen<ylen)?xlen:ylen);
for(i=0; i<max; i++) {
if(x[i] != y[i])
return i;
}
return max;
}
int
bstr_is_prefix_ext(uint8_t* p, radstrlen_type plen, uint8_t* x,
radstrlen_type xlen)
{
return bstr_is_prefix(p, plen, x, xlen);
}
radstrlen_type
bstr_common_ext(uint8_t* x, radstrlen_type xlen, uint8_t* y,
radstrlen_type ylen)
{
return bstr_common(x, xlen, y, ylen);
}
/** allocate remainder from prefixes for a split:
* plen: len prefix, l: longer bstring, llen: length of l. */
static int
radsel_prefix_remainder(struct region* region, radstrlen_type plen,
uint8_t* l, radstrlen_type llen,
uint8_t** s, radstrlen_type* slen)
{
*slen = llen - plen;
*s = (uint8_t*)region_alloc(region, (*slen)*sizeof(uint8_t));
if(!*s)
return 0;
memmove(*s, l+plen, llen-plen);
return 1;
}
/** radsel create a split when two nodes have shared prefix.
* @param r: radsel that gets changed, it contains a node.
* @param k: key byte string
* @param pos: position where the string enters the radsel (e.g. r.str)
* @param len: length of k.
* @param add: additional node for the string k.
* removed by called on failure.
* @return false on alloc failure, no changes made.
*/
static int
radsel_split(struct region* region, struct radsel* r, uint8_t* k,
radstrlen_type pos, radstrlen_type len, struct radnode* add)
{
uint8_t* addstr = k+pos;
radstrlen_type addlen = len-pos;
if(bstr_is_prefix(addstr, addlen, r->str, r->len)) {
uint8_t* split_str=NULL, *dupstr=NULL;
radstrlen_type split_len=0;
/* 'add' is a prefix of r.node */
/* also for empty addstr */
/* set it up so that the 'add' node has r.node as child */
/* so, r.node gets moved below the 'add' node, but we do
* this so that the r.node stays the same pointer for its
* key name */
assert(addlen != r->len);
assert(addlen < r->len);
if(r->len-addlen > 1) {
/* shift one because a char is in the lookup array */
if(!radsel_prefix_remainder(region, addlen+1, r->str,
r->len, &split_str, &split_len))
return 0;
}
if(addlen != 0) {
dupstr = (uint8_t*)region_alloc(region,
addlen*sizeof(uint8_t));
if(!dupstr) {
region_recycle(region, split_str, split_len);
return 0;
}
memcpy(dupstr, addstr, addlen);
}
if(!radnode_array_space(region, add, r->str[addlen])) {
region_recycle(region, split_str, split_len);
region_recycle(region, dupstr, addlen);
return 0;
}
/* alloc succeeded, now link it in */
add->parent = r->node->parent;
add->pidx = r->node->pidx;
add->array[0].node = r->node;
add->array[0].str = split_str;
add->array[0].len = split_len;
r->node->parent = add;
r->node->pidx = 0;
r->node = add;
region_recycle(region, r->str, r->len);
r->str = dupstr;
r->len = addlen;
} else if(bstr_is_prefix(r->str, r->len, addstr, addlen)) {
uint8_t* split_str = NULL;
radstrlen_type split_len = 0;
/* r.node is a prefix of 'add' */
/* set it up so that the 'r.node' has 'add' as child */
/* and basically, r.node is already completely fine,
* we only need to create a node as its child */
assert(addlen != r->len);
assert(r->len < addlen);
if(addlen-r->len > 1) {
/* shift one because a character goes into array */
if(!radsel_prefix_remainder(region, r->len+1, addstr,
addlen, &split_str, &split_len))
return 0;
}
if(!radnode_array_space(region, r->node, addstr[r->len])) {
region_recycle(region, split_str, split_len);
return 0;
}
/* alloc succeeded, now link it in */
add->parent = r->node;
add->pidx = addstr[r->len] - r->node->offset;
r->node->array[add->pidx].node = add;
r->node->array[add->pidx].str = split_str;
r->node->array[add->pidx].len = split_len;
} else {
/* okay we need to create a new node that chooses between
* the nodes 'add' and r.node
* We do this so that r.node stays the same pointer for its
* key name. */
struct radnode* com;
uint8_t* common_str=NULL, *s1_str=NULL, *s2_str=NULL;
radstrlen_type common_len, s1_len=0, s2_len=0;
common_len = bstr_common(r->str, r->len, addstr, addlen);
assert(common_len < r->len);
assert(common_len < addlen);
/* create the new node for choice */
com = (struct radnode*)region_alloc_zero(region, sizeof(*com));
if(!com) return 0; /* out of memory */
/* create the two substrings for subchoices */
if(r->len-common_len > 1) {
/* shift by one char because it goes in lookup array */
if(!radsel_prefix_remainder(region, common_len+1,
r->str, r->len, &s1_str, &s1_len)) {
region_recycle(region, com, sizeof(*com));
return 0;
}
}
if(addlen-common_len > 1) {
if(!radsel_prefix_remainder(region, common_len+1,
addstr, addlen, &s2_str, &s2_len)) {
region_recycle(region, com, sizeof(*com));
region_recycle(region, s1_str, s1_len);
return 0;
}
}
/* create the shared prefix to go in r */
if(common_len > 0) {
common_str = (uint8_t*)region_alloc(region,
common_len*sizeof(uint8_t));
if(!common_str) {
region_recycle(region, com, sizeof(*com));
region_recycle(region, s1_str, s1_len);
region_recycle(region, s2_str, s2_len);
return 0;
}
memcpy(common_str, addstr, common_len);
}
/* make space in the common node array */
if(!radnode_array_space(region, com, r->str[common_len]) ||
!radnode_array_space(region, com, addstr[common_len])) {
region_recycle(region, com->array, com->capacity*sizeof(struct radsel));
region_recycle(region, com, sizeof(*com));
region_recycle(region, common_str, common_len);
region_recycle(region, s1_str, s1_len);
region_recycle(region, s2_str, s2_len);
return 0;
}
/* allocs succeeded, proceed to link it all up */
com->parent = r->node->parent;
com->pidx = r->node->pidx;
r->node->parent = com;
r->node->pidx = r->str[common_len]-com->offset;
add->parent = com;
add->pidx = addstr[common_len]-com->offset;
com->array[r->node->pidx].node = r->node;
com->array[r->node->pidx].str = s1_str;
com->array[r->node->pidx].len = s1_len;
com->array[add->pidx].node = add;
com->array[add->pidx].str = s2_str;
com->array[add->pidx].len = s2_len;
region_recycle(region, r->str, r->len);
r->str = common_str;
r->len = common_len;
r->node = com;
}
return 1;
}
struct radnode* radix_insert(struct radtree* rt, uint8_t* k,
radstrlen_type len, void* elem)
{
struct radnode* n;
radstrlen_type pos = 0;
/* create new element to add */
struct radnode* add = (struct radnode*)region_alloc_zero(rt->region,
sizeof(*add));
if(!add) return NULL; /* out of memory */
add->elem = elem;
/* find out where to add it */
if(!radix_find_prefix_node(rt, k, len, &n, &pos)) {
/* new root */
assert(rt->root == NULL);
if(len == 0) {
rt->root = add;
} else {
/* add a root to point to new node */
n = (struct radnode*)region_alloc_zero(rt->region,
sizeof(*n));
if(!n) {
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
if(!radnode_array_space(rt->region, n, k[0])) {
region_recycle(rt->region, n->array,
n->capacity*sizeof(struct radsel));
region_recycle(rt->region, n, sizeof(*n));
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
add->parent = n;
add->pidx = 0;
n->array[0].node = add;
if(len > 1) {
if(!radsel_prefix_remainder(rt->region, 1, k, len,
&n->array[0].str, &n->array[0].len)) {
region_recycle(rt->region, n->array,
n->capacity*sizeof(struct radsel));
region_recycle(rt->region, n, sizeof(*n));
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
}
rt->root = n;
}
} else if(pos == len) {
/* found an exact match */
if(n->elem) {
/* already exists, failure */
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
n->elem = elem;
region_recycle(rt->region, add, sizeof(*add));
add = n;
} else {
/* n is a node which can accomodate */
uint8_t byte;
assert(pos < len);
byte = k[pos];
/* see if it falls outside of array */
if(byte < n->offset || byte-n->offset >= n->len) {
/* make space in the array for it; adjusts offset */
if(!radnode_array_space(rt->region, n, byte)) {
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
assert(byte>=n->offset && byte-n->offset<n->len);
byte -= n->offset;
/* see if more prefix needs to be split off */
if(pos+1 < len) {
if(!radsel_str_create(rt->region, &n->array[byte],
k, pos+1, len)) {
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
}
/* insert the new node in the new bucket */
add->parent = n;
add->pidx = byte;
n->array[byte].node = add;
/* so a bucket exists and byte falls in it */
} else if(n->array[byte-n->offset].node == NULL) {
/* use existing bucket */
byte -= n->offset;
if(pos+1 < len) {
/* split off more prefix */
if(!radsel_str_create(rt->region, &n->array[byte],
k, pos+1, len)) {
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
}
/* insert the new node in the new bucket */
add->parent = n;
add->pidx = byte;
n->array[byte].node = add;
} else {
/* use bucket but it has a shared prefix,
* split that out and create a new intermediate
* node to split out between the two.
* One of the two might exactmatch the new
* intermediate node */
if(!radsel_split(rt->region, &n->array[byte-n->offset],
k, pos+1, len, add)) {
region_recycle(rt->region, add, sizeof(*add));
return NULL;
}
}
}
rt->count ++;
return add;
}
/** Delete a radnode */
static void radnode_delete(struct region* region, struct radnode* n)
{
unsigned i;
if(!n) return;
for(i=0; i<n->len; i++) {
/* safe to free NULL str */
region_recycle(region, n->array[i].str, n->array[i].len);
}
region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
region_recycle(region, n, sizeof(*n));
}
/** Cleanup node with one child, it is removed and joined into parent[x] str */
static int
radnode_cleanup_onechild(struct region* region, struct radnode* n,
struct radnode* par)
{
uint8_t* join;
radstrlen_type joinlen;
uint8_t pidx = n->pidx;
struct radnode* child = n->array[0].node;
/* node had one child, merge them into the parent. */
/* keep the child node, so its pointers stay valid. */
/* at parent, append child->str to array str */
assert(pidx < par->len);
joinlen = par->array[pidx].len + n->array[0].len + 1;
join = (uint8_t*)region_alloc(region, joinlen*sizeof(uint8_t));
if(!join) {
/* cleanup failed due to out of memory */
/* the tree is inefficient, with node n still existing */
return 0;
}
/* we know that .str and join are malloced, thus aligned */
if(par->array[pidx].str)
memcpy(join, par->array[pidx].str, par->array[pidx].len);
/* the array lookup is gone, put its character in the lookup string*/
join[par->array[pidx].len] = child->pidx + n->offset;
/* but join+len may not be aligned */
if(n->array[0].str)
memmove(join+par->array[pidx].len+1, n->array[0].str, n->array[0].len);
region_recycle(region, par->array[pidx].str, par->array[pidx].len);
par->array[pidx].str = join;
par->array[pidx].len = joinlen;
/* and set the node to our child. */
par->array[pidx].node = child;
child->parent = par;
child->pidx = pidx;
/* we are unlinked, delete our node */
radnode_delete(region, n);
return 1;
}
/** remove array of nodes */
static void
radnode_array_clean_all(struct region* region, struct radnode* n)
{
n->offset = 0;
n->len = 0;
/* shrink capacity */
region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
n->array = NULL;
n->capacity = 0;
}
/** see if capacity can be reduced for the given node array */
static void
radnode_array_reduce_if_needed(struct region* region, struct radnode* n)
{
if(n->len <= n->capacity/2 && n->len != n->capacity) {
struct radsel* a = (struct radsel*)region_alloc_array(region,
sizeof(*a), n->len);
if(!a) return;
memcpy(a, n->array, sizeof(*a)*n->len);
region_recycle(region, n->array, n->capacity*sizeof(*a));
n->array = a;
n->capacity = n->len;
}
}
/** remove NULL nodes from front of array */
static void
radnode_array_clean_front(struct region* region, struct radnode* n)
{
/* move them up and adjust offset */
unsigned idx, shuf = 0;
/* remove until a nonNULL entry */
while(shuf < n->len && n->array[shuf].node == NULL)
shuf++;
if(shuf == 0)
return;
if(shuf == n->len) {
/* the array is empty, the tree is inefficient */
radnode_array_clean_all(region, n);
return;
}
assert(shuf < n->len);
assert((int)shuf <= 255-(int)n->offset);
memmove(&n->array[0], &n->array[shuf],
(n->len - shuf)*sizeof(struct radsel));
n->offset += shuf;
n->len -= shuf;
for(idx=0; idx<n->len; idx++)
if(n->array[idx].node)
n->array[idx].node->pidx = idx;
/* see if capacity can be reduced */
radnode_array_reduce_if_needed(region, n);
}
/** remove NULL nodes from end of array */
static void
radnode_array_clean_end(struct region* region, struct radnode* n)
{
/* shorten it */
unsigned shuf = 0;
/* remove until a nonNULL entry */
while(shuf < n->len && n->array[n->len-1-shuf].node == NULL)
shuf++;
if(shuf == 0)
return;
if(shuf == n->len) {
/* the array is empty, the tree is inefficient */
radnode_array_clean_all(region, n);
return;
}
assert(shuf < n->len);
n->len -= shuf;
/* array elements can stay where they are */
/* see if capacity can be reduced */
radnode_array_reduce_if_needed(region, n);
}
/** clean up radnode leaf, where we know it has a parent */
static void
radnode_cleanup_leaf(struct region* region, struct radnode* n,
struct radnode* par)
{
uint8_t pidx;
/* node was a leaf */
/* delete leaf node, but store parent+idx */
pidx = n->pidx;
radnode_delete(region, n);
/* set parent+idx entry to NULL str and node.*/
assert(pidx < par->len);
region_recycle(region, par->array[pidx].str, par->array[pidx].len);
par->array[pidx].str = NULL;
par->array[pidx].len = 0;
par->array[pidx].node = NULL;
/* see if par offset or len must be adjusted */
if(par->len == 1) {
/* removed final element from array */
radnode_array_clean_all(region, par);
} else if(pidx == 0) {
/* removed first element from array */
radnode_array_clean_front(region, par);
} else if(pidx == par->len-1) {
/* removed last element from array */
radnode_array_clean_end(region, par);
}
}
/**
* Cleanup a radix node that was made smaller, see if it can
* be merged with others.
* @param rt: tree to remove root if needed.
* @param n: node to cleanup
* @return false on alloc failure.
*/
static int
radnode_cleanup(struct radtree* rt, struct radnode* n)
{
while(n) {
if(n->elem) {
/* cannot delete node with a data element */
return 1;
} else if(n->len == 1 && n->parent) {
return radnode_cleanup_onechild(rt->region, n, n->parent);
} else if(n->len == 0) {
struct radnode* par = n->parent;
if(!par) {
/* root deleted */
radnode_delete(rt->region, n);
rt->root = NULL;
return 1;
}
/* remove and delete the leaf node */
radnode_cleanup_leaf(rt->region, n, par);
/* see if parent can now be cleaned up */
n = par;
} else {
/* node cannot be cleaned up */
return 1;
}
}
/* ENOTREACH */
return 1;
}
void radix_delete(struct radtree* rt, struct radnode* n)
{
if(!n) return;
n->elem = NULL;
rt->count --;
if(!radnode_cleanup(rt, n)) {
/* out of memory in cleanup. the elem ptr is NULL, but
* the radix tree could be inefficient. */
}
}
struct radnode* radix_search(struct radtree* rt, uint8_t* k,
radstrlen_type len)
{
struct radnode* n = rt->root;
radstrlen_type pos = 0;
uint8_t byte;
while(n) {
if(pos == len)
return n->elem?n:NULL;
byte = k[pos];
if(byte < n->offset)
return NULL;
byte -= n->offset;
if(byte >= n->len)
return NULL;
pos++;
if(n->array[byte].len != 0) {
/* must match additional string */
if(pos+n->array[byte].len > len)
return NULL; /* no match */
if(memcmp(&k[pos], n->array[byte].str,
n->array[byte].len) != 0)
return NULL; /* no match */
pos += n->array[byte].len;
}
n = n->array[byte].node;
}
return NULL;
}
/** return self or a previous element */
static int ret_self_or_prev(struct radnode* n, struct radnode** result)
{
if(n->elem)
*result = n;
else *result = radix_prev(n);
return 0;
}
int radix_find_less_equal(struct radtree* rt, uint8_t* k, radstrlen_type len,
struct radnode** result)
{
struct radnode* n = rt->root;
radstrlen_type pos = 0;
uint8_t byte;
int r;
if(!n) {
/* empty tree */
*result = NULL;
return 0;
}
while(pos < len) {
byte = k[pos];
if(byte < n->offset) {
/* so the previous is the element itself */
/* or something before this element */
return ret_self_or_prev(n, result);
}
byte -= n->offset;
if(byte >= n->len) {
/* so, the previous is the last of array, or itself */
/* or something before this element */
if((*result=radnode_last_in_subtree_incl_self(n))==0)
*result = radix_prev(n);
return 0;
}
pos++;
if(!n->array[byte].node) {
/* no match */
/* Find an entry in arrays from byte-1 to 0 */
*result = radnode_find_prev_from_idx(n, byte);
if(*result)
return 0;
/* this entry or something before it */
return ret_self_or_prev(n, result);
}
if(n->array[byte].len != 0) {
/* must match additional string */
if(pos+n->array[byte].len > len) {
/* the additional string is longer than key*/
if( (memcmp(&k[pos], n->array[byte].str,
len-pos)) <= 0) {
/* and the key is before this node */
*result = radix_prev(n->array[byte].node);
} else {
/* the key is after the additional
* string, thus everything in that
* subtree is smaller. */
*result=radnode_last_in_subtree_incl_self(n->array[byte].node);
/* if somehow that is NULL,
* then we have an inefficient tree:
* byte+1 is larger than us, so find
* something in byte-1 and before */
if(!*result)
*result = radix_prev(n->array[byte].node);
}
return 0; /* no match */
}
if( (r=memcmp(&k[pos], n->array[byte].str,
n->array[byte].len)) < 0) {
*result = radix_prev(n->array[byte].node);
return 0; /* no match */
} else if(r > 0) {
/* the key is larger than the additional
* string, thus everything in that subtree
* is smaller */
*result=radnode_last_in_subtree_incl_self(n->array[byte].node);
/* if we have an inefficient tree */
if(!*result) *result = radix_prev(n->array[byte].node);
return 0; /* no match */
}
pos += n->array[byte].len;
}
n = n->array[byte].node;
}
if(n->elem) {
/* exact match */
*result = n;
return 1;
}
/* there is a node which is an exact match, but it has no element */
*result = radix_prev(n);
return 0;
}
struct radnode* radix_first(struct radtree* rt)
{
struct radnode* n;
if(!rt || !rt->root) return NULL;
n = rt->root;
if(n->elem) return n;
return radix_next(n);
}
struct radnode* radix_last(struct radtree* rt)
{
if(!rt || !rt->root) return NULL;
return radnode_last_in_subtree_incl_self(rt->root);
}
struct radnode* radix_next(struct radnode* n)
{
if(!n) return NULL;
if(n->len) {
/* go down */
struct radnode* s = radnode_first_in_subtree(n);
if(s) return s;
}
/* go up - the parent->elem is not useful, because it is before us */
while(n->parent) {
unsigned idx = n->pidx;
n = n->parent;
idx++;
for(; idx < n->len; idx++) {
/* go down the next branch */
if(n->array[idx].node) {
struct radnode* s;
/* node itself */
if(n->array[idx].node->elem)
return n->array[idx].node;
/* or subtree */
s = radnode_first_in_subtree(
n->array[idx].node);
if(s) return s;
}
}
}
return NULL;
}
struct radnode* radix_prev(struct radnode* n)
{
if(!n) return NULL;
/* must go up, since all array nodes are after this node */
while(n->parent) {
uint8_t idx = n->pidx;
struct radnode* s;
n = n->parent;
assert(n->len > 0); /* since we are a child */
/* see if there are elements in previous branches there */
s = radnode_find_prev_from_idx(n, idx);
if(s) return s;
/* the current node is before the array */
if(n->elem)
return n;
}
return NULL;
}
/** convert one character from domain-name to radname */
static uint8_t char_d2r(uint8_t c)
{
if(c < 'A') return c+1; /* make space for 00 */
else if(c <= 'Z') return c-'A'+'a'; /* lowercase */
else return c;
}
/** convert one character from radname to domain-name (still lowercased) */
static uint8_t char_r2d(uint8_t c)
{
assert(c != 0); /* end of label */
if(c <= 'A') return c-1;
else return c;
}
/** copy and convert a range of characters */
static void cpy_d2r(uint8_t* to, const uint8_t* from, int len)
{
int i;
for(i=0; i<len; i++)
to[i] = char_d2r(from[i]);
}
/** copy and convert a range of characters */
static void cpy_r2d(uint8_t* to, uint8_t* from, uint8_t len)
{
uint8_t i;
for(i=0; i<len; i++)
to[i] = char_r2d(from[i]);
}
/* radname code: domain to radix-bstring */
void radname_d2r(uint8_t* k, radstrlen_type* len, const uint8_t* dname,
size_t dlen)
{
/* the domain name is converted as follows,
* to preserve the normal (NSEC) ordering of domain names.
* lowercased, and 'end-of-label' is a '00' byte,
* bytes 00-'A' are +1 moved to make space for 00 byte.
* final root label is not appended (string ends).
* because the only allowed empty label is the final root label,
* we can also remove the last 00 label-end.
* The total result length is one-or-two less than the dname.
*
* examples (numbers are bytes, letters are ascii):
* - root: dname: 0, radname: ''
* - nl.: dname: 3nl0, radname: 'nl'
* - labs.nl: dname 4labs3nl0, radname: 'nl0labs'
* - x.labs.nl: dname 1x4labs3nl0, radname: 'nl0labs0x'
*/
/* conversion by putting the label starts on a stack */
const uint8_t* labstart[130];
unsigned int lab = 0, kpos, dpos = 0;
/* sufficient space */
assert(k && dname);
assert(dlen <= 256); /* and therefore not more than 128 labels */
assert(*len >= dlen);
assert(dlen > 0); /* even root label has dlen=1 */
/* root */
if(dlen == 1) {
assert(dname[0] == 0);
*len = 0;
return;
}
/* walk through domain name and remember label positions */
do {
/* compression pointers not allowed */
if((dname[dpos] & 0xc0)) {
*len = 0;
return; /* format error */
}
labstart[lab++] = &dname[dpos];
if(dpos + dname[dpos] + 1 >= dlen) {
*len = 0;
return; /* format error */
}
/* skip the label contents */
dpos += dname[dpos];
dpos ++;
} while(dname[dpos] != 0);
/* exit condition makes root label not in labelstart stack */
/* because the root was handled before, we know there is some text */
assert(lab > 0);
lab-=1;
kpos = *labstart[lab];
cpy_d2r(k, labstart[lab]+1, kpos);
/* if there are more labels, copy them over */
while(lab) {
/* put 'end-of-label' 00 to end previous label */
k[kpos++]=0;
/* append the label */
lab--;
cpy_d2r(k+kpos, labstart[lab]+1, *labstart[lab]);
kpos += *labstart[lab];
}
/* done */
assert(kpos == dlen-2); /* no rootlabel, one less label-marker */
*len = kpos;
}
/* radname code: radix-bstring to domain */
void radname_r2d(uint8_t* k, radstrlen_type len, uint8_t* dname, size_t* dlen)
{
/* find labels and push on stack */
uint8_t* labstart[130];
uint8_t lablen[130];
unsigned int lab = 0, dpos, kpos = 0;
/* sufficient space */
assert(k && dname);
assert((size_t)*dlen >= (size_t)len+2);
assert(len <= 256);
/* root label */
if(len == 0) {
assert(*dlen > 0);
dname[0]=0;
*dlen=1;
return;
}
/* find labels */
while(kpos < len) {
lablen[lab]=0;
labstart[lab]=&k[kpos];
/* skip to next label */
while(kpos < len && k[kpos] != 0) {
lablen[lab]++;
kpos++;
}
lab++;
/* skip 00 byte for label-end */
if(kpos < len) {
assert(k[kpos] == 0);
kpos++;
}
}
/* copy the labels over to the domain name */
dpos = 0;
while(lab) {
lab--;
/* label length */
dname[dpos++] = lablen[lab];
/* label content */
cpy_r2d(dname+dpos, labstart[lab], lablen[lab]);
dpos += lablen[lab];
}
/* append root label */
dname[dpos++] = 0;
/* assert the domain name is wellformed */
assert((int)dpos == (int)len+2);
assert(dname[dpos-1] == 0); /* ends with root label */
*dlen = dpos;
}
/** insert by domain name */
struct radnode*
radname_insert(struct radtree* rt, const uint8_t* d, size_t max, void* elem)
{
/* convert and insert */
uint8_t radname[300];
radstrlen_type len = (radstrlen_type)sizeof(radname);
if(max > sizeof(radname))
return NULL; /* too long */
radname_d2r(radname, &len, d, max);
return radix_insert(rt, radname, len, elem);
}
/** delete by domain name */
void
radname_delete(struct radtree* rt, const uint8_t* d, size_t max)
{
/* search and remove */
struct radnode* n = radname_search(rt, d, max);
if(n) radix_delete(rt, n);
}
/* search for exact match of domain name, converted to radname in tree */
struct radnode* radname_search(struct radtree* rt, const uint8_t* d,
size_t max)
{
/* stack of labels in the domain name */
const uint8_t* labstart[130];
unsigned int lab, dpos, lpos;
struct radnode* n = rt->root;
uint8_t byte;
radstrlen_type i;
uint8_t b;
/* search for root? it is '' */
if(max < 1)
return NULL;
if(d[0] == 0) {
if(!n) return NULL;
return n->elem?n:NULL;
}
/* find labels stack in domain name */
lab = 0;
dpos = 0;
/* must have one label, since root is specialcased */
do {
if((d[dpos] & 0xc0))
return NULL; /* compression ptrs not allowed error */
labstart[lab++] = &d[dpos];
if(dpos + d[dpos] + 1 >= max)
return NULL; /* format error: outside of bounds */
/* skip the label contents */
dpos += d[dpos];
dpos ++;
} while(d[dpos] != 0);
/* exit condition makes that root label is not in the labstarts */
/* now: dpos+1 is length of domain name. lab is number of labels-1 */
/* start processing at the last label */
lab-=1;
lpos = 0;
while(n) {
/* fetch next byte this label */
if(lpos < *labstart[lab])
/* lpos+1 to skip labelstart, lpos++ to move forward */
byte = char_d2r(labstart[lab][++lpos]);
else {
if(lab == 0) /* last label - we're done */
return n->elem?n:NULL;
/* next label, search for byte 00 */
lpos = 0;
lab--;
byte = 0;
}
/* find that byte in the array */
if(byte < n->offset)
return NULL;
byte -= n->offset;
if(byte >= n->len)
return NULL;
if(n->array[byte].len != 0) {
/* must match additional string */
/* see how many bytes we need and start matching them*/
for(i=0; i<n->array[byte].len; i++) {
/* next byte to match */
if(lpos < *labstart[lab])
b = char_d2r(labstart[lab][++lpos]);
else {
/* if last label, no match since
* we are in the additional string */
if(lab == 0)
return NULL;
/* next label, search for byte 00 */
lpos = 0;
lab--;
b = 0;
}
if(n->array[byte].str[i] != b)
return NULL; /* not matched */
}
}
n = n->array[byte].node;
}
return NULL;
}
/* find domain name or smaller or equal domain name in radix tree */
int radname_find_less_equal(struct radtree* rt, const uint8_t* d, size_t max,
struct radnode** result)
{
/* stack of labels in the domain name */
const uint8_t* labstart[130];
unsigned int lab, dpos, lpos;
struct radnode* n = rt->root;
uint8_t byte;
radstrlen_type i;
uint8_t b;
/* empty tree */
if(!n) {
*result = NULL;
return 0;
}
/* search for root? it is '' */
if(max < 1) {
*result = NULL;
return 0; /* parse error, out of bounds */
}
if(d[0] == 0) {
if(n->elem) {
*result = n;
return 1;
}
/* no smaller element than the root */
*result = NULL;
return 0;
}
/* find labels stack in domain name */
lab = 0;
dpos = 0;
/* must have one label, since root is specialcased */
do {
if((d[dpos] & 0xc0)) {
*result = NULL;
return 0; /* compression ptrs not allowed error */
}
labstart[lab++] = &d[dpos];
if(dpos + d[dpos] + 1 >= max) {
*result = NULL; /* format error: outside of bounds */
return 0;
}
/* skip the label contents */
dpos += d[dpos];
dpos ++;
} while(d[dpos] != 0);
/* exit condition makes that root label is not in the labstarts */
/* now: dpos+1 is length of domain name. lab is number of labels-1 */
/* start processing at the last label */
lab-=1;
lpos = 0;
while(1) {
/* fetch next byte this label */
if(lpos < *labstart[lab])
/* lpos+1 to skip labelstart, lpos++ to move forward */
byte = char_d2r(labstart[lab][++lpos]);
else {
if(lab == 0) {
/* last label - we're done */
/* exact match */
if(n->elem) {
*result = n;
return 1;
}
/* there is a node which is an exact match,
* but there no element in it */
*result = radix_prev(n);
return 0;
}
/* next label, search for byte 0 the label separator */
lpos = 0;
lab--;
byte = 0;
}
/* find that byte in the array */
if(byte < n->offset)
/* so the previous is the element itself */
/* or something before this element */
return ret_self_or_prev(n, result);
byte -= n->offset;
if(byte >= n->len) {
/* so, the previous is the last of array, or itself */
/* or something before this element */
*result = radnode_last_in_subtree_incl_self(n);
if(!*result)
*result = radix_prev(n);
return 0;
}
if(!n->array[byte].node) {
/* no match */
/* Find an entry in arrays from byte-1 to 0 */
*result = radnode_find_prev_from_idx(n, byte);
if(*result)
return 0;
/* this entry or something before it */
return ret_self_or_prev(n, result);
}
if(n->array[byte].len != 0) {
/* must match additional string */
/* see how many bytes we need and start matching them*/
for(i=0; i<n->array[byte].len; i++) {
/* next byte to match */
if(lpos < *labstart[lab])
b = char_d2r(labstart[lab][++lpos]);
else {
/* if last label, no match since
* we are in the additional string */
if(lab == 0) {
/* dname ended, thus before
* this array element */
*result =radix_prev(
n->array[byte].node);
return 0;
}
/* next label, search for byte 00 */
lpos = 0;
lab--;
b = 0;
}
if(b < n->array[byte].str[i]) {
*result =radix_prev(
n->array[byte].node);
return 0;
} else if(b > n->array[byte].str[i]) {
/* the key is after the additional,
* so everything in its subtree is
* smaller */
*result = radnode_last_in_subtree_incl_self(n->array[byte].node);
/* if that is NULL, we have an
* inefficient tree, find in byte-1*/
if(!*result)
*result = radix_prev(n->array[byte].node);
return 0;
}
}
}
n = n->array[byte].node;
}
/* ENOTREACH */
return 0;
}
