diff options
| -rw-r--r-- | src/tree.c | 49 | ||||
| -rw-r--r-- | test/tree_bench.c | 2 | ||||
| -rw-r--r-- | test/tree_test.c | 37 | ||||
| -rw-r--r-- | zix/common.h | 5 | ||||
| -rw-r--r-- | zix/tree.h | 12 |
5 files changed, 90 insertions, 15 deletions
@@ -27,10 +27,12 @@ typedef struct ZixTreeNodeImpl ZixTreeNode; struct ZixTreeImpl { - ZixTreeNode* root; - ZixComparator cmp; - void* cmp_data; - bool allow_duplicates; + ZixTreeNode* root; + ZixDestroyFunc destroy; + ZixComparator cmp; + void* cmp_data; + size_t size; + bool allow_duplicates; }; struct ZixTreeNodeImpl { @@ -67,22 +69,30 @@ struct ZixTreeNodeImpl { ZIX_API ZixTree* -zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data) +zix_tree_new(bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy) { ZixTree* t = malloc(sizeof(ZixTree)); t->root = NULL; + t->destroy = destroy; t->cmp = cmp; t->cmp_data = cmp_data; + t->size = 0; t->allow_duplicates = allow_duplicates; return t; } static void -zix_tree_free_rec(ZixTreeNode* n) +zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) { if (n) { - zix_tree_free_rec(n->left); - zix_tree_free_rec(n->right); + zix_tree_free_rec(t, n->left); + zix_tree_free_rec(t, n->right); + if (t->destroy) { + t->destroy(n->data); + } free(n); } } @@ -91,11 +101,16 @@ ZIX_API void zix_tree_free(ZixTree* t) { - zix_tree_free_rec(t->root); - + zix_tree_free_rec(t, t->root); free(t); } +size_t +zix_tree_size(ZixTree* t) +{ + return t->size; +} + static void rotate(ZixTreeNode* p, ZixTreeNode* q) { @@ -131,8 +146,6 @@ rotate(ZixTreeNode* p, ZixTreeNode* q) p->parent = q; } - - /** * Rotate left about @a p. * @@ -413,6 +426,8 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) DUMP(t); + ++t->size; + #ifdef ZIX_TREE_VERIFY if (!verify(t, t->root)) { return ZIX_STATUS_ERROR; @@ -435,7 +450,12 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) if ((n == t->root) && !n->left && !n->right) { t->root = NULL; + if (t->destroy) { + t->destroy(n->data); + } free(n); + --t->size; + assert(t->size == 0); return ZIX_STATUS_SUCCESS; } @@ -559,8 +579,13 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) DUMP(t); + if (t->destroy) { + t->destroy(n->data); + } free(n); + --t->size; + #ifdef ZIX_TREE_VERIFY if (!verify(t, t->root)) { return ZIX_STATUS_ERROR; diff --git a/test/tree_bench.c b/test/tree_bench.c index d0e2611..ff6bd5e 100644 --- a/test/tree_bench.c +++ b/test/tree_bench.c @@ -62,7 +62,7 @@ bench_zix_tree(size_t n_elems, intptr_t r; ZixTreeIter* ti; - ZixTree* t = zix_tree_new(true, int_cmp, NULL); + ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL); srand(seed); diff --git a/test/tree_test.c b/test/tree_test.c index 943dca7..b89d5a8 100644 --- a/test/tree_test.c +++ b/test/tree_test.c @@ -60,7 +60,7 @@ stress(int test_num, size_t n_elems) intptr_t r; ZixTreeIter* ti; - ZixTree* t = zix_tree_new(true, int_cmp, NULL); + ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL); srand(seed); @@ -79,6 +79,12 @@ stress(int test_num, size_t n_elems) } } + // Ensure tree size is correct + if (zix_tree_size(t) != n_elems) { + fprintf(stderr, "Tree size %zu != %zu\n", zix_tree_size(t), n_elems); + return test_fail(); + } + srand(seed); // Search for all elements @@ -146,6 +152,35 @@ stress(int test_num, size_t n_elems) } } + // Ensure the tree is empty + if (zix_tree_size(t) != 0) { + fprintf(stderr, "Tree size %zu != 0\n", zix_tree_size(t)); + return test_fail(); + } + + srand(seed); + + // Insert n_elems elements again (to test non-empty destruction) + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + (intptr_t)zix_tree_get(ti), r); + return test_fail(); + } + } + + // Ensure tree size is correct + if (zix_tree_size(t) != n_elems) { + fprintf(stderr, "Tree size %zu != %zu\n", zix_tree_size(t), n_elems); + return test_fail(); + } + zix_tree_free(t); return EXIT_SUCCESS; diff --git a/zix/common.h b/zix/common.h index a7edf76..8ed0b0b 100644 --- a/zix/common.h +++ b/zix/common.h @@ -60,6 +60,11 @@ typedef int (*ZixComparator)(const void* a, const void* b, void* user_data); Function for testing equality of two elements. */ typedef bool (*ZixEqualFunc)(const void* a, const void* b); + +/** + Function to destroy an element. +*/ +typedef void (*ZixDestroyFunc)(const void* ptr); /**@} */ @@ -18,6 +18,7 @@ #define ZIX_TREE_H #include <stdbool.h> +#include <stddef.h> #include "zix/common.h" @@ -46,7 +47,10 @@ typedef struct ZixTreeNodeImpl ZixTreeIter; Create a new (empty) tree. */ ZixTree* -zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data); +zix_tree_new(bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy); /** Free @a t. @@ -55,6 +59,12 @@ void zix_tree_free(ZixTree* t); /** + Return the number of elements in @a t. +*/ +size_t +zix_tree_size(ZixTree* t); + +/** Insert the element @a e into @a t and point @a ti at the new element. */ ZixStatus |