diff options
Diffstat (limited to 'src/common/general-tree.c')
| -rw-r--r-- | src/common/general-tree.c | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/src/common/general-tree.c b/src/common/general-tree.c new file mode 100644 index 0000000..202b31a --- /dev/null +++ b/src/common/general-tree.c @@ -0,0 +1,215 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "common/general-tree.h" +#include "common/errors.h" + +MOD_TREE_DEFINE(general_tree_node, avl); + +static void gen_rem_func(struct general_tree_node *n1) +{ + free(n1); +} + +general_tree_t *gen_tree_new(int (*comp_func)(void *, void *)) +{ + general_tree_t *ret = malloc(sizeof(general_tree_t)); + if (ret == NULL) { + return NULL; + } + ret->tree = malloc(sizeof(general_avl_tree_t)); + if (ret->tree == NULL) { + free(ret); + return NULL; + } + MOD_TREE_INIT(ret->tree, comp_func); + return ret; +} + +int gen_tree_add(general_tree_t *tree, + void *node, int (*mrg_func)(void **n1, void **n2)) +{ + struct general_tree_node *tree_node = + malloc(sizeof(struct general_tree_node)); + if (tree_node == NULL) { + return -1; + } + memset(tree_node, 0, sizeof(struct general_tree_node)); + tree_node->data = node; + int merged = 0; + MOD_TREE_INSERT(tree->tree, general_tree_node, avl, + tree_node, mrg_func, &merged); + if (merged) { + free(tree_node); + } + return merged; +} + +void gen_tree_remove(general_tree_t *tree, + void *what) +{ + struct general_tree_node tree_node; + tree_node.data = what; + MOD_TREE_REMOVE(tree->tree, general_tree_node, avl, &tree_node, + gen_rem_func); +} + +void *gen_tree_find(general_tree_t *tree, + void *what) +{ + struct general_tree_node tree_node; + tree_node.data = what; + struct general_tree_node *found_node = + MOD_TREE_FIND(tree->tree, general_tree_node, avl, &tree_node); + if (found_node) { + return found_node->data; + } else { + return NULL; + } +} + +int gen_tree_find_less_or_equal(general_tree_t *tree, + void *what, + void **found) +{ + if (tree == NULL || tree->tree == NULL) { + return -1; + } + + /* Check if tree is empty. */ + if (tree->tree->th_root == NULL) { + *found = NULL; + return 0; + } + + struct general_tree_node *f = NULL, *prev = NULL; + struct general_tree_node tree_node; + tree_node.data = what; + int exact_match = + MOD_TREE_FIND_LESS_EQUAL(tree->tree, general_tree_node, avl, + &tree_node, &f, &prev); + if (exact_match < 0) { + *found = NULL; + exact_match = 0; + } else if (exact_match == 0) { + assert(prev != NULL); + *found = prev->data; + } else { + assert(f != NULL); + *found = f->data; + } +// *found = (exact_match > 0) ? f->data : prev->data; + return exact_match; +} + +void gen_tree_apply_inorder(general_tree_t *tree, + void (*app_func) + (void *node, void *data), void *data) +{ + MOD_TREE_FORWARD_APPLY(tree->tree, general_tree_node, avl, + app_func, data); +} + +void gen_tree_destroy(general_tree_t **tree, + void (*dest_func)(void *node, void *data), void *data) +{ +// gen_tree_apply_inorder(*tree, print_node, NULL); + MOD_TREE_DESTROY((*tree)->tree, general_tree_node, avl, dest_func, + gen_rem_func, data); + free((*tree)->tree); + free(*tree); + *tree = NULL; +} + +void gen_tree_clear(general_tree_t *tree) +{ + MOD_TREE_DESTROY(tree->tree, general_tree_node, avl, NULL, + gen_rem_func, NULL); +} + +//static void add_node_to_tree(void *n, void *data) +//{ +// general_tree_t *tree = (general_tree_t *)data; +// gen_tree_add(tree, n, NULL); +//} + +static int gen_tree_copy_node(const struct general_tree_node *from, + struct general_tree_node **to) +{ + if (from == NULL) { + return 0; + } + + *to = malloc(sizeof(struct general_tree_node)); + if (*to == NULL) { + return -1; + } + memset(*to, 0, sizeof(struct general_tree_node)); + + (*to)->data = from->data; + (*to)->avl.avl_height = from->avl.avl_height; + + int ret = gen_tree_copy_node(from->avl.avl_left, + &(*to)->avl.avl_left); + if (ret != 0) { + return ret; + } + + ret = gen_tree_copy_node(from->avl.avl_right, + &(*to)->avl.avl_right); + if (ret != 0) { + /*! \todo Partially cleaunp tree! */ + (*to)->avl.avl_left = NULL; + return ret; + } + + return 0; +} + +general_tree_t *gen_tree_shallow_copy(general_tree_t *tree) +{ + general_tree_t *new_tree = malloc(sizeof(general_tree_t)); + if (new_tree == NULL) { + return NULL; + } + new_tree->tree = malloc(sizeof(general_avl_tree_t)); + if (new_tree->tree == NULL) { + free(new_tree); + return NULL; + } + + MOD_TREE_INIT(new_tree->tree, tree->tree->th_cmp); + assert(new_tree->tree->th_cmp == tree->tree->th_cmp); + +// gen_tree_apply_inorder(tree, add_node_to_tree, new_tree); + + if (gen_tree_copy_node(tree->tree->th_root, + &new_tree->tree->th_root) != 0) { + return NULL; + } + + /* CLEANUP */ +// gen_tree_apply_inorder(tree, print_node, NULL); +// printf("--------------------------\n"); +// gen_tree_apply_inorder(new_tree, print_node, NULL); + + return new_tree; +} + |