diff options
| -rw-r--r-- | src/tree.c | 302 | ||||
| -rw-r--r-- | src/tree_debug.h | 154 | ||||
| -rw-r--r-- | test/tree_bench.c | 11 | ||||
| -rw-r--r-- | test/tree_test.c | 36 | ||||
| -rw-r--r-- | zix/tree.h | 53 |
5 files changed, 336 insertions, 220 deletions
@@ -24,12 +24,7 @@ #include "zix/common.h" #include "zix/tree.h" -// #define ZIX_TREE_DUMP 1 -// #define ZIX_TREE_VERIFY 1 -// #define ZIX_TREE_HYPER_VERIFY 1 - -#define MIN(a, b) (((a) < (b)) ? (a) : (b)) -#define MAX(a, b) (((a) > (b)) ? (a) : (b)) +typedef struct ZixTreeNodeImpl ZixTreeNode; struct ZixTreeImpl { ZixTreeNode* root; @@ -39,35 +34,35 @@ struct ZixTreeImpl { }; struct ZixTreeNodeImpl { - const void* data; + void* data; struct ZixTreeNodeImpl* left; struct ZixTreeNodeImpl* right; struct ZixTreeNodeImpl* parent; int_fast8_t balance; }; +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) + +// 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 -static void -zix_tree_print(ZixTreeNode* node, int level) -{ - if (node) { - if (!node->parent) { - printf("{{{\n"); - } - zix_tree_print(node->right, level + 1); - for (int i = 0; i < level; i++) { - printf(" "); - } - printf("%ld.%d\n", (intptr_t)node->data, node->balance); - zix_tree_print(node->left, level + 1); - if (!node->parent) { - printf("}}}\n"); - } - } -} +# 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 @@ -101,119 +96,6 @@ zix_tree_free(ZixTree* t) free(t); } -#ifdef ZIX_TREE_HYPER_VERIFY -static size_t -height(ZixTreeNode* n) -{ - if (!n) { - return 0; - } else { - return 1 + MAX(height(n->left), height(n->right)); - } -} -#endif - -#if defined(ZIX_TREE_VERIFY) || !defined(NDEBUG) -static bool -verify_balance(ZixTreeNode* n) -{ - if (!n) { - return true; - } - - if (n->balance < -2 || n->balance > 2) { - fprintf(stderr, "Balance out of range : %ld (balance %d)\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance < 0 && !n->left) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance > 0 && !n->right) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n", - (intptr_t)n->data, n->balance); - return false; - } - - if (n->balance != 0 && !n->left && !n->right) { - fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n", - (intptr_t)n->data, n->balance); - return false; - } - -#ifdef ZIX_TREE_HYPER_VERIFY - const intptr_t left_height = (intptr_t)height(n->left); - const intptr_t right_height = (intptr_t)height(n->right); - if (n->balance != right_height - left_height) { - fprintf(stderr, "Bad balance at %ld: h_r (%zu) - l_h (%zu) != %d\n", - (intptr_t)n->data, right_height, left_height, n->balance); - assert(false); - return false; - } -#endif - - return true; -} -#endif - -#ifdef ZIX_TREE_VERIFY -static bool -verify(ZixTree* t, ZixTreeNode* n) -{ - if (!n) { - return true; - } - - if (n->parent) { - if ((n->parent->left != n) && (n->parent->right != n)) { - fprintf(stderr, "Corrupt child/parent pointers\n"); - return false; - } - } - - if (n->left) { - if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { - fprintf(stderr, "Bad order: %zu with left child\n", - (intptr_t)n->data); - fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); - fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data, - (intptr_t)n->left->data); - return false; - } - if (!verify(t, n->left)) { - return false; - } - } - - if (n->right) { - if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { - fprintf(stderr, "Bad order: %zu with right child\n", - (intptr_t)n->data); - return false; - } - if (!verify(t, n->right)) { - return false; - } - } - - if (!verify_balance(n)) { - return false; - } - - if (n->balance <= -2 || n->balance >= 2) { - fprintf(stderr, "Imbalance: %p (balance %d)\n", - (void*)n, n->balance); - return false; - } - - return true; -} -#endif - static void rotate(ZixTreeNode* p, ZixTreeNode* q) { @@ -249,6 +131,8 @@ rotate(ZixTreeNode* p, ZixTreeNode* q) p->parent = q; } + + /** * Rotate left about @a p. * @@ -264,9 +148,7 @@ rotate_left(ZixTreeNode* p, int* height_change) ZixTreeNode* const q = p->right; *height_change = (q->balance == 0) ? 0 : -1; -#ifdef ZIX_TREE_DUMP - printf("LL %ld\n", (intptr_t)p->data); -#endif + DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data); assert(p->balance == 2); assert(q->balance == 0 || q->balance == 1); @@ -278,8 +160,8 @@ rotate_left(ZixTreeNode* p, int* height_change) --q->balance; p->balance = -(q->balance); - assert(verify_balance(p)); - assert(verify_balance(q)); + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); return q; } @@ -299,9 +181,7 @@ rotate_right(ZixTreeNode* p, int* height_change) ZixTreeNode* const q = p->left; *height_change = (q->balance == 0) ? 0 : -1; -#ifdef ZIX_TREE_DUMP - printf("RR %ld\n", (intptr_t)p->data); -#endif + DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data); assert(p->balance == -2); assert(q->balance == 0 || q->balance == -1); @@ -313,9 +193,8 @@ rotate_right(ZixTreeNode* p, int* height_change) ++q->balance; p->balance = -(q->balance); - assert(verify_balance(p)); - assert(verify_balance(q)); - + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); return q; } @@ -341,10 +220,8 @@ rotate_left_right(ZixTreeNode* p, int* height_change) assert(q->balance == 1); assert(r->balance == -1 || r->balance == 0 || r->balance == 1); -#ifdef ZIX_TREE_DUMP - printf("LR %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, p->balance, q->balance, r->balance); -#endif + 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); @@ -357,11 +234,11 @@ rotate_left_right(ZixTreeNode* p, int* height_change) // q->balance = - MAX(r->balance, 0); r->balance = 0; - assert(verify_balance(p)); - assert(verify_balance(q)); - assert(verify_balance(r)); - *height_change = -1; + + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + ASSERT_BALANCE(r); return r; } @@ -387,10 +264,8 @@ rotate_right_left(ZixTreeNode* p, int* height_change) assert(q->balance == -1); assert(r->balance == -1 || r->balance == 0 || r->balance == 1); -#ifdef ZIX_TREE_DUMP - printf("RL %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, p->balance, q->balance, r->balance); -#endif + 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); @@ -404,11 +279,11 @@ rotate_right_left(ZixTreeNode* p, int* height_change) r->balance = 0; // assert(r->balance == 0); - assert(verify_balance(p)); - assert(verify_balance(q)); - assert(verify_balance(r)); - *height_change = -1; + + ASSERT_BALANCE(p); + ASSERT_BALANCE(q); + ASSERT_BALANCE(r); return r; } @@ -418,9 +293,7 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) #ifdef ZIX_TREE_HYPER_VERIFY const size_t old_height = height(node); #endif -#ifdef ZIX_TREE_DUMP - printf("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); -#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)); @@ -453,11 +326,9 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) ZIX_API ZixStatus -zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti) +zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) { -#ifdef ZIX_TREE_DUMP - printf("**** INSERT %ld\n", (intptr_t)e); -#endif + DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); int cmp = 0; ZixTreeNode* n = t->root; ZixTreeNode* p = NULL; @@ -473,10 +344,10 @@ zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti) } else if (t->allow_duplicates) { n = n->right; } else { - *ti = n; -#ifdef ZIX_TREE_DUMP - printf("EXISTS!\n"); -#endif + if (ti) { + *ti = n; + } + DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e); return ZIX_STATUS_EXISTS; } } @@ -488,7 +359,9 @@ zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti) memset(n, '\0', sizeof(ZixTreeNode)); n->data = e; n->balance = 0; - *ti = n; + if (ti) { + *ti = n; + } bool p_height_increased = false; @@ -551,16 +424,14 @@ zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti) ZIX_API ZixStatus -zix_tree_remove(ZixTree* t, ZixTreeIter ti) +zix_tree_remove(ZixTree* t, ZixTreeIter* ti) { ZixTreeNode* const n = ti; ZixTreeNode** pp = NULL; // parent pointer ZixTreeNode* to_balance = n->parent; // lowest node to balance int8_t d_balance = 0; // delta(balance) for n->parent -#ifdef ZIX_TREE_DUMP - printf("*** REMOVE %ld\n", (intptr_t)n->data); -#endif + DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data); if ((n == t->root) && !n->left && !n->right) { t->root = NULL; @@ -701,7 +572,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter ti) ZIX_API ZixStatus -zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti) +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti) { ZixTreeNode* n = t->root; while (n) { @@ -720,14 +591,14 @@ zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti) } ZIX_API -const void* -zix_tree_get_data(ZixTreeIter ti) +void* +zix_tree_get(ZixTreeIter* ti) { return ti->data; } ZIX_API -ZixTreeIter +ZixTreeIter* zix_tree_begin(ZixTree* t) { if (!t->root) { @@ -742,22 +613,51 @@ zix_tree_begin(ZixTree* t) } ZIX_API -ZixTreeIter +ZixTreeIter* zix_tree_end(ZixTree* t) { return NULL; } 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 bool -zix_tree_iter_is_end(ZixTreeIter i) +zix_tree_iter_is_rend(ZixTreeIter* i) { return !i; } ZIX_API -ZixTreeIter -zix_tree_iter_next(ZixTreeIter i) +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i) { if (!i) { return NULL; @@ -778,3 +678,27 @@ 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/tree_debug.h b/src/tree_debug.h new file mode 100644 index 0000000..c2af4bf --- /dev/null +++ b/src/tree_debug.h @@ -0,0 +1,154 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + 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_DEBUG_H +#define ZIX_TREE_DEBUG_H + +#ifdef ZIX_TREE_DUMP +static void +zix_tree_print(ZixTreeNode* node, int level) +{ + if (node) { + if (!node->parent) { + printf("{{{\n"); + } + zix_tree_print(node->right, level + 1); + for (int i = 0; i < level; i++) { + printf(" "); + } + printf("%ld.%d\n", (intptr_t)node->data, node->balance); + zix_tree_print(node->left, level + 1); + if (!node->parent) { + printf("}}}\n"); + } + } +} +#endif + +#ifdef ZIX_TREE_HYPER_VERIFY +static size_t +height(ZixTreeNode* n) +{ + if (!n) { + return 0; + } else { + return 1 + MAX(height(n->left), height(n->right)); + } +} +#endif + +#if defined(ZIX_TREE_VERIFY) || !defined(NDEBUG) +static bool +verify_balance(ZixTreeNode* n) +{ + if (!n) { + return true; + } + + if (n->balance < -2 || n->balance > 2) { + fprintf(stderr, "Balance out of range : %ld (balance %d)\n", + (intptr_t)n->data, n->balance); + return false; + } + + if (n->balance < 0 && !n->left) { + fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n", + (intptr_t)n->data, n->balance); + return false; + } + + if (n->balance > 0 && !n->right) { + fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n", + (intptr_t)n->data, n->balance); + return false; + } + + if (n->balance != 0 && !n->left && !n->right) { + fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n", + (intptr_t)n->data, n->balance); + return false; + } + +#ifdef ZIX_TREE_HYPER_VERIFY + const intptr_t left_height = (intptr_t)height(n->left); + const intptr_t right_height = (intptr_t)height(n->right); + if (n->balance != right_height - left_height) { + fprintf(stderr, "Bad balance at %ld: h_r (%zu) - l_h (%zu) != %d\n", + (intptr_t)n->data, right_height, left_height, n->balance); + assert(false); + return false; + } +#endif + + return true; +} +#endif + +#ifdef ZIX_TREE_VERIFY +static bool +verify(ZixTree* t, ZixTreeNode* n) +{ + if (!n) { + return true; + } + + if (n->parent) { + if ((n->parent->left != n) && (n->parent->right != n)) { + fprintf(stderr, "Corrupt child/parent pointers\n"); + return false; + } + } + + if (n->left) { + if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { + fprintf(stderr, "Bad order: %zu with left child\n", + (intptr_t)n->data); + fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); + fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data, + (intptr_t)n->left->data); + return false; + } + if (!verify(t, n->left)) { + return false; + } + } + + if (n->right) { + if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { + fprintf(stderr, "Bad order: %zu with right child\n", + (intptr_t)n->data); + return false; + } + if (!verify(t, n->right)) { + return false; + } + } + + if (!verify_balance(n)) { + return false; + } + + if (n->balance <= -2 || n->balance >= 2) { + fprintf(stderr, "Imbalance: %p (balance %d)\n", + (void*)n, n->balance); + return false; + } + + return true; +} +#endif + +#endif // ZIX_TREE_DEBUG_H diff --git a/test/tree_bench.c b/test/tree_bench.c index 84d31a8..d0e2611 100644 --- a/test/tree_bench.c +++ b/test/tree_bench.c @@ -60,7 +60,7 @@ bench_zix_tree(size_t n_elems, FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat) { intptr_t r; - ZixTreeIter ti; + ZixTreeIter* ti; ZixTree* t = zix_tree_new(true, int_cmp, NULL); @@ -86,7 +86,7 @@ bench_zix_tree(size_t n_elems, if (zix_tree_find(t, (void*)r, &ti)) { return test_fail("Failed to find %zu\n", r); } - if ((intptr_t)zix_tree_get_data(ti) != r) { + if ((intptr_t)zix_tree_get(ti) != r) { return test_fail("Failed to get %zu\n", r); } } @@ -96,10 +96,10 @@ bench_zix_tree(size_t n_elems, // Iterate over all elements struct timespec iter_start = bench_start(); - for (ZixTreeIter iter = zix_tree_begin(t); + for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter); iter = zix_tree_iter_next(iter)) { - zix_tree_get_data(iter); + zix_tree_get(iter); } fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); @@ -109,7 +109,8 @@ bench_zix_tree(size_t n_elems, struct timespec del_start = bench_start(); for (size_t i = 0; i < n_elems; i++) { r = rand(); - ZixTreeIter item; + ZixTreeIter* + item; if (zix_tree_find(t, (void*)r, &item)) { return test_fail("Failed to find %zu to delete\n", r); } diff --git a/test/tree_test.c b/test/tree_test.c index c352fc0..943dca7 100644 --- a/test/tree_test.c +++ b/test/tree_test.c @@ -57,8 +57,8 @@ test_fail() static int stress(int test_num, size_t n_elems) { - intptr_t r; - ZixTreeIter ti; + intptr_t r; + ZixTreeIter* ti; ZixTree* t = zix_tree_new(true, int_cmp, NULL); @@ -72,9 +72,9 @@ stress(int test_num, size_t n_elems) fprintf(stderr, "Insert failed\n"); return test_fail(); } - if ((intptr_t)zix_tree_get_data(ti) != r) { + if ((intptr_t)zix_tree_get(ti) != r) { fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - (intptr_t)zix_tree_get_data(ti), r); + (intptr_t)zix_tree_get(ti), r); return test_fail(); } } @@ -88,9 +88,9 @@ stress(int test_num, size_t n_elems) fprintf(stderr, "Find failed\n"); return test_fail(); } - if ((intptr_t)zix_tree_get_data(ti) != r) { + if ((intptr_t)zix_tree_get(ti) != r) { fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - (intptr_t)zix_tree_get_data(ti), r); + (intptr_t)zix_tree_get(ti), r); return test_fail(); } } @@ -100,11 +100,11 @@ stress(int test_num, size_t n_elems) // Iterate over all elements size_t i = 0; intptr_t last = -1; - for (ZixTreeIter iter = zix_tree_begin(t); + 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); + const intptr_t iter_data = (intptr_t)zix_tree_get(iter); if (iter_data < last) { fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %zu)\n", iter_data, last); @@ -115,10 +115,28 @@ stress(int test_num, size_t n_elems) srand(seed); + // Iterate over all elements backwards + i = 0; + last = INTPTR_MAX; + for (ZixTreeIter* iter = zix_tree_rbegin(t); + !zix_tree_iter_is_rend(iter); + iter = zix_tree_iter_prev(iter), ++i) { + r = ith_elem(test_num, n_elems, i); + const intptr_t iter_data = (intptr_t)zix_tree_get(iter); + if (iter_data > last) { + fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %zu)\n", + iter_data, last); + return test_fail(); + } + last = iter_data; + } + + srand(seed); + // Delete all elements for (size_t i = 0; i < n_elems; i++) { r = ith_elem(test_num, n_elems, i); - ZixTreeIter item; + ZixTreeIter* item; if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { fprintf(stderr, "Failed to find item to remove\n"); return test_fail(); @@ -38,14 +38,9 @@ extern "C" { typedef struct ZixTreeImpl ZixTree; /** - A node in a @ref ZixTree. -*/ -typedef struct ZixTreeNodeImpl ZixTreeNode; - -/** An iterator over a @ref ZixTree. */ -typedef ZixTreeNode* ZixTreeIter; +typedef struct ZixTreeNodeImpl ZixTreeIter; /** Create a new (empty) tree. @@ -63,50 +58,74 @@ zix_tree_free(ZixTree* t); Insert the element @a e into @a t and point @a ti at the new element. */ ZixStatus -zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti); +zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); /** Remove the item pointed at by @a ti from @a t. */ ZixStatus -zix_tree_remove(ZixTree* t, ZixTreeIter ti); +zix_tree_remove(ZixTree* t, ZixTreeIter* ti); /** - Set @a ti to be the largest element <= @a e in @a t. + 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_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti); +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); /** Return the data associated with the given tree item. */ -const void* -zix_tree_get_data(ZixTreeIter ti); +void* +zix_tree_get(ZixTreeIter* ti); /** Return an iterator to the first (smallest) element in @a t. */ -ZixTreeIter +ZixTreeIter* zix_tree_begin(ZixTree* t); /** Return an iterator the the element one past the last element in @a t. */ -ZixTreeIter +ZixTreeIter* zix_tree_end(ZixTree* t); /** Return true iff @a i is an iterator to the end of its tree. */ bool -zix_tree_iter_is_end(ZixTreeIter i); +zix_tree_iter_is_end(ZixTreeIter* i); + +/** + Return an iterator to the last (largest) element in @a t. +*/ +ZixTreeIter* +zix_tree_rbegin(ZixTree* t); + +/** + Return an iterator the the element one before the first element in @a t. +*/ +ZixTreeIter* +zix_tree_rend(ZixTree* t); + +/** + Return true iff @a i is an iterator to the reverse end of its tree. +*/ +bool +zix_tree_iter_is_rend(ZixTreeIter* i); /** Return an iterator that points to the element one past @a i. */ -ZixTreeIter -zix_tree_iter_next(ZixTreeIter i); +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i); + +/** + Return an iterator that points to the element one before @a i. +*/ +ZixTreeIter* +zix_tree_iter_prev(ZixTreeIter* i); /** @} |