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 LDNS_FREE(add); 229 if (prefix->data) { 230 /* Element already exists */ 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 LDNS_FREE(common); 1124 return 0; 1125 } 1126 } 1127 if (strlen_to_add - common_len > 1) { 1128 if (!ldns_radix_prefix_remainder(common_len+1, 1129 str_to_add, strlen_to_add, &s2, &l2)) { 1130 LDNS_FREE(common); 1131 LDNS_FREE(s1); 1132 return 0; 1133 } 1134 } 1135 /** Create the shared prefix. */ 1136 if (common_len > 0) { 1137 common_str = LDNS_XMALLOC(uint8_t, common_len); 1138 if (!common_str) { 1139 LDNS_FREE(common); 1140 LDNS_FREE(s1); 1141 LDNS_FREE(s2); 1142 return 0; 1143 } 1144 memcpy(common_str, str_to_add, common_len); 1145 } 1146 /** Make space in the common node array. */ 1147 if (!ldns_radix_array_space(common, array->str[common_len]) || 1148 !ldns_radix_array_space(common, str_to_add[common_len])) { 1149 LDNS_FREE(common->array); 1150 LDNS_FREE(common); 1151 LDNS_FREE(common_str); 1152 LDNS_FREE(s1); 1153 LDNS_FREE(s2); 1154 return 0; 1155 } 1156 /** 1157 * The common node should go direct under the parent node. 1158 * The added and existing nodes go under the common node. 1159 */ 1160 common->parent = array->edge->parent; 1161 common->parent_index = array->edge->parent_index; 1162 array->edge->parent = common; 1163 array->edge->parent_index = array->str[common_len] - 1164 common->offset; 1165 add->parent = common; 1166 add->parent_index = str_to_add[common_len] - common->offset; 1167 common->array[array->edge->parent_index].edge = array->edge; 1168 common->array[array->edge->parent_index].str = s1; 1169 common->array[array->edge->parent_index].len = l1; 1170 common->array[add->parent_index].edge = add; 1171 common->array[add->parent_index].str = s2; 1172 common->array[add->parent_index].len = l2; 1173 LDNS_FREE(array->str); 1174 array->edge = common; 1175 array->str = common_str; 1176 array->len = common_len; 1177 } 1178 return 1; 1179 } 1180 1181 1182 /** 1183 * Check if one string prefix of other string. 1184 * @param str1: one string. 1185 * @param len1: one string length. 1186 * @param str2: other string. 1187 * @param len2: other string length. 1188 * @return 1 if prefix, 0 otherwise. 1189 * 1190 */ 1191 static int 1192 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1, 1193 uint8_t* str2, radix_strlen_t len2) 1194 { 1195 if (len1 == 0) { 1196 return 1; /* empty prefix is also a prefix */ 1197 } 1198 if (len1 > len2) { 1199 return 0; /* len1 is longer so str1 cannot be a prefix */ 1200 } 1201 return (memcmp(str1, str2, len1) == 0); 1202 } 1203 1204 1205 /** 1206 * Return the number of bytes in common for the two strings. 1207 * @param str1: one string. 1208 * @param len1: one string length. 1209 * @param str2: other string. 1210 * @param len2: other string length. 1211 * @return length of substring that the two strings have in common. 1212 * 1213 */ 1214 static radix_strlen_t 1215 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1, 1216 uint8_t* str2, radix_strlen_t len2) 1217 { 1218 radix_strlen_t i, max = (len1<len2)?len1:len2; 1219 for (i=0; i<max; i++) { 1220 if (str1[i] != str2[i]) { 1221 return i; 1222 } 1223 } 1224 return max; 1225 } 1226 1227 1228 /** 1229 * Find the next element in the subtree of this node. 1230 * @param node: node. 1231 * @return: node with next element. 1232 * 1233 */ 1234 static ldns_radix_node_t* 1235 ldns_radix_next_in_subtree(ldns_radix_node_t* node) 1236 { 1237 uint16_t i; 1238 ldns_radix_node_t* next; 1239 /** Try every subnode. */ 1240 for (i = 0; i < node->len; i++) { 1241 if (node->array[i].edge) { 1242 /** Node itself. */ 1243 if (node->array[i].edge->data) { 1244 return node->array[i].edge; 1245 } 1246 /** Dive into subtree. */ 1247 next = ldns_radix_next_in_subtree(node->array[i].edge); 1248 if (next) { 1249 return next; 1250 } 1251 } 1252 } 1253 return NULL; 1254 } 1255 1256 1257 /** 1258 * Find the previous element in the array of this node, from index. 1259 * @param node: node. 1260 * @param index: index. 1261 * @return previous node from index. 1262 * 1263 */ 1264 static ldns_radix_node_t* 1265 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index) 1266 { 1267 uint8_t i = index; 1268 while (i > 0) { 1269 i--; 1270 if (node->array[i].edge) { 1271 ldns_radix_node_t* prev = 1272 ldns_radix_last_in_subtree_incl_self(node); 1273 if (prev) { 1274 return prev; 1275 } 1276 } 1277 } 1278 return NULL; 1279 } 1280 1281 1282 /** 1283 * Find last node in subtree, or this node (if have data). 1284 * @param node: node. 1285 * @return last node in subtree, or this node, or NULL. 1286 * 1287 */ 1288 static ldns_radix_node_t* 1289 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node) 1290 { 1291 ldns_radix_node_t* last = ldns_radix_last_in_subtree(node); 1292 if (last) { 1293 return last; 1294 } else if (node->data) { 1295 return node; 1296 } 1297 return NULL; 1298 } 1299 1300 1301 /** 1302 * Find last node in subtree. 1303 * @param node: node. 1304 * @return last node in subtree. 1305 * 1306 */ 1307 static ldns_radix_node_t* 1308 ldns_radix_last_in_subtree(ldns_radix_node_t* node) 1309 { 1310 int i; 1311 /** Look for the most right leaf node. */ 1312 for (i=(int)(node->len)-1; i >= 0; i--) { 1313 if (node->array[i].edge) { 1314 /** Keep looking for the most right leaf node. */ 1315 if (node->array[i].edge->len > 0) { 1316 ldns_radix_node_t* last = 1317 ldns_radix_last_in_subtree( 1318 node->array[i].edge); 1319 if (last) { 1320 return last; 1321 } 1322 } 1323 /** Could this be the most right leaf node? */ 1324 if (node->array[i].edge->data) { 1325 return node->array[i].edge; 1326 } 1327 } 1328 } 1329 return NULL; 1330 } 1331 1332 1333 /** 1334 * Fix tree after deleting element. 1335 * @param tree: tree. 1336 * @param node: node with deleted element. 1337 * 1338 */ 1339 static void 1340 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node) 1341 { 1342 while (node) { 1343 if (node->data) { 1344 /** Thou should not delete nodes with data attached. */ 1345 return; 1346 } else if (node->len == 1 && node->parent) { 1347 /** Node with one child is fold back into. */ 1348 ldns_radix_cleanup_onechild(node); 1349 return; 1350 } else if (node->len == 0) { 1351 /** Leaf node. */ 1352 ldns_radix_node_t* parent = node->parent; 1353 if (!parent) { 1354 /** The root is a leaf node. */ 1355 ldns_radix_node_free(node, NULL); 1356 tree->root = NULL; 1357 return; 1358 } 1359 /** Cleanup leaf node and continue with parent. */ 1360 ldns_radix_cleanup_leaf(node); 1361 node = parent; 1362 } else { 1363 /** 1364 * Node cannot be deleted, because it has edge nodes 1365 * and no parent to fix up to. 1366 */ 1367 return; 1368 } 1369 } 1370 /** Not reached. */ 1371 return; 1372 } 1373 1374 1375 /** 1376 * Clean up a node with one child. 1377 * @param node: node with one child. 1378 * 1379 */ 1380 static void 1381 ldns_radix_cleanup_onechild(ldns_radix_node_t* node) 1382 { 1383 uint8_t* join_str; 1384 radix_strlen_t join_len; 1385 uint8_t parent_index = node->parent_index; 1386 ldns_radix_node_t* child = node->array[0].edge; 1387 ldns_radix_node_t* parent = node->parent; 1388 1389 /** Node has one child, merge the child node into the parent node. */ 1390 assert(parent_index < parent->len); 1391 join_len = parent->array[parent_index].len + node->array[0].len + 1; 1392 1393 join_str = LDNS_XMALLOC(uint8_t, join_len); 1394 if (!join_str) { 1395 /** 1396 * Cleanup failed due to out of memory. 1397 * This tree is now inefficient, with the empty node still 1398 * existing, but it is still valid. 1399 */ 1400 return; 1401 } 1402 1403 memcpy(join_str, parent->array[parent_index].str, 1404 parent->array[parent_index].len); 1405 join_str[parent->array[parent_index].len] = child->parent_index + 1406 node->offset; 1407 memmove(join_str + parent->array[parent_index].len+1, 1408 node->array[0].str, node->array[0].len); 1409 1410 LDNS_FREE(parent->array[parent_index].str); 1411 parent->array[parent_index].str = join_str; 1412 parent->array[parent_index].len = join_len; 1413 parent->array[parent_index].edge = child; 1414 child->parent = parent; 1415 child->parent_index = parent_index; 1416 ldns_radix_node_free(node, NULL); 1417 return; 1418 } 1419 1420 1421 /** 1422 * Clean up a leaf node. 1423 * @param node: leaf node. 1424 * 1425 */ 1426 static void 1427 ldns_radix_cleanup_leaf(ldns_radix_node_t* node) 1428 { 1429 uint8_t parent_index = node->parent_index; 1430 ldns_radix_node_t* parent = node->parent; 1431 /** Delete lead node and fix parent array. */ 1432 assert(parent_index < parent->len); 1433 ldns_radix_node_free(node, NULL); 1434 LDNS_FREE(parent->array[parent_index].str); 1435 parent->array[parent_index].str = NULL; 1436 parent->array[parent_index].len = 0; 1437 parent->array[parent_index].edge = NULL; 1438 /** Fix array in parent. */ 1439 if (parent->len == 1) { 1440 ldns_radix_node_array_free(parent); 1441 } else if (parent_index == 0) { 1442 ldns_radix_node_array_free_front(parent); 1443 } else { 1444 ldns_radix_node_array_free_end(parent); 1445 } 1446 return; 1447 } 1448 1449 1450 /** 1451 * Free a radix node. 1452 * @param node: node. 1453 * @param arg: user argument. 1454 * 1455 */ 1456 static void 1457 ldns_radix_node_free(ldns_radix_node_t* node, void* arg) 1458 { 1459 uint16_t i; 1460 (void) arg; 1461 if (!node) { 1462 return; 1463 } 1464 for (i=0; i < node->len; i++) { 1465 LDNS_FREE(node->array[i].str); 1466 } 1467 node->key = NULL; 1468 node->klen = 0; 1469 LDNS_FREE(node->array); 1470 LDNS_FREE(node); 1471 return; 1472 } 1473 1474 1475 /** 1476 * Free select edge array. 1477 * @param node: node. 1478 * 1479 */ 1480 static void 1481 ldns_radix_node_array_free(ldns_radix_node_t* node) 1482 { 1483 node->offset = 0; 1484 node->len = 0; 1485 LDNS_FREE(node->array); 1486 node->array = NULL; 1487 node->capacity = 0; 1488 return; 1489 } 1490 1491 1492 /** 1493 * Free front of select edge array. 1494 * @param node: node. 1495 * 1496 */ 1497 static void 1498 ldns_radix_node_array_free_front(ldns_radix_node_t* node) 1499 { 1500 uint16_t i, n = 0; 1501 /** Remove until a non NULL entry. */ 1502 while (n < node->len && node->array[n].edge == NULL) { 1503 n++; 1504 } 1505 if (n == 0) { 1506 return; 1507 } 1508 if (n == node->len) { 1509 ldns_radix_node_array_free(node); 1510 return; 1511 } 1512 assert(n < node->len); 1513 assert((int) n <= (255 - (int) node->offset)); 1514 memmove(&node->array[0], &node->array[n], 1515 (node->len - n)*sizeof(ldns_radix_array_t)); 1516 node->offset += n; 1517 node->len -= n; 1518 for (i=0; i < node->len; i++) { 1519 if (node->array[i].edge) { 1520 node->array[i].edge->parent_index = i; 1521 } 1522 } 1523 ldns_radix_array_reduce(node); 1524 return; 1525 } 1526 1527 1528 /** 1529 * Free front of select edge array. 1530 * @param node: node. 1531 * 1532 */ 1533 static void 1534 ldns_radix_node_array_free_end(ldns_radix_node_t* node) 1535 { 1536 uint16_t n = 0; 1537 /** Shorten array. */ 1538 while (n < node->len && node->array[node->len-1-n].edge == NULL) { 1539 n++; 1540 } 1541 if (n == 0) { 1542 return; 1543 } 1544 if (n == node->len) { 1545 ldns_radix_node_array_free(node); 1546 return; 1547 } 1548 assert(n < node->len); 1549 node->len -= n; 1550 ldns_radix_array_reduce(node); 1551 return; 1552 } 1553 1554 1555 /** 1556 * Reduce the capacity of the array if needed. 1557 * @param node: node. 1558 * 1559 */ 1560 static void 1561 ldns_radix_array_reduce(ldns_radix_node_t* node) 1562 { 1563 if (node->len <= node->capacity/2 && node->len != node->capacity) { 1564 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t, 1565 node->len); 1566 if (!a) { 1567 return; 1568 } 1569 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len); 1570 LDNS_FREE(node->array); 1571 node->array = a; 1572 node->capacity = node->len; 1573 } 1574 return; 1575 } 1576 1577 1578 /** 1579 * Return this element if it exists, the previous otherwise. 1580 * @param node: from this node. 1581 * @param result: result node. 1582 * 1583 */ 1584 static void 1585 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result) 1586 { 1587 if (node->data) { 1588 *result = node; 1589 } else { 1590 *result = ldns_radix_prev(node); 1591 } 1592 return; 1593 } 1594