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

6 files changed, 248 insertions, 98 deletions

diff --git a/src/tree.c b/src/tree.c
index 5d09680..d319f1d 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -722,3 +722,56 @@ zix_tree_get_data(ZixTreeIter ti)
 {
 	return ti->data;
 }
+
+ZIX_API
+ZixTreeIter
+zix_tree_begin(ZixTree* t)
+{
+	if (!t->root) {
+		return NULL;
+	}
+
+	ZixTreeNode* n = t->root;
+	while (n->left) {
+		n = n->left;
+	}
+	return n;
+}
+
+ZIX_API
+ZixTreeIter
+zix_tree_end(ZixTree* t)
+{
+	return NULL;
+}
+
+ZIX_API
+bool
+zix_tree_iter_is_end(ZixTreeIter i)
+{
+	return !i;
+}
+
+ZIX_API
+ZixTreeIter
+zix_tree_iter_next(ZixTreeIter i)
+{
+	if (!i) {
+		return NULL;
+	}
+
+	if (i->right) {
+		i = i->right;
+		while (i->left) {
+			i = i->left;
+		}
+	} else {
+		while (i->parent && i->parent->right == i) {  // i is a right child
+			i = i->parent;
+		}
+
+		i = i->parent;
+	}
+
+	return i;
+}
diff --git a/test/tree_test.c b/test/tree_test.c
index d4fb283..656e718 100644
--- a/test/tree_test.c
+++ b/test/tree_test.c
@@ -65,7 +65,7 @@ stress(int test_num, size_t n_elems)
 	srand(seed);
 
 	// Insert n_elems elements
-	for (size_t i = 0; i < n_elems; i++) {
+	for (size_t i = 0; i < n_elems; ++i) {
 		r = ith_elem(test_num, n_elems, i);
 		int status = zix_tree_insert(t, (void*)r, &ti);
 		if (status == ZIX_STATUS_EXISTS) {
@@ -75,8 +75,8 @@ stress(int test_num, size_t n_elems)
 			return test_fail();
 		}
 		if ((intptr_t)zix_tree_get_data(ti) != r) {
-			fprintf(stderr, "Data is corrupted! Saw %" PRIdPTR ", expected %zu\n",
-			        (intptr_t)zix_tree_get_data(ti), i);
+			fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n",
+			        (intptr_t)zix_tree_get_data(ti), r);
 			return test_fail();
 		}
 	}
@@ -84,15 +84,32 @@ stress(int test_num, size_t n_elems)
 	srand(seed);
 
 	// Search for all elements
-	for (size_t i = 0; i < n_elems; i++) {
+	for (size_t i = 0; i < n_elems; ++i) {
 		r = ith_elem(test_num, n_elems, i);
 		if (zix_tree_find(t, (void*)r, &ti)) {
 			fprintf(stderr, "Find failed\n");
 			return test_fail();
 		}
 		if ((intptr_t)zix_tree_get_data(ti) != r) {
-			fprintf(stderr, "Data corrupted (saw %" PRIdPTR ", expected %zu\n",
-			        (intptr_t)zix_tree_get_data(ti), i);
+			fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n",
+			        (intptr_t)zix_tree_get_data(ti), r);
+			return test_fail();
+		}
+	}
+
+	srand(seed);
+
+	// Iterate over all elements
+	size_t i = 0;
+	intptr_t last = -1;
+	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);
+		if (iter_data < last) {
+			fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %zu)\n",
+			        iter_data, last);
 			return test_fail();
 		}
 	}
diff --git a/wscript b/wscript
index ec7f46a..2e48c03 100644
--- a/wscript
+++ b/wscript
@@ -65,7 +65,6 @@ def build(bld):
 
     lib_source = '''
         src/tree.c
-        src/strindex.c
     '''
 
     # Library
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 <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_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 <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_H
+#define ZIX_TREE_H
+
+#include <stdbool.h>
+
+#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 <stdbool.h>
-
-#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);
-
-/**
-   @}
    @}
 */