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 --- zix/common.h | 54 ++++++++++++++++++++++++++++ zix/tree.h | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ zix/zix.h | 93 ++--------------------------------------------- 3 files changed, 172 insertions(+), 91 deletions(-) create mode 100644 zix/common.h create mode 100644 zix/tree.h (limited to 'zix') 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