diff options
| -rw-r--r-- | src/sord.c | 11 | ||||
| -rw-r--r-- | src/zix/common.h | 12 | ||||
| -rw-r--r-- | src/zix/hash.c | 81 | ||||
| -rw-r--r-- | src/zix/hash.h | 24 | ||||
| -rw-r--r-- | src/zix/tree.c | 209 | ||||
| -rw-r--r-- | src/zix/tree.h | 53 | ||||
| -rw-r--r-- | wscript | 2 |
7 files changed, 275 insertions, 117 deletions
@@ -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); /** @@ -115,7 +115,7 @@ def build(bld): autowaf.build_pc(bld, 'SORD', SORD_VERSION, SORD_MAJOR_VERSION, 'SERD', {'SORD_MAJOR_VERSION' : SORD_MAJOR_VERSION}) - source = 'src/sord.c src/syntax.c src/zix/hash.c src/zix/tree.c' + source = 'src/sord.c src/syntax.c' libflags = ['-fvisibility=hidden'] libs = ['m'] |