From: Fredrik Tolf <fredrik@dolda2000.com>
Date: Sun, 24 Feb 2008 04:03:55 +0000 (+0100)
Subject: Added functions for btree iteration.
X-Git-Tag: 1.2~25
X-Git-Url: http://dolda2000.com/gitweb/?p=doldaconnect.git;a=commitdiff_plain;h=a1e6d478fa8edd72c08ce8b89a122bc12f6bf8d2

Added functions for btree iteration.
---

diff --git a/common/utils.c b/common/utils.c
index 701f162..7a7de92 100644
--- a/common/utils.c
+++ b/common/utils.c
@@ -37,6 +37,14 @@
 #include <utils.h>
 #include <log.h>
 
+struct treeiter {
+    struct {
+	struct btree *n;
+	int s;
+    } *st;
+    size_t stsize, sp;
+};
+
 static char *base64set = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
 static int base64rev[] = {
     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
@@ -1030,3 +1038,93 @@ void *btreeget(struct btree *tree, void *key, int (*cmp)(void *, void *))
     }
 }
 
+void btreefree(struct btree *tree)
+{
+    if(tree == NULL)
+	return;
+    btreefree(tree->l);
+    btreefree(tree->r);
+    free(tree);
+}
+
+static void *btreenext(void **iterp)
+{
+    struct treeiter *iter;
+    int s;
+    struct btree *n;
+    
+    if((iter = *iterp) == NULL)
+	return(NULL);
+    while(1) {
+	s = iter->st[iter->sp].s;
+	n = iter->st[iter->sp].n;
+	if(s == 0) {
+	    iter->st[iter->sp].s = 1;
+	    if(n->l != NULL) {
+		iter->sp++;
+		sizebuf2(iter->st, iter->sp + 1, 1);
+		iter->st[iter->sp].s = 0;
+		iter->st[iter->sp].n = n->l;
+	    }
+	} else if(s == 1) {
+	    iter->st[iter->sp].s = 2;
+	    return(iter->st[iter->sp].n->d);
+	} else if(s == 2) {
+	    iter->st[iter->sp].s = 3;
+	    if(n->r != NULL) {
+		iter->sp++;
+		sizebuf2(iter->st, iter->sp + 1, 1);
+		iter->st[iter->sp].s = 0;
+		iter->st[iter->sp].n = n->r;
+	    }
+	} else {
+	    iter->sp--;
+	    if(iter->sp < 0) {
+		free(iter->st);
+		free(iter);
+		*iterp = NULL;
+		return(NULL);
+	    }
+	}
+    }
+}
+
+static void *btreefirst(struct btree *tree, void **iterp)
+{
+    struct treeiter *iter;
+    
+    if(tree == NULL) {
+	*iterp = NULL;
+	return(NULL);
+    }
+    *iterp = iter = memset(smalloc(sizeof(*iter)), 0, sizeof(*iter));
+    sizebuf2(iter->st, 1, 1);
+    iter->st[0].n = tree;
+    iter->st[0].s = 0;
+    return(btreenext(iterp));
+}
+
+static void btreestop(void **iterp)
+{
+    struct treeiter *iter;
+    
+    if((iter = *iterp) == NULL)
+	return;
+    if(iter->st != NULL)
+	free(iter->st);
+    free(iter);
+    *iterp = NULL;
+}
+
+void *btreeiter(struct btree *tree)
+{
+    static void *iter = NULL;
+    
+    if(tree == NULL) {
+	return(btreenext(&iter));
+    } else {
+	if(iter != NULL)
+	    btreestop(&iter);
+	return(btreefirst(tree, &iter));
+    }
+}
diff --git a/include/utils.h b/include/utils.h
index cff0025..390d3b4 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -115,6 +115,8 @@ wchar_t *wpfind(struct wcspair *list, wchar_t *key);
 int bbtreedel(struct btree **tree, void *item, int (*cmp)(void *, void *));
 int bbtreeput(struct btree **tree, void *item, int (*cmp)(void *, void *));
 void *btreeget(struct btree *tree, void *key, int (*cmp)(void *, void *));
+void *btreeiter(struct btree *tree);
+void btreefree(struct btree *tree);
 
 #define sizebuf(b, bs, rs, es, a) _sizebuf((void **)(void *)(b), (bs), (rs), (es), (a))
 #define sizebuf2(b, rs, a) _sizebuf((void **)(void *)(&(b)), &(b ## size), (rs), sizeof(*(b)), (a))