From e8f41104c807804d2a8ca6fc14b0e826e70b248b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 9 Aug 2012 03:53:13 +0000 Subject: Update zix. Fix --static-progs. git-svn-id: http://svn.drobilla.net/lad/trunk/lilv@4636 a436a847-0d15-0410-975c-d299462d15a1 --- src/zix/common.h | 7 +++++ src/zix/tree.c | 95 +++++++++++++++++++++++++++++++++++++++----------------- src/zix/tree.h | 30 +++++++++--------- 3 files changed, 89 insertions(+), 43 deletions(-) (limited to 'src') diff --git a/src/zix/common.h b/src/zix/common.h index ab7e431..f126cd1 100644 --- a/src/zix/common.h +++ b/src/zix/common.h @@ -36,8 +36,13 @@ # 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 #else # define ZIX_API +# define ZIX_PRIVATE static #endif /** @endcond */ @@ -53,6 +58,8 @@ typedef enum { ZIX_STATUS_NO_MEM, ZIX_STATUS_NOT_FOUND, ZIX_STATUS_EXISTS, + ZIX_STATUS_BAD_ARG, + ZIX_STATUS_BAD_PERMS, } ZixStatus; /** diff --git a/src/zix/tree.c b/src/zix/tree.c index dd6be5d..844adb9 100644 --- a/src/zix/tree.c +++ b/src/zix/tree.c @@ -66,8 +66,7 @@ struct ZixTreeNodeImpl { # define DEBUG_PRINTF(fmt, ...) #endif -ZIX_API -ZixTree* +ZIX_API ZixTree* zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, @@ -83,7 +82,7 @@ zix_tree_new(bool allow_duplicates, return t; } -static void +ZIX_PRIVATE void zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) { if (n) { @@ -96,8 +95,7 @@ zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) } } -ZIX_API -void +ZIX_API void zix_tree_free(ZixTree* t) { if (t) { @@ -106,13 +104,13 @@ zix_tree_free(ZixTree* t) } } -size_t +ZIX_API size_t zix_tree_size(const ZixTree* t) { return t->size; } -static void +ZIX_PRIVATE void rotate(ZixTreeNode* p, ZixTreeNode* q) { assert(q->parent == p); @@ -156,7 +154,7 @@ rotate(ZixTreeNode* p, ZixTreeNode* q) * / \ / \ * B C A B */ -static ZixTreeNode* +ZIX_PRIVATE ZixTreeNode* rotate_left(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->right; @@ -189,7 +187,7 @@ rotate_left(ZixTreeNode* p, int* height_change) * A B B C * */ -static ZixTreeNode* +ZIX_PRIVATE ZixTreeNode* rotate_right(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->left; @@ -224,7 +222,7 @@ rotate_right(ZixTreeNode* p, int* height_change) * B C * */ -static ZixTreeNode* +ZIX_PRIVATE ZixTreeNode* rotate_left_right(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->left; @@ -268,7 +266,7 @@ rotate_left_right(ZixTreeNode* p, int* height_change) * B C * */ -static ZixTreeNode* +ZIX_PRIVATE ZixTreeNode* rotate_right_left(ZixTreeNode* p, int* height_change) { ZixTreeNode* const q = p->right; @@ -301,7 +299,7 @@ rotate_right_left(ZixTreeNode* p, int* height_change) return r; } -static ZixTreeNode* +ZIX_PRIVATE ZixTreeNode* zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) { #ifdef ZIX_TREE_HYPER_VERIFY @@ -338,8 +336,7 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) return replacement; } -ZIX_API -ZixStatus +ZIX_API ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) { DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); @@ -438,8 +435,7 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) return ZIX_STATUS_SUCCESS; } -ZIX_API -ZixStatus +ZIX_API ZixStatus zix_tree_remove(ZixTree* t, ZixTreeIter* ti) { ZixTreeNode* const n = ti; @@ -596,8 +592,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti) return ZIX_STATUS_SUCCESS; } -ZIX_API -ZixStatus +ZIX_API ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) { ZixTreeNode* n = t->root; @@ -616,15 +611,13 @@ zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; } -ZIX_API -void* +ZIX_API void* zix_tree_get(ZixTreeIter* ti) { return ti ? ti->data : NULL; } -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_begin(ZixTree* t) { if (!t->root) { @@ -638,22 +631,45 @@ zix_tree_begin(ZixTree* t) return n; } -ZIX_API -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_end(ZixTree* t) { return NULL; } -ZIX_API -bool +ZIX_API ZixTreeIter* +zix_tree_rbegin(ZixTree* t) +{ + if (!t->root) { + return NULL; + } + + ZixTreeNode* n = t->root; + while (n->right) { + n = n->right; + } + return n; +} + +ZIX_API ZixTreeIter* +zix_tree_rend(ZixTree* t) +{ + return NULL; +} + +ZIX_API bool zix_tree_iter_is_end(ZixTreeIter* i) { return !i; } -ZIX_API -ZixTreeIter* +ZIX_API bool +zix_tree_iter_is_rend(ZixTreeIter* i) +{ + return !i; +} + +ZIX_API ZixTreeIter* zix_tree_iter_next(ZixTreeIter* i) { if (!i) { @@ -675,3 +691,26 @@ zix_tree_iter_next(ZixTreeIter* i) return i; } + +ZIX_API 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 index cb8c60d..f89d9e5 100644 --- a/src/zix/tree.h +++ b/src/zix/tree.h @@ -45,7 +45,7 @@ typedef struct ZixTreeNodeImpl ZixTreeIter; /** Create a new (empty) tree. */ -ZixTree* +ZIX_API ZixTree* zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, @@ -54,86 +54,86 @@ zix_tree_new(bool allow_duplicates, /** Free @a t. */ -void +ZIX_API void zix_tree_free(ZixTree* t); /** Return the number of elements in @a t. */ -size_t +ZIX_API size_t zix_tree_size(const ZixTree* t); /** Insert the element @a e into @a t and point @a ti at the new element. */ -ZixStatus +ZIX_API ZixStatus zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); /** Remove the item pointed at by @a ti from @a t. */ -ZixStatus +ZIX_API ZixStatus zix_tree_remove(ZixTree* t, ZixTreeIter* ti); /** Set @a ti to an element equal to @a e in @a t. If no such item exists, @a ti is set to NULL. */ -ZixStatus +ZIX_API ZixStatus zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); /** Return the data associated with the given tree item. */ -void* +ZIX_API void* zix_tree_get(ZixTreeIter* ti); /** Return an iterator to the first (smallest) element in @a t. */ -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_begin(ZixTree* t); /** Return an iterator the the element one past the last element in @a t. */ -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_end(ZixTree* t); /** Return true iff @a i is an iterator to the end of its tree. */ -bool +ZIX_API bool zix_tree_iter_is_end(ZixTreeIter* i); /** Return an iterator to the last (largest) element in @a t. */ -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_rbegin(ZixTree* t); /** Return an iterator the the element one before the first element in @a t. */ -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_rend(ZixTree* t); /** Return true iff @a i is an iterator to the reverse end of its tree. */ -bool +ZIX_API bool zix_tree_iter_is_rend(ZixTreeIter* i); /** Return an iterator that points to the element one past @a i. */ -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_iter_next(ZixTreeIter* i); /** Return an iterator that points to the element one before @a i. */ -ZixTreeIter* +ZIX_API ZixTreeIter* zix_tree_iter_prev(ZixTreeIter* i); /** -- cgit v1.2.1