From 37f824f48e8141cd039e5acb318f8e62a93498e3 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 10 Jan 2021 22:10:21 +0100 Subject: Update zix --- src/zix/common.h | 92 +++++++++++++++++++++++++++++++++++++++++++------------- src/zix/tree.c | 91 +++++++++++++++++++++++++++++-------------------------- src/zix/tree.h | 69 +++++++++++++++++++++++++----------------- 3 files changed, 161 insertions(+), 91 deletions(-) (limited to 'src/zix') diff --git a/src/zix/common.h b/src/zix/common.h index 51683c4..d47586c 100644 --- a/src/zix/common.h +++ b/src/zix/common.h @@ -1,5 +1,5 @@ /* - Copyright 2016 David Robillard + Copyright 2016-2020 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -17,39 +17,65 @@ #ifndef ZIX_COMMON_H #define ZIX_COMMON_H +#include + /** @addtogroup zix @{ */ /** @cond */ -#ifdef ZIX_SHARED -# ifdef _WIN32 -# define ZIX_LIB_IMPORT __declspec(dllimport) -# define ZIX_LIB_EXPORT __declspec(dllexport) -# else -# define ZIX_LIB_IMPORT __attribute__((visibility("default"))) -# define ZIX_LIB_EXPORT __attribute__((visibility("default"))) -# endif -# ifdef ZIX_INTERNAL -# define ZIX_API ZIX_LIB_EXPORT -# else -# define ZIX_API ZIX_LIB_IMPORT -# endif -# define ZIX_PRIVATE static -#elif defined(ZIX_INLINE) -# define ZIX_API static inline -# define ZIX_PRIVATE static inline +#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 -# define ZIX_PRIVATE static #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 -# include +# 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 { @@ -62,10 +88,34 @@ typedef enum { 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, void* user_data); +typedef int (*ZixComparator)(const void* a, + const void* b, + const void* user_data); /** Function for testing equality of two elements. diff --git a/src/zix/tree.c b/src/zix/tree.c index 658cafc..9faf13c 100644 --- a/src/zix/tree.c +++ b/src/zix/tree.c @@ -1,5 +1,5 @@ /* - Copyright 2011-2019 David Robillard + Copyright 2011-2020 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -15,10 +15,10 @@ */ #include "zix/tree.h" + #include "zix/common.h" #include -#include #include #include @@ -38,7 +38,7 @@ struct ZixTreeNodeImpl { struct ZixTreeNodeImpl* left; struct ZixTreeNodeImpl* right; struct ZixTreeNodeImpl* parent; - int_fast8_t balance; + int balance; }; #define MIN(a, b) (((a) < (b)) ? (a) : (b)) @@ -65,11 +65,11 @@ struct ZixTreeNodeImpl { # define DEBUG_PRINTF(fmt, ...) #endif -ZIX_API ZixTree* - zix_tree_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy) +ZixTree* +zix_tree_new(bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy) { ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree)); t->root = NULL; @@ -81,7 +81,7 @@ ZIX_API ZixTree* return t; } -ZIX_PRIVATE void +static void zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) { if (n) { @@ -94,7 +94,7 @@ zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) } } -ZIX_API void +void zix_tree_free(ZixTree* t) { if (t) { @@ -103,13 +103,13 @@ zix_tree_free(ZixTree* t) } } -ZIX_API size_t +size_t zix_tree_size(const ZixTree* t) { return t->size; } -ZIX_PRIVATE void +static void rotate(ZixTreeNode* p, ZixTreeNode* q) { assert(q->parent == p); @@ -153,8 +153,8 @@ rotate(ZixTreeNode* p, ZixTreeNode* q) * / \ / \ * B C A B */ -ZIX_PRIVATE ZixTreeNode* - rotate_left(ZixTreeNode* p, int* height_change) +static ZixTreeNode* +rotate_left(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->right; *height_change = (q->balance == 0) ? 0 : -1; @@ -186,8 +186,8 @@ ZIX_PRIVATE ZixTreeNode* * A B B C * */ -ZIX_PRIVATE ZixTreeNode* - rotate_right(ZixTreeNode* p, int* height_change) +static ZixTreeNode* +rotate_right(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->left; *height_change = (q->balance == 0) ? 0 : -1; @@ -221,8 +221,8 @@ ZIX_PRIVATE ZixTreeNode* * B C * */ -ZIX_PRIVATE ZixTreeNode* - rotate_left_right(ZixTreeNode* p, int* height_change) +static ZixTreeNode* +rotate_left_right(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->left; ZixTreeNode* const r = q->right; @@ -268,8 +268,8 @@ ZIX_PRIVATE ZixTreeNode* * B C * */ -ZIX_PRIVATE ZixTreeNode* - rotate_right_left(ZixTreeNode* p, int* height_change) +static ZixTreeNode* +rotate_right_left(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->right; ZixTreeNode* const r = q->left; @@ -304,7 +304,7 @@ ZIX_PRIVATE ZixTreeNode* return r; } -ZIX_PRIVATE ZixTreeNode* +static ZixTreeNode* zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) { #ifdef ZIX_TREE_HYPER_VERIFY @@ -341,7 +341,7 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) return replacement; } -ZIX_API ZixStatus +ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) { DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); @@ -355,9 +355,7 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) cmp = t->cmp(e, n->data, t->cmp_data); if (cmp < 0) { n = n->left; - } else if (cmp > 0) { - n = n->right; - } else if (t->allow_duplicates) { + } else if (cmp > 0 || t->allow_duplicates) { n = n->right; } else { if (ti) { @@ -440,13 +438,13 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) return ZIX_STATUS_SUCCESS; } -ZIX_API ZixStatus +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 - int8_t d_balance = 0; // delta(balance) for n->parent + int d_balance = 0; // delta(balance) for n->parent DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data); @@ -484,6 +482,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) 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) { @@ -494,6 +493,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) } n->right->parent = n->parent; height_change = -1; + } else if (!n->right) { // Replace n with left (only) child if (pp) { @@ -504,6 +504,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) } n->left->parent = n->parent; height_change = -1; + } else { // Replace n with in-order successor (leftmost child of right subtree) ZixTreeNode* replace = n->right; @@ -543,6 +544,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) assert(t->root == n); t->root = replace; } + replace->parent = n->parent; replace->left = n->left; n->left->parent = replace; @@ -596,7 +598,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) return ZIX_STATUS_SUCCESS; } -ZIX_API ZixStatus +ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) { ZixTreeNode* n = t->root; @@ -617,14 +619,14 @@ zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; } -ZIX_API void* +void* zix_tree_get(const ZixTreeIter* ti) { return ti ? ti->data : NULL; } -ZIX_API ZixTreeIter* - zix_tree_begin(ZixTree* t) +ZixTreeIter* +zix_tree_begin(ZixTree* t) { if (!t->root) { return NULL; @@ -634,17 +636,18 @@ ZIX_API ZixTreeIter* while (n->left) { n = n->left; } + return n; } -ZIX_API ZixTreeIter* - zix_tree_end(ZixTree* t) +ZixTreeIter* +zix_tree_end(ZixTree* ZIX_UNUSED(t)) { return NULL; } -ZIX_API ZixTreeIter* - zix_tree_rbegin(ZixTree* t) +ZixTreeIter* +zix_tree_rbegin(ZixTree* t) { if (!t->root) { return NULL; @@ -654,29 +657,30 @@ ZIX_API ZixTreeIter* while (n->right) { n = n->right; } + return n; } -ZIX_API ZixTreeIter* - zix_tree_rend(ZixTree* t) +ZixTreeIter* +zix_tree_rend(ZixTree* ZIX_UNUSED(t)) { return NULL; } -ZIX_API bool +bool zix_tree_iter_is_end(const ZixTreeIter* i) { return !i; } -ZIX_API bool +bool zix_tree_iter_is_rend(const ZixTreeIter* i) { return !i; } -ZIX_API ZixTreeIter* - zix_tree_iter_next(ZixTreeIter* i) +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i) { if (!i) { return NULL; @@ -698,8 +702,8 @@ ZIX_API ZixTreeIter* return i; } -ZIX_API ZixTreeIter* - zix_tree_iter_prev(ZixTreeIter* i) +ZixTreeIter* +zix_tree_iter_prev(ZixTreeIter* i) { if (!i) { return NULL; @@ -710,6 +714,7 @@ ZIX_API ZixTreeIter* while (i->right) { i = i->right; } + } else { while (i->parent && i->parent->left == i) { // i is a left child i = i->parent; diff --git a/src/zix/tree.h b/src/zix/tree.h index 15ad105..a2d5fe7 100644 --- a/src/zix/tree.h +++ b/src/zix/tree.h @@ -1,5 +1,5 @@ /* - Copyright 2011-2019 David Robillard + Copyright 2011-2020 David Robillard Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above @@ -39,103 +39,118 @@ extern "C" { typedef struct ZixTreeImpl ZixTree; /** - An iterator over a 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); +ZIX_API +ZixTree* +zix_tree_new(bool allow_duplicates, + ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy); /** Free `t`. */ -ZIX_API void +ZIX_API +void zix_tree_free(ZixTree* t); /** Return the number of elements in `t`. */ -ZIX_API size_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_API +ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); /** Remove the item pointed at by `ti` from `t`. */ -ZIX_API ZixStatus +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_API +ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); /** Return the data associated with the given tree item. */ -ZIX_API void* +ZIX_PURE_API +void* zix_tree_get(const ZixTreeIter* ti); /** Return an iterator to the first (smallest) element in `t`. */ -ZIX_API ZixTreeIter* - zix_tree_begin(ZixTree* t); +ZIX_PURE_API +ZixTreeIter* +zix_tree_begin(ZixTree* t); /** Return an iterator the the element one past the last element in `t`. */ -ZIX_API ZixTreeIter* - zix_tree_end(ZixTree* t); +ZIX_CONST_API +ZixTreeIter* +zix_tree_end(ZixTree* t); /** Return true iff `i` is an iterator to the end of its tree. */ -ZIX_API bool +ZIX_CONST_API +bool zix_tree_iter_is_end(const ZixTreeIter* i); /** Return an iterator to the last (largest) element in `t`. */ -ZIX_API ZixTreeIter* - zix_tree_rbegin(ZixTree* t); +ZIX_PURE_API +ZixTreeIter* +zix_tree_rbegin(ZixTree* t); /** Return an iterator the the element one before the first element in `t`. */ -ZIX_API ZixTreeIter* - zix_tree_rend(ZixTree* 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_API bool +ZIX_CONST_API +bool zix_tree_iter_is_rend(const ZixTreeIter* i); /** Return an iterator that points to the element one past `i`. */ -ZIX_API ZixTreeIter* - zix_tree_iter_next(ZixTreeIter* i); +ZIX_PURE_API +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i); /** Return an iterator that points to the element one before `i`. */ -ZIX_API ZixTreeIter* - zix_tree_iter_prev(ZixTreeIter* i); +ZIX_PURE_API +ZixTreeIter* +zix_tree_iter_prev(ZixTreeIter* i); /** @} -- cgit v1.2.1