diff options
Diffstat (limited to 'src/libknot/zone/zone-tree.c')
| -rw-r--r-- | src/libknot/zone/zone-tree.c | 503 |
1 files changed, 174 insertions, 329 deletions
diff --git a/src/libknot/zone/zone-tree.c b/src/libknot/zone/zone-tree.c index 1d7991e..27cdf5f 100644 --- a/src/libknot/zone/zone-tree.c +++ b/src/libknot/zone/zone-tree.c @@ -14,192 +14,104 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#include <config.h> #include <assert.h> #include <stdlib.h> #include <stdio.h> -#include "zone-tree.h" #include "zone/node.h" #include "util/debug.h" +#include "common/hattrie/hat-trie.h" /*----------------------------------------------------------------------------*/ /* Non-API functions */ /*----------------------------------------------------------------------------*/ -// AVL tree functions -TREE_DEFINE(knot_zone_tree_node, avl); - -/*----------------------------------------------------------------------------*/ - -static int knot_zone_tree_node_compare(knot_zone_tree_node_t *node1, - knot_zone_tree_node_t *node2) -{ - assert(node1 != NULL); - assert(node2 != NULL); - assert(node1->node != NULL); - assert(node2->node != NULL); - assert(knot_node_owner(node1->node) != NULL); - assert(knot_node_owner(node2->node) != NULL); - - return knot_node_compare(node1->node, node2->node); -} - -/*----------------------------------------------------------------------------*/ - -static void knot_zone_tree_delete_subtree(knot_zone_tree_node_t *root) -{ - if (root == NULL) { - return; +#define DNAME_LFT_MAXLEN 255 /* maximum lookup format length */ + +/*! + * \brief Convert domain name from wire to lookup format. + * + * Formats names from rightmost label to the leftmost, separated by the lowest + * possible character (\x00). Sorting such formatted names also gives + * correct canonical order (for NSEC/NSEC3). + * + * Example: + * Name: lake.example.com. Wire: \x04lake\x07example\x03com\x00 + * Lookup format com\x00example\x00lake\x00 + * + * Maximum length of such a domain name is DNAME_LFT_MAXLEN characters. + * + * \param dst Memory to store converted name into. + * \param maxlen Maximum memory length. + * \param src Source domain name. + * + * \retval KNOT_EOK if successful + * \retval KNOT_ESPACE when not enough memory. + * \retval KNOT_EINVAL on invalid parameters + */ +static int dname_lf(uint8_t *dst, const knot_dname_t *src, size_t maxlen) { + if (src->size > maxlen) + return KNOT_ESPACE; + *dst = (uint8_t)src->size; + /* need to save last \x00 for root dname */ + if (*dst > 1) + *dst -= 1; + *++dst = '\0'; + uint8_t* l = src->name; + uint8_t lstack[DNAME_LFT_MAXLEN]; + uint8_t *sp = lstack; + while(*l != 0) { /* build label stack */ + *sp++ = (l - src->name); + l += 1 + *l; + } + while(sp != lstack) { /* consume stack */ + l = src->name + *--sp; /* fetch rightmost label */ + memcpy(dst, l+1, *l); /* write label */ + dst += *l; + *dst++ = '\0'; /* label separator */ } - - knot_zone_tree_delete_subtree(root->avl.avl_left); - knot_zone_tree_delete_subtree(root->avl.avl_right); - free(root); + return KNOT_EOK; } -/*----------------------------------------------------------------------------*/ - -static int knot_zone_tree_copy_node(knot_zone_tree_node_t *from, - knot_zone_tree_node_t **to) +static value_t knot_zone_node_copy(value_t v) { - if (from == NULL) { - *to = NULL; - return KNOT_EOK; - } - - *to = (knot_zone_tree_node_t *) - malloc(sizeof(knot_zone_tree_node_t)); - if (*to == NULL) { - return KNOT_ENOMEM; - } - - (*to)->node = from->node; - (*to)->avl.avl_height = from->avl.avl_height; - - int ret = knot_zone_tree_copy_node(from->avl.avl_left, - &(*to)->avl.avl_left); - if (ret != KNOT_EOK) { - return ret; - } - - ret = knot_zone_tree_copy_node(from->avl.avl_right, - &(*to)->avl.avl_right); - if (ret != KNOT_EOK) { - knot_zone_tree_delete_subtree((*to)->avl.avl_left); - (*to)->avl.avl_left = NULL; - free(*to); - *to = NULL; - return ret; - } - - return KNOT_EOK; + return v; } -/*----------------------------------------------------------------------------*/ - -static void knot_zone_tree_free_node(knot_zone_tree_node_t *node, - int free_data) +static value_t knot_zone_node_deep_copy(value_t v) { - if (node == NULL) { - return; - } - - knot_zone_tree_free_node(node->avl.avl_left, free_data); - - knot_zone_tree_free_node(node->avl.avl_right, free_data); - - if (free_data) { - knot_node_free(&node->node); - } - - free(node); + knot_node_t *n = NULL; + knot_node_shallow_copy((knot_node_t *)v, &n); + knot_node_set_new_node((knot_node_t *)v, n); + return (value_t)n; } /*----------------------------------------------------------------------------*/ +/* API functions */ +/*----------------------------------------------------------------------------*/ -static int knot_zone_tree_deep_copy_node(knot_zone_tree_node_t *from, - knot_zone_tree_node_t **to) +knot_zone_tree_t* knot_zone_tree_create() { - if (from == NULL) { - *to = NULL; - return KNOT_EOK; - } - - *to = (knot_zone_tree_node_t *)malloc(sizeof(knot_zone_tree_node_t)); - if (*to == NULL) { - return KNOT_ENOMEM; - } - - int ret = knot_node_shallow_copy(from->node, &(*to)->node); - - if (ret != KNOT_EOK) { - dbg_zone_verb("Failed to do shallow copy of node.\n"); - free(*to); - return ret; - } - - (*to)->avl.avl_height = from->avl.avl_height; - - ret = knot_zone_tree_deep_copy_node(from->avl.avl_left, - &(*to)->avl.avl_left); - if (ret != KNOT_EOK) { - dbg_zone_verb("Failed to do shallow copy of left subtree.\n"); - return ret; - } - - ret = knot_zone_tree_deep_copy_node(from->avl.avl_right, - &(*to)->avl.avl_right); - if (ret != KNOT_EOK) { - dbg_zone_verb("Failed to do shallow copy of right subtree.\n"); - knot_zone_tree_free_node((*to)->avl.avl_left, 1); - (*to)->avl.avl_left = NULL; - knot_node_free(&(*to)->node); - free(*to); - *to = NULL; - return ret; - } - - knot_node_set_new_node(from->node, (*to)->node); - - return KNOT_EOK; + return hattrie_create(); } /*----------------------------------------------------------------------------*/ -/* API functions */ -/*----------------------------------------------------------------------------*/ -int knot_zone_tree_init(knot_zone_tree_t *tree) +size_t knot_zone_tree_weight(knot_zone_tree_t* tree) { - if (tree == NULL) { - return KNOT_EINVAL; - } - - TREE_INIT(tree, knot_zone_tree_node_compare); - return KNOT_EOK; + return hattrie_weight(tree); } /*----------------------------------------------------------------------------*/ int knot_zone_tree_insert(knot_zone_tree_t *tree, knot_node_t *node) { - if (tree == NULL || node == NULL) { - return KNOT_EINVAL; - } - - knot_zone_tree_node_t *znode = (knot_zone_tree_node_t *)malloc( - sizeof(knot_zone_tree_node_t)); - if (znode == NULL) { - return KNOT_ENOMEM; - } - - znode->node = node; - znode->avl.avl_left = NULL; - znode->avl.avl_right = NULL; - znode->avl.avl_height = 0; - - /*! \todo How to know if this was successful? */ - TREE_INSERT(tree, knot_zone_tree_node, avl, znode); + assert(tree && node && node->owner); + uint8_t lf[DNAME_LFT_MAXLEN]; + dname_lf(lf, node->owner, sizeof(lf)); + *hattrie_get(tree, (char*)lf+1, *lf) = node; return KNOT_EOK; } @@ -211,11 +123,8 @@ int knot_zone_tree_find(knot_zone_tree_t *tree, const knot_dname_t *owner, if (tree == NULL || owner == NULL || found == NULL) { return KNOT_EINVAL; } - - knot_node_t *f = NULL; - int ret = knot_zone_tree_get(tree, owner, &f); - *found = f; - return ret; + + return knot_zone_tree_get(tree, owner, (knot_node_t **)found); } /*----------------------------------------------------------------------------*/ @@ -227,32 +136,14 @@ int knot_zone_tree_get(knot_zone_tree_t *tree, const knot_dname_t *owner, return KNOT_EINVAL; } - *found = NULL; - - // create dummy node to use for lookup - knot_zone_tree_node_t *tmp = (knot_zone_tree_node_t *)malloc( - sizeof(knot_zone_tree_node_t)); - if (tmp == NULL) { - return KNOT_ENOMEM; - } - - // create dummy data node to use for lookup - knot_node_t *tmp_data = knot_node_new( - (knot_dname_t *)owner, NULL, 0); - if (tmp_data == NULL) { - free(tmp); - return KNOT_ENOMEM; - } - tmp->node = tmp_data; - - knot_zone_tree_node_t *n = TREE_FIND(tree, knot_zone_tree_node, avl, - tmp); - - knot_node_free(&tmp_data); - free(tmp); + uint8_t lf[DNAME_LFT_MAXLEN]; + dname_lf(lf, owner, sizeof(lf)); - if (n != NULL) { - *found = n->node; + value_t *val = hattrie_tryget(tree, (char*)lf+1, *lf); + if (val == NULL) { + *found = NULL; + } else { + *found = (knot_node_t*)(*val); } return KNOT_EOK; @@ -268,7 +159,7 @@ int knot_zone_tree_find_less_or_equal(knot_zone_tree_t *tree, if (tree == NULL || owner == NULL || found == NULL || previous == NULL) { return KNOT_EINVAL; } - + knot_node_t *f = NULL, *p = NULL; int ret = knot_zone_tree_get_less_or_equal(tree, owner, &f, &p); @@ -290,85 +181,55 @@ int knot_zone_tree_get_less_or_equal(knot_zone_tree_t *tree, return KNOT_EINVAL; } - knot_zone_tree_node_t *f = NULL, *prev = NULL; - - // create dummy node to use for lookup - knot_zone_tree_node_t *tmp = (knot_zone_tree_node_t *)malloc( - sizeof(knot_zone_tree_node_t)); - if (tmp == NULL) { - return KNOT_ENOMEM; + uint8_t lf[DNAME_LFT_MAXLEN]; + dname_lf(lf, owner, sizeof(lf)); + + value_t *fval = NULL; + int ret = hattrie_find_leq(tree, (char*)lf+1, *lf, &fval); + if (fval) *found = (knot_node_t *)(*fval); + int exact_match = 0; + if (ret == 0) { + *previous = knot_node_get_previous(*found); + exact_match = 1; + } else if (ret < 0) { + *previous = *found; + *found = NULL; + } else if (ret > 0) { + /* Previous should be the rightmost node. + * For regular zone it is the node left of apex, but for some + * cases like NSEC3, there is no such sort of thing (name wise). + */ + /*! \todo We could store rightmost node in zonetree probably. */ + hattrie_iter_t *i = hattrie_iter_begin(tree, 1); + *previous = *(knot_node_t **)hattrie_iter_val(i); /* leftmost */ + *previous = knot_node_get_previous(*previous); /* rightmost */ + *found = NULL; + hattrie_iter_free(i); } - // create dummy data node to use for lookup - knot_node_t *tmp_data = knot_node_new( - (knot_dname_t *)owner, NULL, 0); - if (tmp_data == NULL) { - free(tmp); - return KNOT_ENOMEM; + /* Check if previous node is not an empty non-terminal. */ + if (knot_node_rrset_count(*previous) == 0) { + *previous = knot_node_get_previous(*previous); } - tmp->node = tmp_data; - - int exact_match = TREE_FIND_LESS_EQUAL( - tree, knot_zone_tree_node, avl, tmp, &f, &prev); - - knot_node_free(&tmp_data); - free(tmp); - - *found = (exact_match > 0) ? f->node : NULL; dbg_zone_exec_detail( char *name = knot_dname_to_str(owner); - char *name_f = (f != NULL) - ? knot_dname_to_str(knot_node_owner(f->node)) + char *name_f = (*found != NULL) + ? knot_dname_to_str(knot_node_owner(*found)) : "none"; dbg_zone_detail("Searched for owner %s in zone tree.\n", name); dbg_zone_detail("Exact match: %d\n", exact_match); - dbg_zone_detail("Found node: %p: %s.\n", f, name_f); - dbg_zone_detail("Previous node: %p.\n", prev); + dbg_zone_detail("Found node: %p: %s.\n", *found, name_f); + dbg_zone_detail("Previous node: %p.\n", *previous); free(name); - if (f != NULL) { + if (*found != NULL) { free(name_f); } ); - if (exact_match < 0) { - // previous is not really previous but should be the leftmost - // node in the tree; take it's previous - assert(prev != NULL); - *previous = knot_node_get_previous(prev->node); - exact_match = 0; - } else if (prev == NULL) { - // either the returned node is the root of the tree, or - // it is the leftmost node in the tree; in both cases - // node was found set the previous node of the found - // node - assert(exact_match > 0); - assert(f != NULL); - *previous = knot_node_get_previous(f->node); - } else { - // otherwise check if the previous node is not an empty - // non-terminal - /*! \todo Here we assume that the 'prev' pointer always points - * to an empty non-terminal. - */ - /*! \todo What did I mean by the previous TODO?? - * Nevertheless, it seems to me that node->prev can be - * an empty non-terminal too, cannot it? - */ - dbg_zone_detail("Previous: %p\n", prev->node); - *previous = (knot_node_rrset_count(prev->node) == 0) - ? knot_node_get_previous(prev->node) - : prev->node; - dbg_zone_detail("Previous: %p, is empty: %d\n", *previous, - (*previous) ? knot_node_is_empty(*previous) - : -1); - } - - assert(exact_match >= 0); - return exact_match; } @@ -376,84 +237,53 @@ dbg_zone_exec_detail( int knot_zone_tree_remove(knot_zone_tree_t *tree, const knot_dname_t *owner, - knot_zone_tree_node_t **removed) + knot_node_t **removed) { - if (tree == NULL || owner == NULL || removed == NULL) { + if (tree == NULL || owner == NULL) { return KNOT_EINVAL; } - // create dummy node to use for lookup - knot_zone_tree_node_t *tmp = (knot_zone_tree_node_t *)malloc( - sizeof(knot_zone_tree_node_t)); - if (tmp == NULL) { - return KNOT_ENOMEM; - } + uint8_t lf[DNAME_LFT_MAXLEN]; + dname_lf(lf, owner, sizeof(lf)); - // create dummy data node to use for lookup - knot_node_t *tmp_data = knot_node_new( - (knot_dname_t *)owner, NULL, 0); - if (tmp_data == NULL) { - free(tmp); - return KNOT_ENOMEM; + value_t *rval = hattrie_tryget(tree, (char*)lf+1, *lf); + if (rval == NULL) { + return KNOT_ENOENT; + } else { + *removed = (knot_node_t *)(*rval); } - tmp->node = tmp_data; - // we must first find the node, so that it may be destroyed - knot_zone_tree_node_t *n = TREE_FIND(tree, knot_zone_tree_node, avl, - tmp); - /*! \todo How to know if this was successful? */ - TREE_REMOVE(tree, knot_zone_tree_node, avl, tmp); - - knot_node_free(&tmp_data); - free(tmp); - - *removed = n; - + hattrie_del(tree, (char*)lf+1, *lf); return KNOT_EOK; } /*----------------------------------------------------------------------------*/ -int knot_zone_tree_forward_apply_inorder(knot_zone_tree_t *tree, - void (*function)( - knot_zone_tree_node_t *node, - void *data), - void *data) +int knot_zone_tree_apply_inorder(knot_zone_tree_t *tree, + void (*function)(knot_node_t **node, + void *data), + void *data) { if (tree == NULL || function == NULL) { return KNOT_EINVAL; } - TREE_FORWARD_APPLY(tree, knot_zone_tree_node, avl, - function, data); - - return KNOT_EOK; -} - -/*----------------------------------------------------------------------------*/ - -int knot_zone_tree_forward_apply_postorder(knot_zone_tree_t *tree, - void (*function)( - knot_zone_tree_node_t *node, - void *data), - void *data) -{ - if (tree == NULL || function == NULL) { - return KNOT_EINVAL; + hattrie_iter_t *i = hattrie_iter_begin(tree, 1); + while(!hattrie_iter_finished(i)) { + function((knot_node_t **)hattrie_iter_val(i), data); + hattrie_iter_next(i); } - - TREE_POST_ORDER_APPLY(tree, knot_zone_tree_node, avl, - function, data); + hattrie_iter_free(i); return KNOT_EOK; } /*----------------------------------------------------------------------------*/ -int knot_zone_tree_reverse_apply_inorder(knot_zone_tree_t *tree, +int knot_zone_tree_apply_recursive(knot_zone_tree_t *tree, void (*function)( - knot_zone_tree_node_t *node, + knot_node_t **node, void *data), void *data) { @@ -461,26 +291,23 @@ int knot_zone_tree_reverse_apply_inorder(knot_zone_tree_t *tree, return KNOT_EINVAL; } - TREE_REVERSE_APPLY(tree, knot_zone_tree_node, avl, - function, data); + hattrie_apply_rev(tree, (void (*)(value_t*,void*))function, data); return KNOT_EOK; } /*----------------------------------------------------------------------------*/ -int knot_zone_tree_reverse_apply_postorder(knot_zone_tree_t *tree, - void (*function)( - knot_zone_tree_node_t *node, - void *data), - void *data) +int knot_zone_tree_apply(knot_zone_tree_t *tree, + void (*function)(knot_node_t **node, void *data), + void *data) { - if (tree == NULL || function == NULL) { - return KNOT_EINVAL; + hattrie_iter_t *i = hattrie_iter_begin(tree, 0); + while(!hattrie_iter_finished(i)) { + function((knot_node_t **)hattrie_iter_val(i), data); + hattrie_iter_next(i); } - - TREE_REVERSE_APPLY_POST(tree, knot_zone_tree_node, avl, - function, data); + hattrie_iter_free(i); return KNOT_EOK; } @@ -488,39 +315,29 @@ int knot_zone_tree_reverse_apply_postorder(knot_zone_tree_t *tree, /*----------------------------------------------------------------------------*/ int knot_zone_tree_shallow_copy(knot_zone_tree_t *from, - knot_zone_tree_t *to) + knot_zone_tree_t **to) { if (to == NULL || from == NULL) { return KNOT_EINVAL; } - /* - * This function will copy the tree by hand, so that the nodes - * do not have to be inserted the normal way. It should be substantially - * faster. - */ - to->th_cmp = from->th_cmp; + *to = hattrie_dup(from, knot_zone_node_copy); - return knot_zone_tree_copy_node(from->th_root, &to->th_root); + return KNOT_EOK; } /*----------------------------------------------------------------------------*/ int knot_zone_tree_deep_copy(knot_zone_tree_t *from, - knot_zone_tree_t *to) + knot_zone_tree_t **to) { if (to == NULL || from == NULL) { return KNOT_EINVAL; } - /* - * This function will copy the tree by hand, so that the nodes - * do not have to be inserted the normal way. It should be substantially - * faster. - */ - to->th_cmp = from->th_cmp; + *to = hattrie_dup(from, knot_zone_node_deep_copy); - return knot_zone_tree_deep_copy_node(from->th_root, &to->th_root); + return KNOT_EOK; } /*----------------------------------------------------------------------------*/ @@ -530,21 +347,49 @@ void knot_zone_tree_free(knot_zone_tree_t **tree) if (tree == NULL || *tree == NULL) { return; } - knot_zone_tree_free_node((*tree)->th_root, 0); - free(*tree); + hattrie_free(*tree); *tree = NULL; } /*----------------------------------------------------------------------------*/ +static void knot_zone_tree_free_node(knot_node_t **node, void *data) +{ + UNUSED(data); + if (node) { + knot_node_free(node); + } +} + void knot_zone_tree_deep_free(knot_zone_tree_t **tree) { if (tree == NULL || *tree == NULL) { return; } - knot_zone_tree_free_node((*tree)->th_root, 1); - free(*tree); - *tree = NULL; + + knot_zone_tree_apply_recursive(*tree, knot_zone_tree_free_node, NULL); + knot_zone_tree_free(tree); +} + +/*----------------------------------------------------------------------------*/ + +void hattrie_insert_dname(hattrie_t *tr, knot_dname_t *dname) +{ + *hattrie_get(tr, (char *)dname->name, dname->size) = dname; } /*----------------------------------------------------------------------------*/ + +knot_dname_t *hattrie_get_dname(hattrie_t *tr, knot_dname_t *dname) +{ + if (tr == NULL || dname == NULL) { + return NULL; + } + + value_t *val = hattrie_tryget(tr, (char *)dname->name, dname->size); + if (val == NULL) { + return NULL; + } else { + return (knot_dname_t *)(*val); + } +} |