Switch to external zix dependency

9 files changed, 44 insertions, 1017 deletions

diff --git a/meson.build b/meson.build
index 512e22a..aecfbda 100644
--- a/meson.build
+++ b/meson.build
@@ -90,6 +90,7 @@ add_project_arguments(platform_defines, language: ['c'])
 m_dep = cc.find_library('m', required: false)
 dl_dep = cc.find_library('dl', required: false)
 
+zix_dep = dependency('zix-0', fallback: 'zix', version: '>= 0.3.0')
 serd_dep = dependency('serd-0', fallback: 'serd', version: '>= 0.30.10')
 sord_dep = dependency('sord-0', fallback: 'sord', version: '>= 0.16.10')
 lv2_dep = dependency('lv2', fallback: 'lv2', version: '>= 1.18.2')
@@ -117,7 +118,6 @@ sources = files(
   'src/ui.c',
   'src/util.c',
   'src/world.c',
-  'src/zix/tree.c',
 )
 
 common_dependencies = [
@@ -127,6 +127,7 @@ common_dependencies = [
   serd_dep,
   sord_dep,
   sratom_dep,
+  zix_dep,
 ]
 
 # Set appropriate arguments for building against the library type
@@ -140,7 +141,7 @@ endif
 liblilv = library(
   meson.project_name() + library_suffix,
   sources,
-  c_args: c_suppressions +  extra_c_args + ['-DLILV_INTERNAL', '-DZIX_STATIC'],
+  c_args: c_suppressions +  extra_c_args + ['-DLILV_INTERNAL'],
   dependencies: common_dependencies,
   gnu_symbol_visibility: 'hidden',
   include_directories: include_directories('include', 'src'),
@@ -204,7 +205,7 @@ if not get_option('tests').disabled()
       meson.project_name() + library_suffix,
       sources,
       include_directories: include_directories('include', 'src'),
-      c_args: c_suppressions + ['-DLILV_INTERNAL', '-DLILV_STATIC', '-DZIX_STATIC'],
+      c_args: c_suppressions + ['-DLILV_INTERNAL', '-DLILV_STATIC'],
       dependencies: common_dependencies,
       gnu_symbol_visibility: 'default')
   else
diff --git a/src/collections.c b/src/collections.c
index 10b15b0..2ea812b 100644
--- a/src/collections.c
+++ b/src/collections.c
@@ -5,12 +5,13 @@
 
 #include "lilv/lilv.h"
 #include "sord/sord.h"
-#include "zix/common.h"
 #include "zix/tree.h"
 
 #include <stdbool.h>
 #include <stddef.h>
 
+typedef void (*LilvFreeFunc)(void* ptr);
+
 int
 lilv_ptr_cmp(const void* a, const void* b, const void* user_data)
 {
@@ -32,10 +33,18 @@ lilv_resource_node_cmp(const void* a, const void* b, const void* user_data)
 
 /* Generic collection functions */
 
+static void
+destroy(void* const ptr, const void* const user_data)
+{
+  if (user_data) {
+    ((LilvFreeFunc)user_data)(ptr);
+  }
+}
+
 static inline LilvCollection*
-lilv_collection_new(ZixComparator cmp, ZixDestroyFunc destructor)
+lilv_collection_new(ZixTreeCompareFunc cmp, LilvFreeFunc free_func)
 {
-  return zix_tree_new(false, cmp, NULL, destructor);
+  return zix_tree_new(NULL, false, cmp, NULL, destroy, (const void*)free_func);
 }
 
 void
@@ -71,28 +80,27 @@ lilv_collection_get(const LilvCollection* collection, const LilvIter* i)
 LilvScalePoints*
 lilv_scale_points_new(void)
 {
-  return lilv_collection_new(lilv_ptr_cmp,
-                             (ZixDestroyFunc)lilv_scale_point_free);
+  return lilv_collection_new(lilv_ptr_cmp, (LilvFreeFunc)lilv_scale_point_free);
 }
 
 LilvNodes*
 lilv_nodes_new(void)
 {
-  return lilv_collection_new(lilv_ptr_cmp, (ZixDestroyFunc)lilv_node_free);
+  return lilv_collection_new(lilv_ptr_cmp, (LilvFreeFunc)lilv_node_free);
 }
 
 LilvUIs*
 lilv_uis_new(void)
 {
   return lilv_collection_new(lilv_header_compare_by_uri,
-                             (ZixDestroyFunc)lilv_ui_free);
+                             (LilvFreeFunc)lilv_ui_free);
 }
 
 LilvPluginClasses*
 lilv_plugin_classes_new(void)
 {
   return lilv_collection_new(lilv_header_compare_by_uri,
-                             (ZixDestroyFunc)lilv_plugin_class_free);
+                             (LilvFreeFunc)lilv_plugin_class_free);
 }
 
 /* URI based accessors (for collections of things with URIs) */
diff --git a/src/pluginclass.c b/src/pluginclass.c
index b4bc352..f3da602 100644
--- a/src/pluginclass.c
+++ b/src/pluginclass.c
@@ -60,8 +60,9 @@ LilvPluginClasses*
 lilv_plugin_class_get_children(const LilvPluginClass* plugin_class)
 {
   // Returned list doesn't own categories
-  LilvPluginClasses* all    = plugin_class->world->plugin_classes;
-  LilvPluginClasses* result = zix_tree_new(false, lilv_ptr_cmp, NULL, NULL);
+  LilvPluginClasses* all = plugin_class->world->plugin_classes;
+  LilvPluginClasses* result =
+    zix_tree_new(NULL, false, lilv_ptr_cmp, NULL, NULL, NULL);
 
   for (ZixTreeIter* i = zix_tree_begin((ZixTree*)all);
        i != zix_tree_end((ZixTree*)all);
diff --git a/src/port.c b/src/port.c
index b7aaa1b..55641e7 100644
--- a/src/port.c
+++ b/src/port.c
@@ -224,11 +224,12 @@ lilv_port_get_scale_points(const LilvPlugin* plugin, const LilvPort* port)
     sord_new_uri(plugin->world->world, (const uint8_t*)LV2_CORE__scalePoint),
     NULL);
 
-  LilvScalePoints* ret = NULL;
-  if (!sord_iter_end(points)) {
-    ret = lilv_scale_points_new();
+  if (sord_iter_end(points)) {
+    return NULL;
   }
 
+  LilvScalePoints* ret = lilv_scale_points_new();
+
   FOREACH_MATCH (points) {
     const SordNode* point = sord_iter_get_node(points, SORD_OBJECT);
 
@@ -244,7 +245,7 @@ lilv_port_get_scale_points(const LilvPlugin* plugin, const LilvPort* port)
   }
   sord_iter_free(points);
 
-  assert(!ret || lilv_nodes_size(ret) > 0);
+  assert(lilv_nodes_size(ret) > 0);
   return ret;
 }
 
diff --git a/src/state.c b/src/state.c
index fd27a1b..a4fa11c 100644
--- a/src/state.c
+++ b/src/state.c
@@ -107,8 +107,9 @@ value_cmp(const void* a, const void* b)
 }
 
 static void
-path_rel_free(void* ptr)
+map_free(void* ptr, const void* user_data)
 {
+  (void)user_data;
   free(((PathMap*)ptr)->abs);
   free(((PathMap*)ptr)->rel);
   free(ptr);
@@ -429,8 +430,8 @@ lilv_state_new_from_instance(const LilvPlugin*         plugin,
   LilvWorld* const    world     = plugin->world;
   LilvState* const    state     = (LilvState*)calloc(1, sizeof(LilvState));
   state->plugin_uri  = lilv_node_duplicate(lilv_plugin_get_uri(plugin));
-  state->abs2rel     = zix_tree_new(false, abs_cmp, NULL, path_rel_free);
-  state->rel2abs     = zix_tree_new(false, rel_cmp, NULL, NULL);
+  state->abs2rel     = zix_tree_new(NULL, false, abs_cmp, NULL, map_free, NULL);
+  state->rel2abs     = zix_tree_new(NULL, false, rel_cmp, NULL, NULL, NULL);
   state->scratch_dir = scratch_dir ? real_dir(scratch_dir) : NULL;
   state->copy_dir    = copy_dir ? real_dir(copy_dir) : NULL;
   state->link_dir    = link_dir ? real_dir(link_dir) : NULL;
diff --git a/src/world.c b/src/world.c
index cff1876..af0ab06 100644
--- a/src/world.c
+++ b/src/world.c
@@ -8,7 +8,6 @@
 #include "lilv/lilv.h"
 #include "serd/serd.h"
 #include "sord/sord.h"
-#include "zix/common.h"
 #include "zix/tree.h"
 
 #include "lv2/core/lv2.h"
@@ -28,6 +27,13 @@
 static int
 lilv_world_drop_graph(LilvWorld* world, const SordNode* graph);
 
+static void
+destroy_node(void* const ptr, const void* const user_data)
+{
+  (void)user_data;
+  lilv_node_free((LilvNode*)ptr);
+}
+
 LilvWorld*
 lilv_world_new(void)
 {
@@ -47,10 +53,11 @@ lilv_world_new(void)
   world->plugin_classes = lilv_plugin_classes_new();
   world->plugins        = lilv_plugins_new();
   world->zombies        = lilv_plugins_new();
-  world->loaded_files   = zix_tree_new(
-    false, lilv_resource_node_cmp, NULL, (ZixDestroyFunc)lilv_node_free);
 
-  world->libs = zix_tree_new(false, lilv_lib_compare, NULL, NULL);
+  world->loaded_files =
+    zix_tree_new(NULL, false, lilv_resource_node_cmp, NULL, destroy_node, NULL);
+
+  world->libs = zix_tree_new(NULL, false, lilv_lib_compare, NULL, NULL, NULL);
 
 #define NS_DCTERMS "http://purl.org/dc/terms/"
 #define NS_DYNMAN "http://lv2plug.in/ns/ext/dynmanifest#"
@@ -914,7 +921,7 @@ lilv_world_unload_bundle(LilvWorld* world, const LilvNode* bundle_uri)
      still be used.
   */
   ZixTreeIter* i = zix_tree_begin((ZixTree*)world->plugins);
-  while (i != zix_tree_end((ZixTree*)world->plugins)) {
+  while (i && i != zix_tree_end((ZixTree*)world->plugins)) {
     LilvPlugin*  p    = (LilvPlugin*)zix_tree_get(i);
     ZixTreeIter* next = zix_tree_iter_next(i);
 
diff --git a/src/zix/common.h b/src/zix/common.h
deleted file mode 100644
index 46307b1..0000000
--- a/src/zix/common.h
+++ /dev/null
@@ -1,125 +0,0 @@
-// Copyright 2016-2020 David Robillard <d@drobilla.net>
-// SPDX-License-Identifier: ISC
-
-#ifndef ZIX_COMMON_H
-#define ZIX_COMMON_H
-
-#include <stdbool.h>
-
-/**
-   @addtogroup zix
-   @{
-*/
-
-/** @cond */
-#if defined(_WIN32) && !defined(ZIX_STATIC) && defined(ZIX_INTERNAL)
-#  define ZIX_API __declspec(dllexport)
-#elif defined(_WIN32) && !defined(ZIX_STATIC)
-#  define ZIX_API __declspec(dllimport)
-#elif defined(__GNUC__)
-#  define ZIX_API __attribute__((visibility("default")))
-#else
-#  define ZIX_API
-#endif
-
-#ifdef __GNUC__
-#  define ZIX_PURE_FUNC __attribute__((pure))
-#  define ZIX_CONST_FUNC __attribute__((const))
-#  define ZIX_MALLOC_FUNC __attribute__((malloc))
-#else
-#  define ZIX_PURE_FUNC
-#  define ZIX_CONST_FUNC
-#  define ZIX_MALLOC_FUNC
-#endif
-
-#define ZIX_PURE_API \
-  ZIX_API            \
-  ZIX_PURE_FUNC
-
-#define ZIX_CONST_API \
-  ZIX_API             \
-  ZIX_CONST_FUNC
-
-#define ZIX_MALLOC_API \
-  ZIX_API              \
-  ZIX_MALLOC_FUNC
-
-/** @endcond */
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#ifdef __GNUC__
-#  define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1)))
-#else
-#  define ZIX_LOG_FUNC(fmt, arg1)
-#endif
-
-// Unused parameter macro to suppresses warnings and make it impossible to use
-#if defined(__cplusplus)
-#  define ZIX_UNUSED(name)
-#elif defined(__GNUC__)
-#  define ZIX_UNUSED(name) name##_unused __attribute__((__unused__))
-#else
-#  define ZIX_UNUSED(name) name
-#endif
-
-typedef enum {
-  ZIX_STATUS_SUCCESS,
-  ZIX_STATUS_ERROR,
-  ZIX_STATUS_NO_MEM,
-  ZIX_STATUS_NOT_FOUND,
-  ZIX_STATUS_EXISTS,
-  ZIX_STATUS_BAD_ARG,
-  ZIX_STATUS_BAD_PERMS
-} ZixStatus;
-
-static inline const char*
-zix_strerror(const ZixStatus status)
-{
-  switch (status) {
-  case ZIX_STATUS_SUCCESS:
-    return "Success";
-  case ZIX_STATUS_ERROR:
-    return "Unknown error";
-  case ZIX_STATUS_NO_MEM:
-    return "Out of memory";
-  case ZIX_STATUS_NOT_FOUND:
-    return "Not found";
-  case ZIX_STATUS_EXISTS:
-    return "Exists";
-  case ZIX_STATUS_BAD_ARG:
-    return "Bad argument";
-  case ZIX_STATUS_BAD_PERMS:
-    return "Bad permissions";
-  }
-  return "Unknown error";
-}
-
-/**
-   Function for comparing two elements.
-*/
-typedef int (*ZixComparator)(const void* a,
-                             const void* b,
-                             const 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)(void* ptr);
-
-/**
-   @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_COMMON_H */
diff --git a/src/zix/tree.c b/src/zix/tree.c
deleted file mode 100644
index 9e4ed1c..0000000
--- a/src/zix/tree.c
+++ /dev/null
@@ -1,716 +0,0 @@
-// Copyright 2011-2020 David Robillard <d@drobilla.net>
-// SPDX-License-Identifier: ISC
-
-#include "zix/tree.h"
-
-#include "zix/common.h"
-
-#include <assert.h>
-#include <stdlib.h>
-#include <string.h>
-
-typedef struct ZixTreeNodeImpl ZixTreeNode;
-
-struct ZixTreeImpl {
-  ZixTreeNode*   root;
-  ZixDestroyFunc destroy;
-  ZixComparator  cmp;
-  void*          cmp_data;
-  size_t         size;
-  bool           allow_duplicates;
-};
-
-struct ZixTreeNodeImpl {
-  void*                   data;
-  struct ZixTreeNodeImpl* left;
-  struct ZixTreeNodeImpl* right;
-  struct ZixTreeNodeImpl* parent;
-  int                     balance;
-};
-
-#define MIN(a, b) (((a) < (b)) ? (a) : (b))
-#define MAX(a, b) (((a) > (b)) ? (a) : (b))
-
-// Uncomment these for debugging features
-// #define ZIX_TREE_DUMP         1
-// #define ZIX_TREE_VERIFY       1
-// #define ZIX_TREE_HYPER_VERIFY 1
-
-#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY)
-#  include "tree_debug.h"
-#  define ASSERT_BALANCE(n) assert(verify_balance(n))
-#else
-#  define ASSERT_BALANCE(n)
-#endif
-
-#ifdef ZIX_TREE_DUMP
-#  include "tree_debug.h"
-#  define DUMP(t) zix_tree_print(t->root, 0)
-#  define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
-#else
-#  define DUMP(t)
-#  define DEBUG_PRINTF(fmt, ...)
-#endif
-
-ZixTree*
-zix_tree_new(bool           allow_duplicates,
-             ZixComparator  cmp,
-             void*          cmp_data,
-             ZixDestroyFunc destroy)
-{
-  ZixTree* t          = (ZixTree*)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(ZixTree* t, ZixTreeNode* n)
-{
-  if (n) {
-    zix_tree_free_rec(t, n->left);
-    zix_tree_free_rec(t, n->right);
-    if (t->destroy) {
-      t->destroy(n->data);
-    }
-    free(n);
-  }
-}
-
-void
-zix_tree_free(ZixTree* t)
-{
-  if (t) {
-    zix_tree_free_rec(t, t->root);
-    free(t);
-  }
-}
-
-size_t
-zix_tree_size(const ZixTree* t)
-{
-  return t->size;
-}
-
-static void
-rotate(ZixTreeNode* p, ZixTreeNode* q)
-{
-  assert(q->parent == p);
-  assert(p->left == q || p->right == q);
-
-  q->parent = p->parent;
-  if (q->parent) {
-    if (q->parent->left == p) {
-      q->parent->left = q;
-    } else {
-      q->parent->right = q;
-    }
-  }
-
-  if (p->right == q) {
-    // Rotate left
-    p->right = q->left;
-    q->left  = p;
-    if (p->right) {
-      p->right->parent = p;
-    }
-  } else {
-    // Rotate right
-    assert(p->left == q);
-    p->left  = q->right;
-    q->right = p;
-    if (p->left) {
-      p->left->parent = p;
-    }
-  }
-
-  p->parent = q;
-}
-
-/**
- * Rotate left about `p`.
- *
- *    p              q
- *   / \            / \
- *  A   q    =>    p   C
- *     / \        / \
- *    B   C      A   B
- */
-static ZixTreeNode*
-rotate_left(ZixTreeNode* p, int* height_change)
-{
-  ZixTreeNode* const q = p->right;
-  *height_change       = (q->balance == 0) ? 0 : -1;
-
-  DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data);
-
-  assert(p->balance == 2);
-  assert(q->balance == 0 || q->balance == 1);
-
-  rotate(p, q);
-
-  // p->balance -= 1 + MAX(0, q->balance);
-  // q->balance -= 1 - MIN(0, p->balance);
-  --q->balance;
-  p->balance = -(q->balance);
-
-  ASSERT_BALANCE(p);
-  ASSERT_BALANCE(q);
-  return q;
-}
-
-/**
- * Rotate right about `p`.
- *
- *      p          q
- *     / \        / \
- *    q   C  =>  A   p
- *   / \            / \
- *  A   B          B   C
- *
- */
-static ZixTreeNode*
-rotate_right(ZixTreeNode* p, int* height_change)
-{
-  ZixTreeNode* const q = p->left;
-  *height_change       = (q->balance == 0) ? 0 : -1;
-
-  DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data);
-
-  assert(p->balance == -2);
-  assert(q->balance == 0 || q->balance == -1);
-
-  rotate(p, q);
-
-  // p->balance += 1 - MIN(0, q->balance);
-  // q->balance += 1 + MAX(0, p->balance);
-  ++q->balance;
-  p->balance = -(q->balance);
-
-  ASSERT_BALANCE(p);
-  ASSERT_BALANCE(q);
-  return q;
-}
-
-/**
- * Rotate left about `p->left` then right about `p`.
- *
- *      p             r
- *     / \           / \
- *    q   D  =>    q     p
- *   / \          / \   / \
- *  A   r        A   B C   D
- *     / \
- *    B   C
- *
- */
-static ZixTreeNode*
-rotate_left_right(ZixTreeNode* p, int* height_change)
-{
-  ZixTreeNode* const q = p->left;
-  ZixTreeNode* const r = q->right;
-
-  assert(p->balance == -2);
-  assert(q->balance == 1);
-  assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
-
-  DEBUG_PRINTF("LR %ld  P: %2d  Q: %2d  R: %2d\n",
-               (intptr_t)p->data,
-               p->balance,
-               q->balance,
-               r->balance);
-
-  rotate(q, r);
-  rotate(p, r);
-
-  q->balance -= 1 + MAX(0, r->balance);
-  p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
-  // r->balance += MAX(0, p->balance) + MIN(0, q->balance);
-
-  // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0;
-  // q->balance = - MAX(r->balance, 0);
-  r->balance = 0;
-
-  *height_change = -1;
-
-  ASSERT_BALANCE(p);
-  ASSERT_BALANCE(q);
-  ASSERT_BALANCE(r);
-  return r;
-}
-
-/**
- * Rotate right about `p->right` then right about `p`.
- *
- *    p               r
- *   / \             / \
- *  A   q    =>    p     q
- *     / \        / \   / \
- *    r   D      A   B C   D
- *   / \
- *  B   C
- *
- */
-static ZixTreeNode*
-rotate_right_left(ZixTreeNode* p, int* height_change)
-{
-  ZixTreeNode* const q = p->right;
-  ZixTreeNode* const r = q->left;
-
-  assert(p->balance == 2);
-  assert(q->balance == -1);
-  assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
-
-  DEBUG_PRINTF("RL %ld  P: %2d  Q: %2d  R: %2d\n",
-               (intptr_t)p->data,
-               p->balance,
-               q->balance,
-               r->balance);
-
-  rotate(q, r);
-  rotate(p, r);
-
-  q->balance += 1 - MIN(0, r->balance);
-  p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
-  // r->balance += MAX(0, q->balance) + MIN(0, p->balance);
-
-  // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0;
-  // q->balance = - MIN(r->balance, 0);
-  r->balance = 0;
-  // assert(r->balance == 0);
-
-  *height_change = -1;
-
-  ASSERT_BALANCE(p);
-  ASSERT_BALANCE(q);
-  ASSERT_BALANCE(r);
-  return r;
-}
-
-static ZixTreeNode*
-zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
-{
-#ifdef ZIX_TREE_HYPER_VERIFY
-  const size_t old_height = height(node);
-#endif
-  DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance);
-  *height_change     = 0;
-  const bool is_root = !node->parent;
-  assert((is_root && t->root == node) || (!is_root && t->root != node));
-  ZixTreeNode* replacement = node;
-  if (node->balance == -2) {
-    assert(node->left);
-    if (node->left->balance == 1) {
-      replacement = rotate_left_right(node, height_change);
-    } else {
-      replacement = rotate_right(node, height_change);
-    }
-  } else if (node->balance == 2) {
-    assert(node->right);
-    if (node->right->balance == -1) {
-      replacement = rotate_right_left(node, height_change);
-    } else {
-      replacement = rotate_left(node, height_change);
-    }
-  }
-  if (is_root) {
-    assert(!replacement->parent);
-    t->root = replacement;
-  }
-  DUMP(t);
-#ifdef ZIX_TREE_HYPER_VERIFY
-  assert(old_height + *height_change == height(replacement));
-#endif
-  return replacement;
-}
-
-ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
-{
-  DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
-  int          cmp = 0;
-  ZixTreeNode* n   = t->root;
-  ZixTreeNode* p   = NULL;
-
-  // Find the parent p of e
-  while (n) {
-    p   = n;
-    cmp = t->cmp(e, n->data, t->cmp_data);
-    if (cmp < 0) {
-      n = n->left;
-    } else if (cmp > 0 || t->allow_duplicates) {
-      n = n->right;
-    } else {
-      if (ti) {
-        *ti = n;
-      }
-      DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
-      return ZIX_STATUS_EXISTS;
-    }
-  }
-
-  // Allocate a new node n
-  if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) {
-    return ZIX_STATUS_NO_MEM;
-  }
-  memset(n, '\0', sizeof(ZixTreeNode));
-  n->data    = e;
-  n->balance = 0;
-  if (ti) {
-    *ti = n;
-  }
-
-  bool p_height_increased = false;
-
-  // Make p the parent of n
-  n->parent = p;
-  if (!p) {
-    t->root = n;
-  } else {
-    if (cmp < 0) {
-      assert(!p->left);
-      assert(p->balance == 0 || p->balance == 1);
-      p->left = n;
-      --p->balance;
-      p_height_increased = !p->right;
-    } else {
-      assert(!p->right);
-      assert(p->balance == 0 || p->balance == -1);
-      p->right = n;
-      ++p->balance;
-      p_height_increased = !p->left;
-    }
-  }
-
-  DUMP(t);
-
-  // Rebalance if necessary (at most 1 rotation)
-  assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
-  if (p && p_height_increased) {
-    int height_change = 0;
-    for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
-      if (i == i->parent->left) {
-        if (--i->parent->balance == -2) {
-          zix_tree_rebalance(t, i->parent, &height_change);
-          break;
-        }
-      } else {
-        assert(i == i->parent->right);
-        if (++i->parent->balance == 2) {
-          zix_tree_rebalance(t, i->parent, &height_change);
-          break;
-        }
-      }
-
-      if (i->parent->balance == 0) {
-        break;
-      }
-    }
-  }
-
-  DUMP(t);
-
-  ++t->size;
-
-#ifdef ZIX_TREE_VERIFY
-  if (!verify(t, t->root)) {
-    return ZIX_STATUS_ERROR;
-  }
-#endif
-
-  return ZIX_STATUS_SUCCESS;
-}
-
-ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
-{
-  ZixTreeNode* const n          = ti;
-  ZixTreeNode**      pp         = NULL;      // parent pointer
-  ZixTreeNode*       to_balance = n->parent; // lowest node to balance
-  int                d_balance  = 0;         // delta(balance) for n->parent
-
-  DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
-
-  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;
-  }
-
-  // Set pp to the parent pointer to n, if applicable
-  if (n->parent) {
-    assert(n->parent->left == n || n->parent->right == n);
-    if (n->parent->left == n) { // n is left child
-      pp        = &n->parent->left;
-      d_balance = 1;
-    } else { // n is right child
-      assert(n->parent->right == n);
-      pp        = &n->parent->right;
-      d_balance = -1;
-    }
-  }
-
-  assert(!pp || *pp == n);
-
-  int height_change = 0;
-  if (!n->left && !n->right) {
-    // n is a leaf, just remove it
-    if (pp) {
-      *pp           = NULL;
-      to_balance    = n->parent;
-      height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
-    }
-
-  } else if (!n->left) {
-    // Replace n with right (only) child
-    if (pp) {
-      *pp        = n->right;
-      to_balance = n->parent;
-    } else {
-      t->root = n->right;
-    }
-    n->right->parent = n->parent;
-    height_change    = -1;
-
-  } else if (!n->right) {
-    // Replace n with left (only) child
-    if (pp) {
-      *pp        = n->left;
-      to_balance = n->parent;
-    } else {
-      t->root = n->left;
-    }
-    n->left->parent = n->parent;
-    height_change   = -1;
-
-  } else {
-    // Replace n with in-order successor (leftmost child of right subtree)
-    ZixTreeNode* replace = n->right;
-    while (replace->left) {
-      assert(replace->left->parent == replace);
-      replace = replace->left;
-    }
-
-    // Remove replace from parent (replace_p)
-    if (replace->parent->left == replace) {
-      height_change         = replace->parent->right ? 0 : -1;
-      d_balance             = 1;
-      to_balance            = replace->parent;
-      replace->parent->left = replace->right;
-    } else {
-      assert(replace->parent == n);
-      height_change          = replace->parent->left ? 0 : -1;
-      d_balance              = -1;
-      to_balance             = replace->parent;
-      replace->parent->right = replace->right;
-    }
-
-    if (to_balance == n) {
-      to_balance = replace;
-    }
-
-    if (replace->right) {
-      replace->right->parent = replace->parent;
-    }
-
-    replace->balance = n->balance;
-
-    // Swap node to delete with replace
-    if (pp) {
-      *pp = replace;
-    } else {
-      assert(t->root == n);
-      t->root = replace;
-    }
-
-    replace->parent = n->parent;
-    replace->left   = n->left;
-    n->left->parent = replace;
-    replace->right  = n->right;
-    if (n->right) {
-      n->right->parent = replace;
-    }
-
-    assert(!replace->parent || replace->parent->left == replace ||
-           replace->parent->right == replace);
-  }
-
-  // Rebalance starting at to_balance upwards.
-  for (ZixTreeNode* i = to_balance; i; i = i->parent) {
-    i->balance += d_balance;
-    if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
-      break;
-    }
-
-    assert(i != n);
-    i = zix_tree_rebalance(t, i, &height_change);
-    if (i->balance == 0) {
-      height_change = -1;
-    }
-
-    if (i->parent) {
-      if (i == i->parent->left) {
-        d_balance = height_change * -1;
-      } else {
-        assert(i == i->parent->right);
-        d_balance = height_change;
-      }
-    }
-  }
-
-  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;
-  }
-#endif
-
-  return ZIX_STATUS_SUCCESS;
-}
-
-ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
-{
-  ZixTreeNode* n = t->root;
-  while (n) {
-    const int cmp = t->cmp(e, n->data, t->cmp_data);
-    if (cmp == 0) {
-      break;
-    }
-
-    if (cmp < 0) {
-      n = n->left;
-    } else {
-      n = n->right;
-    }
-  }
-
-  *ti = n;
-  return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-}
-
-void*
-zix_tree_get(const ZixTreeIter* ti)
-{
-  return ti ? ti->data : NULL;
-}
-
-ZixTreeIter*
-zix_tree_begin(ZixTree* t)
-{
-  if (!t->root) {
-    return NULL;
-  }
-
-  ZixTreeNode* n = t->root;
-  while (n->left) {
-    n = n->left;
-  }
-
-  return n;
-}
-
-ZixTreeIter*
-zix_tree_end(ZixTree* t)
-{
-  (void)t;
-  return NULL;
-}
-
-ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
-{
-  if (!t->root) {
-    return NULL;
-  }
-
-  ZixTreeNode* n = t->root;
-  while (n->right) {
-    n = n->right;
-  }
-
-  return n;
-}
-
-ZixTreeIter*
-zix_tree_rend(ZixTree* t)
-{
-  (void)t;
-  return NULL;
-}
-
-bool
-zix_tree_iter_is_end(const ZixTreeIter* i)
-{
-  return !i;
-}
-
-bool
-zix_tree_iter_is_rend(const ZixTreeIter* i)
-{
-  return !i;
-}
-
-ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i)
-{
-  if (!i) {
-    return NULL;
-  }
-
-  if (i->right) {
-    i = i->right;
-    while (i->left) {
-      i = i->left;
-    }
-  } else {
-    while (i->parent && i->parent->right == i) { // i is a right child
-      i = i->parent;
-    }
-
-    i = i->parent;
-  }
-
-  return i;
-}
-
-ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i)
-{
-  if (!i) {
-    return NULL;
-  }
-
-  if (i->left) {
-    i = i->left;
-    while (i->right) {
-      i = i->right;
-    }
-
-  } else {
-    while (i->parent && i->parent->left == i) { // i is a left child
-      i = i->parent;
-    }
-
-    i = i->parent;
-  }
-
-  return i;
-}
diff --git a/src/zix/tree.h b/src/zix/tree.h
deleted file mode 100644
index 9fc968f..0000000
--- a/src/zix/tree.h
+++ /dev/null
@@ -1,151 +0,0 @@
-// Copyright 2011-2020 David Robillard <d@drobilla.net>
-// SPDX-License-Identifier: ISC
-
-#ifndef ZIX_TREE_H
-#define ZIX_TREE_H
-
-#include "zix/common.h"
-
-#include <stdbool.h>
-#include <stddef.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
-   @addtogroup zix
-   @{
-   @name Tree
-   @{
-*/
-
-/**
-   A balanced binary search tree.
-*/
-typedef struct ZixTreeImpl ZixTree;
-
-/**
-   An iterator over a @ref ZixTree.
-*/
-typedef struct ZixTreeNodeImpl ZixTreeIter;
-
-/**
-   Create a new (empty) tree.
-*/
-ZIX_API
-ZixTree*
-zix_tree_new(bool           allow_duplicates,
-             ZixComparator  cmp,
-             void*          cmp_data,
-             ZixDestroyFunc destroy);
-
-/**
-   Free `t`.
-*/
-ZIX_API
-void
-zix_tree_free(ZixTree* t);
-
-/**
-   Return the number of elements in `t`.
-*/
-ZIX_PURE_API
-size_t
-zix_tree_size(const ZixTree* t);
-
-/**
-   Insert the element `e` into `t` and point `ti` at the new element.
-*/
-ZIX_API
-ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
-
-/**
-   Remove the item pointed at by `ti` from `t`.
-*/
-ZIX_API
-ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
-
-/**
-   Set `ti` to an element equal to `e` in `t`.
-   If no such item exists, `ti` is set to NULL.
-*/
-ZIX_API
-ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
-
-/**
-   Return the data associated with the given tree item.
-*/
-ZIX_PURE_API
-void*
-zix_tree_get(const ZixTreeIter* ti);
-
-/**
-   Return an iterator to the first (smallest) element in `t`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_begin(ZixTree* t);
-
-/**
-   Return an iterator the the element one past the last element in `t`.
-*/
-ZIX_CONST_API
-ZixTreeIter*
-zix_tree_end(ZixTree* t);
-
-/**
-   Return true iff `i` is an iterator to the end of its tree.
-*/
-ZIX_CONST_API
-bool
-zix_tree_iter_is_end(const ZixTreeIter* i);
-
-/**
-   Return an iterator to the last (largest) element in `t`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_rbegin(ZixTree* t);
-
-/**
-   Return an iterator the the element one before the first element in `t`.
-*/
-ZIX_CONST_API
-ZixTreeIter*
-zix_tree_rend(ZixTree* t);
-
-/**
-   Return true iff `i` is an iterator to the reverse end of its tree.
-*/
-ZIX_CONST_API
-bool
-zix_tree_iter_is_rend(const ZixTreeIter* i);
-
-/**
-   Return an iterator that points to the element one past `i`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i);
-
-/**
-   Return an iterator that points to the element one before `i`.
-*/
-ZIX_PURE_API
-ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i);
-
-/**
-   @}
-   @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_TREE_H */