summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2022-11-01 23:16:39 -0400
committerDavid Robillard <d@drobilla.net>2022-11-16 10:22:53 -0500
commit2c309084f8b96f637c204aabb5e8edad3162ba05 (patch)
treec2f77a138eb648dae5d3b739c371aa2257518315
parentea4d4090c53ae0166f99e6af7f232705e8dc1641 (diff)
downloadlilv-2c309084f8b96f637c204aabb5e8edad3162ba05.tar.gz
lilv-2c309084f8b96f637c204aabb5e8edad3162ba05.tar.bz2
lilv-2c309084f8b96f637c204aabb5e8edad3162ba05.zip
Switch to external zix dependency
-rw-r--r--meson.build7
-rw-r--r--src/collections.c24
-rw-r--r--src/pluginclass.c5
-rw-r--r--src/port.c9
-rw-r--r--src/state.c7
-rw-r--r--src/world.c17
-rw-r--r--src/zix/common.h125
-rw-r--r--src/zix/tree.c716
-rw-r--r--src/zix/tree.h151
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 */