From 2c309084f8b96f637c204aabb5e8edad3162ba05 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Tue, 1 Nov 2022 23:16:39 -0400 Subject: Switch to external zix dependency --- meson.build | 7 +- src/collections.c | 24 +- src/pluginclass.c | 5 +- src/port.c | 9 +- src/state.c | 7 +- src/world.c | 17 +- src/zix/common.h | 125 ---------- src/zix/tree.c | 716 ------------------------------------------------------ src/zix/tree.h | 151 ------------ 9 files changed, 44 insertions(+), 1017 deletions(-) delete mode 100644 src/zix/common.h delete mode 100644 src/zix/tree.c delete mode 100644 src/zix/tree.h 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 #include +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 -// SPDX-License-Identifier: ISC - -#ifndef ZIX_COMMON_H -#define ZIX_COMMON_H - -#include - -/** - @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 -// SPDX-License-Identifier: ISC - -#include "zix/tree.h" - -#include "zix/common.h" - -#include -#include -#include - -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 -// SPDX-License-Identifier: ISC - -#ifndef ZIX_TREE_H -#define ZIX_TREE_H - -#include "zix/common.h" - -#include -#include - -#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 */ -- cgit v1.2.1