Remove destroy field of BTree and add zix_btree_clear()

If this is used, it is only when clearing or freeing a tree.  Allowing it to be
given as a parameter directly there is clearer and avoids bloating the tree
itself with information that isn't needed.

4 files changed, 109 insertions, 44 deletions

diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c
index f57538d..e01b64f 100644
--- a/benchmark/tree_bench.c
+++ b/benchmark/tree_bench.c
@@ -156,7 +156,7 @@ bench_zix_btree(size_t n_elems,
 
   uintptr_t     r  = 0u;
   ZixBTreeIter* ti = NULL;
-  ZixBTree*     t  = zix_btree_new(int_cmp, NULL, NULL);
+  ZixBTree*     t  = zix_btree_new(int_cmp, NULL);
 
   // Insert n_elems elements
   struct timespec insert_start = bench_start();
@@ -205,7 +205,7 @@ bench_zix_btree(size_t n_elems,
   }
   fprintf(del_dat, "\t%lf", bench_end(&del_start));
 
-  zix_btree_free(t);
+  zix_btree_free(t, NULL);
 
   return EXIT_SUCCESS;
 }
diff --git a/include/zix/btree.h b/include/zix/btree.h
index bce3068..5472eca 100644
--- a/include/zix/btree.h
+++ b/include/zix/btree.h
@@ -50,12 +50,27 @@ typedef struct ZixBTreeIterImpl ZixBTreeIter;
 /// Create a new (empty) B-Tree
 ZIX_API
 ZixBTree*
-zix_btree_new(ZixComparator cmp, const void* cmp_data, ZixDestroyFunc destroy);
+zix_btree_new(ZixComparator cmp, const void* cmp_data);
 
-/// Free `t`
+/**
+   Free `t` and all the nodes it contains.
+
+   @param destroy Function to call once for every value in the tree.  This can
+   be used to free values if they are dynamically allocated.
+*/
+ZIX_API
+void
+zix_btree_free(ZixBTree* t, ZixDestroyFunc destroy);
+
+/**
+   Clear everything from `t`, leaving it empty.
+
+   @param destroy Function called exactly once for every value in the tree,
+   just before that value is removed from the tree.
+*/
 ZIX_API
 void
-zix_btree_free(ZixBTree* t);
+zix_btree_clear(ZixBTree* t, ZixDestroyFunc destroy);
 
 /// Return the number of elements in `t`
 ZIX_PURE_API
diff --git a/src/btree.c b/src/btree.c
index 65c6e7b..eb5a5f5 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -39,12 +39,11 @@ typedef uint16_t ZixShort;
 #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2u)
 
 struct ZixBTreeImpl {
-  ZixBTreeNode*  root;
-  ZixDestroyFunc destroy;
-  ZixComparator  cmp;
-  const void*    cmp_data;
-  size_t         size;
-  unsigned       height; ///< Number of levels, i.e. root only has height 1
+  ZixBTreeNode* root;
+  ZixComparator cmp;
+  const void*   cmp_data;
+  size_t        size;
+  unsigned      height; ///< Number of levels, i.e. root only has height 1
 };
 
 struct ZixBTreeNodeImpl {
@@ -113,14 +112,11 @@ zix_btree_child(const ZixBTreeNode* const node, const unsigned i)
 }
 
 ZixBTree*
-zix_btree_new(const ZixComparator  cmp,
-              const void* const    cmp_data,
-              const ZixDestroyFunc destroy)
+zix_btree_new(const ZixComparator cmp, const void* const cmp_data)
 {
   ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
   if (t) {
     t->root     = zix_btree_node_new(true);
-    t->destroy  = destroy;
     t->cmp      = cmp;
     t->cmp_data = cmp_data;
     t->size     = 0;
@@ -134,40 +130,51 @@ zix_btree_new(const ZixComparator  cmp,
 }
 
 static void
-zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n)
-{
-  if (n) {
+zix_btree_free_children(ZixBTree* const     t,
+                        ZixBTreeNode* const n,
+                        ZixDestroyFunc      destroy)
+{
+  if (!n->is_leaf) {
+    for (ZixShort i = 0; i < n->n_vals + 1u; ++i) {
+      zix_btree_free_children(t, zix_btree_child(n, i), destroy);
+      free(zix_btree_child(n, i));
+    }
+  }
+
+  if (destroy) {
     if (n->is_leaf) {
-      if (t->destroy) {
-        for (ZixShort i = 0u; i < n->n_vals; ++i) {
-          t->destroy(n->data.leaf.vals[i]);
-        }
+      for (ZixShort i = 0u; i < n->n_vals; ++i) {
+        destroy(n->data.leaf.vals[i]);
       }
     } else {
-      if (t->destroy) {
-        for (ZixShort i = 0u; i < n->n_vals; ++i) {
-          t->destroy(n->data.inode.vals[i]);
-        }
-      }
-
-      for (ZixShort i = 0u; i < n->n_vals + 1u; ++i) {
-        zix_btree_free_rec(t, zix_btree_child(n, i));
+      for (ZixShort i = 0u; i < n->n_vals; ++i) {
+        destroy(n->data.inode.vals[i]);
       }
     }
-
-    free(n);
   }
 }
 
 void
-zix_btree_free(ZixBTree* const t)
+zix_btree_free(ZixBTree* const t, ZixDestroyFunc destroy)
 {
   if (t) {
-    zix_btree_free_rec(t, t->root);
+    zix_btree_clear(t, destroy);
+    free(t->root);
     free(t);
   }
 }
 
+void
+zix_btree_clear(ZixBTree* const t, ZixDestroyFunc destroy)
+{
+  zix_btree_free_children(t, t->root, destroy);
+
+  memset(t->root, 0, sizeof(ZixBTreeNode));
+  t->root->is_leaf = true;
+  t->size          = 0u;
+  t->height        = 1u;
+}
+
 size_t
 zix_btree_size(const ZixBTree* const t)
 {
diff --git a/test/btree_test.c b/test/btree_test.c
index 6914053..4e84ac4 100644
--- a/test/btree_test.c
+++ b/test/btree_test.c
@@ -55,11 +55,6 @@ ith_elem(const unsigned test_num, const size_t n_elems, const size_t i)
   }
 }
 
-static void
-destroy(void* ZIX_UNUSED(ptr))
-{
-}
-
 typedef struct {
   unsigned test_num;
   size_t   n_elems;
@@ -104,10 +99,11 @@ ZIX_LOG_FUNC(2, 3)
 static int
 test_fail(ZixBTree* t, const char* fmt, ...)
 {
-  zix_btree_free(t);
+  zix_btree_free(t, NULL);
   if (expect_failure) {
     return EXIT_SUCCESS;
   }
+
   va_list args;
   va_start(args, fmt);
   fprintf(stderr, "error: ");
@@ -116,6 +112,50 @@ test_fail(ZixBTree* t, const char* fmt, ...)
   return EXIT_FAILURE;
 }
 
+static const size_t n_clear_insertions = 1024u;
+
+static void
+destroy(void* const ptr)
+{
+  assert(ptr);
+  assert((uintptr_t)ptr <= n_clear_insertions);
+}
+
+static void
+no_destroy(void* const ptr)
+{
+  assert(!ptr);
+}
+
+static void
+test_clear(void)
+{
+  ZixBTree* t = zix_btree_new(int_cmp, NULL);
+
+  for (uintptr_t r = 0u; r < n_clear_insertions; ++r) {
+    assert(!zix_btree_insert(t, (void*)(r + 1u)));
+  }
+
+  zix_btree_clear(t, destroy);
+  assert(zix_btree_size(t) == 0);
+
+  zix_btree_free(t, no_destroy);
+}
+
+static void
+test_free(void)
+{
+  ZixBTree* t = zix_btree_new(int_cmp, NULL);
+
+  for (uintptr_t r = 0u; r < n_clear_insertions; ++r) {
+    assert(!zix_btree_insert(t, (void*)(r + 1u)));
+  }
+
+  assert(zix_btree_size(t) == n_clear_insertions);
+
+  zix_btree_free(t, destroy);
+}
+
 static int
 stress(const unsigned test_num, const size_t n_elems)
 {
@@ -124,7 +164,7 @@ stress(const unsigned test_num, const size_t n_elems)
   }
 
   uintptr_t r  = 0;
-  ZixBTree* t  = zix_btree_new(int_cmp, NULL, NULL);
+  ZixBTree* t  = zix_btree_new(int_cmp, NULL);
   ZixStatus st = ZIX_STATUS_SUCCESS;
 
   if (!t) {
@@ -441,12 +481,12 @@ stress(const unsigned test_num, const size_t n_elems)
   zix_btree_iter_free(next);
   next = NULL;
 
-  zix_btree_free(t);
+  zix_btree_free(t, NULL);
 
   // Test lower_bound with wildcard comparator
 
   TestContext ctx = {test_num, n_elems};
-  if (!(t = zix_btree_new(wildcard_cmp, &ctx, destroy))) {
+  if (!(t = zix_btree_new(wildcard_cmp, &ctx))) {
     return test_fail(t, "Failed to allocate tree\n");
   }
 
@@ -499,7 +539,7 @@ stress(const unsigned test_num, const size_t n_elems)
   }
 
   zix_btree_iter_free(ti);
-  zix_btree_free(t);
+  zix_btree_free(t, NULL);
 
   return EXIT_SUCCESS;
 }
@@ -512,6 +552,9 @@ main(int argc, char** argv)
     return EXIT_FAILURE;
   }
 
+  test_clear();
+  test_free();
+
   const unsigned n_tests = 3u;
   const size_t   n_elems = (argc > 1) ? strtoul(argv[1], NULL, 10) : 524288u;