From 9c129fa5ca61da479507d2598951f3fdacc1e143 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Mon, 5 Sep 2011 15:56:02 +0000 Subject: Separate tree functions into a separate header. Add tree iterator functions. git-svn-id: http://svn.drobilla.net/zix/trunk@2 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- src/tree.c | 53 +++++++++++++++++++++++++ test/tree_test.c | 29 +++++++++++--- wscript | 1 - zix/common.h | 54 ++++++++++++++++++++++++++ zix/tree.h | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ zix/zix.h | 93 +------------------------------------------- 6 files changed, 248 insertions(+), 98 deletions(-) create mode 100644 zix/common.h create mode 100644 zix/tree.h diff --git a/src/tree.c b/src/tree.c index 5d09680..d319f1d 100644 --- a/src/tree.c +++ b/src/tree.c @@ -722,3 +722,56 @@ zix_tree_get_data(ZixTreeIter ti) { return ti->data; } + +ZIX_API +ZixTreeIter +zix_tree_begin(ZixTree* t) +{ + if (!t->root) { + return NULL; + } + + ZixTreeNode* n = t->root; + while (n->left) { + n = n->left; + } + return n; +} + +ZIX_API +ZixTreeIter +zix_tree_end(ZixTree* t) +{ + return NULL; +} + +ZIX_API +bool +zix_tree_iter_is_end(ZixTreeIter i) +{ + return !i; +} + +ZIX_API +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; +} diff --git a/test/tree_test.c b/test/tree_test.c index d4fb283..656e718 100644 --- a/test/tree_test.c +++ b/test/tree_test.c @@ -65,7 +65,7 @@ stress(int test_num, size_t n_elems) srand(seed); // Insert n_elems elements - for (size_t i = 0; i < n_elems; i++) { + for (size_t i = 0; i < n_elems; ++i) { r = ith_elem(test_num, n_elems, i); int status = zix_tree_insert(t, (void*)r, &ti); if (status == ZIX_STATUS_EXISTS) { @@ -75,8 +75,8 @@ stress(int test_num, size_t n_elems) return test_fail(); } if ((intptr_t)zix_tree_get_data(ti) != r) { - fprintf(stderr, "Data is corrupted! Saw %" PRIdPTR ", expected %zu\n", - (intptr_t)zix_tree_get_data(ti), i); + fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + (intptr_t)zix_tree_get_data(ti), r); return test_fail(); } } @@ -84,15 +84,32 @@ stress(int test_num, size_t n_elems) srand(seed); // Search for all elements - for (size_t i = 0; i < n_elems; i++) { + for (size_t i = 0; i < n_elems; ++i) { r = ith_elem(test_num, n_elems, i); if (zix_tree_find(t, (void*)r, &ti)) { fprintf(stderr, "Find failed\n"); return test_fail(); } if ((intptr_t)zix_tree_get_data(ti) != r) { - fprintf(stderr, "Data corrupted (saw %" PRIdPTR ", expected %zu\n", - (intptr_t)zix_tree_get_data(ti), i); + fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + (intptr_t)zix_tree_get_data(ti), r); + return test_fail(); + } + } + + srand(seed); + + // Iterate over all elements + size_t i = 0; + intptr_t last = -1; + for (ZixTreeIter iter = zix_tree_begin(t); + !zix_tree_iter_is_end(iter); + iter = zix_tree_iter_next(iter), ++i) { + r = ith_elem(test_num, n_elems, i); + const intptr_t iter_data = (intptr_t)zix_tree_get_data(iter); + if (iter_data < last) { + fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %zu)\n", + iter_data, last); return test_fail(); } } diff --git a/wscript b/wscript index ec7f46a..2e48c03 100644 --- a/wscript +++ b/wscript @@ -65,7 +65,6 @@ def build(bld): lib_source = ''' src/tree.c - src/strindex.c ''' # Library diff --git a/zix/common.h b/zix/common.h new file mode 100644 index 0000000..dd86a8b --- /dev/null +++ b/zix/common.h @@ -0,0 +1,54 @@ +/* + Copyright 2011 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 + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#ifndef ZIX_COMMON_H +#define ZIX_COMMON_H + +/** + @addtogroup zix + @{ +*/ + +#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 +#else +# define ZIX_API +#endif + +typedef enum { + ZIX_STATUS_SUCCESS, + ZIX_STATUS_ERROR, + ZIX_STATUS_NO_MEM, + ZIX_STATUS_NOT_FOUND, + ZIX_STATUS_EXISTS, +} ZixStatus; + +/** + @} +*/ + +#endif /* ZIX_COMMON_H */ diff --git a/zix/tree.h b/zix/tree.h new file mode 100644 index 0000000..db628a6 --- /dev/null +++ b/zix/tree.h @@ -0,0 +1,116 @@ +/* + Copyright 2011 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 + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#ifndef ZIX_TREE_H +#define ZIX_TREE_H + +#include + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @addtogroup zix + @{ + @name Tree + @{ +*/ + +/** + Function for comparing two elements. +*/ +typedef int (*ZixComparator)(const void* a, const void* b, void* user_data); + +/** + A balanced binary search tree. +*/ +typedef struct _ZixTree ZixTree; + +/** + A node in a @ref ZixTree. +*/ +typedef struct _ZixTreeNode ZixTreeNode; + +/** + An iterator over a @ref ZixTree. +*/ +typedef ZixTreeNode* ZixTreeIter; + +/** + Create a new (empty) tree. +*/ +ZixTree* +zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data); + +/** + Free @a t. +*/ +void +zix_tree_free(ZixTree* t); + +/** + Insert the element @a e into @a t and point @a ti at the new element. +*/ +int +zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti); + +/** + Remove the item pointed at by @a ti from @a t. +*/ +int +zix_tree_remove(ZixTree* t, ZixTreeIter ti); + +/** + Set @a ti to be the largest element <= @a e in @a t. + If no such item exists, @a ti is set to NULL. +*/ +int +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti); + +/** + Return the data associated with the given avltree item. +*/ +const void* +zix_tree_get_data(ZixTreeIter ti); + +/** + Return an iterator to the first (smallest) element in @a t. +*/ +ZixTreeIter +zix_tree_begin(ZixTree* t); + +ZixTreeIter +zix_tree_end(ZixTree* t); + +bool +zix_tree_iter_is_end(ZixTreeIter i); + +ZixTreeIter +zix_tree_iter_next(ZixTreeIter i); + +/** + @} + @} +*/ + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_TREE_H */ diff --git a/zix/zix.h b/zix/zix.h index a264b43..12a19bc 100644 --- a/zix/zix.h +++ b/zix/zix.h @@ -17,105 +17,16 @@ #ifndef ZIX_ZIX_H #define ZIX_ZIX_H -#include - -#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 -#else -# define ZIX_API -#endif - -#ifdef __cplusplus -extern "C" { -#endif - /** @defgroup zix Zix A lightweight portability library. @{ */ -/** - @name Tree - @{ -*/ - -#define ZIX_STATUS_SUCCESS 0 -#define ZIX_STATUS_ERROR 1 -#define ZIX_STATUS_NO_MEM 2 -#define ZIX_STATUS_NOT_FOUND 3 -#define ZIX_STATUS_EXISTS 4 - -/** - Function for comparing two elements. -*/ -typedef int (*ZixComparator)(const void* a, const void* b, void* user_data); - -/** - A balanced binary search tree. -*/ -typedef struct _ZixTree ZixTree; - -/** - A node in a @ref ZixTree. -*/ -typedef struct _ZixTreeNode ZixTreeNode; - -/** - An iterator over a @ref ZixTree. -*/ -typedef ZixTreeNode* ZixTreeIter; - -/** - Create a new (empty) tree. -*/ -ZixTree* -zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data); - -/** - Free @a t. -*/ -void -zix_tree_free(ZixTree* t); - -/** - Insert the element @a e into @a t and point @a ti at the new element. -*/ -int -zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti); +#include "zix/common.h" +#include "zix/tree.h" /** - Remove the item pointed at by @a ti from @a t. -*/ -int -zix_tree_remove(ZixTree* t, ZixTreeIter ti); - -/** - Set @a ti to be the largest element <= @a e in @a t. - If no such item exists, @a ti is set to NULL. -*/ -int -zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti); - -/** - Return the data associated with the given avltree item. -*/ -const void* -zix_tree_get_data(ZixTreeIter ti); - -/** - @} @} */ -- cgit v1.2.1