summaryrefslogtreecommitdiffstats
path: root/src/zix
diff options
context:
space:
mode:
Diffstat (limited to 'src/zix')
-rw-r--r--src/zix/common.h7
-rw-r--r--src/zix/tree.c95
-rw-r--r--src/zix/tree.h30
3 files changed, 89 insertions, 43 deletions
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);
/**
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-11 08:38:48 +0000