radix.c
Go to the documentation of this file.
00001 /*
00002  * radix.c -- generic radix tree
00003  *
00004  * Taken from NSD4, modified for ldns
00005  *
00006  * Copyright (c) 2012, NLnet Labs. All rights reserved.
00007  *
00008  * This software is open source.
00009  *
00010  * Redistribution and use in source and binary forms, with or without
00011  * modification, are permitted provided that the following conditions
00012  * are met:
00013  *
00014  * Redistributions of source code must retain the above copyright notice,
00015  * this list of conditions and the following disclaimer.
00016  *
00017  * Redistributions in binary form must reproduce the above copyright notice,
00018  * this list of conditions and the following disclaimer in the documentation
00019  * and/or other materials provided with the distribution.
00020  *
00021  * Neither the name of the NLNET LABS nor the names of its contributors may
00022  * be used to endorse or promote products derived from this software without
00023  * specific prior written permission.
00024  *
00025  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00026  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
00027  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
00029  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00030  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00031  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00032  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00033  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00034  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00035  * POSSIBILITY OF SUCH DAMAGE.
00036  *
00037  */
00038 
00044 #include <ldns/config.h>
00045 #include <ldns/radix.h>
00046 #include <ldns/util.h>
00047 #include <stdlib.h>
00048 
00050 static ldns_radix_node_t* ldns_radix_new_node(void* data, uint8_t* key,
00051         radix_strlen_t len);
00052 static int ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
00053         radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* pos);
00054 static int ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte);
00055 static int ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need);
00056 static int ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
00057         radix_strlen_t pos, radix_strlen_t len);
00058 static int ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
00059         uint8_t* longer_str, radix_strlen_t longer_len, uint8_t** split_str,
00060         radix_strlen_t* split_len);
00061 static int ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
00062         radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add);
00063 static int ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
00064         uint8_t* str2, radix_strlen_t len2);
00065 static radix_strlen_t ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
00066         uint8_t* str2, radix_strlen_t len2);
00067 static ldns_radix_node_t* ldns_radix_next_in_subtree(ldns_radix_node_t* node);
00068 static ldns_radix_node_t* ldns_radix_prev_from_index(ldns_radix_node_t* node,
00069         uint8_t index);
00070 static ldns_radix_node_t* ldns_radix_last_in_subtree_incl_self(
00071         ldns_radix_node_t* node);
00072 static ldns_radix_node_t* ldns_radix_last_in_subtree(ldns_radix_node_t* node);
00073 static void ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node);
00074 static void ldns_radix_cleanup_onechild(ldns_radix_node_t* node);
00075 static void ldns_radix_cleanup_leaf(ldns_radix_node_t* node);
00076 static void ldns_radix_node_free(ldns_radix_node_t* node, void* arg);
00077 static void ldns_radix_node_array_free(ldns_radix_node_t* node);
00078 static void ldns_radix_node_array_free_front(ldns_radix_node_t* node);
00079 static void ldns_radix_node_array_free_end(ldns_radix_node_t* node);
00080 static void ldns_radix_array_reduce(ldns_radix_node_t* node);
00081 static void ldns_radix_self_or_prev(ldns_radix_node_t* node,
00082         ldns_radix_node_t** result);
00083 
00084 
00089 static ldns_radix_node_t*
00090 ldns_radix_new_node(void* data, uint8_t* key, radix_strlen_t len)
00091 {
00092         ldns_radix_node_t* node = LDNS_MALLOC(ldns_radix_node_t);
00093         if (!node) {
00094                 return NULL;
00095         }
00096         node->data = data;
00097         node->key = key;
00098         node->klen = len;
00099         node->parent = NULL;
00100         node->parent_index = 0;
00101         node->len = 0;
00102         node->offset = 0;
00103         node->capacity = 0;
00104         node->array = NULL;
00105         return node;
00106 }
00107 
00108 
00113 ldns_radix_t *
00114 ldns_radix_create(void)
00115 {
00116         ldns_radix_t* tree;
00117 
00119         tree = (ldns_radix_t *) LDNS_MALLOC(ldns_radix_t);
00120         if (!tree) {
00121                 return NULL;
00122         }
00124         ldns_radix_init(tree);
00125         return tree;
00126 }
00127 
00128 
00133 void
00134 ldns_radix_init(ldns_radix_t* tree)
00135 {
00137         if (tree) {
00138                 tree->root = NULL;
00139                 tree->count = 0;
00140         }
00141         return;
00142 }
00143 
00144 
00149 void
00150 ldns_radix_free(ldns_radix_t* tree)
00151 {
00152         if (tree) {
00153                 if (tree->root) {
00154                         ldns_radix_traverse_postorder(tree->root,
00155                                 ldns_radix_node_free, NULL);
00156                 }
00157                 LDNS_FREE(tree);
00158         }
00159         return;
00160 }
00161 
00162 
00167 ldns_status
00168 ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len,
00169         void* data)
00170 {
00171         radix_strlen_t pos = 0;
00172         ldns_radix_node_t* add = NULL;
00173         ldns_radix_node_t* prefix = NULL;
00174 
00175         if (!tree || !key || !data) {
00176                 return LDNS_STATUS_NULL;
00177         }
00178         add = ldns_radix_new_node(data, key, len);
00179         if (!add) {
00180                 return LDNS_STATUS_MEM_ERR;
00181         }
00183         if (!ldns_radix_find_prefix(tree, key, len, &prefix, &pos)) {
00185                 assert(tree->root == NULL);
00186                 if (len == 0) {
00191                         tree->root = add;
00192                 } else {
00197                         prefix = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
00198                         if (!prefix) {
00199                                 LDNS_FREE(add);
00200                                 return LDNS_STATUS_MEM_ERR;
00201                         }
00203                         if (!ldns_radix_array_space(prefix, key[0])) {
00204                                 LDNS_FREE(add);
00205                                 LDNS_FREE(prefix->array);
00206                                 LDNS_FREE(prefix);
00207                                 return LDNS_STATUS_MEM_ERR;
00208                         }
00210                         add->parent = prefix;
00211                         add->parent_index = 0;
00212                         prefix->array[0].edge = add;
00213                         if (len > 1) {
00215                                 if (!ldns_radix_prefix_remainder(1, key,
00216                                         len, &prefix->array[0].str,
00217                                         &prefix->array[0].len)) {
00218                                         LDNS_FREE(add);
00219                                         LDNS_FREE(prefix->array);
00220                                         LDNS_FREE(prefix);
00221                                         return LDNS_STATUS_MEM_ERR;
00222                                 }
00223                         }
00224                         tree->root = prefix;
00225                 }
00226         } else if (pos == len) {
00228                 if (prefix->data) {
00229                         /* Element already exists */
00230                         LDNS_FREE(add);
00231                         return LDNS_STATUS_EXISTS_ERR;
00232                 }
00233                 prefix->data = data;
00234                 prefix->key = key;
00235                 prefix->klen = len; /* redundant */
00236         } else {
00238                 uint8_t byte = key[pos];
00239                 assert(pos < len);
00240                 if (byte < prefix->offset ||
00241                         (byte - prefix->offset) >= prefix->len) {
00249                         if (!ldns_radix_array_space(prefix, byte)) {
00250                                 LDNS_FREE(add);
00251                                 return LDNS_STATUS_MEM_ERR;
00252                         }
00253                         assert(byte >= prefix->offset);
00254                         assert((byte - prefix->offset) <= prefix->len);
00255                         byte -= prefix->offset;
00256                         if (pos+1 < len) {
00258                                 if (!ldns_radix_str_create(
00259                                         &prefix->array[byte], key, pos+1,
00260                                         len)) {
00261                                         LDNS_FREE(add);
00262                                         return LDNS_STATUS_MEM_ERR;
00263                                 }
00264                         }
00266                         add->parent = prefix;
00267                         add->parent_index = byte;
00268                         prefix->array[byte].edge = add;
00269                 } else if (prefix->array[byte-prefix->offset].edge == NULL) {
00278                         byte -= prefix->offset;
00279                         if (pos+1 < len) {
00281                                 if (!ldns_radix_str_create(
00282                                         &prefix->array[byte], key, pos+1,
00283                                         len)) {
00284                                         LDNS_FREE(add);
00285                                         return LDNS_STATUS_MEM_ERR;
00286                                 }
00287                         }
00289                         add->parent = prefix;
00290                         add->parent_index = byte;
00291                         prefix->array[byte].edge = add;
00292                 } else {
00297                         if (!ldns_radix_array_split(&prefix->array[byte-(prefix->offset)],
00298                                 key, pos+1, len, add)) {
00299                                 LDNS_FREE(add);
00300                                 return LDNS_STATUS_MEM_ERR;
00301                         }
00302                 }
00303         }
00304 
00305         tree->count ++;
00306         return LDNS_STATUS_OK;
00307 }
00308 
00309 
00314 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
00315 {
00316     ldns_radix_node_t* del = ldns_radix_search(tree, key, len);
00317     void* data = NULL;
00318     if (del) {
00319         tree->count--;
00320         data = del->data;
00321         del->data = NULL;
00322         ldns_radix_del_fix(tree, del);
00323         return data;
00324     }
00325     return NULL;
00326 }
00327 
00328 
00333 ldns_radix_node_t*
00334 ldns_radix_search(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len)
00335 {
00336         ldns_radix_node_t* node = NULL;
00337         radix_strlen_t pos = 0;
00338         uint8_t byte = 0;
00339 
00340         if (!tree || !key) {
00341                 return NULL;
00342         }
00343         node = tree->root;
00344         while (node) {
00345                 if (pos == len) {
00346                         return node->data?node:NULL;
00347                 }
00348                 byte = key[pos];
00349                 if (byte < node->offset) {
00350                         return NULL;
00351                 }
00352                 byte -= node->offset;
00353                 if (byte >= node->len) {
00354                         return NULL;
00355                 }
00356                 pos++;
00357                 if (node->array[byte].len > 0) {
00359                         if (pos + node->array[byte].len > len) {
00360                                 return NULL;
00361                         }
00362                         if (memcmp(&key[pos], node->array[byte].str,
00363                                 node->array[byte].len) != 0) {
00364                                 return NULL;
00365                         }
00366                         pos += node->array[byte].len;
00367                 }
00368                 node = node->array[byte].edge;
00369         }
00370         return NULL;
00371 }
00372 
00373 
00379 int
00380 ldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key,
00381         radix_strlen_t len, ldns_radix_node_t** result)
00382 {
00383         ldns_radix_node_t* node = NULL;
00384         radix_strlen_t pos = 0;
00385         uint8_t byte;
00386         int memcmp_res = 0;
00387 
00388         if (!tree || !tree->root || !key) {
00389                 *result = NULL;
00390                 return 0;
00391         }
00392 
00393         node = tree->root;
00394         while (pos < len) {
00395                 byte = key[pos];
00396                 if (byte < node->offset) {
00401                         ldns_radix_self_or_prev(node, result);
00402                         return 0;
00403                 }
00404                 byte -= node->offset;
00405                 if (byte >= node->len) {
00410                         *result = ldns_radix_last_in_subtree_incl_self(node);
00411                         if (*result == NULL) {
00412                                 *result = ldns_radix_prev(node);
00413                         }
00414                         return 0;
00415                 }
00416                 pos++;
00417                 if (!node->array[byte].edge) {
00422                         *result = ldns_radix_prev_from_index(node, byte);
00423                         if (*result == NULL) {
00424                                 ldns_radix_self_or_prev(node, result);
00425                         }
00426                         return 0;
00427                 }
00428                 if (node->array[byte].len != 0) {
00430                         if (pos + node->array[byte].len > len) {
00432                                 if (memcmp(&key[pos], node->array[byte].str,
00433                                         len-pos) <= 0) {
00435                                         *result = ldns_radix_prev(
00436                                                 node->array[byte].edge);
00437                                 } else {
00439                                         *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
00440                                         if (*result == NULL) {
00441                                                  *result = ldns_radix_prev(node->array[byte].edge);
00442                                         }
00443                                 }
00444                                 return 0;
00445                         }
00446                         memcmp_res = memcmp(&key[pos], node->array[byte].str,
00447                                 node->array[byte].len);
00448                         if (memcmp_res < 0) {
00449                                 *result = ldns_radix_prev(
00450                                         node->array[byte].edge);
00451                                 return 0;
00452                         } else if (memcmp_res > 0) {
00453                                 *result = ldns_radix_last_in_subtree_incl_self(node->array[byte].edge);
00454                                 if (*result == NULL) {
00455                                          *result = ldns_radix_prev(node->array[byte].edge);
00456                                 }
00457                                 return 0;
00458                         }
00459 
00460                         pos += node->array[byte].len;
00461                 }
00462                 node = node->array[byte].edge;
00463         }
00464         if (node->data) {
00466                 *result = node;
00467                 return 1;
00468         }
00470         *result = ldns_radix_prev(node);
00471         return 0;
00472 }
00473 
00474 
00479 ldns_radix_node_t*
00480 ldns_radix_first(ldns_radix_t* tree)
00481 {
00482         ldns_radix_node_t* first = NULL;
00483         if (!tree || !tree->root) {
00484                 return NULL;
00485         }
00486         first = tree->root;
00487         if (first->data) {
00488                 return first;
00489         }
00490         return ldns_radix_next(first);
00491 }
00492 
00493 
00498 ldns_radix_node_t*
00499 ldns_radix_last(ldns_radix_t* tree)
00500 {
00501         if (!tree || !tree->root) {
00502                 return NULL;
00503         }
00504         return ldns_radix_last_in_subtree_incl_self(tree->root);
00505 }
00506 
00507 
00512 ldns_radix_node_t*
00513 ldns_radix_next(ldns_radix_node_t* node)
00514 {
00515         if (!node) {
00516                 return NULL;
00517         }
00518         if (node->len) {
00520                 ldns_radix_node_t* next = ldns_radix_next_in_subtree(node);
00521                 if (next) {
00522                         return next;
00523                 }
00524         }
00526         while (node->parent) {
00527                 uint8_t index = node->parent_index;
00528                 node = node->parent;
00529                 index++;
00530                 for (; index < node->len; index++) {
00531                         if (node->array[index].edge) {
00532                                 ldns_radix_node_t* next;
00534                                 if (node->array[index].edge->data) {
00535                                         return node->array[index].edge;
00536                                 }
00538                                 next = ldns_radix_next_in_subtree(node);
00539                                 if (next) {
00540                                         return next;
00541                                 }
00542                         }
00543                 }
00544         }
00545         return NULL;
00546 }
00547 
00548 
00553 ldns_radix_node_t*
00554 ldns_radix_prev(ldns_radix_node_t* node)
00555 {
00556         if (!node) {
00557                 return NULL;
00558         }
00559 
00561         while (node->parent) {
00562                 uint8_t index = node->parent_index;
00563                 ldns_radix_node_t* prev;
00564                 node = node->parent;
00565                 assert(node->len > 0);
00566                 prev = ldns_radix_prev_from_index(node, index);
00567                 if (prev) {
00568                         return prev;
00569                 }
00570                 if (node->data) {
00571                         return node;
00572                 }
00573         }
00574         return NULL;
00575 }
00576 
00577 
00582 static void
00583 ldns_radix_node_print(FILE* fd, ldns_radix_node_t* node,
00584         uint8_t i, uint8_t* str, radix_strlen_t len, unsigned d)
00585 {
00586         uint8_t j;
00587         if (!node) {
00588                 return;
00589         }
00590         for (j = 0; j < d; j++) {
00591                 fprintf(fd, "--");
00592         }
00593         if (str) {
00594                 radix_strlen_t l;
00595                 fprintf(fd, "| [%u+", (unsigned) i);
00596                 for (l=0; l < len; l++) {
00597                         fprintf(fd, "%c", (char) str[l]);
00598                 }
00599                 fprintf(fd, "]%u", (unsigned) len);
00600         } else {
00601                 fprintf(fd, "| [%u]", (unsigned) i);
00602         }
00603 
00604         if (node->data) {
00605                 fprintf(fd, " %s", (char*) node->data);
00606         }
00607         fprintf(fd, "\n");
00608 
00609         for (j = 0; j < node->len; j++) {
00610                 if (node->array[j].edge) {
00611                         ldns_radix_node_print(fd, node->array[j].edge, j,
00612                                 node->array[j].str, node->array[j].len, d+1);
00613                 }
00614         }
00615         return;
00616 }
00617 
00618 
00623 void
00624 ldns_radix_printf(FILE* fd, ldns_radix_t* tree)
00625 {
00626         if (!fd || !tree) {
00627                 return;
00628         }
00629         if (!tree->root) {
00630                 fprintf(fd, "; empty radix tree\n");
00631                 return;
00632         }
00633         ldns_radix_node_print(fd, tree->root, 0, NULL, 0, 0);
00634         return;
00635 }
00636 
00637 
00642 ldns_status
00643 ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2)
00644 {
00645         ldns_radix_node_t* cur_node, *next_node;
00646         ldns_status status;
00647         if (!tree2 || !tree2->root) {
00648                 return LDNS_STATUS_OK;
00649         }
00652         cur_node = ldns_radix_first(tree2);
00653         while (cur_node) {
00654                 status = LDNS_STATUS_NO_DATA;
00656                 if (cur_node->data) {
00657                         status = ldns_radix_insert(tree1, cur_node->key,
00658                                 cur_node->klen, cur_node->data);
00660                         if (status != LDNS_STATUS_OK &&
00661                             status != LDNS_STATUS_EXISTS_ERR) {
00662                                 return status;
00663                         }
00664                 }
00665                 next_node = ldns_radix_next(cur_node);
00666                 if (status == LDNS_STATUS_OK) {
00667                         (void) ldns_radix_delete(tree2, cur_node->key,
00668                                 cur_node->klen);
00669                 }
00670                 cur_node = next_node;
00671         }
00672 
00673         return LDNS_STATUS_OK;
00674 }
00675 
00676 
00681 ldns_status
00682 ldns_radix_split(ldns_radix_t* tree1, size_t num, ldns_radix_t** tree2)
00683 {
00684         size_t count = 0;
00685         ldns_radix_node_t* cur_node;
00686         ldns_status status = LDNS_STATUS_OK;
00687         if (!tree1 || !tree1->root || num == 0) {
00688                 return LDNS_STATUS_OK;
00689         }
00690         if (!tree2) {
00691                 return LDNS_STATUS_NULL;
00692         }
00693         if (!*tree2) {
00694                 *tree2 = ldns_radix_create();
00695                 if (!*tree2) {
00696                         return LDNS_STATUS_MEM_ERR;
00697                 }
00698         }
00699         cur_node = ldns_radix_first(tree1);
00700         while (count < num && cur_node) {
00701                 if (cur_node->data) {
00703                         uint8_t* cur_key = cur_node->key;
00704                         radix_strlen_t cur_len = cur_node->klen;
00705                         void* cur_data = ldns_radix_delete(tree1, cur_key,
00706                                 cur_len);
00708                         if (!cur_data) {
00709                                 return LDNS_STATUS_NO_DATA;
00710                         }
00711                         status = ldns_radix_insert(*tree2, cur_key, cur_len,
00712                                 cur_data);
00713                         if (status != LDNS_STATUS_OK &&
00714                             status != LDNS_STATUS_EXISTS_ERR) {
00715                                 return status;
00716                         }
00717 /*
00718                         if (status == LDNS_STATUS_OK) {
00719                                 cur_node->key = NULL;
00720                                 cur_node->klen = 0;
00721                         }
00722 */
00724                         count++;
00725                         cur_node = ldns_radix_first(tree1);
00726                 } else {
00727                         cur_node = ldns_radix_next(cur_node);
00728                 }
00729         }
00730         return LDNS_STATUS_OK;
00731 }
00732 
00733 
00739 void
00740 ldns_radix_traverse_postorder(ldns_radix_node_t* node,
00741         void (*func)(ldns_radix_node_t*, void*), void* arg)
00742 {
00743         uint8_t i;
00744         if (!node) {
00745                 return;
00746         }
00747         for (i=0; i < node->len; i++) {
00748                 ldns_radix_traverse_postorder(node->array[i].edge,
00749                         func, arg);
00750         }
00752         (*func)(node, arg);
00753         return;
00754 }
00755 
00756 
00772 static int
00773 ldns_radix_find_prefix(ldns_radix_t* tree, uint8_t* key,
00774         radix_strlen_t len, ldns_radix_node_t** result, radix_strlen_t* respos)
00775 {
00777         ldns_radix_node_t* n = tree->root;
00778         radix_strlen_t pos = 0;
00779         uint8_t byte;
00780         *respos = 0;
00781         *result = n;
00782         if (!n) {
00784                 return 0;
00785         }
00787         while (n) {
00788                 if (pos == len) {
00790                         return 1;
00791                 }
00792                 byte = key[pos];
00793                 if (byte < n->offset) {
00795                         return 1;
00796                 }
00797                 byte -= n->offset;
00798                 if (byte >= n->len) {
00800                         return 1;
00801                 }
00803                 pos++;
00804                 if (n->array[byte].len != 0) {
00806                         if (pos + n->array[byte].len > len) {
00807                                 return 1; /* no match at child node */
00808                         }
00809                         if (memcmp(&key[pos], n->array[byte].str,
00810                                 n->array[byte].len) != 0) {
00811                                 return 1; /* no match at child node */
00812                         }
00813                         pos += n->array[byte].len;
00814                 }
00816                 n = n->array[byte].edge;
00817                 if (!n) {
00818                         return 1;
00819                 }
00821                 *respos = pos;
00822                 *result = n;
00823         }
00825         return 1;
00826 }
00827 
00828 
00836 static int
00837 ldns_radix_array_space(ldns_radix_node_t* node, uint8_t byte)
00838 {
00840         if (!node->array) {
00841                 assert(node->capacity == 0);
00843                 node->array = LDNS_MALLOC(ldns_radix_array_t);
00844                 if (!node->array) {
00845                         return 0;
00846                 }
00847                 memset(&node->array[0], 0, sizeof(ldns_radix_array_t));
00848                 node->len = 1;
00849                 node->capacity = 1;
00850                 node->offset = byte;
00851                 return 1;
00852         }
00854         assert(node->array != NULL);
00855         assert(node->capacity > 0);
00856 
00857         if (node->len == 0) {
00859                 node->len = 1;
00860                 node->offset = byte;
00861         } else if (byte < node->offset) {
00863                 uint8_t index;
00864                 uint16_t need = node->offset - byte;
00866                 if (node->len + need > node->capacity) {
00868                         if (!ldns_radix_array_grow(node,
00869                                 (unsigned) (node->len + need))) {
00870                                 return 0; /* failed to grow array */
00871                         }
00872                 }
00874                 memmove(&node->array[need], &node->array[0],
00875                         node->len*sizeof(ldns_radix_array_t));
00877                 for (index = 0; index < node->len; index++) {
00878                         if (node->array[index+need].edge) {
00879                                 node->array[index+need].edge->parent_index =
00880                                         index + need;
00881                         }
00882                 }
00884                 memset(&node->array[0], 0, need*sizeof(ldns_radix_array_t));
00885                 node->len += need;
00886                 node->offset = byte;
00887         } else if (byte - node->offset >= node->len) {
00889                 uint16_t need = (byte - node->offset) - node->len + 1;
00891                 if (node->len + need > node->capacity) {
00893                         if (!ldns_radix_array_grow(node,
00894                                 (unsigned) (node->len + need))) {
00895                                 return 0; /* failed to grow array */
00896                         }
00897                 }
00899                 memset(&node->array[node->len], 0,
00900                         need*sizeof(ldns_radix_array_t));
00901                 node->len += need;
00902         }
00903         return 1;
00904 }
00905 
00906 
00915 static int
00916 ldns_radix_array_grow(ldns_radix_node_t* node, unsigned need)
00917 {
00918         unsigned size = ((unsigned)node->capacity)*2;
00919         ldns_radix_array_t* a = NULL;
00920         if (need > size) {
00921                 size = need;
00922         }
00923         if (size > 256) {
00924                 size = 256;
00925         }
00926         a = LDNS_XMALLOC(ldns_radix_array_t, size);
00927         if (!a) {
00928                 return 0;
00929         }
00930         assert(node->len <= node->capacity);
00931         assert(node->capacity < size);
00932         memcpy(&a[0], &node->array[0], node->len*sizeof(ldns_radix_array_t));
00933         LDNS_FREE(node->array);
00934         node->array = a;
00935         node->capacity = size;
00936         return 1;
00937 }
00938 
00939 
00949 static int
00950 ldns_radix_str_create(ldns_radix_array_t* array, uint8_t* key,
00951         radix_strlen_t pos, radix_strlen_t len)
00952 {
00953         array->str = LDNS_XMALLOC(uint8_t, (len-pos));
00954         if (!array->str) {
00955                 return 0;
00956         }
00957         memmove(array->str, key+pos, len-pos);
00958         array->len = (len-pos);
00959         return 1;
00960 }
00961 
00962 
00973 static int
00974 ldns_radix_prefix_remainder(radix_strlen_t prefix_len,
00975         uint8_t* longer_str, radix_strlen_t longer_len,
00976         uint8_t** split_str, radix_strlen_t* split_len)
00977 {
00978         *split_len = longer_len - prefix_len;
00979         *split_str = LDNS_XMALLOC(uint8_t, (*split_len));
00980         if (!*split_str) {
00981                 return 0;
00982         }
00983         memmove(*split_str, longer_str+prefix_len, longer_len-prefix_len);
00984         return 1;
00985 }
00986 
00987 
00998 static int
00999 ldns_radix_array_split(ldns_radix_array_t* array, uint8_t* key,
01000         radix_strlen_t pos, radix_strlen_t len, ldns_radix_node_t* add)
01001 {
01002         uint8_t* str_to_add = key + pos;
01003         radix_strlen_t strlen_to_add = len - pos;
01004 
01005         if (ldns_radix_str_is_prefix(str_to_add, strlen_to_add,
01006                 array->str, array->len)) {
01008                 uint8_t* split_str = NULL, *dup_str = NULL;
01009                 radix_strlen_t split_len = 0;
01018                 assert(strlen_to_add < array->len);
01020                 if (array->len - strlen_to_add > 1) {
01021                         if (!ldns_radix_prefix_remainder(strlen_to_add+1,
01022                                 array->str, array->len, &split_str,
01023                                 &split_len)) {
01024                                 return 0;
01025                         }
01026                 }
01028                 if (strlen_to_add != 0) {
01029                         dup_str = LDNS_XMALLOC(uint8_t, strlen_to_add);
01030                         if (!dup_str) {
01031                                 LDNS_FREE(split_str);
01032                                 return 0;
01033                         }
01034                         memcpy(dup_str, str_to_add, strlen_to_add);
01035                 }
01037                 if (!ldns_radix_array_space(add,
01038                         array->str[strlen_to_add])) {
01039                         LDNS_FREE(split_str);
01040                         LDNS_FREE(dup_str);
01041                         return 0;
01042                 }
01047                 add->parent = array->edge->parent;
01048                 add->parent_index = array->edge->parent_index;
01049                 add->array[0].edge = array->edge;
01050                 add->array[0].str = split_str;
01051                 add->array[0].len = split_len;
01052                 array->edge->parent = add;
01053                 array->edge->parent_index = 0;
01054                 LDNS_FREE(array->str);
01055                 array->edge = add;
01056                 array->str = dup_str;
01057                 array->len = strlen_to_add;
01058         } else if (ldns_radix_str_is_prefix(array->str, array->len,
01059                 str_to_add, strlen_to_add)) {
01070                 uint8_t* split_str = NULL;
01071                 radix_strlen_t split_len = 0;
01072                 assert(array->len < strlen_to_add);
01073                 if (strlen_to_add - array->len > 1) {
01074                         if (!ldns_radix_prefix_remainder(array->len+1,
01075                                 str_to_add, strlen_to_add, &split_str,
01076                                 &split_len)) {
01077                                 return 0;
01078                         }
01079                 }
01081                 if (!ldns_radix_array_space(array->edge,
01082                         str_to_add[array->len])) {
01083                         LDNS_FREE(split_str);
01084                         return 0;
01085                 }
01089                 add->parent = array->edge;
01090                 add->parent_index = str_to_add[array->len] -
01091                                                         array->edge->offset;
01092                 array->edge->array[add->parent_index].edge = add;
01093                 array->edge->array[add->parent_index].str = split_str;
01094                 array->edge->array[add->parent_index].len = split_len;
01095         } else {
01108                 ldns_radix_node_t* common = NULL;
01109                 uint8_t* common_str = NULL, *s1 = NULL, *s2 = NULL;
01110                 radix_strlen_t common_len = 0, l1 = 0, l2 = 0;
01111                 common_len = ldns_radix_str_common(array->str, array->len,
01112                         str_to_add, strlen_to_add);
01113                 assert(common_len < array->len);
01114                 assert(common_len < strlen_to_add);
01116                 common = ldns_radix_new_node(NULL, (uint8_t*)"", 0);
01117                 if (!common) {
01118                         return 0;
01119                 }
01120                 if (array->len - common_len > 1) {
01121                         if (!ldns_radix_prefix_remainder(common_len+1,
01122                                 array->str, array->len, &s1, &l1)) {
01123                                 return 0;
01124                         }
01125                 }
01126                 if (strlen_to_add - common_len > 1) {
01127                         if (!ldns_radix_prefix_remainder(common_len+1,
01128                                 str_to_add, strlen_to_add, &s2, &l2)) {
01129                                 return 0;
01130                         }
01131                 }
01133                 if (common_len > 0) {
01134                         common_str = LDNS_XMALLOC(uint8_t, common_len);
01135                         if (!common_str) {
01136                                 LDNS_FREE(common);
01137                                 LDNS_FREE(s1);
01138                                 LDNS_FREE(s2);
01139                                 return 0;
01140                         }
01141                         memcpy(common_str, str_to_add, common_len);
01142                 }
01144                 if (!ldns_radix_array_space(common, array->str[common_len]) ||
01145                     !ldns_radix_array_space(common, str_to_add[common_len])) {
01146                         LDNS_FREE(common->array);
01147                         LDNS_FREE(common);
01148                         LDNS_FREE(common_str);
01149                         LDNS_FREE(s1);
01150                         LDNS_FREE(s2);
01151                         return 0;
01152                 }
01157                 common->parent = array->edge->parent;
01158                 common->parent_index = array->edge->parent_index;
01159                 array->edge->parent = common;
01160                 array->edge->parent_index = array->str[common_len] -
01161                                                                 common->offset;
01162                 add->parent = common;
01163                 add->parent_index = str_to_add[common_len] - common->offset;
01164                 common->array[array->edge->parent_index].edge = array->edge;
01165                 common->array[array->edge->parent_index].str = s1;
01166                 common->array[array->edge->parent_index].len = l1;
01167                 common->array[add->parent_index].edge = add;
01168                 common->array[add->parent_index].str = s2;
01169                 common->array[add->parent_index].len = l2;
01170                 LDNS_FREE(array->str);
01171                 array->edge = common;
01172                 array->str = common_str;
01173                 array->len = common_len;
01174         }
01175         return 1;
01176 }
01177 
01178 
01188 static int
01189 ldns_radix_str_is_prefix(uint8_t* str1, radix_strlen_t len1,
01190         uint8_t* str2, radix_strlen_t len2)
01191 {
01192         if (len1 == 0) {
01193                 return 1; /* empty prefix is also a prefix */
01194         }
01195         if (len1 > len2) {
01196                 return 0; /* len1 is longer so str1 cannot be a prefix */
01197         }
01198         return (memcmp(str1, str2, len1) == 0);
01199 }
01200 
01201 
01211 static radix_strlen_t
01212 ldns_radix_str_common(uint8_t* str1, radix_strlen_t len1,
01213         uint8_t* str2, radix_strlen_t len2)
01214 {
01215         radix_strlen_t i, max = (len1<len2)?len1:len2;
01216         for (i=0; i<max; i++) {
01217                 if (str1[i] != str2[i]) {
01218                         return i;
01219                 }
01220         }
01221         return max;
01222 }
01223 
01224 
01231 static ldns_radix_node_t*
01232 ldns_radix_next_in_subtree(ldns_radix_node_t* node)
01233 {
01234         uint16_t i;
01235         ldns_radix_node_t* next;
01237         for (i = 0; i < node->len; i++) {
01238                 if (node->array[i].edge) {
01240                         if (node->array[i].edge->data) {
01241                                 return node->array[i].edge;
01242                         }
01244                         next = ldns_radix_next_in_subtree(node->array[i].edge);
01245                         if (next) {
01246                                 return next;
01247                         }
01248                 }
01249         }
01250         return NULL;
01251 }
01252 
01253 
01261 static ldns_radix_node_t*
01262 ldns_radix_prev_from_index(ldns_radix_node_t* node, uint8_t index)
01263 {
01264         uint8_t i = index;
01265         while (i > 0) {
01266                 i--;
01267                 if (node->array[i].edge) {
01268                         ldns_radix_node_t* prev =
01269                                 ldns_radix_last_in_subtree_incl_self(node);
01270                         if (prev) {
01271                                 return prev;
01272                         }
01273                 }
01274         }
01275         return NULL;
01276 }
01277 
01278 
01285 static ldns_radix_node_t*
01286 ldns_radix_last_in_subtree_incl_self(ldns_radix_node_t* node)
01287 {
01288         ldns_radix_node_t* last = ldns_radix_last_in_subtree(node);
01289         if (last) {
01290                 return last;
01291         } else if (node->data) {
01292                 return node;
01293         }
01294         return NULL;
01295 }
01296 
01297 
01304 static ldns_radix_node_t*
01305 ldns_radix_last_in_subtree(ldns_radix_node_t* node)
01306 {
01307         int i;
01309         for (i=(int)(node->len)-1; i >= 0; i--) {
01310                 if (node->array[i].edge) {
01312                         if (node->array[i].edge->len > 0) {
01313                                 ldns_radix_node_t* last =
01314                                         ldns_radix_last_in_subtree(
01315                                         node->array[i].edge);
01316                                 if (last) {
01317                                         return last;
01318                                 }
01319                         }
01321                         if (node->array[i].edge->data) {
01322                                 return node->array[i].edge;
01323                         }
01324                 }
01325         }
01326         return NULL;
01327 }
01328 
01329 
01336 static void
01337 ldns_radix_del_fix(ldns_radix_t* tree, ldns_radix_node_t* node)
01338 {
01339         while (node) {
01340                 if (node->data) {
01342                         return;
01343                 } else if (node->len == 1 && node->parent) {
01345                         ldns_radix_cleanup_onechild(node);
01346                         return;
01347                 } else if (node->len == 0) {
01349                         ldns_radix_node_t* parent = node->parent;
01350                         if (!parent) {
01352                                 ldns_radix_node_free(node, NULL);
01353                                 tree->root = NULL;
01354                                 return;
01355                         }
01357                         ldns_radix_cleanup_leaf(node);
01358                         node = parent;
01359                 } else {
01364                         return;
01365                 }
01366         }
01368         return;
01369 }
01370 
01371 
01377 static void
01378 ldns_radix_cleanup_onechild(ldns_radix_node_t* node)
01379 {
01380         uint8_t* join_str;
01381         radix_strlen_t join_len;
01382         uint8_t parent_index = node->parent_index;
01383         ldns_radix_node_t* child = node->array[0].edge;
01384         ldns_radix_node_t* parent = node->parent;
01385 
01387         assert(parent_index < parent->len);
01388         join_len = parent->array[parent_index].len + node->array[0].len + 1;
01389 
01390         join_str = LDNS_XMALLOC(uint8_t, join_len);
01391         if (!join_str) {
01397                 return;
01398         }
01399 
01400         memcpy(join_str, parent->array[parent_index].str,
01401                 parent->array[parent_index].len);
01402         join_str[parent->array[parent_index].len] = child->parent_index +
01403                 node->offset;
01404         memmove(join_str + parent->array[parent_index].len+1,
01405                 node->array[0].str, node->array[0].len);
01406 
01407         LDNS_FREE(parent->array[parent_index].str);
01408         parent->array[parent_index].str = join_str;
01409         parent->array[parent_index].len = join_len;
01410         parent->array[parent_index].edge = child;
01411         child->parent = parent;
01412         child->parent_index = parent_index;
01413         ldns_radix_node_free(node, NULL);
01414         return;
01415 }
01416 
01417 
01423 static void
01424 ldns_radix_cleanup_leaf(ldns_radix_node_t* node)
01425 {
01426         uint8_t parent_index = node->parent_index;
01427         ldns_radix_node_t* parent = node->parent;
01429         assert(parent_index < parent->len);
01430         ldns_radix_node_free(node, NULL);
01431         LDNS_FREE(parent->array[parent_index].str);
01432         parent->array[parent_index].str = NULL;
01433         parent->array[parent_index].len = 0;
01434         parent->array[parent_index].edge = NULL;
01436         if (parent->len == 1) {
01437                 ldns_radix_node_array_free(parent);
01438         } else if (parent_index == 0) {
01439                 ldns_radix_node_array_free_front(parent);
01440         } else {
01441                 ldns_radix_node_array_free_end(parent);
01442         }
01443         return;
01444 }
01445 
01446 
01453 static void
01454 ldns_radix_node_free(ldns_radix_node_t* node, void* arg)
01455 {
01456         uint16_t i;
01457         (void) arg;
01458         if (!node) {
01459                 return;
01460         }
01461         for (i=0; i < node->len; i++) {
01462                 LDNS_FREE(node->array[i].str);
01463         }
01464         node->key = NULL;
01465         node->klen = 0;
01466         LDNS_FREE(node->array);
01467         LDNS_FREE(node);
01468         return;
01469 }
01470 
01471 
01477 static void
01478 ldns_radix_node_array_free(ldns_radix_node_t* node)
01479 {
01480         node->offset = 0;
01481         node->len = 0;
01482         LDNS_FREE(node->array);
01483         node->array = NULL;
01484         node->capacity = 0;
01485         return;
01486 }
01487 
01488 
01494 static void
01495 ldns_radix_node_array_free_front(ldns_radix_node_t* node)
01496 {
01497         uint16_t i, n = 0;
01499         while (n < node->len && node->array[n].edge == NULL) {
01500                 n++;
01501         }
01502         if (n == 0) {
01503                 return;
01504         }
01505         if (n == node->len) {
01506                 ldns_radix_node_array_free(node);
01507                 return;
01508         }
01509         assert(n < node->len);
01510         assert((int) n <= (255 - (int) node->offset));
01511         memmove(&node->array[0], &node->array[n],
01512                 (node->len - n)*sizeof(ldns_radix_array_t));
01513         node->offset += n;
01514         node->len -= n;
01515         for (i=0; i < node->len; i++) {
01516                 if (node->array[i].edge) {
01517                         node->array[i].edge->parent_index = i;
01518                 }
01519         }
01520         ldns_radix_array_reduce(node);
01521         return;
01522 }
01523 
01524 
01530 static void
01531 ldns_radix_node_array_free_end(ldns_radix_node_t* node)
01532 {
01533         uint16_t n = 0;
01535         while (n < node->len && node->array[node->len-1-n].edge == NULL) {
01536                 n++;
01537         }
01538         if (n == 0) {
01539                 return;
01540         }
01541         if (n == node->len) {
01542                 ldns_radix_node_array_free(node);
01543                 return;
01544         }
01545         assert(n < node->len);
01546         node->len -= n;
01547         ldns_radix_array_reduce(node);
01548         return;
01549 }
01550 
01551 
01557 static void
01558 ldns_radix_array_reduce(ldns_radix_node_t* node)
01559 {
01560         if (node->len <= node->capacity/2 && node->len != node->capacity) {
01561                 ldns_radix_array_t* a = LDNS_XMALLOC(ldns_radix_array_t,
01562                                                                 node->len);
01563                 if (!a) {
01564                         return;
01565                 }
01566                 memcpy(a, node->array, sizeof(ldns_radix_array_t)*node->len);
01567                 LDNS_FREE(node->array);
01568                 node->array = a;
01569                 node->capacity = node->len;
01570         }
01571         return;
01572 }
01573 
01574 
01581 static void
01582 ldns_radix_self_or_prev(ldns_radix_node_t* node, ldns_radix_node_t** result)
01583 {
01584         if (node->data) {
01585                 *result = node;
01586         } else {
01587                 *result = ldns_radix_prev(node);
01588         }
01589         return;
01590 }