1d3fecca9Ssthen /* 2d3fecca9Ssthen * radtree -- generic radix tree for binary strings. 3d3fecca9Ssthen * 4d3fecca9Ssthen * Copyright (c) 2010, NLnet Labs. See LICENSE for license. 5d3fecca9Ssthen */ 6d3fecca9Ssthen #include "config.h" 7d3fecca9Ssthen #include <assert.h> 8d3fecca9Ssthen #include <stdlib.h> 9d3fecca9Ssthen #include <string.h> 10d3fecca9Ssthen #include <unistd.h> 11d3fecca9Ssthen #include <time.h> 12d3fecca9Ssthen #include "radtree.h" 13d3fecca9Ssthen #include "util.h" 14d3fecca9Ssthen #include "region-allocator.h" 15d3fecca9Ssthen 16d3fecca9Ssthen #include <stdio.h> 17d3fecca9Ssthen #include <ctype.h> 18d3fecca9Ssthen 19d3fecca9Ssthen struct radtree* radix_tree_create(struct region* region) 20d3fecca9Ssthen { 21d3fecca9Ssthen struct radtree* rt = (struct radtree*)region_alloc(region, sizeof(*rt)); 22d3fecca9Ssthen if(!rt) return NULL; 23d3fecca9Ssthen rt->region = region; 24d3fecca9Ssthen radix_tree_init(rt); 25d3fecca9Ssthen return rt; 26d3fecca9Ssthen } 27d3fecca9Ssthen 28d3fecca9Ssthen void radix_tree_init(struct radtree* rt) 29d3fecca9Ssthen { 30d3fecca9Ssthen rt->root = NULL; 31d3fecca9Ssthen rt->count = 0; 32d3fecca9Ssthen } 33d3fecca9Ssthen 34d3fecca9Ssthen /** delete radnodes in postorder recursion */ 35d3fecca9Ssthen static void radnode_del_postorder(struct region* region, struct radnode* n) 36d3fecca9Ssthen { 37d3fecca9Ssthen unsigned i; 38d3fecca9Ssthen if(!n) return; 39d3fecca9Ssthen for(i=0; i<n->len; i++) { 40d3fecca9Ssthen radnode_del_postorder(region, n->array[i].node); 41d3fecca9Ssthen region_recycle(region, n->array[i].str, n->array[i].len); 42d3fecca9Ssthen } 43d3fecca9Ssthen region_recycle(region, n->array, n->capacity*sizeof(struct radsel)); 44d3fecca9Ssthen region_recycle(region, n, sizeof(*n)); 45d3fecca9Ssthen } 46d3fecca9Ssthen 47d3fecca9Ssthen void radix_tree_clear(struct radtree* rt) 48d3fecca9Ssthen { 49d3fecca9Ssthen radnode_del_postorder(rt->region, rt->root); 50d3fecca9Ssthen rt->root = NULL; 51d3fecca9Ssthen rt->count = 0; 52d3fecca9Ssthen } 53d3fecca9Ssthen 54d3fecca9Ssthen void radix_tree_delete(struct radtree* rt) 55d3fecca9Ssthen { 56d3fecca9Ssthen if(!rt) return; 57d3fecca9Ssthen radix_tree_clear(rt); 58d3fecca9Ssthen region_recycle(rt->region, rt, sizeof(*rt)); 59d3fecca9Ssthen } 60d3fecca9Ssthen 61d3fecca9Ssthen /** return last elem-containing node in this subtree (excl self) */ 62d3fecca9Ssthen static struct radnode* 63d3fecca9Ssthen radnode_last_in_subtree(struct radnode* n) 64d3fecca9Ssthen { 65d3fecca9Ssthen int idx; 66d3fecca9Ssthen /* try last entry in array first */ 67d3fecca9Ssthen for(idx=((int)n->len)-1; idx >= 0; idx--) { 68d3fecca9Ssthen if(n->array[idx].node) { 69d3fecca9Ssthen /* does it have entries in its subtrees? */ 70d3fecca9Ssthen if(n->array[idx].node->len > 0) { 71d3fecca9Ssthen struct radnode* s = radnode_last_in_subtree( 72d3fecca9Ssthen n->array[idx].node); 73d3fecca9Ssthen if(s) return s; 74d3fecca9Ssthen } 75d3fecca9Ssthen /* no, does it have an entry itself? */ 76d3fecca9Ssthen if(n->array[idx].node->elem) 77d3fecca9Ssthen return n->array[idx].node; 78d3fecca9Ssthen } 79d3fecca9Ssthen } 80d3fecca9Ssthen return NULL; 81d3fecca9Ssthen } 82d3fecca9Ssthen 83d3fecca9Ssthen /** last in subtree, incl self */ 84d3fecca9Ssthen static struct radnode* 85d3fecca9Ssthen radnode_last_in_subtree_incl_self(struct radnode* n) 86d3fecca9Ssthen { 87d3fecca9Ssthen struct radnode* s = radnode_last_in_subtree(n); 88d3fecca9Ssthen if(s) return s; 89d3fecca9Ssthen if(n->elem) return n; 90d3fecca9Ssthen return NULL; 91d3fecca9Ssthen } 92d3fecca9Ssthen 93d3fecca9Ssthen /** return first elem-containing node in this subtree (excl self) */ 94d3fecca9Ssthen static struct radnode* 95d3fecca9Ssthen radnode_first_in_subtree(struct radnode* n) 96d3fecca9Ssthen { 97d3fecca9Ssthen unsigned idx; 98d3fecca9Ssthen struct radnode* s; 99d3fecca9Ssthen /* try every subnode */ 100d3fecca9Ssthen for(idx=0; idx<n->len; idx++) { 101d3fecca9Ssthen if(n->array[idx].node) { 102d3fecca9Ssthen /* does it have elem itself? */ 103d3fecca9Ssthen if(n->array[idx].node->elem) 104d3fecca9Ssthen return n->array[idx].node; 105d3fecca9Ssthen /* try its subtrees */ 106d3fecca9Ssthen if((s=radnode_first_in_subtree(n->array[idx].node))!=0) 107d3fecca9Ssthen return s; 108d3fecca9Ssthen } 109d3fecca9Ssthen } 110d3fecca9Ssthen return NULL; 111d3fecca9Ssthen } 112d3fecca9Ssthen 113d3fecca9Ssthen /** Find an entry in arrays from idx-1 to 0 */ 114d3fecca9Ssthen static struct radnode* 115d3fecca9Ssthen radnode_find_prev_from_idx(struct radnode* n, unsigned from) 116d3fecca9Ssthen { 117d3fecca9Ssthen unsigned idx = from; 118d3fecca9Ssthen while(idx > 0) { 119d3fecca9Ssthen idx --; 120d3fecca9Ssthen if(n->array[idx].node) { 121d3fecca9Ssthen struct radnode* s = radnode_last_in_subtree_incl_self( 122d3fecca9Ssthen n->array[idx].node); 123d3fecca9Ssthen if(s) return s; 124d3fecca9Ssthen } 125d3fecca9Ssthen } 126d3fecca9Ssthen return NULL; 127d3fecca9Ssthen } 128d3fecca9Ssthen 129d3fecca9Ssthen /** 130d3fecca9Ssthen * Find a prefix of the key, in whole-nodes. 131d3fecca9Ssthen * Finds the longest prefix that corresponds to a whole radnode entry. 132d3fecca9Ssthen * There may be a slightly longer prefix in one of the array elements. 133d3fecca9Ssthen * @param result: the longest prefix, the entry itself if *respos==len, 134d3fecca9Ssthen * otherwise an array entry, residx. 135d3fecca9Ssthen * @param respos: pos in string where next unmatched byte is, if == len an 136d3fecca9Ssthen * exact match has been found. If == 0 then a "" match was found. 137d3fecca9Ssthen * @return false if no prefix found, not even the root "" prefix. 138d3fecca9Ssthen */ 139d3fecca9Ssthen static int radix_find_prefix_node(struct radtree* rt, uint8_t* k, 140d3fecca9Ssthen radstrlen_t len, struct radnode** result, radstrlen_t* respos) 141d3fecca9Ssthen { 142d3fecca9Ssthen struct radnode* n = rt->root; 143d3fecca9Ssthen radstrlen_t pos = 0; 144d3fecca9Ssthen uint8_t byte; 145d3fecca9Ssthen *respos = 0; 146d3fecca9Ssthen *result = n; 147d3fecca9Ssthen if(!n) return 0; 148d3fecca9Ssthen while(n) { 149d3fecca9Ssthen if(pos == len) { 150d3fecca9Ssthen return 1; 151d3fecca9Ssthen } 152d3fecca9Ssthen byte = k[pos]; 153d3fecca9Ssthen if(byte < n->offset) { 154d3fecca9Ssthen return 1; 155d3fecca9Ssthen } 156d3fecca9Ssthen byte -= n->offset; 157d3fecca9Ssthen if(byte >= n->len) { 158d3fecca9Ssthen return 1; 159d3fecca9Ssthen } 160d3fecca9Ssthen pos++; 161d3fecca9Ssthen if(n->array[byte].len != 0) { 162d3fecca9Ssthen /* must match additional string */ 163d3fecca9Ssthen if(pos+n->array[byte].len > len) { 164d3fecca9Ssthen return 1; 165d3fecca9Ssthen } 166d3fecca9Ssthen if(memcmp(&k[pos], n->array[byte].str, 167d3fecca9Ssthen n->array[byte].len) != 0) { 168d3fecca9Ssthen return 1; 169d3fecca9Ssthen } 170d3fecca9Ssthen pos += n->array[byte].len; 171d3fecca9Ssthen } 172d3fecca9Ssthen n = n->array[byte].node; 173d3fecca9Ssthen if(!n) return 1; 174d3fecca9Ssthen *respos = pos; 175d3fecca9Ssthen *result = n; 176d3fecca9Ssthen } 177d3fecca9Ssthen return 1; 178d3fecca9Ssthen } 179d3fecca9Ssthen 180d3fecca9Ssthen /** grow array to at least the given size, offset unchanged */ 181d3fecca9Ssthen static int 182d3fecca9Ssthen radnode_array_grow(struct region* region, struct radnode* n, unsigned want) 183d3fecca9Ssthen { 184d3fecca9Ssthen unsigned ns = ((unsigned)n->capacity)*2; 185d3fecca9Ssthen struct radsel* a; 186d3fecca9Ssthen assert(want <= 256); /* cannot be more, range of uint8 */ 187d3fecca9Ssthen if(want > ns) 188d3fecca9Ssthen ns = want; 189d3fecca9Ssthen if(ns > 256) ns = 256; 190d3fecca9Ssthen /* we do not use realloc, because we want to keep the old array 191d3fecca9Ssthen * in case alloc fails, so that the tree is still usable */ 192c939baa4Ssthen a = (struct radsel*)region_alloc_array(region, ns, sizeof(struct radsel)); 193d3fecca9Ssthen if(!a) return 0; 194d3fecca9Ssthen assert(n->len <= n->capacity); 195d3fecca9Ssthen assert(n->capacity < ns); 196d3fecca9Ssthen memcpy(&a[0], &n->array[0], n->len*sizeof(struct radsel)); 197d3fecca9Ssthen region_recycle(region, n->array, n->capacity*sizeof(struct radsel)); 198d3fecca9Ssthen n->array = a; 199d3fecca9Ssthen n->capacity = ns; 200d3fecca9Ssthen return 1; 201d3fecca9Ssthen } 202d3fecca9Ssthen 203d3fecca9Ssthen /** make space in radnode array for another byte */ 204d3fecca9Ssthen static int 205d3fecca9Ssthen radnode_array_space(struct region* region, struct radnode* n, uint8_t byte) 206d3fecca9Ssthen { 207d3fecca9Ssthen /* is there an array? */ 208d3fecca9Ssthen if(!n->array || n->capacity == 0) { 209d3fecca9Ssthen n->array = (struct radsel*)region_alloc(region, 210d3fecca9Ssthen sizeof(struct radsel)); 211d3fecca9Ssthen if(!n->array) return 0; 212d3fecca9Ssthen memset(&n->array[0], 0, sizeof(struct radsel)); 213d3fecca9Ssthen n->len = 1; 214d3fecca9Ssthen n->capacity = 1; 215d3fecca9Ssthen n->offset = byte; 216d3fecca9Ssthen /* is the array unused? */ 217d3fecca9Ssthen } else if(n->len == 0 && n->capacity != 0) { 218d3fecca9Ssthen n->len = 1; 219d3fecca9Ssthen n->offset = byte; 220d3fecca9Ssthen memset(&n->array[0], 0, sizeof(struct radsel)); 221d3fecca9Ssthen /* is it below the offset? */ 222d3fecca9Ssthen } else if(byte < n->offset) { 223d3fecca9Ssthen /* is capacity enough? */ 224d3fecca9Ssthen unsigned idx; 225d3fecca9Ssthen unsigned need = n->offset-byte; 226d3fecca9Ssthen if(n->len+need > n->capacity) { 227d3fecca9Ssthen /* grow array */ 228d3fecca9Ssthen if(!radnode_array_grow(region, n, n->len+need)) 229d3fecca9Ssthen return 0; 230d3fecca9Ssthen } 231d3fecca9Ssthen /* reshuffle items to end */ 232d3fecca9Ssthen memmove(&n->array[need], &n->array[0], 233d3fecca9Ssthen n->len*sizeof(struct radsel)); 234d3fecca9Ssthen /* fixup pidx */ 235d3fecca9Ssthen for(idx = 0; idx < n->len; idx++) { 236d3fecca9Ssthen if(n->array[idx+need].node) 237d3fecca9Ssthen n->array[idx+need].node->pidx = idx+need; 238d3fecca9Ssthen } 239d3fecca9Ssthen /* zero the first */ 240d3fecca9Ssthen memset(&n->array[0], 0, need*sizeof(struct radsel)); 241d3fecca9Ssthen n->len += need; 242d3fecca9Ssthen n->offset = byte; 243d3fecca9Ssthen /* is it above the max? */ 244d3fecca9Ssthen } else if(byte-n->offset >= n->len) { 245d3fecca9Ssthen /* is capacity enough? */ 246d3fecca9Ssthen unsigned need = (byte-n->offset) - n->len + 1; 247d3fecca9Ssthen /* grow array */ 248d3fecca9Ssthen if(n->len + need > n->capacity) { 249d3fecca9Ssthen if(!radnode_array_grow(region, n, n->len+need)) 250d3fecca9Ssthen return 0; 251d3fecca9Ssthen } 252d3fecca9Ssthen /* zero added entries */ 253d3fecca9Ssthen memset(&n->array[n->len], 0, need*sizeof(struct radsel)); 254d3fecca9Ssthen /* grow length */ 255d3fecca9Ssthen n->len += need; 256d3fecca9Ssthen } 257d3fecca9Ssthen return 1; 258d3fecca9Ssthen } 259d3fecca9Ssthen 260d3fecca9Ssthen /** create a prefix in the array strs */ 261d3fecca9Ssthen static int 262d3fecca9Ssthen radsel_str_create(struct region* region, struct radsel* r, uint8_t* k, 263d3fecca9Ssthen radstrlen_t pos, radstrlen_t len) 264d3fecca9Ssthen { 265d3fecca9Ssthen r->str = (uint8_t*)region_alloc(region, sizeof(uint8_t)*(len-pos)); 266d3fecca9Ssthen if(!r->str) 267d3fecca9Ssthen return 0; /* out of memory */ 268d3fecca9Ssthen memmove(r->str, k+pos, len-pos); 269d3fecca9Ssthen r->len = len-pos; 270d3fecca9Ssthen return 1; 271d3fecca9Ssthen } 272d3fecca9Ssthen 273d3fecca9Ssthen /** see if one byte string p is a prefix of another x (equality is true) */ 274d3fecca9Ssthen static int 275d3fecca9Ssthen bstr_is_prefix(uint8_t* p, radstrlen_t plen, uint8_t* x, radstrlen_t xlen) 276d3fecca9Ssthen { 277d3fecca9Ssthen /* if plen is zero, it is an (empty) prefix */ 278d3fecca9Ssthen if(plen == 0) 279d3fecca9Ssthen return 1; 280d3fecca9Ssthen /* if so, p must be shorter */ 281d3fecca9Ssthen if(plen > xlen) 282d3fecca9Ssthen return 0; 283d3fecca9Ssthen return (memcmp(p, x, plen) == 0); 284d3fecca9Ssthen } 285d3fecca9Ssthen 286d3fecca9Ssthen /** number of bytes in common for the two strings */ 287d3fecca9Ssthen static radstrlen_t 288d3fecca9Ssthen bstr_common(uint8_t* x, radstrlen_t xlen, uint8_t* y, radstrlen_t ylen) 289d3fecca9Ssthen { 290d3fecca9Ssthen unsigned i, max = ((xlen<ylen)?xlen:ylen); 291d3fecca9Ssthen for(i=0; i<max; i++) { 292d3fecca9Ssthen if(x[i] != y[i]) 293d3fecca9Ssthen return i; 294d3fecca9Ssthen } 295d3fecca9Ssthen return max; 296d3fecca9Ssthen } 297d3fecca9Ssthen 298d3fecca9Ssthen 299d3fecca9Ssthen int 300d3fecca9Ssthen bstr_is_prefix_ext(uint8_t* p, radstrlen_t plen, uint8_t* x, radstrlen_t xlen) 301d3fecca9Ssthen { 302d3fecca9Ssthen return bstr_is_prefix(p, plen, x, xlen); 303d3fecca9Ssthen } 304d3fecca9Ssthen 305d3fecca9Ssthen radstrlen_t 306d3fecca9Ssthen bstr_common_ext(uint8_t* x, radstrlen_t xlen, uint8_t* y, radstrlen_t ylen) 307d3fecca9Ssthen { 308d3fecca9Ssthen return bstr_common(x, xlen, y, ylen); 309d3fecca9Ssthen } 310d3fecca9Ssthen 311d3fecca9Ssthen /** allocate remainder from prefixes for a split: 312d3fecca9Ssthen * plen: len prefix, l: longer bstring, llen: length of l. */ 313d3fecca9Ssthen static int 314d3fecca9Ssthen radsel_prefix_remainder(struct region* region, radstrlen_t plen, 315d3fecca9Ssthen uint8_t* l, radstrlen_t llen, 316d3fecca9Ssthen uint8_t** s, radstrlen_t* slen) 317d3fecca9Ssthen { 318d3fecca9Ssthen *slen = llen - plen; 319d3fecca9Ssthen *s = (uint8_t*)region_alloc(region, (*slen)*sizeof(uint8_t)); 320d3fecca9Ssthen if(!*s) 321d3fecca9Ssthen return 0; 322d3fecca9Ssthen memmove(*s, l+plen, llen-plen); 323d3fecca9Ssthen return 1; 324d3fecca9Ssthen } 325d3fecca9Ssthen 326d3fecca9Ssthen /** radsel create a split when two nodes have shared prefix. 327d3fecca9Ssthen * @param r: radsel that gets changed, it contains a node. 328d3fecca9Ssthen * @param k: key byte string 329d3fecca9Ssthen * @param pos: position where the string enters the radsel (e.g. r.str) 330d3fecca9Ssthen * @param len: length of k. 331d3fecca9Ssthen * @param add: additional node for the string k. 332d3fecca9Ssthen * removed by called on failure. 333d3fecca9Ssthen * @return false on alloc failure, no changes made. 334d3fecca9Ssthen */ 335d3fecca9Ssthen static int 336d3fecca9Ssthen radsel_split(struct region* region, struct radsel* r, uint8_t* k, 337d3fecca9Ssthen radstrlen_t pos, radstrlen_t len, struct radnode* add) 338d3fecca9Ssthen { 339d3fecca9Ssthen uint8_t* addstr = k+pos; 340d3fecca9Ssthen radstrlen_t addlen = len-pos; 341d3fecca9Ssthen if(bstr_is_prefix(addstr, addlen, r->str, r->len)) { 342d3fecca9Ssthen uint8_t* split_str=NULL, *dupstr=NULL; 343d3fecca9Ssthen radstrlen_t split_len=0; 344d3fecca9Ssthen /* 'add' is a prefix of r.node */ 345d3fecca9Ssthen /* also for empty addstr */ 346d3fecca9Ssthen /* set it up so that the 'add' node has r.node as child */ 347d3fecca9Ssthen /* so, r.node gets moved below the 'add' node, but we do 348d3fecca9Ssthen * this so that the r.node stays the same pointer for its 349d3fecca9Ssthen * key name */ 350d3fecca9Ssthen assert(addlen != r->len); 351d3fecca9Ssthen assert(addlen < r->len); 352d3fecca9Ssthen if(r->len-addlen > 1) { 353d3fecca9Ssthen /* shift one because a char is in the lookup array */ 354d3fecca9Ssthen if(!radsel_prefix_remainder(region, addlen+1, r->str, 355d3fecca9Ssthen r->len, &split_str, &split_len)) 356d3fecca9Ssthen return 0; 357d3fecca9Ssthen } 358d3fecca9Ssthen if(addlen != 0) { 359d3fecca9Ssthen dupstr = (uint8_t*)region_alloc(region, 360d3fecca9Ssthen addlen*sizeof(uint8_t)); 361d3fecca9Ssthen if(!dupstr) { 362d3fecca9Ssthen region_recycle(region, split_str, split_len); 363d3fecca9Ssthen return 0; 364d3fecca9Ssthen } 365d3fecca9Ssthen memcpy(dupstr, addstr, addlen); 366d3fecca9Ssthen } 367d3fecca9Ssthen if(!radnode_array_space(region, add, r->str[addlen])) { 368d3fecca9Ssthen region_recycle(region, split_str, split_len); 369d3fecca9Ssthen region_recycle(region, dupstr, addlen); 370d3fecca9Ssthen return 0; 371d3fecca9Ssthen } 372d3fecca9Ssthen /* alloc succeeded, now link it in */ 373d3fecca9Ssthen add->parent = r->node->parent; 374d3fecca9Ssthen add->pidx = r->node->pidx; 375d3fecca9Ssthen add->array[0].node = r->node; 376d3fecca9Ssthen add->array[0].str = split_str; 377d3fecca9Ssthen add->array[0].len = split_len; 378d3fecca9Ssthen r->node->parent = add; 379d3fecca9Ssthen r->node->pidx = 0; 380d3fecca9Ssthen 381d3fecca9Ssthen r->node = add; 382d3fecca9Ssthen region_recycle(region, r->str, r->len); 383d3fecca9Ssthen r->str = dupstr; 384d3fecca9Ssthen r->len = addlen; 385d3fecca9Ssthen } else if(bstr_is_prefix(r->str, r->len, addstr, addlen)) { 386d3fecca9Ssthen uint8_t* split_str = NULL; 387d3fecca9Ssthen radstrlen_t split_len = 0; 388d3fecca9Ssthen /* r.node is a prefix of 'add' */ 389d3fecca9Ssthen /* set it up so that the 'r.node' has 'add' as child */ 390d3fecca9Ssthen /* and basically, r.node is already completely fine, 391d3fecca9Ssthen * we only need to create a node as its child */ 392d3fecca9Ssthen assert(addlen != r->len); 393d3fecca9Ssthen assert(r->len < addlen); 394d3fecca9Ssthen if(addlen-r->len > 1) { 395d3fecca9Ssthen /* shift one because a character goes into array */ 396d3fecca9Ssthen if(!radsel_prefix_remainder(region, r->len+1, addstr, 397d3fecca9Ssthen addlen, &split_str, &split_len)) 398d3fecca9Ssthen return 0; 399d3fecca9Ssthen } 400d3fecca9Ssthen if(!radnode_array_space(region, r->node, addstr[r->len])) { 401d3fecca9Ssthen region_recycle(region, split_str, split_len); 402d3fecca9Ssthen return 0; 403d3fecca9Ssthen } 404d3fecca9Ssthen /* alloc succeeded, now link it in */ 405d3fecca9Ssthen add->parent = r->node; 406d3fecca9Ssthen add->pidx = addstr[r->len] - r->node->offset; 407d3fecca9Ssthen r->node->array[add->pidx].node = add; 408d3fecca9Ssthen r->node->array[add->pidx].str = split_str; 409d3fecca9Ssthen r->node->array[add->pidx].len = split_len; 410d3fecca9Ssthen } else { 411d3fecca9Ssthen /* okay we need to create a new node that chooses between 412d3fecca9Ssthen * the nodes 'add' and r.node 413d3fecca9Ssthen * We do this so that r.node stays the same pointer for its 414d3fecca9Ssthen * key name. */ 415d3fecca9Ssthen struct radnode* com; 416d3fecca9Ssthen uint8_t* common_str=NULL, *s1_str=NULL, *s2_str=NULL; 417d3fecca9Ssthen radstrlen_t common_len, s1_len=0, s2_len=0; 418d3fecca9Ssthen common_len = bstr_common(r->str, r->len, addstr, addlen); 419d3fecca9Ssthen assert(common_len < r->len); 420d3fecca9Ssthen assert(common_len < addlen); 421d3fecca9Ssthen 422d3fecca9Ssthen /* create the new node for choice */ 423d3fecca9Ssthen com = (struct radnode*)region_alloc_zero(region, sizeof(*com)); 424d3fecca9Ssthen if(!com) return 0; /* out of memory */ 425d3fecca9Ssthen 426d3fecca9Ssthen /* create the two substrings for subchoices */ 427d3fecca9Ssthen if(r->len-common_len > 1) { 428d3fecca9Ssthen /* shift by one char because it goes in lookup array */ 429d3fecca9Ssthen if(!radsel_prefix_remainder(region, common_len+1, 430d3fecca9Ssthen r->str, r->len, &s1_str, &s1_len)) { 431d3fecca9Ssthen region_recycle(region, com, sizeof(*com)); 432d3fecca9Ssthen return 0; 433d3fecca9Ssthen } 434d3fecca9Ssthen } 435d3fecca9Ssthen if(addlen-common_len > 1) { 436d3fecca9Ssthen if(!radsel_prefix_remainder(region, common_len+1, 437d3fecca9Ssthen addstr, addlen, &s2_str, &s2_len)) { 438d3fecca9Ssthen region_recycle(region, com, sizeof(*com)); 439d3fecca9Ssthen region_recycle(region, s1_str, s1_len); 440d3fecca9Ssthen return 0; 441d3fecca9Ssthen } 442d3fecca9Ssthen } 443d3fecca9Ssthen 444d3fecca9Ssthen /* create the shared prefix to go in r */ 445d3fecca9Ssthen if(common_len > 0) { 446d3fecca9Ssthen common_str = (uint8_t*)region_alloc(region, 447cbbc2d6cSbrad common_len*sizeof(uint8_t)); 448d3fecca9Ssthen if(!common_str) { 449d3fecca9Ssthen region_recycle(region, com, sizeof(*com)); 450d3fecca9Ssthen region_recycle(region, s1_str, s1_len); 451d3fecca9Ssthen region_recycle(region, s2_str, s2_len); 452d3fecca9Ssthen return 0; 453d3fecca9Ssthen } 454d3fecca9Ssthen memcpy(common_str, addstr, common_len); 455d3fecca9Ssthen } 456d3fecca9Ssthen 457d3fecca9Ssthen /* make space in the common node array */ 458d3fecca9Ssthen if(!radnode_array_space(region, com, r->str[common_len]) || 459d3fecca9Ssthen !radnode_array_space(region, com, addstr[common_len])) { 460d3fecca9Ssthen region_recycle(region, com->array, com->capacity*sizeof(struct radsel)); 461d3fecca9Ssthen region_recycle(region, com, sizeof(*com)); 462d3fecca9Ssthen region_recycle(region, common_str, common_len); 463d3fecca9Ssthen region_recycle(region, s1_str, s1_len); 464d3fecca9Ssthen region_recycle(region, s2_str, s2_len); 465d3fecca9Ssthen return 0; 466d3fecca9Ssthen } 467d3fecca9Ssthen 468d3fecca9Ssthen /* allocs succeeded, proceed to link it all up */ 469d3fecca9Ssthen com->parent = r->node->parent; 470d3fecca9Ssthen com->pidx = r->node->pidx; 471d3fecca9Ssthen r->node->parent = com; 472d3fecca9Ssthen r->node->pidx = r->str[common_len]-com->offset; 473d3fecca9Ssthen add->parent = com; 474d3fecca9Ssthen add->pidx = addstr[common_len]-com->offset; 475d3fecca9Ssthen com->array[r->node->pidx].node = r->node; 476d3fecca9Ssthen com->array[r->node->pidx].str = s1_str; 477d3fecca9Ssthen com->array[r->node->pidx].len = s1_len; 478d3fecca9Ssthen com->array[add->pidx].node = add; 479d3fecca9Ssthen com->array[add->pidx].str = s2_str; 480d3fecca9Ssthen com->array[add->pidx].len = s2_len; 481d3fecca9Ssthen region_recycle(region, r->str, r->len); 482d3fecca9Ssthen r->str = common_str; 483d3fecca9Ssthen r->len = common_len; 484d3fecca9Ssthen r->node = com; 485d3fecca9Ssthen } 486d3fecca9Ssthen return 1; 487d3fecca9Ssthen } 488d3fecca9Ssthen 489d3fecca9Ssthen struct radnode* radix_insert(struct radtree* rt, uint8_t* k, radstrlen_t len, 490d3fecca9Ssthen void* elem) 491d3fecca9Ssthen { 492d3fecca9Ssthen struct radnode* n; 493d3fecca9Ssthen radstrlen_t pos = 0; 494d3fecca9Ssthen /* create new element to add */ 495d3fecca9Ssthen struct radnode* add = (struct radnode*)region_alloc_zero(rt->region, 496d3fecca9Ssthen sizeof(*add)); 497d3fecca9Ssthen if(!add) return NULL; /* out of memory */ 498d3fecca9Ssthen add->elem = elem; 499d3fecca9Ssthen 500d3fecca9Ssthen /* find out where to add it */ 501d3fecca9Ssthen if(!radix_find_prefix_node(rt, k, len, &n, &pos)) { 502d3fecca9Ssthen /* new root */ 503d3fecca9Ssthen assert(rt->root == NULL); 504d3fecca9Ssthen if(len == 0) { 505d3fecca9Ssthen rt->root = add; 506d3fecca9Ssthen } else { 507d3fecca9Ssthen /* add a root to point to new node */ 508d3fecca9Ssthen n = (struct radnode*)region_alloc_zero(rt->region, 509d3fecca9Ssthen sizeof(*n)); 510d3fecca9Ssthen if(!n) return NULL; 511d3fecca9Ssthen if(!radnode_array_space(rt->region, n, k[0])) { 512d3fecca9Ssthen region_recycle(rt->region, n->array, 513d3fecca9Ssthen n->capacity*sizeof(struct radsel)); 514d3fecca9Ssthen region_recycle(rt->region, n, sizeof(*n)); 515d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 516d3fecca9Ssthen return NULL; 517d3fecca9Ssthen } 518d3fecca9Ssthen add->parent = n; 519d3fecca9Ssthen add->pidx = 0; 520d3fecca9Ssthen n->array[0].node = add; 521d3fecca9Ssthen if(len > 1) { 522d3fecca9Ssthen if(!radsel_prefix_remainder(rt->region, 1, k, len, 523d3fecca9Ssthen &n->array[0].str, &n->array[0].len)) { 524d3fecca9Ssthen region_recycle(rt->region, n->array, 525d3fecca9Ssthen n->capacity*sizeof(struct radsel)); 526d3fecca9Ssthen region_recycle(rt->region, n, sizeof(*n)); 527d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 528d3fecca9Ssthen return NULL; 529d3fecca9Ssthen } 530d3fecca9Ssthen } 531d3fecca9Ssthen rt->root = n; 532d3fecca9Ssthen } 533d3fecca9Ssthen } else if(pos == len) { 534d3fecca9Ssthen /* found an exact match */ 535d3fecca9Ssthen if(n->elem) { 536d3fecca9Ssthen /* already exists, failure */ 537d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 538d3fecca9Ssthen return NULL; 539d3fecca9Ssthen } 540d3fecca9Ssthen n->elem = elem; 541d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 542d3fecca9Ssthen add = n; 543d3fecca9Ssthen } else { 544d3fecca9Ssthen /* n is a node which can accomodate */ 545d3fecca9Ssthen uint8_t byte; 546d3fecca9Ssthen assert(pos < len); 547d3fecca9Ssthen byte = k[pos]; 548d3fecca9Ssthen 549d3fecca9Ssthen /* see if it falls outside of array */ 550d3fecca9Ssthen if(byte < n->offset || byte-n->offset >= n->len) { 551d3fecca9Ssthen /* make space in the array for it; adjusts offset */ 552d3fecca9Ssthen if(!radnode_array_space(rt->region, n, byte)) { 553d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 554d3fecca9Ssthen return NULL; 555d3fecca9Ssthen } 556d3fecca9Ssthen assert(byte>=n->offset && byte-n->offset<n->len); 557d3fecca9Ssthen byte -= n->offset; 558d3fecca9Ssthen /* see if more prefix needs to be split off */ 559d3fecca9Ssthen if(pos+1 < len) { 560d3fecca9Ssthen if(!radsel_str_create(rt->region, &n->array[byte], 561d3fecca9Ssthen k, pos+1, len)) { 562d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 563d3fecca9Ssthen return NULL; 564d3fecca9Ssthen } 565d3fecca9Ssthen } 566d3fecca9Ssthen /* insert the new node in the new bucket */ 567d3fecca9Ssthen add->parent = n; 568d3fecca9Ssthen add->pidx = byte; 569d3fecca9Ssthen n->array[byte].node = add; 570d3fecca9Ssthen /* so a bucket exists and byte falls in it */ 571d3fecca9Ssthen } else if(n->array[byte-n->offset].node == NULL) { 572d3fecca9Ssthen /* use existing bucket */ 573d3fecca9Ssthen byte -= n->offset; 574d3fecca9Ssthen if(pos+1 < len) { 575d3fecca9Ssthen /* split off more prefix */ 576d3fecca9Ssthen if(!radsel_str_create(rt->region, &n->array[byte], 577d3fecca9Ssthen k, pos+1, len)) { 578d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 579d3fecca9Ssthen return NULL; 580d3fecca9Ssthen } 581d3fecca9Ssthen } 582d3fecca9Ssthen /* insert the new node in the new bucket */ 583d3fecca9Ssthen add->parent = n; 584d3fecca9Ssthen add->pidx = byte; 585d3fecca9Ssthen n->array[byte].node = add; 586d3fecca9Ssthen } else { 587d3fecca9Ssthen /* use bucket but it has a shared prefix, 588d3fecca9Ssthen * split that out and create a new intermediate 589d3fecca9Ssthen * node to split out between the two. 590d3fecca9Ssthen * One of the two might exactmatch the new 591d3fecca9Ssthen * intermediate node */ 592d3fecca9Ssthen if(!radsel_split(rt->region, &n->array[byte-n->offset], 593d3fecca9Ssthen k, pos+1, len, add)) { 594d3fecca9Ssthen region_recycle(rt->region, add, sizeof(*add)); 595d3fecca9Ssthen return NULL; 596d3fecca9Ssthen } 597d3fecca9Ssthen } 598d3fecca9Ssthen } 599d3fecca9Ssthen 600d3fecca9Ssthen rt->count ++; 601d3fecca9Ssthen return add; 602d3fecca9Ssthen } 603d3fecca9Ssthen 604d3fecca9Ssthen /** Delete a radnode */ 605d3fecca9Ssthen static void radnode_delete(struct region* region, struct radnode* n) 606d3fecca9Ssthen { 607d3fecca9Ssthen unsigned i; 608d3fecca9Ssthen if(!n) return; 609d3fecca9Ssthen for(i=0; i<n->len; i++) { 610d3fecca9Ssthen /* safe to free NULL str */ 611d3fecca9Ssthen region_recycle(region, n->array[i].str, n->array[i].len); 612d3fecca9Ssthen } 613d3fecca9Ssthen region_recycle(region, n->array, n->capacity*sizeof(struct radsel)); 614d3fecca9Ssthen region_recycle(region, n, sizeof(*n)); 615d3fecca9Ssthen } 616d3fecca9Ssthen 617d3fecca9Ssthen /** Cleanup node with one child, it is removed and joined into parent[x] str */ 618d3fecca9Ssthen static int 619d3fecca9Ssthen radnode_cleanup_onechild(struct region* region, struct radnode* n, 620d3fecca9Ssthen struct radnode* par) 621d3fecca9Ssthen { 622d3fecca9Ssthen uint8_t* join; 623d3fecca9Ssthen radstrlen_t joinlen; 624d3fecca9Ssthen uint8_t pidx = n->pidx; 625d3fecca9Ssthen struct radnode* child = n->array[0].node; 626d3fecca9Ssthen /* node had one child, merge them into the parent. */ 627d3fecca9Ssthen /* keep the child node, so its pointers stay valid. */ 628d3fecca9Ssthen 629d3fecca9Ssthen /* at parent, append child->str to array str */ 630d3fecca9Ssthen assert(pidx < par->len); 631d3fecca9Ssthen joinlen = par->array[pidx].len + n->array[0].len + 1; 632d3fecca9Ssthen join = (uint8_t*)region_alloc(region, joinlen*sizeof(uint8_t)); 633d3fecca9Ssthen if(!join) { 634d3fecca9Ssthen /* cleanup failed due to out of memory */ 635d3fecca9Ssthen /* the tree is inefficient, with node n still existing */ 636d3fecca9Ssthen return 0; 637d3fecca9Ssthen } 638d3fecca9Ssthen /* we know that .str and join are malloced, thus aligned */ 639*6a6b9a23Sflorian if(par->array[pidx].str) 640d3fecca9Ssthen memcpy(join, par->array[pidx].str, par->array[pidx].len); 641d3fecca9Ssthen /* the array lookup is gone, put its character in the lookup string*/ 642d3fecca9Ssthen join[par->array[pidx].len] = child->pidx + n->offset; 643d3fecca9Ssthen /* but join+len may not be aligned */ 644*6a6b9a23Sflorian if(n->array[0].str) 645d3fecca9Ssthen memmove(join+par->array[pidx].len+1, n->array[0].str, n->array[0].len); 646d3fecca9Ssthen region_recycle(region, par->array[pidx].str, par->array[pidx].len); 647d3fecca9Ssthen par->array[pidx].str = join; 648d3fecca9Ssthen par->array[pidx].len = joinlen; 649d3fecca9Ssthen /* and set the node to our child. */ 650d3fecca9Ssthen par->array[pidx].node = child; 651d3fecca9Ssthen child->parent = par; 652d3fecca9Ssthen child->pidx = pidx; 653d3fecca9Ssthen /* we are unlinked, delete our node */ 654d3fecca9Ssthen radnode_delete(region, n); 655d3fecca9Ssthen return 1; 656d3fecca9Ssthen } 657d3fecca9Ssthen 658d3fecca9Ssthen /** remove array of nodes */ 659d3fecca9Ssthen static void 660d3fecca9Ssthen radnode_array_clean_all(struct region* region, struct radnode* n) 661d3fecca9Ssthen { 662d3fecca9Ssthen n->offset = 0; 663d3fecca9Ssthen n->len = 0; 664d3fecca9Ssthen /* shrink capacity */ 665d3fecca9Ssthen region_recycle(region, n->array, n->capacity*sizeof(struct radsel)); 666d3fecca9Ssthen n->array = NULL; 667d3fecca9Ssthen n->capacity = 0; 668d3fecca9Ssthen } 669d3fecca9Ssthen 670d3fecca9Ssthen /** see if capacity can be reduced for the given node array */ 671d3fecca9Ssthen static void 672d3fecca9Ssthen radnode_array_reduce_if_needed(struct region* region, struct radnode* n) 673d3fecca9Ssthen { 674d3fecca9Ssthen if(n->len <= n->capacity/2 && n->len != n->capacity) { 675c939baa4Ssthen struct radsel* a = (struct radsel*)region_alloc_array(region, 676c939baa4Ssthen sizeof(*a), n->len); 677d3fecca9Ssthen if(!a) return; 678d3fecca9Ssthen memcpy(a, n->array, sizeof(*a)*n->len); 679d3fecca9Ssthen region_recycle(region, n->array, n->capacity*sizeof(*a)); 680d3fecca9Ssthen n->array = a; 681d3fecca9Ssthen n->capacity = n->len; 682d3fecca9Ssthen } 683d3fecca9Ssthen } 684d3fecca9Ssthen 685d3fecca9Ssthen /** remove NULL nodes from front of array */ 686d3fecca9Ssthen static void 687d3fecca9Ssthen radnode_array_clean_front(struct region* region, struct radnode* n) 688d3fecca9Ssthen { 689d3fecca9Ssthen /* move them up and adjust offset */ 690d3fecca9Ssthen unsigned idx, shuf = 0; 691d3fecca9Ssthen /* remove until a nonNULL entry */ 692d3fecca9Ssthen while(shuf < n->len && n->array[shuf].node == NULL) 693d3fecca9Ssthen shuf++; 694d3fecca9Ssthen if(shuf == 0) 695d3fecca9Ssthen return; 696d3fecca9Ssthen if(shuf == n->len) { 697d3fecca9Ssthen /* the array is empty, the tree is inefficient */ 698d3fecca9Ssthen radnode_array_clean_all(region, n); 699d3fecca9Ssthen return; 700d3fecca9Ssthen } 701d3fecca9Ssthen assert(shuf < n->len); 702d3fecca9Ssthen assert((int)shuf <= 255-(int)n->offset); 703d3fecca9Ssthen memmove(&n->array[0], &n->array[shuf], 704d3fecca9Ssthen (n->len - shuf)*sizeof(struct radsel)); 705d3fecca9Ssthen n->offset += shuf; 706d3fecca9Ssthen n->len -= shuf; 707d3fecca9Ssthen for(idx=0; idx<n->len; idx++) 708d3fecca9Ssthen if(n->array[idx].node) 709d3fecca9Ssthen n->array[idx].node->pidx = idx; 710d3fecca9Ssthen /* see if capacity can be reduced */ 711d3fecca9Ssthen radnode_array_reduce_if_needed(region, n); 712d3fecca9Ssthen } 713d3fecca9Ssthen 714d3fecca9Ssthen /** remove NULL nodes from end of array */ 715d3fecca9Ssthen static void 716d3fecca9Ssthen radnode_array_clean_end(struct region* region, struct radnode* n) 717d3fecca9Ssthen { 718d3fecca9Ssthen /* shorten it */ 719d3fecca9Ssthen unsigned shuf = 0; 720d3fecca9Ssthen /* remove until a nonNULL entry */ 721d3fecca9Ssthen while(shuf < n->len && n->array[n->len-1-shuf].node == NULL) 722d3fecca9Ssthen shuf++; 723d3fecca9Ssthen if(shuf == 0) 724d3fecca9Ssthen return; 725d3fecca9Ssthen if(shuf == n->len) { 726d3fecca9Ssthen /* the array is empty, the tree is inefficient */ 727d3fecca9Ssthen radnode_array_clean_all(region, n); 728d3fecca9Ssthen return; 729d3fecca9Ssthen } 730d3fecca9Ssthen assert(shuf < n->len); 731d3fecca9Ssthen n->len -= shuf; 732d3fecca9Ssthen /* array elements can stay where they are */ 733d3fecca9Ssthen /* see if capacity can be reduced */ 734d3fecca9Ssthen radnode_array_reduce_if_needed(region, n); 735d3fecca9Ssthen } 736d3fecca9Ssthen 737d3fecca9Ssthen /** clean up radnode leaf, where we know it has a parent */ 738d3fecca9Ssthen static void 739d3fecca9Ssthen radnode_cleanup_leaf(struct region* region, struct radnode* n, 740d3fecca9Ssthen struct radnode* par) 741d3fecca9Ssthen { 742d3fecca9Ssthen uint8_t pidx; 743d3fecca9Ssthen /* node was a leaf */ 744d3fecca9Ssthen /* delete leaf node, but store parent+idx */ 745d3fecca9Ssthen pidx = n->pidx; 746d3fecca9Ssthen radnode_delete(region, n); 747d3fecca9Ssthen 748d3fecca9Ssthen /* set parent+idx entry to NULL str and node.*/ 749d3fecca9Ssthen assert(pidx < par->len); 750d3fecca9Ssthen region_recycle(region, par->array[pidx].str, par->array[pidx].len); 751d3fecca9Ssthen par->array[pidx].str = NULL; 752d3fecca9Ssthen par->array[pidx].len = 0; 753d3fecca9Ssthen par->array[pidx].node = NULL; 754d3fecca9Ssthen 755d3fecca9Ssthen /* see if par offset or len must be adjusted */ 756d3fecca9Ssthen if(par->len == 1) { 757d3fecca9Ssthen /* removed final element from array */ 758d3fecca9Ssthen radnode_array_clean_all(region, par); 759d3fecca9Ssthen } else if(pidx == 0) { 760d3fecca9Ssthen /* removed first element from array */ 761d3fecca9Ssthen radnode_array_clean_front(region, par); 762d3fecca9Ssthen } else if(pidx == par->len-1) { 763d3fecca9Ssthen /* removed last element from array */ 764d3fecca9Ssthen radnode_array_clean_end(region, par); 765d3fecca9Ssthen } 766d3fecca9Ssthen } 767d3fecca9Ssthen 768d3fecca9Ssthen /** 769d3fecca9Ssthen * Cleanup a radix node that was made smaller, see if it can 770d3fecca9Ssthen * be merged with others. 771d3fecca9Ssthen * @param rt: tree to remove root if needed. 772d3fecca9Ssthen * @param n: node to cleanup 773d3fecca9Ssthen * @return false on alloc failure. 774d3fecca9Ssthen */ 775d3fecca9Ssthen static int 776d3fecca9Ssthen radnode_cleanup(struct radtree* rt, struct radnode* n) 777d3fecca9Ssthen { 778d3fecca9Ssthen while(n) { 779d3fecca9Ssthen if(n->elem) { 780d3fecca9Ssthen /* cannot delete node with a data element */ 781d3fecca9Ssthen return 1; 782d3fecca9Ssthen } else if(n->len == 1 && n->parent) { 783d3fecca9Ssthen return radnode_cleanup_onechild(rt->region, n, n->parent); 784d3fecca9Ssthen } else if(n->len == 0) { 785d3fecca9Ssthen struct radnode* par = n->parent; 786d3fecca9Ssthen if(!par) { 787d3fecca9Ssthen /* root deleted */ 788d3fecca9Ssthen radnode_delete(rt->region, n); 789d3fecca9Ssthen rt->root = NULL; 790d3fecca9Ssthen return 1; 791d3fecca9Ssthen } 792d3fecca9Ssthen /* remove and delete the leaf node */ 793d3fecca9Ssthen radnode_cleanup_leaf(rt->region, n, par); 794d3fecca9Ssthen /* see if parent can now be cleaned up */ 795d3fecca9Ssthen n = par; 796d3fecca9Ssthen } else { 797d3fecca9Ssthen /* node cannot be cleaned up */ 798d3fecca9Ssthen return 1; 799d3fecca9Ssthen } 800d3fecca9Ssthen } 801d3fecca9Ssthen /* ENOTREACH */ 802d3fecca9Ssthen return 1; 803d3fecca9Ssthen } 804d3fecca9Ssthen 805d3fecca9Ssthen void radix_delete(struct radtree* rt, struct radnode* n) 806d3fecca9Ssthen { 807d3fecca9Ssthen if(!n) return; 808d3fecca9Ssthen n->elem = NULL; 809d3fecca9Ssthen rt->count --; 810d3fecca9Ssthen if(!radnode_cleanup(rt, n)) { 811d3fecca9Ssthen /* out of memory in cleanup. the elem ptr is NULL, but 812d3fecca9Ssthen * the radix tree could be inefficient. */ 813d3fecca9Ssthen } 814d3fecca9Ssthen } 815d3fecca9Ssthen 816d3fecca9Ssthen struct radnode* radix_search(struct radtree* rt, uint8_t* k, radstrlen_t len) 817d3fecca9Ssthen { 818d3fecca9Ssthen struct radnode* n = rt->root; 819d3fecca9Ssthen radstrlen_t pos = 0; 820d3fecca9Ssthen uint8_t byte; 821d3fecca9Ssthen while(n) { 822d3fecca9Ssthen if(pos == len) 823d3fecca9Ssthen return n->elem?n:NULL; 824d3fecca9Ssthen byte = k[pos]; 825d3fecca9Ssthen if(byte < n->offset) 826d3fecca9Ssthen return NULL; 827d3fecca9Ssthen byte -= n->offset; 828d3fecca9Ssthen if(byte >= n->len) 829d3fecca9Ssthen return NULL; 830d3fecca9Ssthen pos++; 831d3fecca9Ssthen if(n->array[byte].len != 0) { 832d3fecca9Ssthen /* must match additional string */ 833d3fecca9Ssthen if(pos+n->array[byte].len > len) 834d3fecca9Ssthen return NULL; /* no match */ 835d3fecca9Ssthen if(memcmp(&k[pos], n->array[byte].str, 836d3fecca9Ssthen n->array[byte].len) != 0) 837d3fecca9Ssthen return NULL; /* no match */ 838d3fecca9Ssthen pos += n->array[byte].len; 839d3fecca9Ssthen } 840d3fecca9Ssthen n = n->array[byte].node; 841d3fecca9Ssthen } 842d3fecca9Ssthen return NULL; 843d3fecca9Ssthen } 844d3fecca9Ssthen 845d3fecca9Ssthen /** return self or a previous element */ 846d3fecca9Ssthen static int ret_self_or_prev(struct radnode* n, struct radnode** result) 847d3fecca9Ssthen { 848d3fecca9Ssthen if(n->elem) 849d3fecca9Ssthen *result = n; 850d3fecca9Ssthen else *result = radix_prev(n); 851d3fecca9Ssthen return 0; 852d3fecca9Ssthen } 853d3fecca9Ssthen 854d3fecca9Ssthen int radix_find_less_equal(struct radtree* rt, uint8_t* k, radstrlen_t len, 855d3fecca9Ssthen struct radnode** result) 856d3fecca9Ssthen { 857d3fecca9Ssthen struct radnode* n = rt->root; 858d3fecca9Ssthen radstrlen_t pos = 0; 859d3fecca9Ssthen uint8_t byte; 860d3fecca9Ssthen int r; 861d3fecca9Ssthen if(!n) { 862d3fecca9Ssthen /* empty tree */ 863d3fecca9Ssthen *result = NULL; 864d3fecca9Ssthen return 0; 865d3fecca9Ssthen } 866d3fecca9Ssthen while(pos < len) { 867d3fecca9Ssthen byte = k[pos]; 868d3fecca9Ssthen if(byte < n->offset) { 869d3fecca9Ssthen /* so the previous is the element itself */ 870d3fecca9Ssthen /* or something before this element */ 871d3fecca9Ssthen return ret_self_or_prev(n, result); 872d3fecca9Ssthen } 873d3fecca9Ssthen byte -= n->offset; 874d3fecca9Ssthen if(byte >= n->len) { 875d3fecca9Ssthen /* so, the previous is the last of array, or itself */ 876d3fecca9Ssthen /* or something before this element */ 877d3fecca9Ssthen if((*result=radnode_last_in_subtree_incl_self(n))==0) 878d3fecca9Ssthen *result = radix_prev(n); 879d3fecca9Ssthen return 0; 880d3fecca9Ssthen } 881d3fecca9Ssthen pos++; 882d3fecca9Ssthen if(!n->array[byte].node) { 883d3fecca9Ssthen /* no match */ 884d3fecca9Ssthen /* Find an entry in arrays from byte-1 to 0 */ 885d3fecca9Ssthen *result = radnode_find_prev_from_idx(n, byte); 886d3fecca9Ssthen if(*result) 887d3fecca9Ssthen return 0; 888d3fecca9Ssthen /* this entry or something before it */ 889d3fecca9Ssthen return ret_self_or_prev(n, result); 890d3fecca9Ssthen } 891d3fecca9Ssthen if(n->array[byte].len != 0) { 892d3fecca9Ssthen /* must match additional string */ 893d3fecca9Ssthen if(pos+n->array[byte].len > len) { 894d3fecca9Ssthen /* the additional string is longer than key*/ 895d3fecca9Ssthen if( (memcmp(&k[pos], n->array[byte].str, 896d3fecca9Ssthen len-pos)) <= 0) { 897d3fecca9Ssthen /* and the key is before this node */ 898d3fecca9Ssthen *result = radix_prev(n->array[byte].node); 899d3fecca9Ssthen } else { 900d3fecca9Ssthen /* the key is after the additional 901d3fecca9Ssthen * string, thus everything in that 902d3fecca9Ssthen * subtree is smaller. */ 903d3fecca9Ssthen *result=radnode_last_in_subtree_incl_self(n->array[byte].node); 904d3fecca9Ssthen /* if somehow that is NULL, 905d3fecca9Ssthen * then we have an inefficient tree: 906d3fecca9Ssthen * byte+1 is larger than us, so find 907d3fecca9Ssthen * something in byte-1 and before */ 908d3fecca9Ssthen if(!*result) 909d3fecca9Ssthen *result = radix_prev(n->array[byte].node); 910d3fecca9Ssthen } 911d3fecca9Ssthen return 0; /* no match */ 912d3fecca9Ssthen } 913d3fecca9Ssthen if( (r=memcmp(&k[pos], n->array[byte].str, 914d3fecca9Ssthen n->array[byte].len)) < 0) { 915d3fecca9Ssthen *result = radix_prev(n->array[byte].node); 916d3fecca9Ssthen return 0; /* no match */ 917d3fecca9Ssthen } else if(r > 0) { 918d3fecca9Ssthen /* the key is larger than the additional 919d3fecca9Ssthen * string, thus everything in that subtree 920d3fecca9Ssthen * is smaller */ 921d3fecca9Ssthen *result=radnode_last_in_subtree_incl_self(n->array[byte].node); 922d3fecca9Ssthen /* if we have an inefficient tree */ 923d3fecca9Ssthen if(!*result) *result = radix_prev(n->array[byte].node); 924d3fecca9Ssthen return 0; /* no match */ 925d3fecca9Ssthen } 926d3fecca9Ssthen pos += n->array[byte].len; 927d3fecca9Ssthen } 928d3fecca9Ssthen n = n->array[byte].node; 929d3fecca9Ssthen } 930d3fecca9Ssthen if(n->elem) { 931d3fecca9Ssthen /* exact match */ 932d3fecca9Ssthen *result = n; 933d3fecca9Ssthen return 1; 934d3fecca9Ssthen } 935d3fecca9Ssthen /* there is a node which is an exact match, but it has no element */ 936d3fecca9Ssthen *result = radix_prev(n); 937d3fecca9Ssthen return 0; 938d3fecca9Ssthen } 939d3fecca9Ssthen 940d3fecca9Ssthen 941d3fecca9Ssthen struct radnode* radix_first(struct radtree* rt) 942d3fecca9Ssthen { 943d3fecca9Ssthen struct radnode* n; 944d3fecca9Ssthen if(!rt || !rt->root) return NULL; 945d3fecca9Ssthen n = rt->root; 946d3fecca9Ssthen if(n->elem) return n; 947d3fecca9Ssthen return radix_next(n); 948d3fecca9Ssthen } 949d3fecca9Ssthen 950d3fecca9Ssthen struct radnode* radix_last(struct radtree* rt) 951d3fecca9Ssthen { 952d3fecca9Ssthen if(!rt || !rt->root) return NULL; 953d3fecca9Ssthen return radnode_last_in_subtree_incl_self(rt->root); 954d3fecca9Ssthen } 955d3fecca9Ssthen 956d3fecca9Ssthen struct radnode* radix_next(struct radnode* n) 957d3fecca9Ssthen { 958c939baa4Ssthen if(!n) return NULL; 959d3fecca9Ssthen if(n->len) { 960d3fecca9Ssthen /* go down */ 961d3fecca9Ssthen struct radnode* s = radnode_first_in_subtree(n); 962d3fecca9Ssthen if(s) return s; 963d3fecca9Ssthen } 964d3fecca9Ssthen /* go up - the parent->elem is not useful, because it is before us */ 965d3fecca9Ssthen while(n->parent) { 966d3fecca9Ssthen unsigned idx = n->pidx; 967d3fecca9Ssthen n = n->parent; 968d3fecca9Ssthen idx++; 969d3fecca9Ssthen for(; idx < n->len; idx++) { 970d3fecca9Ssthen /* go down the next branch */ 971d3fecca9Ssthen if(n->array[idx].node) { 972d3fecca9Ssthen struct radnode* s; 973d3fecca9Ssthen /* node itself */ 974d3fecca9Ssthen if(n->array[idx].node->elem) 975d3fecca9Ssthen return n->array[idx].node; 976d3fecca9Ssthen /* or subtree */ 977d3fecca9Ssthen s = radnode_first_in_subtree( 978d3fecca9Ssthen n->array[idx].node); 979d3fecca9Ssthen if(s) return s; 980d3fecca9Ssthen } 981d3fecca9Ssthen } 982d3fecca9Ssthen } 983d3fecca9Ssthen return NULL; 984d3fecca9Ssthen } 985d3fecca9Ssthen 986d3fecca9Ssthen struct radnode* radix_prev(struct radnode* n) 987d3fecca9Ssthen { 988c939baa4Ssthen if(!n) return NULL; 989d3fecca9Ssthen /* must go up, since all array nodes are after this node */ 990d3fecca9Ssthen while(n->parent) { 991d3fecca9Ssthen uint8_t idx = n->pidx; 992d3fecca9Ssthen struct radnode* s; 993d3fecca9Ssthen n = n->parent; 994d3fecca9Ssthen assert(n->len > 0); /* since we are a child */ 995d3fecca9Ssthen /* see if there are elements in previous branches there */ 996d3fecca9Ssthen s = radnode_find_prev_from_idx(n, idx); 997d3fecca9Ssthen if(s) return s; 998d3fecca9Ssthen /* the current node is before the array */ 999d3fecca9Ssthen if(n->elem) 1000d3fecca9Ssthen return n; 1001d3fecca9Ssthen } 1002d3fecca9Ssthen return NULL; 1003d3fecca9Ssthen } 1004d3fecca9Ssthen 1005d3fecca9Ssthen /** convert one character from domain-name to radname */ 1006d3fecca9Ssthen static uint8_t char_d2r(uint8_t c) 1007d3fecca9Ssthen { 1008d3fecca9Ssthen if(c < 'A') return c+1; /* make space for 00 */ 1009d3fecca9Ssthen else if(c <= 'Z') return c-'A'+'a'; /* lowercase */ 1010d3fecca9Ssthen else return c; 1011d3fecca9Ssthen } 1012d3fecca9Ssthen 1013d3fecca9Ssthen /** convert one character from radname to domain-name (still lowercased) */ 1014d3fecca9Ssthen static uint8_t char_r2d(uint8_t c) 1015d3fecca9Ssthen { 1016d3fecca9Ssthen assert(c != 0); /* end of label */ 1017d3fecca9Ssthen if(c <= 'A') return c-1; 1018d3fecca9Ssthen else return c; 1019d3fecca9Ssthen } 1020d3fecca9Ssthen 1021d3fecca9Ssthen /** copy and convert a range of characters */ 1022d3fecca9Ssthen static void cpy_d2r(uint8_t* to, const uint8_t* from, int len) 1023d3fecca9Ssthen { 1024d3fecca9Ssthen int i; 1025d3fecca9Ssthen for(i=0; i<len; i++) 1026d3fecca9Ssthen to[i] = char_d2r(from[i]); 1027d3fecca9Ssthen } 1028d3fecca9Ssthen 1029d3fecca9Ssthen /** copy and convert a range of characters */ 1030d3fecca9Ssthen static void cpy_r2d(uint8_t* to, uint8_t* from, uint8_t len) 1031d3fecca9Ssthen { 1032d3fecca9Ssthen uint8_t i; 1033d3fecca9Ssthen for(i=0; i<len; i++) 1034d3fecca9Ssthen to[i] = char_r2d(from[i]); 1035d3fecca9Ssthen } 1036d3fecca9Ssthen 1037d3fecca9Ssthen /* radname code: domain to radix-bstring */ 1038d3fecca9Ssthen void radname_d2r(uint8_t* k, radstrlen_t* len, const uint8_t* dname, 1039d3fecca9Ssthen size_t dlen) 1040d3fecca9Ssthen { 1041d3fecca9Ssthen /* the domain name is converted as follows, 1042d3fecca9Ssthen * to preserve the normal (NSEC) ordering of domain names. 1043d3fecca9Ssthen * lowercased, and 'end-of-label' is a '00' byte, 1044d3fecca9Ssthen * bytes 00-'A' are +1 moved to make space for 00 byte. 1045d3fecca9Ssthen * final root label is not appended (string ends). 1046d3fecca9Ssthen * because the only allowed empty label is the final root label, 1047d3fecca9Ssthen * we can also remove the last 00 label-end. 1048d3fecca9Ssthen * The total result length is one-or-two less than the dname. 1049d3fecca9Ssthen * 1050d3fecca9Ssthen * examples (numbers are bytes, letters are ascii): 1051d3fecca9Ssthen * - root: dname: 0, radname: '' 1052d3fecca9Ssthen * - nl.: dname: 3nl0, radname: 'nl' 1053d3fecca9Ssthen * - labs.nl: dname 4labs3nl0, radname: 'nl0labs' 1054d3fecca9Ssthen * - x.labs.nl: dname 1x4labs3nl0, radname: 'nl0labs0x' 1055d3fecca9Ssthen */ 1056d3fecca9Ssthen 1057d3fecca9Ssthen /* conversion by putting the label starts on a stack */ 1058d3fecca9Ssthen const uint8_t* labstart[130]; 1059d3fecca9Ssthen unsigned int lab = 0, kpos, dpos = 0; 1060d3fecca9Ssthen /* sufficient space */ 1061d3fecca9Ssthen assert(k && dname); 1062d3fecca9Ssthen assert(dlen <= 256); /* and therefore not more than 128 labels */ 1063d3fecca9Ssthen assert(*len >= dlen); 1064d3fecca9Ssthen assert(dlen > 0); /* even root label has dlen=1 */ 1065d3fecca9Ssthen 1066d3fecca9Ssthen /* root */ 1067d3fecca9Ssthen if(dlen == 1) { 1068d3fecca9Ssthen assert(dname[0] == 0); 1069d3fecca9Ssthen *len = 0; 1070d3fecca9Ssthen return; 1071d3fecca9Ssthen } 1072d3fecca9Ssthen 1073d3fecca9Ssthen /* walk through domain name and remember label positions */ 1074d3fecca9Ssthen do { 1075d3fecca9Ssthen /* compression pointers not allowed */ 1076d3fecca9Ssthen if((dname[dpos] & 0xc0)) { 1077d3fecca9Ssthen *len = 0; 1078d3fecca9Ssthen return; /* format error */ 1079d3fecca9Ssthen } 1080d3fecca9Ssthen labstart[lab++] = &dname[dpos]; 1081d3fecca9Ssthen if(dpos + dname[dpos] + 1 >= dlen) { 1082d3fecca9Ssthen *len = 0; 1083d3fecca9Ssthen return; /* format error */ 1084d3fecca9Ssthen } 1085d3fecca9Ssthen /* skip the label contents */ 1086d3fecca9Ssthen dpos += dname[dpos]; 1087d3fecca9Ssthen dpos ++; 1088d3fecca9Ssthen } while(dname[dpos] != 0); 1089d3fecca9Ssthen /* exit condition makes root label not in labelstart stack */ 1090d3fecca9Ssthen /* because the root was handled before, we know there is some text */ 1091d3fecca9Ssthen assert(lab > 0); 1092d3fecca9Ssthen lab-=1; 1093d3fecca9Ssthen kpos = *labstart[lab]; 1094d3fecca9Ssthen cpy_d2r(k, labstart[lab]+1, kpos); 1095d3fecca9Ssthen /* if there are more labels, copy them over */ 1096d3fecca9Ssthen while(lab) { 1097d3fecca9Ssthen /* put 'end-of-label' 00 to end previous label */ 1098d3fecca9Ssthen k[kpos++]=0; 1099d3fecca9Ssthen /* append the label */ 1100d3fecca9Ssthen lab--; 1101d3fecca9Ssthen cpy_d2r(k+kpos, labstart[lab]+1, *labstart[lab]); 1102d3fecca9Ssthen kpos += *labstart[lab]; 1103d3fecca9Ssthen } 1104d3fecca9Ssthen /* done */ 1105d3fecca9Ssthen assert(kpos == dlen-2); /* no rootlabel, one less label-marker */ 1106d3fecca9Ssthen *len = kpos; 1107d3fecca9Ssthen } 1108d3fecca9Ssthen 1109d3fecca9Ssthen /* radname code: radix-bstring to domain */ 1110d3fecca9Ssthen void radname_r2d(uint8_t* k, radstrlen_t len, uint8_t* dname, size_t* dlen) 1111d3fecca9Ssthen { 1112d3fecca9Ssthen /* find labels and push on stack */ 1113d3fecca9Ssthen uint8_t* labstart[130]; 1114d3fecca9Ssthen uint8_t lablen[130]; 1115d3fecca9Ssthen unsigned int lab = 0, dpos, kpos = 0; 1116d3fecca9Ssthen /* sufficient space */ 1117d3fecca9Ssthen assert(k && dname); 1118d3fecca9Ssthen assert((size_t)*dlen >= (size_t)len+2); 1119d3fecca9Ssthen assert(len <= 256); 1120d3fecca9Ssthen /* root label */ 1121d3fecca9Ssthen if(len == 0) { 1122d3fecca9Ssthen assert(*dlen > 0); 1123d3fecca9Ssthen dname[0]=0; 1124d3fecca9Ssthen *dlen=1; 1125d3fecca9Ssthen return; 1126d3fecca9Ssthen } 1127d3fecca9Ssthen /* find labels */ 1128d3fecca9Ssthen while(kpos < len) { 1129d3fecca9Ssthen lablen[lab]=0; 1130d3fecca9Ssthen labstart[lab]=&k[kpos]; 1131d3fecca9Ssthen /* skip to next label */ 1132d3fecca9Ssthen while(kpos < len && k[kpos] != 0) { 1133d3fecca9Ssthen lablen[lab]++; 1134d3fecca9Ssthen kpos++; 1135d3fecca9Ssthen } 1136d3fecca9Ssthen lab++; 1137d3fecca9Ssthen /* skip 00 byte for label-end */ 1138d3fecca9Ssthen if(kpos < len) { 1139d3fecca9Ssthen assert(k[kpos] == 0); 1140d3fecca9Ssthen kpos++; 1141d3fecca9Ssthen } 1142d3fecca9Ssthen } 1143d3fecca9Ssthen /* copy the labels over to the domain name */ 1144d3fecca9Ssthen dpos = 0; 1145d3fecca9Ssthen while(lab) { 1146d3fecca9Ssthen lab--; 1147d3fecca9Ssthen /* label length */ 1148d3fecca9Ssthen dname[dpos++] = lablen[lab]; 1149d3fecca9Ssthen /* label content */ 1150d3fecca9Ssthen cpy_r2d(dname+dpos, labstart[lab], lablen[lab]); 1151d3fecca9Ssthen dpos += lablen[lab]; 1152d3fecca9Ssthen } 1153d3fecca9Ssthen /* append root label */ 1154d3fecca9Ssthen dname[dpos++] = 0; 1155d3fecca9Ssthen /* assert the domain name is wellformed */ 1156d3fecca9Ssthen assert((int)dpos == (int)len+2); 1157d3fecca9Ssthen assert(dname[dpos-1] == 0); /* ends with root label */ 1158d3fecca9Ssthen *dlen = dpos; 1159d3fecca9Ssthen } 1160d3fecca9Ssthen 1161d3fecca9Ssthen /** insert by domain name */ 1162d3fecca9Ssthen struct radnode* 1163d3fecca9Ssthen radname_insert(struct radtree* rt, const uint8_t* d, size_t max, void* elem) 1164d3fecca9Ssthen { 1165d3fecca9Ssthen /* convert and insert */ 1166d3fecca9Ssthen uint8_t radname[300]; 1167d3fecca9Ssthen radstrlen_t len = (radstrlen_t)sizeof(radname); 1168d3fecca9Ssthen if(max > sizeof(radname)) 1169d3fecca9Ssthen return NULL; /* too long */ 1170d3fecca9Ssthen radname_d2r(radname, &len, d, max); 1171d3fecca9Ssthen return radix_insert(rt, radname, len, elem); 1172d3fecca9Ssthen } 1173d3fecca9Ssthen 1174d3fecca9Ssthen /** delete by domain name */ 1175d3fecca9Ssthen void 1176d3fecca9Ssthen radname_delete(struct radtree* rt, const uint8_t* d, size_t max) 1177d3fecca9Ssthen { 1178d3fecca9Ssthen /* search and remove */ 1179d3fecca9Ssthen struct radnode* n = radname_search(rt, d, max); 1180d3fecca9Ssthen if(n) radix_delete(rt, n); 1181d3fecca9Ssthen } 1182d3fecca9Ssthen 1183d3fecca9Ssthen /* search for exact match of domain name, converted to radname in tree */ 1184d3fecca9Ssthen struct radnode* radname_search(struct radtree* rt, const uint8_t* d, 1185d3fecca9Ssthen size_t max) 1186d3fecca9Ssthen { 1187d3fecca9Ssthen /* stack of labels in the domain name */ 1188d3fecca9Ssthen const uint8_t* labstart[130]; 1189d3fecca9Ssthen unsigned int lab, dpos, lpos; 1190d3fecca9Ssthen struct radnode* n = rt->root; 1191d3fecca9Ssthen uint8_t byte; 1192d3fecca9Ssthen radstrlen_t i; 1193d3fecca9Ssthen uint8_t b; 1194d3fecca9Ssthen 1195d3fecca9Ssthen /* search for root? it is '' */ 1196d3fecca9Ssthen if(max < 1) 1197d3fecca9Ssthen return NULL; 1198d3fecca9Ssthen if(d[0] == 0) { 1199d3fecca9Ssthen if(!n) return NULL; 1200d3fecca9Ssthen return n->elem?n:NULL; 1201d3fecca9Ssthen } 1202d3fecca9Ssthen 1203d3fecca9Ssthen /* find labels stack in domain name */ 1204d3fecca9Ssthen lab = 0; 1205d3fecca9Ssthen dpos = 0; 1206d3fecca9Ssthen /* must have one label, since root is specialcased */ 1207d3fecca9Ssthen do { 1208d3fecca9Ssthen if((d[dpos] & 0xc0)) 1209d3fecca9Ssthen return NULL; /* compression ptrs not allowed error */ 1210d3fecca9Ssthen labstart[lab++] = &d[dpos]; 1211d3fecca9Ssthen if(dpos + d[dpos] + 1 >= max) 1212d3fecca9Ssthen return NULL; /* format error: outside of bounds */ 1213d3fecca9Ssthen /* skip the label contents */ 1214d3fecca9Ssthen dpos += d[dpos]; 1215d3fecca9Ssthen dpos ++; 1216d3fecca9Ssthen } while(d[dpos] != 0); 1217d3fecca9Ssthen /* exit condition makes that root label is not in the labstarts */ 1218d3fecca9Ssthen /* now: dpos+1 is length of domain name. lab is number of labels-1 */ 1219d3fecca9Ssthen 1220d3fecca9Ssthen /* start processing at the last label */ 1221d3fecca9Ssthen lab-=1; 1222d3fecca9Ssthen lpos = 0; 1223d3fecca9Ssthen while(n) { 1224d3fecca9Ssthen /* fetch next byte this label */ 1225d3fecca9Ssthen if(lpos < *labstart[lab]) 1226d3fecca9Ssthen /* lpos+1 to skip labelstart, lpos++ to move forward */ 1227d3fecca9Ssthen byte = char_d2r(labstart[lab][++lpos]); 1228d3fecca9Ssthen else { 1229d3fecca9Ssthen if(lab == 0) /* last label - we're done */ 1230d3fecca9Ssthen return n->elem?n:NULL; 1231d3fecca9Ssthen /* next label, search for byte 00 */ 1232d3fecca9Ssthen lpos = 0; 1233d3fecca9Ssthen lab--; 1234d3fecca9Ssthen byte = 0; 1235d3fecca9Ssthen } 1236d3fecca9Ssthen /* find that byte in the array */ 1237d3fecca9Ssthen if(byte < n->offset) 1238d3fecca9Ssthen return NULL; 1239d3fecca9Ssthen byte -= n->offset; 1240d3fecca9Ssthen if(byte >= n->len) 1241d3fecca9Ssthen return NULL; 1242d3fecca9Ssthen if(n->array[byte].len != 0) { 1243d3fecca9Ssthen /* must match additional string */ 1244d3fecca9Ssthen /* see how many bytes we need and start matching them*/ 1245d3fecca9Ssthen for(i=0; i<n->array[byte].len; i++) { 1246d3fecca9Ssthen /* next byte to match */ 1247d3fecca9Ssthen if(lpos < *labstart[lab]) 1248d3fecca9Ssthen b = char_d2r(labstart[lab][++lpos]); 1249d3fecca9Ssthen else { 1250d3fecca9Ssthen /* if last label, no match since 1251d3fecca9Ssthen * we are in the additional string */ 1252d3fecca9Ssthen if(lab == 0) 1253d3fecca9Ssthen return NULL; 1254d3fecca9Ssthen /* next label, search for byte 00 */ 1255d3fecca9Ssthen lpos = 0; 1256d3fecca9Ssthen lab--; 1257d3fecca9Ssthen b = 0; 1258d3fecca9Ssthen } 1259d3fecca9Ssthen if(n->array[byte].str[i] != b) 1260d3fecca9Ssthen return NULL; /* not matched */ 1261d3fecca9Ssthen } 1262d3fecca9Ssthen } 1263d3fecca9Ssthen n = n->array[byte].node; 1264d3fecca9Ssthen } 1265d3fecca9Ssthen return NULL; 1266d3fecca9Ssthen } 1267d3fecca9Ssthen 1268d3fecca9Ssthen /* find domain name or smaller or equal domain name in radix tree */ 1269d3fecca9Ssthen int radname_find_less_equal(struct radtree* rt, const uint8_t* d, size_t max, 1270d3fecca9Ssthen struct radnode** result) 1271d3fecca9Ssthen { 1272d3fecca9Ssthen /* stack of labels in the domain name */ 1273d3fecca9Ssthen const uint8_t* labstart[130]; 1274d3fecca9Ssthen unsigned int lab, dpos, lpos; 1275d3fecca9Ssthen struct radnode* n = rt->root; 1276d3fecca9Ssthen uint8_t byte; 1277d3fecca9Ssthen radstrlen_t i; 1278d3fecca9Ssthen uint8_t b; 1279d3fecca9Ssthen 1280d3fecca9Ssthen /* empty tree */ 1281d3fecca9Ssthen if(!n) { 1282d3fecca9Ssthen *result = NULL; 1283d3fecca9Ssthen return 0; 1284d3fecca9Ssthen } 1285d3fecca9Ssthen 1286d3fecca9Ssthen /* search for root? it is '' */ 1287d3fecca9Ssthen if(max < 1) { 1288d3fecca9Ssthen *result = NULL; 1289d3fecca9Ssthen return 0; /* parse error, out of bounds */ 1290d3fecca9Ssthen } 1291d3fecca9Ssthen if(d[0] == 0) { 1292d3fecca9Ssthen if(n->elem) { 1293d3fecca9Ssthen *result = n; 1294d3fecca9Ssthen return 1; 1295d3fecca9Ssthen } 1296d3fecca9Ssthen /* no smaller element than the root */ 1297d3fecca9Ssthen *result = NULL; 1298d3fecca9Ssthen return 0; 1299d3fecca9Ssthen } 1300d3fecca9Ssthen 1301d3fecca9Ssthen /* find labels stack in domain name */ 1302d3fecca9Ssthen lab = 0; 1303d3fecca9Ssthen dpos = 0; 1304d3fecca9Ssthen /* must have one label, since root is specialcased */ 1305d3fecca9Ssthen do { 1306d3fecca9Ssthen if((d[dpos] & 0xc0)) { 1307d3fecca9Ssthen *result = NULL; 1308d3fecca9Ssthen return 0; /* compression ptrs not allowed error */ 1309d3fecca9Ssthen } 1310d3fecca9Ssthen labstart[lab++] = &d[dpos]; 1311d3fecca9Ssthen if(dpos + d[dpos] + 1 >= max) { 1312d3fecca9Ssthen *result = NULL; /* format error: outside of bounds */ 1313d3fecca9Ssthen return 0; 1314d3fecca9Ssthen } 1315d3fecca9Ssthen /* skip the label contents */ 1316d3fecca9Ssthen dpos += d[dpos]; 1317d3fecca9Ssthen dpos ++; 1318d3fecca9Ssthen } while(d[dpos] != 0); 1319d3fecca9Ssthen /* exit condition makes that root label is not in the labstarts */ 1320d3fecca9Ssthen /* now: dpos+1 is length of domain name. lab is number of labels-1 */ 1321d3fecca9Ssthen 1322d3fecca9Ssthen /* start processing at the last label */ 1323d3fecca9Ssthen lab-=1; 1324d3fecca9Ssthen lpos = 0; 1325d3fecca9Ssthen while(1) { 1326d3fecca9Ssthen /* fetch next byte this label */ 1327d3fecca9Ssthen if(lpos < *labstart[lab]) 1328d3fecca9Ssthen /* lpos+1 to skip labelstart, lpos++ to move forward */ 1329d3fecca9Ssthen byte = char_d2r(labstart[lab][++lpos]); 1330d3fecca9Ssthen else { 1331d3fecca9Ssthen if(lab == 0) { 1332d3fecca9Ssthen /* last label - we're done */ 1333d3fecca9Ssthen /* exact match */ 1334d3fecca9Ssthen if(n->elem) { 1335d3fecca9Ssthen *result = n; 1336d3fecca9Ssthen return 1; 1337d3fecca9Ssthen } 1338d3fecca9Ssthen /* there is a node which is an exact match, 1339d3fecca9Ssthen * but there no element in it */ 1340d3fecca9Ssthen *result = radix_prev(n); 1341d3fecca9Ssthen return 0; 1342d3fecca9Ssthen } 1343d3fecca9Ssthen /* next label, search for byte 0 the label separator */ 1344d3fecca9Ssthen lpos = 0; 1345d3fecca9Ssthen lab--; 1346d3fecca9Ssthen byte = 0; 1347d3fecca9Ssthen } 1348d3fecca9Ssthen /* find that byte in the array */ 1349d3fecca9Ssthen if(byte < n->offset) 1350d3fecca9Ssthen /* so the previous is the element itself */ 1351d3fecca9Ssthen /* or something before this element */ 1352d3fecca9Ssthen return ret_self_or_prev(n, result); 1353d3fecca9Ssthen byte -= n->offset; 1354d3fecca9Ssthen if(byte >= n->len) { 1355d3fecca9Ssthen /* so, the previous is the last of array, or itself */ 1356d3fecca9Ssthen /* or something before this element */ 1357d3fecca9Ssthen *result = radnode_last_in_subtree_incl_self(n); 1358d3fecca9Ssthen if(!*result) 1359d3fecca9Ssthen *result = radix_prev(n); 1360d3fecca9Ssthen return 0; 1361d3fecca9Ssthen } 1362d3fecca9Ssthen if(!n->array[byte].node) { 1363d3fecca9Ssthen /* no match */ 1364d3fecca9Ssthen /* Find an entry in arrays from byte-1 to 0 */ 1365d3fecca9Ssthen *result = radnode_find_prev_from_idx(n, byte); 1366d3fecca9Ssthen if(*result) 1367d3fecca9Ssthen return 0; 1368d3fecca9Ssthen /* this entry or something before it */ 1369d3fecca9Ssthen return ret_self_or_prev(n, result); 1370d3fecca9Ssthen } 1371d3fecca9Ssthen if(n->array[byte].len != 0) { 1372d3fecca9Ssthen /* must match additional string */ 1373d3fecca9Ssthen /* see how many bytes we need and start matching them*/ 1374d3fecca9Ssthen for(i=0; i<n->array[byte].len; i++) { 1375d3fecca9Ssthen /* next byte to match */ 1376d3fecca9Ssthen if(lpos < *labstart[lab]) 1377d3fecca9Ssthen b = char_d2r(labstart[lab][++lpos]); 1378d3fecca9Ssthen else { 1379d3fecca9Ssthen /* if last label, no match since 1380d3fecca9Ssthen * we are in the additional string */ 1381d3fecca9Ssthen if(lab == 0) { 1382d3fecca9Ssthen /* dname ended, thus before 1383d3fecca9Ssthen * this array element */ 1384d3fecca9Ssthen *result =radix_prev( 1385d3fecca9Ssthen n->array[byte].node); 1386d3fecca9Ssthen return 0; 1387d3fecca9Ssthen } 1388d3fecca9Ssthen /* next label, search for byte 00 */ 1389d3fecca9Ssthen lpos = 0; 1390d3fecca9Ssthen lab--; 1391d3fecca9Ssthen b = 0; 1392d3fecca9Ssthen } 1393d3fecca9Ssthen if(b < n->array[byte].str[i]) { 1394d3fecca9Ssthen *result =radix_prev( 1395d3fecca9Ssthen n->array[byte].node); 1396d3fecca9Ssthen return 0; 1397d3fecca9Ssthen } else if(b > n->array[byte].str[i]) { 1398d3fecca9Ssthen /* the key is after the additional, 1399d3fecca9Ssthen * so everything in its subtree is 1400d3fecca9Ssthen * smaller */ 1401d3fecca9Ssthen *result = radnode_last_in_subtree_incl_self(n->array[byte].node); 1402d3fecca9Ssthen /* if that is NULL, we have an 1403d3fecca9Ssthen * inefficient tree, find in byte-1*/ 1404d3fecca9Ssthen if(!*result) 1405d3fecca9Ssthen *result = radix_prev(n->array[byte].node); 1406d3fecca9Ssthen return 0; 1407d3fecca9Ssthen } 1408d3fecca9Ssthen } 1409d3fecca9Ssthen } 1410d3fecca9Ssthen n = n->array[byte].node; 1411d3fecca9Ssthen } 1412d3fecca9Ssthen /* ENOTREACH */ 1413d3fecca9Ssthen return 0; 1414d3fecca9Ssthen } 1415d3fecca9Ssthen 1416