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