00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
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
00230 LDNS_FREE(add);
00231 return LDNS_STATUS_EXISTS_ERR;
00232 }
00233 prefix->data = data;
00234 prefix->key = key;
00235 prefix->klen = len;
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
00719
00720
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;
00808 }
00809 if (memcmp(&key[pos], n->array[byte].str,
00810 n->array[byte].len) != 0) {
00811 return 1;
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;
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;
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;
01194 }
01195 if (len1 > len2) {
01196 return 0;
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 }