summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/sord.c11
-rw-r--r--src/zix/common.h12
-rw-r--r--src/zix/hash.c81
-rw-r--r--src/zix/hash.h24
-rw-r--r--src/zix/tree.c209
-rw-r--r--src/zix/tree.h53
6 files changed, 274 insertions, 116 deletions
diff --git a/src/sord.c b/src/sord.c
index f0f3428..bd68d65 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -22,7 +22,10 @@
#include <stdlib.h>
#include <string.h>
+#define ZIX_INLINE
+#include "zix/hash.c"
#include "zix/hash.h"
+#include "zix/tree.c"
#include "zix/tree.h"
#include "sord_config.h"
@@ -640,10 +643,10 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
if (indices & (1 << i)) {
sord->indices[i] = zix_tree_new(
- false, sord_quad_compare, (void*)ordering);
+ false, sord_quad_compare, (void*)ordering, NULL);
if (graphs) {
sord->indices[i + (NUM_ORDERS / 2)] = zix_tree_new(
- false, sord_quad_compare, (void*)g_ordering);
+ false, sord_quad_compare, (void*)g_ordering, NULL);
} else {
sord->indices[i + (NUM_ORDERS / 2)] = NULL;
}
@@ -655,11 +658,11 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
if (!sord->indices[DEFAULT_ORDER]) {
sord->indices[DEFAULT_ORDER] = zix_tree_new(
- false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER]);
+ false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL);
}
if (graphs && !sord->indices[DEFAULT_GRAPH_ORDER]) {
sord->indices[DEFAULT_GRAPH_ORDER] = zix_tree_new(
- false, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER]);
+ false, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL);
}
return sord;
diff --git a/src/zix/common.h b/src/zix/common.h
index e7d35e1..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;
/**
@@ -66,6 +73,11 @@ typedef int (*ZixComparator)(const void* a, const void* b, void* user_data);
typedef bool (*ZixEqualFunc)(const void* a, const void* b);
/**
+ Function to destroy an element.
+*/
+typedef void (*ZixDestroyFunc)(void* ptr);
+
+/**
@}
*/
diff --git a/src/zix/hash.c b/src/zix/hash.c
index f654e91..aacf993 100644
--- a/src/zix/hash.c
+++ b/src/zix/hash.c
@@ -30,44 +30,42 @@ static const unsigned sizes[] = {
50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0
};
-typedef struct _Entry {
- const void* key; ///< Hash key
- void* data; ///< Value
- struct _Entry* next; ///< Next entry in bucket
- unsigned hash; ///< Non-modulo hash value (for cheap rehash)
-} Entry;
+typedef struct ZixHashEntry {
+ const void* key; ///< Hash key
+ void* data; ///< Value
+ struct ZixHashEntry* next; ///< Next entry in bucket
+ unsigned hash; ///< Non-modulo hash value (for cheap rehash)
+} ZixHashEntry;
struct ZixHashImpl {
ZixHashFunc hash_func;
ZixEqualFunc key_equal_func;
- Entry** buckets;
+ ZixHashEntry** buckets;
const unsigned* n_buckets;
unsigned count;
};
-ZixHash*
+ZIX_API ZixHash*
zix_hash_new(ZixHashFunc hash_func,
ZixEqualFunc key_equal_func)
-
{
ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
hash->hash_func = hash_func;
hash->key_equal_func = key_equal_func;
hash->count = 0;
hash->n_buckets = &sizes[0];
- hash->buckets = (Entry**)malloc(*hash->n_buckets * sizeof(Entry*));
- memset(hash->buckets, 0, *hash->n_buckets * sizeof(Entry*));
-
+ hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
+ sizeof(ZixHashEntry*));
return hash;
}
-void
+ZIX_API void
zix_hash_free(ZixHash* hash)
{
for (unsigned b = 0; b < *hash->n_buckets; ++b) {
- Entry* bucket = hash->buckets[b];
- for (Entry* e = bucket; e;) {
- Entry* next = e->next;
+ ZixHashEntry* bucket = hash->buckets[b];
+ for (ZixHashEntry* e = bucket; e;) {
+ ZixHashEntry* next = e->next;
free(e);
e = next;
}
@@ -77,7 +75,7 @@ zix_hash_free(ZixHash* hash)
free(hash);
}
-unsigned
+ZIX_API unsigned
zix_string_hash(const void* key)
{
// Trusty old DJB hash
@@ -89,34 +87,32 @@ zix_string_hash(const void* key)
return h;
}
-bool
+ZIX_API bool
zix_string_equal(const void* a, const void* b)
{
return !strcmp((const char*)a, (const char*)b);
}
-static void
-insert_entry(Entry** bucket,
- Entry* entry)
+ZIX_PRIVATE void
+insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
{
entry->next = *bucket;
*bucket = entry;
}
-static ZixStatus
+ZIX_PRIVATE ZixStatus
rehash(ZixHash* hash, unsigned new_n_buckets)
{
- Entry** new_buckets = (Entry**)malloc(new_n_buckets * sizeof(Entry*));
+ ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(new_n_buckets,
+ sizeof(ZixHashEntry*));
if (!new_buckets) {
return ZIX_STATUS_NO_MEM;
}
- memset(new_buckets, 0, new_n_buckets * sizeof(Entry*));
-
for (unsigned b = 0; b < *hash->n_buckets; ++b) {
- for (Entry* e = hash->buckets[b]; e;) {
- Entry* const next = e->next;
- const unsigned h = e->hash % new_n_buckets;
+ for (ZixHashEntry* e = hash->buckets[b]; e;) {
+ ZixHashEntry* const next = e->next;
+ const unsigned h = e->hash % new_n_buckets;
insert_entry(&new_buckets[h], e);
e = next;
}
@@ -128,12 +124,12 @@ rehash(ZixHash* hash, unsigned new_n_buckets)
return ZIX_STATUS_SUCCESS;
}
-static Entry*
+ZIX_PRIVATE ZixHashEntry*
find_entry(const ZixHash* hash,
const void* key,
unsigned h)
{
- for (Entry* e = hash->buckets[h]; e; e = e->next) {
+ for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
if (hash->key_equal_func(e->key, key)) {
return e;
}
@@ -142,27 +138,27 @@ find_entry(const ZixHash* hash,
return NULL;
}
-void*
+ZIX_API void*
zix_hash_find(const ZixHash* hash, const void* key)
{
- const unsigned h = hash->hash_func(key) % *hash->n_buckets;
- Entry* const entry = find_entry(hash, key, h);
+ const unsigned h = hash->hash_func(key) % *hash->n_buckets;
+ ZixHashEntry* const entry = find_entry(hash, key, h);
return entry ? entry->data : 0;
}
-ZixStatus
+ZIX_API ZixStatus
zix_hash_insert(ZixHash* hash, const void* key, void* data)
{
unsigned h_nomod = hash->hash_func(key);
unsigned h = h_nomod % *hash->n_buckets;
- Entry* elem = find_entry(hash, key, h);
+ ZixHashEntry* elem = find_entry(hash, key, h);
if (elem) {
assert(elem->hash == h_nomod);
return ZIX_STATUS_EXISTS;
}
- elem = (Entry*)malloc(sizeof(Entry));
+ elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry));
if (!elem) {
return ZIX_STATUS_NO_MEM;
}
@@ -182,13 +178,13 @@ zix_hash_insert(ZixHash* hash, const void* key, void* data)
return ZIX_STATUS_SUCCESS;
}
-ZixStatus
+ZIX_API ZixStatus
zix_hash_remove(ZixHash* hash, const void* key)
{
unsigned h = hash->hash_func(key) % *hash->n_buckets;
- Entry** next_ptr = &hash->buckets[h];
- for (Entry* e = hash->buckets[h]; e; e = e->next) {
+ ZixHashEntry** next_ptr = &hash->buckets[h];
+ for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
if (hash->key_equal_func(e->key, key)) {
*next_ptr = e->next;
free(e);
@@ -210,15 +206,14 @@ zix_hash_remove(ZixHash* hash, const void* key)
return ZIX_STATUS_NOT_FOUND;
}
-ZIX_API
-void
+ZIX_API void
zix_hash_foreach(const ZixHash* hash,
void (*f)(const void* key, void* value, void* user_data),
void* user_data)
{
for (unsigned b = 0; b < *hash->n_buckets; ++b) {
- Entry* bucket = hash->buckets[b];
- for (Entry* e = bucket; e; e = e->next) {
+ ZixHashEntry* bucket = hash->buckets[b];
+ for (ZixHashEntry* e = bucket; e; e = e->next) {
f(e->key, e->data, user_data);
}
}
diff --git a/src/zix/hash.h b/src/zix/hash.h
index 44521f1..4d93eaa 100644
--- a/src/zix/hash.h
+++ b/src/zix/hash.h
@@ -30,40 +30,32 @@ typedef struct ZixHashImpl ZixHash;
*/
typedef unsigned (*ZixHashFunc)(const void* key);
-ZIX_API
-ZixHash*
+ZIX_API ZixHash*
zix_hash_new(ZixHashFunc hash_func,
ZixEqualFunc key_equal_func);
-ZIX_API
-void
+ZIX_API void
zix_hash_free(ZixHash* hash);
-ZIX_API
-unsigned
+ZIX_API unsigned
zix_string_hash(const void* key);
-ZIX_API
-bool
+ZIX_API bool
zix_string_equal(const void* a, const void* b);
-ZIX_API
-ZixStatus
+ZIX_API ZixStatus
zix_hash_insert(ZixHash* hash,
const void* key,
void* data);
-ZIX_API
-ZixStatus
+ZIX_API ZixStatus
zix_hash_remove(ZixHash* hash, const void* key);
-ZIX_API
-void*
+ZIX_API void*
zix_hash_find(const ZixHash* hash,
const void* key);
-ZIX_API
-void
+ZIX_API void
zix_hash_foreach(const ZixHash* hash,
void (*f)(const void* key, void* value, void* user_data),
void* user_data);
diff --git a/src/zix/tree.c b/src/zix/tree.c
index 64e6e7c..844adb9 100644
--- a/src/zix/tree.c
+++ b/src/zix/tree.c
@@ -26,10 +26,12 @@
typedef struct ZixTreeNodeImpl ZixTreeNode;
struct ZixTreeImpl {
- ZixTreeNode* root;
- ZixComparator cmp;
- void* cmp_data;
- bool allow_duplicates;
+ ZixTreeNode* root;
+ ZixDestroyFunc destroy;
+ ZixComparator cmp;
+ void* cmp_data;
+ size_t size;
+ bool allow_duplicates;
};
struct ZixTreeNodeImpl {
@@ -43,38 +45,72 @@ struct ZixTreeNodeImpl {
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
-ZIX_API
-ZixTree*
-zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data)
+// Uncomment these for debugging features
+// #define ZIX_TREE_DUMP 1
+// #define ZIX_TREE_VERIFY 1
+// #define ZIX_TREE_HYPER_VERIFY 1
+
+#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY)
+# include "tree_debug.h"
+# define ASSERT_BALANCE(n) assert(verify_balance(n))
+#else
+# define ASSERT_BALANCE(n)
+#endif
+
+#ifdef ZIX_TREE_DUMP
+# include "tree_debug.h"
+# define DUMP(t) zix_tree_print(t->root, 0)
+# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
+#else
+# define DUMP(t)
+# define DEBUG_PRINTF(fmt, ...)
+#endif
+
+ZIX_API ZixTree*
+zix_tree_new(bool allow_duplicates,
+ ZixComparator cmp,
+ void* cmp_data,
+ ZixDestroyFunc destroy)
{
ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree));
t->root = NULL;
+ t->destroy = destroy;
t->cmp = cmp;
t->cmp_data = cmp_data;
+ t->size = 0;
t->allow_duplicates = allow_duplicates;
return t;
}
-static void
-zix_tree_free_rec(ZixTreeNode* n)
+ZIX_PRIVATE void
+zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
{
if (n) {
- zix_tree_free_rec(n->left);
- zix_tree_free_rec(n->right);
+ zix_tree_free_rec(t, n->left);
+ zix_tree_free_rec(t, n->right);
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
free(n);
}
}
-ZIX_API
-void
+ZIX_API void
zix_tree_free(ZixTree* t)
{
- zix_tree_free_rec(t->root);
+ if (t) {
+ zix_tree_free_rec(t, t->root);
+ free(t);
+ }
+}
- free(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);
@@ -118,20 +154,26 @@ 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;
*height_change = (q->balance == 0) ? 0 : -1;
+ DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data);
+
assert(p->balance == 2);
assert(q->balance == 0 || q->balance == 1);
rotate(p, q);
+ // p->balance -= 1 + MAX(0, q->balance);
+ // q->balance -= 1 - MIN(0, p->balance);
--q->balance;
p->balance = -(q->balance);
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
return q;
}
@@ -145,20 +187,26 @@ 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;
*height_change = (q->balance == 0) ? 0 : -1;
+ DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data);
+
assert(p->balance == -2);
assert(q->balance == 0 || q->balance == -1);
rotate(p, q);
+ // p->balance += 1 - MIN(0, q->balance);
+ // q->balance += 1 + MAX(0, p->balance);
++q->balance;
p->balance = -(q->balance);
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
return q;
}
@@ -174,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;
@@ -184,15 +232,25 @@ rotate_left_right(ZixTreeNode* p, int* height_change)
assert(q->balance == 1);
assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+ DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n",
+ (intptr_t)p->data, p->balance, q->balance, r->balance);
+
rotate(q, r);
rotate(p, r);
q->balance -= 1 + MAX(0, r->balance);
p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
+ // r->balance += MAX(0, p->balance) + MIN(0, q->balance);
+
+ // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0;
+ // q->balance = - MAX(r->balance, 0);
r->balance = 0;
*height_change = -1;
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ ASSERT_BALANCE(r);
return r;
}
@@ -208,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;
@@ -218,21 +276,36 @@ rotate_right_left(ZixTreeNode* p, int* height_change)
assert(q->balance == -1);
assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+ DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n",
+ (intptr_t)p->data, p->balance, q->balance, r->balance);
+
rotate(q, r);
rotate(p, r);
q->balance += 1 - MIN(0, r->balance);
p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
+ // r->balance += MAX(0, q->balance) + MIN(0, p->balance);
+
+ // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0;
+ // q->balance = - MIN(r->balance, 0);
r->balance = 0;
+ // assert(r->balance == 0);
*height_change = -1;
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ ASSERT_BALANCE(r);
return r;
}
-static ZixTreeNode*
+ZIX_PRIVATE ZixTreeNode*
zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
{
+#ifdef ZIX_TREE_HYPER_VERIFY
+ const size_t old_height = height(node);
+#endif
+ DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance);
*height_change = 0;
const bool is_root = !node->parent;
assert((is_root && t->root == node) || (!is_root && t->root != node));
@@ -256,14 +329,17 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
assert(!replacement->parent);
t->root = replacement;
}
-
+ DUMP(t);
+#ifdef ZIX_TREE_HYPER_VERIFY
+ assert(old_height + *height_change == height(replacement));
+#endif
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);
int cmp = 0;
ZixTreeNode* n = t->root;
ZixTreeNode* p = NULL;
@@ -282,6 +358,7 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
if (ti) {
*ti = n;
}
+ DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
return ZIX_STATUS_EXISTS;
}
}
@@ -319,6 +396,8 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
}
}
+ DUMP(t);
+
// Rebalance if necessary (at most 1 rotation)
assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
if (p && p_height_increased) {
@@ -343,11 +422,20 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
}
}
+ DUMP(t);
+
+ ++t->size;
+
+#ifdef ZIX_TREE_VERIFY
+ if (!verify(t, t->root)) {
+ return ZIX_STATUS_ERROR;
+ }
+#endif
+
return ZIX_STATUS_SUCCESS;
}
-ZIX_API
-ZixStatus
+ZIX_API ZixStatus
zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
{
ZixTreeNode* const n = ti;
@@ -355,9 +443,16 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
ZixTreeNode* to_balance = n->parent; // lowest node to balance
int8_t d_balance = 0; // delta(balance) for n->parent
+ DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
+
if ((n == t->root) && !n->left && !n->right) {
t->root = NULL;
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
free(n);
+ --t->size;
+ assert(t->size == 0);
return ZIX_STATUS_SUCCESS;
}
@@ -479,13 +574,25 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
}
}
+ DUMP(t);
+
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
free(n);
+ --t->size;
+
+#ifdef ZIX_TREE_VERIFY
+ if (!verify(t, t->root)) {
+ return ZIX_STATUS_ERROR;
+ }
+#endif
+
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;
@@ -504,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->data;
+ return ti ? ti->data : NULL;
}
-ZIX_API
-ZixTreeIter*
+ZIX_API ZixTreeIter*
zix_tree_begin(ZixTree* t)
{
if (!t->root) {
@@ -526,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) {
@@ -564,8 +692,7 @@ zix_tree_iter_next(ZixTreeIter* i)
return i;
}
-ZIX_API
-ZixTreeIter*
+ZIX_API ZixTreeIter*
zix_tree_iter_prev(ZixTreeIter* i)
{
if (!i) {
diff --git a/src/zix/tree.h b/src/zix/tree.h
index bcbde26..f89d9e5 100644
--- a/src/zix/tree.h
+++ b/src/zix/tree.h
@@ -17,6 +17,8 @@
#ifndef ZIX_TREE_H
#define ZIX_TREE_H
+#include <stddef.h>
+
#include "zix/common.h"
#ifdef __cplusplus
@@ -43,68 +45,95 @@ typedef struct ZixTreeNodeImpl ZixTreeIter;
/**
Create a new (empty) tree.
*/
-ZixTree*
-zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data);
+ZIX_API ZixTree*
+zix_tree_new(bool allow_duplicates,
+ ZixComparator cmp,
+ void* cmp_data,
+ ZixDestroyFunc destroy);
/**
Free @a t.
*/
-void
+ZIX_API void
zix_tree_free(ZixTree* t);
/**
+ Return the number of elements in @a 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.
+*/
+ZIX_API ZixTreeIter*
+zix_tree_rbegin(ZixTree* t);
+
+/**
+ Return an iterator the the element one before the first element in @a t.
+*/
+ZIX_API ZixTreeIter*
+zix_tree_rend(ZixTree* t);
+
+/**
+ Return true iff @a i is an iterator to the reverse end of its tree.
+*/
+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-09 22:37:43 +0000