1 /* 2 * radix.c -- generic radix tree 3 * 4 * Taken from NSD4, modified for ldns 5 * 6 * Copyright (c) 2012, NLnet Labs. All rights reserved. 7 * 8 * This software is open source. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * Redistributions of source code must retain the above copyright notice, 15 * this list of conditions and the following disclaimer. 16 * 17 * Redistributions in binary form must reproduce the above copyright notice, 18 * this list of conditions and the following disclaimer in the documentation 19 * and/or other materials provided with the distribution. 20 * 21 * Neither the name of the NLNET LABS nor the names of its contributors may 22 * be used to endorse or promote products derived from this software without 23 * specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 32 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 33 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 34 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 35 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 */ 38 39 /** 40 * \file 41 * Implementation of a radix tree. 42 */ 43 44 #include <ldns/config.h> 45 #include <ldns/radix.h> 46 #include <ldns/util.h> 47 #include <stdlib.h> 48 49 /** Helper functions */ 50 static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key, 51 radix_strlen_t len); 52 static int ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key, 53 radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos); 54 static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte); 55 static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need); 56 static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key, 57 radix_strlen_t pos, radix_strlen_t len); 58 static int ldns_radix_prefix_remainder(radix_strlen_t prefix_len, 59 uint8_t* longer_str, radix_strlen_t longer_len, uint8_t** split_str, 60 radix_strlen_t* split_len); 61 static int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key, 62 radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add); 63 static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1, 64 uint8_t* str2, radix_strlen_t len2); 65 static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1, 66 uint8_t* str2, radix_strlen_t len2); 67 static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node); 68 static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node, 69 uint8_t index); 70 static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self( 71 ldns_radix_node_t* node); 72 static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node); 73 static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node); 74 static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node); 75 static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node); 76 static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg); 77 static void ldns_radix_node_array_free(ldns_radix_node_t* node); 78 static void ldns_radix_node_array_free_front(ldns_radix_node_t* node); 79 static void ldns_radix_node_array_free_end(ldns_radix_node_t* node); 80 static void ldns_radix_array_reduce(ldns_radix_node_t* node); 81 static void ldns_radix_self_or_prev(ldns_radix_node_t* node, 82 ldns_radix_node_t** result); 83 84 85 /** 86 * Create a new radix node. 87 * 88 */ 89 static ldns_radix_node_t* 90 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len) 91 { 92 ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t); 93 if (!node) { 94 return NULL; 95 } 96 node->data = data; 97 node->key = key; 98 node->klen = len; 99 node->parent = NULL; 100 node->parent_index = 0; 101 node->len = 0; 102 node->offset = 0; 103 node->capacity = 0; 104 node->array = NULL; 105 return node; 106 } 107 108 109 /** 110 * Create a new radix tree. 111 * 112 */ 113 ldns_radix_t * 114 ldns_radix_create(void) 115 { 116 ldns_radix_t* tree; 117 118 /** Allocate memory for it */ 119 tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t); 120 if (!tree) { 121 return NULL; 122 } 123 /** Initialize it */ 124 ldns_radix_init(tree); 125 return tree; 126 } 127 128 129 /** 130 * Initialize radix tree. 131 * 132 */ 133 void 134 ldns_radix_init(ldns_radix_t* tree) 135 { 136 /** Initialize it */ 137 if (tree) { 138 tree->root = NULL; 139 tree->count = 0; 140 } 141 return; 142 } 143 144 145 /** 146 * Free radix tree. 147 * 148 */ 149 void 150 ldns_radix_free(ldns_radix_t* tree) 151 { 152 if (tree) { 153 if (tree->root) { 154 ldns_radix_traverse_postorder(tree->root, 155 ldns_radix_node_free, NULL); 156 } 157 LDNS_FREE(tree); 158 } 159 return; 160 } 161 162 163 /** 164 * Insert data into the tree. 165 * 166 */ 167 ldns_status 168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len, 169 void* data) 170 { 171 radix_strlen_t pos = 0; 172 ldns_radix_node_t* add = NULL; 173 ldns_radix_node_t* prefix = NULL; 174 175 if (!tree || !key || !data) { 176 return LDNS_STATUS_NULL; 177 } 178 add = ldns_radix_new_node(data, key, len); 179 if (!add) { 180 return LDNS_STATUS_MEM_ERR; 181 } 182 /** Search the trie until we can make no further process. */ 183 if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) { 184 /** No prefix found */ 185 assert(tree->root == NULL); 186 if (len == 0) { 187 /** 188 * Example 1: The root: 189 * | [0] 190 **/ 191 tree->root = add; 192 } else { 193 /** Example 2: 'dns': 194 * | [0] 195 * --| [d+ns] dns 196 **/ 197 prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0); 198 if (!prefix) { 199 LDNS_FREE(add); 200 return LDNS_STATUS_MEM_ERR; 201 } 202 /** Find some space in the array for the first byte */ 203 if (!ldns_radix_array_space(prefix, key[0])) { 204 LDNS_FREE(add); 205 LDNS_FREE(prefix->array); 206 LDNS_FREE(prefix); 207 return LDNS_STATUS_MEM_ERR; 208 } 209 /** Set relational pointers */ 210 add->parent = prefix; 211 add->parent_index = 0; 212 prefix->array[0].edge = add; 213 if (len > 1) { 214 /** Store the remainder of the prefix */ 215 if (!ldns_radix_prefix_remainder(1, key, 216 len, &prefix->array[0].str, 217 &prefix->array[0].len)) { 218 LDNS_FREE(add); 219 LDNS_FREE(prefix->array); 220 LDNS_FREE(prefix); 221 return LDNS_STATUS_MEM_ERR; 222 } 223 } 224 tree->root = prefix; 225 } 226 } else if (pos == len) { 227 /** Exact match found */ 228 if (prefix->data) { 229 /* Element already exists */ 230 LDNS_FREE(add); 231 return LDNS_STATUS_EXISTS_ERR; 232 } 233 prefix->data = data; 234 prefix->key = key; 235 prefix->klen = len; /* redundant */ 236 } else { 237 /** Prefix found */ 238 uint8_t byte = key[pos]; 239 assert(pos < len); 240 if (byte < prefix->offset || 241 (byte - prefix->offset) >= prefix->len) { 242 /** Find some space in the array for the byte. */ 243 /** 244 * Example 3: 'ldns' 245 * | [0] 246 * --| [d+ns] dns 247 * --| [l+dns] ldns 248 **/ 249 if (!ldns_radix_array_space(prefix, byte)) { 250 LDNS_FREE(add); 251 return LDNS_STATUS_MEM_ERR; 252 } 253 assert(byte >= prefix->offset); 254 assert((byte - prefix->offset) <= prefix->len); 255 byte -= prefix->offset; 256 if (pos+1 < len) { 257 /** Create remainder of the string. */ 258 if (!ldns_radix_str_create( 259 &prefix->array[byte], key, pos+1, 260 len)) { 261 LDNS_FREE(add); 262 return LDNS_STATUS_MEM_ERR; 263 } 264 } 265 /** Add new node. */ 266 add->parent = prefix; 267 add->parent_index = byte; 268 prefix->array[byte].edge = add; 269 } else if (prefix->array[byte-prefix->offset].edge == NULL) { 270 /** Use existing element. */ 271 /** 272 * Example 4: 'edns' 273 * | [0] 274 * --| [d+ns] dns 275 * --| [e+dns] edns 276 * --| [l+dns] ldns 277 **/ 278 byte -= prefix->offset; 279 if (pos+1 < len) { 280 /** Create remainder of the string. */ 281 if (!ldns_radix_str_create( 282 &prefix->array[byte], key, pos+1, 283 len)) { 284 LDNS_FREE(add); 285 return LDNS_STATUS_MEM_ERR; 286 } 287 } 288 /** Add new node. */ 289 add->parent = prefix; 290 add->parent_index = byte; 291 prefix->array[byte].edge = add; 292 } else { 293 /** 294 * Use existing element, but it has a shared prefix, 295 * we need a split. 296 */ 297 if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)], 298 key, pos+1, len, add)) { 299 LDNS_FREE(add); 300 return LDNS_STATUS_MEM_ERR; 301 } 302 } 303 } 304 305 tree->count ++; 306 return LDNS_STATUS_OK; 307 } 308 309 310 /** 311 * Delete data from the tree. 312 * 313 */ 314 void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len) 315 { 316 ldns_radix_node_t* del = ldns_radix_search(tree, key, len); 317 void* data = NULL; 318 if (del) { 319 tree->count--; 320 data = del->data; 321 del->data = NULL; 322 ldns_radix_del_fix(tree, del); 323 return data; 324 } 325 return NULL; 326 } 327 328 329 /** 330 * Search data in the tree. 331 * 332 */ 333 ldns_radix_node_t* 334 ldns_radix_search(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len) 335 { 336 ldns_radix_node_t* node = NULL; 337 radix_strlen_t pos = 0; 338 uint8_t byte = 0; 339 340 if (!tree || !key) { 341 return NULL; 342 } 343 node = tree->root; 344 while (node) { 345 if (pos == len) { 346 return node->data?node:NULL; 347 } 348 byte = key[pos]; 349 if (byte < node->offset) { 350 return NULL; 351 } 352 byte -= node->offset; 353 if (byte >= node->len) { 354 return NULL; 355 } 356 pos++; 357 if (node->array[byte].len > 0) { 358 /** Must match additional string. */ 359 if (pos + node->array[byte].len > len) { 360 return NULL; 361 } 362 if (memcmp(&key[pos], node->array[byte].str, 363 node->array[byte].len) != 0) { 364 return NULL; 365 } 366 pos += node->array[byte].len; 367 } 368 node = node->array[byte].edge; 369 } 370 return NULL; 371 } 372 373 374 /** 375 * Search data in the tree, and if not found, find the closest smaller 376 * element in the tree. 377 * 378 */ 379 int 380 ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key, 381 radix_strlen_t len, ldns_radix_node_t** result) 382 { 383 ldns_radix_node_t* node = NULL; 384 radix_strlen_t pos = 0; 385 uint8_t byte; 386 int memcmp_res = 0; 387 388 if (!tree || !tree->root || !key) { 389 *result = NULL; 390 return 0; 391 } 392 393 node = tree->root; 394 while (pos < len) { 395 byte = key[pos]; 396 if (byte < node->offset) { 397 /** 398 * No exact match. The lesser is in this or the 399 * previous node. 400 */ 401 ldns_radix_self_or_prev(node, result); 402 return 0; 403 } 404 byte -= node->offset; 405 if (byte >= node->len) { 406 /** 407 * No exact match. The lesser is in this node or the 408 * last of this array, or something before this node. 409 */ 410 *result = ldns_radix_last_in_subtree_incl_self(node); 411 if (*result == NULL) { 412 *result = ldns_radix_prev(node); 413 } 414 return 0; 415 } 416 pos++; 417 if (!node->array[byte].edge) { 418 /** 419 * No exact match. Find the previous in the array 420 * from this index. 421 */ 422 *result = ldns_radix_prev_from_index(node, byte); 423 if (*result == NULL) { 424 ldns_radix_self_or_prev(node, result); 425 } 426 return 0; 427 } 428 if (node->array[byte].len != 0) { 429 /** Must match additional string. */ 430 if (pos + node->array[byte].len > len) { 431 /** Additional string is longer than key. */ 432 if (memcmp(&key[pos], node->array[byte].str, 433 len-pos) <= 0) { 434 /** Key is before this node. */ 435 *result = ldns_radix_prev( 436 node->array[byte].edge); 437 } else { 438 /** Key is after additional string. */ 439 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge); 440 if (*result == NULL) { 441 *result = ldns_radix_prev(node->array[byte].edge); 442 } 443 } 444 return 0; 445 } 446 memcmp_res = memcmp(&key[pos], node->array[byte].str, 447 node->array[byte].len); 448 if (memcmp_res < 0) { 449 *result = ldns_radix_prev( 450 node->array[byte].edge); 451 return 0; 452 } else if (memcmp_res > 0) { 453 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge); 454 if (*result == NULL) { 455 *result = ldns_radix_prev(node->array[byte].edge); 456 } 457 return 0; 458 } 459 460 pos += node->array[byte].len; 461 } 462 node = node->array[byte].edge; 463 } 464 if (node->data) { 465 /** Exact match. */ 466 *result = node; 467 return 1; 468 } 469 /** There is a node which is an exact match, but has no element. */ 470 *result = ldns_radix_prev(node); 471 return 0; 472 } 473 474 475 /** 476 * Get the first element in the tree. 477 * 478 */ 479 ldns_radix_node_t* 480 ldns_radix_first(const ldns_radix_t* tree) 481 { 482 ldns_radix_node_t* first = NULL; 483 if (!tree || !tree->root) { 484 return NULL; 485 } 486 first = tree->root; 487 if (first->data) { 488 return first; 489 } 490 return ldns_radix_next(first); 491 } 492 493 494 /** 495 * Get the last element in the tree. 496 * 497 */ 498 ldns_radix_node_t* 499 ldns_radix_last(const ldns_radix_t* tree) 500 { 501 if (!tree || !tree->root) { 502 return NULL; 503 } 504 return ldns_radix_last_in_subtree_incl_self(tree->root); 505 } 506 507 508 /** 509 * Next element. 510 * 511 */ 512 ldns_radix_node_t* 513 ldns_radix_next(ldns_radix_node_t* node) 514 { 515 if (!node) { 516 return NULL; 517 } 518 if (node->len) { 519 /** Go down: most-left child is the next. */ 520 ldns_radix_node_t* next = ldns_radix_next_in_subtree(node); 521 if (next) { 522 return next; 523 } 524 } 525 /** No elements in subtree, get to parent and go down next branch. */ 526 while (node->parent) { 527 uint8_t index = node->parent_index; 528 node = node->parent; 529 index++; 530 for (; index < node->len; index++) { 531 if (node->array[index].edge) { 532 ldns_radix_node_t* next; 533 /** Node itself. */ 534 if (node->array[index].edge->data) { 535 return node->array[index].edge; 536 } 537 /** Dive into subtree. */ 538 next = ldns_radix_next_in_subtree(node); 539 if (next) { 540 return next; 541 } 542 } 543 } 544 } 545 return NULL; 546 } 547 548 549 /** 550 * Previous element. 551 * 552 */ 553 ldns_radix_node_t* 554 ldns_radix_prev(ldns_radix_node_t* node) 555 { 556 if (!node) { 557 return NULL; 558 } 559 560 /** Get to parent and go down previous branch. */ 561 while (node->parent) { 562 uint8_t index = node->parent_index; 563 ldns_radix_node_t* prev; 564 node = node->parent; 565 assert(node->len > 0); 566 prev = ldns_radix_prev_from_index(node, index); 567 if (prev) { 568 return prev; 569 } 570 if (node->data) { 571 return node; 572 } 573 } 574 return NULL; 575 } 576 577 578 /** 579 * Print node. 580 * 581 */ 582 static void 583 ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node, 584 uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d) 585 { 586 uint8_t j; 587 if (!node) { 588 return; 589 } 590 for (j = 0; j < d; j++) { 591 fprintf(fd, "--"); 592 } 593 if (str) { 594 radix_strlen_t l; 595 fprintf(fd, "| [%u+", (unsigned) i); 596 for (l=0; l < len; l++) { 597 fprintf(fd, "%c", (char) str[l]); 598 } 599 fprintf(fd, "]%u", (unsigned) len); 600 } else { 601 fprintf(fd, "| [%u]", (unsigned) i); 602 } 603 604 if (node->data) { 605 fprintf(fd, " %s", (char*) node->data); 606 } 607 fprintf(fd, "\n"); 608 609 for (j = 0; j < node->len; j++) { 610 if (node->array[j].edge) { 611 ldns_radix_node_print(fd, node->array[j].edge, j, 612 node->array[j].str, node->array[j].len, d+1); 613 } 614 } 615 return; 616 } 617 618 619 /** 620 * Print radix tree. 621 * 622 */ 623 void 624 ldns_radix_printf(FILE* fd, const ldns_radix_t* tree) 625 { 626 if (!fd || !tree) { 627 return; 628 } 629 if (!tree->root) { 630 fprintf(fd, "; empty radix tree\n"); 631 return; 632 } 633 ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0); 634 return; 635 } 636 637 638 /** 639 * Join two radix trees. 640 * 641 */ 642 ldns_status 643 ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2) 644 { 645 ldns_radix_node_t* cur_node, *next_node; 646 ldns_status status; 647 if (!tree2 || !tree2->root) { 648 return LDNS_STATUS_OK; 649 } 650 /** Add all elements from tree2 into tree1. */ 651 652 cur_node = ldns_radix_first(tree2); 653 while (cur_node) { 654 status = LDNS_STATUS_NO_DATA; 655 /** Insert current node into tree1 */ 656 if (cur_node->data) { 657 status = ldns_radix_insert(tree1, cur_node->key, 658 cur_node->klen, cur_node->data); 659 /** Exist errors may occur */ 660 if (status != LDNS_STATUS_OK && 661 status != LDNS_STATUS_EXISTS_ERR) { 662 return status; 663 } 664 } 665 next_node = ldns_radix_next(cur_node); 666 if (status == LDNS_STATUS_OK) { 667 (void) ldns_radix_delete(tree2, cur_node->key, 668 cur_node->klen); 669 } 670 cur_node = next_node; 671 } 672 673 return LDNS_STATUS_OK; 674 } 675 676 677 /** 678 * Split a radix tree intwo. 679 * 680 */ 681 ldns_status 682 ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2) 683 { 684 size_t count = 0; 685 ldns_radix_node_t* cur_node; 686 ldns_status status = LDNS_STATUS_OK; 687 if (!tree1 || !tree1->root || num == 0) { 688 return LDNS_STATUS_OK; 689 } 690 if (!tree2) { 691 return LDNS_STATUS_NULL; 692 } 693 if (!*tree2) { 694 *tree2 = ldns_radix_create(); 695 if (!*tree2) { 696 return LDNS_STATUS_MEM_ERR; 697 } 698 } 699 cur_node = ldns_radix_first(tree1); 700 while (count < num && cur_node) { 701 if (cur_node->data) { 702 /** Delete current node from tree1. */ 703 uint8_t* cur_key = cur_node->key; 704 radix_strlen_t cur_len = cur_node->klen; 705 void* cur_data = ldns_radix_delete(tree1, cur_key, 706 cur_len); 707 /** Insert current node into tree2/ */ 708 if (!cur_data) { 709 return LDNS_STATUS_NO_DATA; 710 } 711 status = ldns_radix_insert(*tree2, cur_key, cur_len, 712 cur_data); 713 if (status != LDNS_STATUS_OK && 714 status != LDNS_STATUS_EXISTS_ERR) { 715 return status; 716 } 717 /* 718 if (status == LDNS_STATUS_OK) { 719 cur_node->key = NULL; 720 cur_node->klen = 0; 721 } 722 */ 723 /** Update count; get first element from tree1 again. */ 724 count++; 725 cur_node = ldns_radix_first(tree1); 726 } else { 727 cur_node = ldns_radix_next(cur_node); 728 } 729 } 730 return LDNS_STATUS_OK; 731 } 732 733 734 /** 735 * Call function for all nodes in the tree, such that leaf nodes are 736 * called before parent nodes. 737 * 738 */ 739 void 740 ldns_radix_traverse_postorder(ldns_radix_node_t* node, 741 void (*func)(ldns_radix_node_t*, void*), void* arg) 742 { 743 uint8_t i; 744 if (!node) { 745 return; 746 } 747 for (i=0; i < node->len; i++) { 748 ldns_radix_traverse_postorder(node->array[i].edge, 749 func, arg); 750 } 751 /** Call user function */ 752 (*func)(node, arg); 753 return; 754 } 755 756 757 /** Static helper functions */ 758 759 /** 760 * Find a prefix of the key. 761 * @param tree: tree. 762 * @param key: key. 763 * @param len: length of key. 764 * @param result: the longest prefix, the entry itself if *pos==len, 765 * otherwise an array entry. 766 * @param pos: position in string where next unmatched byte is. 767 * If *pos==len, an exact match is found. 768 * If *pos== 0, a "" match was found. 769 * @return 0 (false) if no prefix found. 770 * 771 */ 772 static int 773 ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key, 774 radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos) 775 { 776 /** Start searching at the root node */ 777 ldns_radix_node_t* n = tree->root; 778 radix_strlen_t pos = 0; 779 uint8_t byte; 780 *respos = 0; 781 *result = n; 782 if (!n) { 783 /** No root, no prefix found */ 784 return 0; 785 } 786 /** For each node, look if we can make further progress */ 787 while (n) { 788 if (pos == len) { 789 /** Exact match */ 790 return 1; 791 } 792 byte = key[pos]; 793 if (byte < n->offset) { 794 /** key < node */ 795 return 1; 796 } 797 byte -= n->offset; 798 if (byte >= n->len) { 799 /** key > node */ 800 return 1; 801 } 802 /** So far, the trie matches */ 803 pos++; 804 if (n->array[byte].len != 0) { 805 /** Must match additional string */ 806 if (pos + n->array[byte].len > len) { 807 return 1; /* no match at child node */ 808 } 809 if (memcmp(&key[pos], n->array[byte].str, 810 n->array[byte].len) != 0) { 811 return 1; /* no match at child node */ 812 } 813 pos += n->array[byte].len; 814 } 815 /** Continue searching prefix at this child node */ 816 n = n->array[byte].edge; 817 if (!n) { 818 return 1; 819 } 820 /** Update the prefix node */ 821 *respos = pos; 822 *result = n; 823 } 824 /** Done */ 825 return 1; 826 } 827 828 829 /** 830 * Make space in the node's array for another byte. 831 * @param node: node. 832 * @param byte: byte. 833 * @return 1 if successful, 0 otherwise. 834 * 835 */ 836 static int 837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte) 838 { 839 /** Is there an array? */ 840 if (!node->array) { 841 assert(node->capacity == 0); 842 /** No array, create new array */ 843 node->array = LDNS_MALLOC(ldns_radix_array_t); 844 if (!node->array) { 845 return 0; 846 } 847 memset(&node->array[0], 0, sizeof(ldns_radix_array_t)); 848 node->len = 1; 849 node->capacity = 1; 850 node->offset = byte; 851 return 1; 852 } 853 /** Array exist */ 854 assert(node->array != NULL); 855 assert(node->capacity > 0); 856 857 if (node->len == 0) { 858 /** Unused array */ 859 node->len = 1; 860 node->offset = byte; 861 } else if (byte < node->offset) { 862 /** Byte is below the offset */ 863 uint8_t index; 864 uint16_t need = node->offset - byte; 865 /** Is there enough capacity? */ 866 if (node->len + need > node->capacity) { 867 /** Not enough capacity, grow array */ 868 if (!ldns_radix_array_grow(node, 869 (unsigned) (node->len + need))) { 870 return 0; /* failed to grow array */ 871 } 872 } 873 /** Move items to the end */ 874 memmove(&node->array[need], &node->array[0], 875 node->len*sizeof(ldns_radix_array_t)); 876 /** Fix parent index */ 877 for (index = 0; index < node->len; index++) { 878 if (node->array[index+need].edge) { 879 node->array[index+need].edge->parent_index = 880 index + need; 881 } 882 } 883 /** Zero the first */ 884 memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t)); 885 node->len += need; 886 node->offset = byte; 887 } else if (byte - node->offset >= node->len) { 888 /** Byte does not fit in array */ 889 uint16_t need = (byte - node->offset) - node->len + 1; 890 /** Is there enough capacity? */ 891 if (node->len + need > node->capacity) { 892 /** Not enough capacity, grow array */ 893 if (!ldns_radix_array_grow(node, 894 (unsigned) (node->len + need))) { 895 return 0; /* failed to grow array */ 896 } 897 } 898 /** Zero the added items */ 899 memset(&node->array[node->len], 0, 900 need*sizeof(ldns_radix_array_t)); 901 node->len += need; 902 } 903 return 1; 904 } 905 906 907 /** 908 * Grow the array. 909 * @param node: node. 910 * @param need: number of elements the array at least need to grow. 911 * Can't be bigger than 256. 912 * @return: 0 if failed, 1 if was successful. 913 * 914 */ 915 static int 916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need) 917 { 918 unsigned size = ((unsigned)node->capacity)*2; 919 ldns_radix_array_t* a = NULL; 920 if (need > size) { 921 size = need; 922 } 923 if (size > 256) { 924 size = 256; 925 } 926 a = LDNS_XMALLOC(ldns_radix_array_t, size); 927 if (!a) { 928 return 0; 929 } 930 assert(node->len <= node->capacity); 931 assert(node->capacity < size); 932 memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t)); 933 LDNS_FREE(node->array); 934 node->array = a; 935 node->capacity = size; 936 return 1; 937 } 938 939 940 /** 941 * Create a prefix in the array string. 942 * @param array: array. 943 * @param key: key. 944 * @param pos: start position in key. 945 * @param len: length of key. 946 * @return 0 if failed, 1 if was successful. 947 * 948 */ 949 static int 950 ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key, 951 radix_strlen_t pos, radix_strlen_t len) 952 { 953 array->str = LDNS_XMALLOC(uint8_t, (len-pos)); 954 if (!array->str) { 955 return 0; 956 } 957 memmove(array->str, key+pos, len-pos); 958 array->len = (len-pos); 959 return 1; 960 } 961 962 963 /** 964 * Allocate remainder from prefixes for a split. 965 * @param prefixlen: length of prefix. 966 * @param longer_str: the longer string. 967 * @param longer_len: the longer string length. 968 * @param split_str: the split string. 969 * @param split_len: the split string length. 970 * @return 0 if failed, 1 if successful. 971 * 972 */ 973 static int 974 ldns_radix_prefix_remainder(radix_strlen_t prefix_len, 975 uint8_t* longer_str, radix_strlen_t longer_len, 976 uint8_t** split_str, radix_strlen_t* split_len) 977 { 978 *split_len = longer_len - prefix_len; 979 *split_str = LDNS_XMALLOC(uint8_t, (*split_len)); 980 if (!*split_str) { 981 return 0; 982 } 983 memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len); 984 return 1; 985 } 986 987 988 /** 989 * Create a split when two nodes have a shared prefix. 990 * @param array: array. 991 * @param key: key. 992 * @param pos: start position in key. 993 * @param len: length of the key. 994 * @param add: node to be added. 995 * @return 0 if failed, 1 if was successful. 996 * 997 */ 998 static int 999 ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key, 1000 radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add) 1001 { 1002 uint8_t* str_to_add = key + pos; 1003 radix_strlen_t strlen_to_add = len - pos; 1004 1005 if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add, 1006 array->str, array->len)) { 1007 /** The string to add is a prefix of the existing string */ 1008 uint8_t* split_str = NULL, *dup_str = NULL; 1009 radix_strlen_t split_len = 0; 1010 /** 1011 * Example 5: 'ld' 1012 * | [0] 1013 * --| [d+ns] dns 1014 * --| [e+dns] edns 1015 * --| [l+d] ld 1016 * ----| [n+s] ldns 1017 **/ 1018 assert(strlen_to_add < array->len); 1019 /** Store the remainder in the split string */ 1020 if (array->len - strlen_to_add > 1) { 1021 if (!ldns_radix_prefix_remainder(strlen_to_add+1, 1022 array->str, array->len, &split_str, 1023 &split_len)) { 1024 return 0; 1025 } 1026 } 1027 /** Duplicate the string to add */ 1028 if (strlen_to_add != 0) { 1029 dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add); 1030 if (!dup_str) { 1031 LDNS_FREE(split_str); 1032 return 0; 1033 } 1034 memcpy(dup_str, str_to_add, strlen_to_add); 1035 } 1036 /** Make space in array for the new node */ 1037 if (!ldns_radix_array_space(add, 1038 array->str[strlen_to_add])) { 1039 LDNS_FREE(split_str); 1040 LDNS_FREE(dup_str); 1041 return 0; 1042 } 1043 /** 1044 * The added node should go direct under the existing parent. 1045 * The existing node should go under the added node. 1046 */ 1047 add->parent = array->edge->parent; 1048 add->parent_index = array->edge->parent_index; 1049 add->array[0].edge = array->edge; 1050 add->array[0].str = split_str; 1051 add->array[0].len = split_len; 1052 array->edge->parent = add; 1053 array->edge->parent_index = 0; 1054 LDNS_FREE(array->str); 1055 array->edge = add; 1056 array->str = dup_str; 1057 array->len = strlen_to_add; 1058 } else if (ldns_radix_str_is_prefix(array->str, array->len, 1059 str_to_add, strlen_to_add)) { 1060 /** The existing string is a prefix of the string to add */ 1061 /** 1062 * Example 6: 'dns-ng' 1063 * | [0] 1064 * --| [d+ns] dns 1065 * ----| [-+ng] dns-ng 1066 * --| [e+dns] edns 1067 * --| [l+d] ld 1068 * ----| [n+s] ldns 1069 **/ 1070 uint8_t* split_str = NULL; 1071 radix_strlen_t split_len = 0; 1072 assert(array->len < strlen_to_add); 1073 if (strlen_to_add - array->len > 1) { 1074 if (!ldns_radix_prefix_remainder(array->len+1, 1075 str_to_add, strlen_to_add, &split_str, 1076 &split_len)) { 1077 return 0; 1078 } 1079 } 1080 /** Make space in array for the new node */ 1081 if (!ldns_radix_array_space(array->edge, 1082 str_to_add[array->len])) { 1083 LDNS_FREE(split_str); 1084 return 0; 1085 } 1086 /** 1087 * The added node should go direct under the existing node. 1088 */ 1089 add->parent = array->edge; 1090 add->parent_index = str_to_add[array->len] - 1091 array->edge->offset; 1092 array->edge->array[add->parent_index].edge = add; 1093 array->edge->array[add->parent_index].str = split_str; 1094 array->edge->array[add->parent_index].len = split_len; 1095 } else { 1096 /** Create a new split node. */ 1097 /** 1098 * Example 7: 'dndns' 1099 * | [0] 1100 * --| [d+n] 1101 * ----| [d+ns] dndns 1102 * ----| [s] dns 1103 * ------| [-+ng] dns-ng 1104 * --| [e+dns] edns 1105 * --| [l+d] ld 1106 * ----| [n+s] ldns 1107 **/ 1108 ldns_radix_node_t* common = NULL; 1109 uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL; 1110 radix_strlen_t common_len = 0, l1 = 0, l2 = 0; 1111 common_len = ldns_radix_str_common(array->str, array->len, 1112 str_to_add, strlen_to_add); 1113 assert(common_len < array->len); 1114 assert(common_len < strlen_to_add); 1115 /** Create the new common node. */ 1116 common = ldns_radix_new_node(NULL, (uint8_t*)"", 0); 1117 if (!common) { 1118 return 0; 1119 } 1120 if (array->len - common_len > 1) { 1121 if (!ldns_radix_prefix_remainder(common_len+1, 1122 array->str, array->len, &s1, &l1)) { 1123 return 0; 1124 } 1125 } 1126 if (strlen_to_add - common_len > 1) { 1127 if (!ldns_radix_prefix_remainder(common_len+1, 1128 str_to_add, strlen_to_add, &s2, &l2)) { 1129 return 0; 1130 } 1131 } 1132 /** Create the shared prefix. */ 1133 if (common_len > 0) { 1134 common_str = LDNS_XMALLOC(uint8_t, common_len); 1135 if (!common_str) { 1136 LDNS_FREE(common); 1137 LDNS_FREE(s1); 1138 LDNS_FREE(s2); 1139 return 0; 1140 } 1141 memcpy(common_str, str_to_add, common_len); 1142 } 1143 /** Make space in the common node array. */ 1144 if (!ldns_radix_array_space(common, array->str[common_len]) || 1145 !ldns_radix_array_space(common, str_to_add[common_len])) { 1146 LDNS_FREE(common->array); 1147 LDNS_FREE(common); 1148 LDNS_FREE(common_str); 1149 LDNS_FREE(s1); 1150 LDNS_FREE(s2); 1151 return 0; 1152 } 1153 /** 1154 * The common node should go direct under the parent node. 1155 * The added and existing nodes go under the common node. 1156 */ 1157 common->parent = array->edge->parent; 1158 common->parent_index = array->edge->parent_index; 1159 array->edge->parent = common; 1160 array->edge->parent_index = array->str[common_len] - 1161 common->offset; 1162 add->parent = common; 1163 add->parent_index = str_to_add[common_len] - common->offset; 1164 common->array[array->edge->parent_index].edge = array->edge; 1165 common->array[array->edge->parent_index].str = s1; 1166 common->array[array->edge->parent_index].len = l1; 1167 common->array[add->parent_index].edge = add; 1168 common->array[add->parent_index].str = s2; 1169 common->array[add->parent_index].len = l2; 1170 LDNS_FREE(array->str); 1171 array->edge = common; 1172 array->str = common_str; 1173 array->len = common_len; 1174 } 1175 return 1; 1176 } 1177 1178 1179 /** 1180 * Check if one string prefix of other string. 1181 * @param str1: one string. 1182 * @param len1: one string length. 1183 * @param str2: other string. 1184 * @param len2: other string length. 1185 * @return 1 if prefix, 0 otherwise. 1186 * 1187 */ 1188 static int 1189 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1, 1190 uint8_t* str2, radix_strlen_t len2) 1191 { 1192 if (len1 == 0) { 1193 return 1; /* empty prefix is also a prefix */ 1194 } 1195 if (len1 > len2) { 1196 return 0; /* len1 is longer so str1 cannot be a prefix */ 1197 } 1198 return (memcmp(str1, str2, len1) == 0); 1199 } 1200 1201 1202 /** 1203 * Return the number of bytes in common for the two strings. 1204 * @param str1: one string. 1205 * @param len1: one string length. 1206 * @param str2: other string. 1207 * @param len2: other string length. 1208 * @return length of substring that the two strings have in common. 1209 * 1210 */ 1211 static radix_strlen_t 1212 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1, 1213 uint8_t* str2, radix_strlen_t len2) 1214 { 1215 radix_strlen_t i, max = (len1<len2)?len1:len2; 1216 for (i=0; i<max; i++) { 1217 if (str1[i] != str2[i]) { 1218 return i; 1219 } 1220 } 1221 return max; 1222 } 1223 1224 1225 /** 1226 * Find the next element in the subtree of this node. 1227 * @param node: node. 1228 * @return: node with next element. 1229 * 1230 */ 1231 static ldns_radix_node_t* 1232 ldns_radix_next_in_subtree(ldns_radix_node_t* node) 1233 { 1234 uint16_t i; 1235 ldns_radix_node_t* next; 1236 /** Try every subnode. */ 1237 for (i = 0; i < node->len; i++) { 1238 if (node->array[i].edge) { 1239 /** Node itself. */ 1240 if (node->array[i].edge->data) { 1241 return node->array[i].edge; 1242 } 1243 /** Dive into subtree. */ 1244 next = ldns_radix_next_in_subtree(node->array[i].edge); 1245 if (next) { 1246 return next; 1247 } 1248 } 1249 } 1250 return NULL; 1251 } 1252 1253 1254 /** 1255 * Find the previous element in the array of this node, from index. 1256 * @param node: node. 1257 * @param index: index. 1258 * @return previous node from index. 1259 * 1260 */ 1261 static ldns_radix_node_t* 1262 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index) 1263 { 1264 uint8_t i = index; 1265 while (i > 0) { 1266 i--; 1267 if (node->array[i].edge) { 1268 ldns_radix_node_t* prev = 1269 ldns_radix_last_in_subtree_incl_self(node); 1270 if (prev) { 1271 return prev; 1272 } 1273 } 1274 } 1275 return NULL; 1276 } 1277 1278 1279 /** 1280 * Find last node in subtree, or this node (if have data). 1281 * @param node: node. 1282 * @return last node in subtree, or this node, or NULL. 1283 * 1284 */ 1285 static ldns_radix_node_t* 1286 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node) 1287 { 1288 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node); 1289 if (last) { 1290 return last; 1291 } else if (node->data) { 1292 return node; 1293 } 1294 return NULL; 1295 } 1296 1297 1298 /** 1299 * Find last node in subtree. 1300 * @param node: node. 1301 * @return last node in subtree. 1302 * 1303 */ 1304 static ldns_radix_node_t* 1305 ldns_radix_last_in_subtree(ldns_radix_node_t* node) 1306 { 1307 int i; 1308 /** Look for the most right leaf node. */ 1309 for (i=(int)(node->len)-1; i >= 0; i--) { 1310 if (node->array[i].edge) { 1311 /** Keep looking for the most right leaf node. */ 1312 if (node->array[i].edge->len > 0) { 1313 ldns_radix_node_t* last = 1314 ldns_radix_last_in_subtree( 1315 node->array[i].edge); 1316 if (last) { 1317 return last; 1318 } 1319 } 1320 /** Could this be the most right leaf node? */ 1321 if (node->array[i].edge->data) { 1322 return node->array[i].edge; 1323 } 1324 } 1325 } 1326 return NULL; 1327 } 1328 1329 1330 /** 1331 * Fix tree after deleting element. 1332 * @param tree: tree. 1333 * @param node: node with deleted element. 1334 * 1335 */ 1336 static void 1337 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node) 1338 { 1339 while (node) { 1340 if (node->data) { 1341 /** Thou should not delete nodes with data attached. */ 1342 return; 1343 } else if (node->len == 1 && node->parent) { 1344 /** Node with one child is fold back into. */ 1345 ldns_radix_cleanup_onechild(node); 1346 return; 1347 } else if (node->len == 0) { 1348 /** Leaf node. */ 1349 ldns_radix_node_t* parent = node->parent; 1350 if (!parent) { 1351 /** The root is a leaf node. */ 1352 ldns_radix_node_free(node, NULL); 1353 tree->root = NULL; 1354 return; 1355 } 1356 /** Cleanup leaf node and continue with parent. */ 1357 ldns_radix_cleanup_leaf(node); 1358 node = parent; 1359 } else { 1360 /** 1361 * Node cannot be deleted, because it has edge nodes 1362 * and no parent to fix up to. 1363 */ 1364 return; 1365 } 1366 } 1367 /** Not reached. */ 1368 return; 1369 } 1370 1371 1372 /** 1373 * Clean up a node with one child. 1374 * @param node: node with one child. 1375 * 1376 */ 1377 static void 1378 ldns_radix_cleanup_onechild(ldns_radix_node_t* node) 1379 { 1380 uint8_t* join_str; 1381 radix_strlen_t join_len; 1382 uint8_t parent_index = node->parent_index; 1383 ldns_radix_node_t* child = node->array[0].edge; 1384 ldns_radix_node_t* parent = node->parent; 1385 1386 /** Node has one child, merge the child node into the parent node. */ 1387 assert(parent_index < parent->len); 1388 join_len = parent->array[parent_index].len + node->array[0].len + 1; 1389 1390 join_str = LDNS_XMALLOC(uint8_t, join_len); 1391 if (!join_str) { 1392 /** 1393 * Cleanup failed due to out of memory. 1394 * This tree is now inefficient, with the empty node still 1395 * existing, but it is still valid. 1396 */ 1397 return; 1398 } 1399 1400 memcpy(join_str, parent->array[parent_index].str, 1401 parent->array[parent_index].len); 1402 join_str[parent->array[parent_index].len] = child->parent_index + 1403 node->offset; 1404 memmove(join_str + parent->array[parent_index].len+1, 1405 node->array[0].str, node->array[0].len); 1406 1407 LDNS_FREE(parent->array[parent_index].str); 1408 parent->array[parent_index].str = join_str; 1409 parent->array[parent_index].len = join_len; 1410 parent->array[parent_index].edge = child; 1411 child->parent = parent; 1412 child->parent_index = parent_index; 1413 ldns_radix_node_free(node, NULL); 1414 return; 1415 } 1416 1417 1418 /** 1419 * Clean up a leaf node. 1420 * @param node: leaf node. 1421 * 1422 */ 1423 static void 1424 ldns_radix_cleanup_leaf(ldns_radix_node_t* node) 1425 { 1426 uint8_t parent_index = node->parent_index; 1427 ldns_radix_node_t* parent = node->parent; 1428 /** Delete lead node and fix parent array. */ 1429 assert(parent_index < parent->len); 1430 ldns_radix_node_free(node, NULL); 1431 LDNS_FREE(parent->array[parent_index].str); 1432 parent->array[parent_index].str = NULL; 1433 parent->array[parent_index].len = 0; 1434 parent->array[parent_index].edge = NULL; 1435 /** Fix array in parent. */ 1436 if (parent->len == 1) { 1437 ldns_radix_node_array_free(parent); 1438 } else if (parent_index == 0) { 1439 ldns_radix_node_array_free_front(parent); 1440 } else { 1441 ldns_radix_node_array_free_end(parent); 1442 } 1443 return; 1444 } 1445 1446 1447 /** 1448 * Free a radix node. 1449 * @param node: node. 1450 * @param arg: user argument. 1451 * 1452 */ 1453 static void 1454 ldns_radix_node_free(ldns_radix_node_t* node, void* arg) 1455 { 1456 uint16_t i; 1457 (void) arg; 1458 if (!node) { 1459 return; 1460 } 1461 for (i=0; i < node->len; i++) { 1462 LDNS_FREE(node->array[i].str); 1463 } 1464 node->key = NULL; 1465 node->klen = 0; 1466 LDNS_FREE(node->array); 1467 LDNS_FREE(node); 1468 return; 1469 } 1470 1471 1472 /** 1473 * Free select edge array. 1474 * @param node: node. 1475 * 1476 */ 1477 static void 1478 ldns_radix_node_array_free(ldns_radix_node_t* node) 1479 { 1480 node->offset = 0; 1481 node->len = 0; 1482 LDNS_FREE(node->array); 1483 node->array = NULL; 1484 node->capacity = 0; 1485 return; 1486 } 1487 1488 1489 /** 1490 * Free front of select edge array. 1491 * @param node: node. 1492 * 1493 */ 1494 static void 1495 ldns_radix_node_array_free_front(ldns_radix_node_t* node) 1496 { 1497 uint16_t i, n = 0; 1498 /** Remove until a non NULL entry. */ 1499 while (n < node->len && node->array[n].edge == NULL) { 1500 n++; 1501 } 1502 if (n == 0) { 1503 return; 1504 } 1505 if (n == node->len) { 1506 ldns_radix_node_array_free(node); 1507 return; 1508 } 1509 assert(n < node->len); 1510 assert((int) n <= (255 - (int) node->offset)); 1511 memmove(&node->array[0], &node->array[n], 1512 (node->len - n)*sizeof(ldns_radix_array_t)); 1513 node->offset += n; 1514 node->len -= n; 1515 for (i=0; i < node->len; i++) { 1516 if (node->array[i].edge) { 1517 node->array[i].edge->parent_index = i; 1518 } 1519 } 1520 ldns_radix_array_reduce(node); 1521 return; 1522 } 1523 1524 1525 /** 1526 * Free front of select edge array. 1527 * @param node: node. 1528 * 1529 */ 1530 static void 1531 ldns_radix_node_array_free_end(ldns_radix_node_t* node) 1532 { 1533 uint16_t n = 0; 1534 /** Shorten array. */ 1535 while (n < node->len && node->array[node->len-1-n].edge == NULL) { 1536 n++; 1537 } 1538 if (n == 0) { 1539 return; 1540 } 1541 if (n == node->len) { 1542 ldns_radix_node_array_free(node); 1543 return; 1544 } 1545 assert(n < node->len); 1546 node->len -= n; 1547 ldns_radix_array_reduce(node); 1548 return; 1549 } 1550 1551 1552 /** 1553 * Reduce the capacity of the array if needed. 1554 * @param node: node. 1555 * 1556 */ 1557 static void 1558 ldns_radix_array_reduce(ldns_radix_node_t* node) 1559 { 1560 if (node->len <= node->capacity/2 && node->len != node->capacity) { 1561 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t, 1562 node->len); 1563 if (!a) { 1564 return; 1565 } 1566 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len); 1567 LDNS_FREE(node->array); 1568 node->array = a; 1569 node->capacity = node->len; 1570 } 1571 return; 1572 } 1573 1574 1575 /** 1576 * Return this element if it exists, the previous otherwise. 1577 * @param node: from this node. 1578 * @param result: result node. 1579 * 1580 */ 1581 static void 1582 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result) 1583 { 1584 if (node->data) { 1585 *result = node; 1586 } else { 1587 *result = ldns_radix_prev(node); 1588 } 1589 return; 1590 } 1591