contrib/ldns/radix.c

   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 LIMITED
  27  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  28  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  29  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  30  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  33  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  35  * 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, 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, 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, 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(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(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, 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 }