Reduce empty BTree memory requirements

Avoid over-allocating the ZixBTree structure, and only allocate a root node
when elements are inserted. The over-allocation was to make all allocations use
pages (towards disk-backed storage), but since this isn't actually supported at
the moment it was just a waste of memory.

3 files changed, 47 insertions, 23 deletions

diff --git a/NEWS b/NEWS
index 09d2912..9970fcc 100644
--- a/NEWS
+++ b/NEWS
@@ -1,8 +1,9 @@
 zix (0.6.3) unstable; urgency=medium
 
+  * Reduce empty BTree memory requirements
   * Use getenv() instead of environ to avoid issues on FreeBSD
 
- -- David Robillard <d@drobilla.net>  Mon, 10 Feb 2025 21:36:46 +0000
+ -- David Robillard <d@drobilla.net>  Thu, 29 May 2025 15:22:01 +0000
 
 zix (0.6.2) stable; urgency=medium
 
diff --git a/src/btree.c b/src/btree.c
index 093d0c3..c66ae6b 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -102,23 +102,15 @@ zix_btree_new(ZixAllocator* const       allocator,
 
   assert(cmp);
 
-  ZixBTree* const t = (ZixBTree*)zix_aligned_alloc(
-    allocator, ZIX_BTREE_PAGE_SIZE, ZIX_BTREE_PAGE_SIZE);
-
-  if (!t) {
-    return NULL;
-  }
-
-  if (!(t->root = zix_btree_node_new(allocator, true))) {
-    zix_aligned_free(allocator, t);
-    return NULL;
+  ZixBTree* const t = (ZixBTree*)zix_malloc(allocator, sizeof(ZixBTree));
+  if (t) {
+    t->allocator = allocator;
+    t->root      = NULL;
+    t->cmp       = cmp;
+    t->cmp_data  = cmp_data;
+    t->size      = 0U;
   }
 
-  t->allocator = allocator;
-  t->cmp       = cmp;
-  t->cmp_data  = cmp_data;
-  t->size      = 0U;
-
   return t;
 }
 
@@ -157,7 +149,7 @@ zix_btree_free(ZixBTree* const           t,
   if (t) {
     zix_btree_clear(t, destroy, destroy_user_data);
     zix_aligned_free(t->allocator, t->root);
-    zix_aligned_free(t->allocator, t);
+    zix_free(t->allocator, t);
   }
 }
 
@@ -166,11 +158,13 @@ zix_btree_clear(ZixBTree* const     t,
                 ZixBTreeDestroyFunc destroy,
                 const void*         destroy_user_data)
 {
-  zix_btree_free_children(t, t->root, destroy, destroy_user_data);
+  if (t->root) {
+    zix_btree_free_children(t, t->root, destroy, destroy_user_data);
+    zix_aligned_free(t->allocator, t->root);
+    t->root = NULL;
+  }
 
-  memset(t->root, 0U, sizeof(ZixBTreeNode));
-  t->root->is_leaf = true;
-  t->size          = 0U;
+  t->size = 0U;
 }
 
 size_t
@@ -436,8 +430,13 @@ zix_btree_insert(ZixBTree* const t, void* const e)
 
   ZixStatus st = ZIX_STATUS_SUCCESS;
 
-  // Grow up if necessary to ensure the root is not full
-  if (zix_btree_is_full(t->root)) {
+  if (!t->root) {
+    // Empty tree, create a new leaf root
+    if (!(t->root = zix_btree_node_new(t->allocator, true))) {
+      return ZIX_STATUS_NO_MEM;
+    }
+  } else if (zix_btree_is_full(t->root)) {
+    // Grow up if necessary to ensure the root is not full
     if ((st = zix_btree_grow_up(t))) {
       return st;
     }
@@ -829,6 +828,9 @@ zix_btree_find(const ZixBTree* const t,
   ZixBTreeNode* n = t->root;
 
   *ti = zix_btree_end_iter;
+  if (!n) {
+    return ZIX_STATUS_NOT_FOUND;
+  }
 
   while (!n->is_leaf) {
     bool           equal = false;
@@ -870,6 +872,9 @@ zix_btree_lower_bound(const ZixBTree* const     t,
   ZixBTreeNode* n           = t->root; // Current node
   uint16_t      found_level = 0U;      // Lowest level a match was found at
   bool          found       = false;   // True if a match was ever found
+  if (!n) {
+    return ZIX_STATUS_SUCCESS;
+  }
 
   // Search down until we reach a leaf
   while (!n->is_leaf) {
diff --git a/test/test_btree.c b/test/test_btree.c
index dd665c7..a87e26e 100644
--- a/test/test_btree.c
+++ b/test/test_btree.c
@@ -101,6 +101,23 @@ destroy(void* const ptr, const void* const user_data)
 }
 
 static void
+test_empty(void)
+{
+  ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL);
+  assert(t);
+
+  // Check that reading functions work properly with an empty (rootless) tree
+  const int    e  = 42;
+  ZixBTreeIter ti = zix_btree_end(t);
+  zix_btree_clear(t, NULL, NULL);
+  assert(!zix_btree_size(t));
+  assert(zix_btree_find(t, &e, &ti) == ZIX_STATUS_NOT_FOUND);
+  assert(!zix_btree_lower_bound(t, int_cmp, NULL, &e, &ti));
+
+  zix_btree_free(t, destroy, NULL);
+}
+
+static void
 test_clear(void)
 {
   ZixBTree* t = zix_btree_new(NULL, int_cmp, NULL);
@@ -576,6 +593,7 @@ main(int argc, char** argv)
     return EXIT_FAILURE;
   }
 
+  test_empty();
   test_clear();
   test_free();
   test_iter_comparison();