--- a/src/lib-storage/list/mailbox-list-maildir-iter.c	Wed Apr 11 20:40:18 2007 +0300
+++ b/src/lib-storage/list/mailbox-list-maildir-iter.c	Wed Apr 11 22:07:15 2007 +0300
@@ -19,10 +19,8 @@
 	const char *dir, *prefix;
 
         struct mailbox_tree_context *tree_ctx;
+	struct mailbox_tree_iterate_context *tree_iter;
 
-	string_t *node_path;
-	size_t parent_pos;
-	struct mailbox_node *root, *next_node;
 	struct mailbox_info info;
 };
 
@@ -279,8 +277,8 @@
 		}
 	}
 
-	ctx->node_path = str_new(pool, 256);
-	ctx->root = mailbox_tree_get(ctx->tree_ctx, NULL, NULL);
+	ctx->tree_iter = mailbox_tree_iterate_init(ctx->tree_ctx, NULL,
+						   MAILBOX_FLAG_MATCHED);
 	return &ctx->ctx;
 }
 
@@ -290,41 +288,13 @@
 		(struct maildir_list_iterate_context *)_ctx;
 	int ret = ctx->ctx.failed ? -1 : 0;
 
-	mailbox_tree_deinit(ctx->tree_ctx);
+	if (ctx->tree_iter != NULL)
+		mailbox_tree_iterate_deinit(&ctx->tree_iter);
+	mailbox_tree_deinit(&ctx->tree_ctx);
 	pool_unref(ctx->pool);
 	return ret;
 }
 
-static struct mailbox_node *find_next(struct mailbox_node **node,
-				      string_t *path, char hierarchy_sep)
-{
-	struct mailbox_node *child;
-	size_t len;
-
-	while (*node != NULL) {
-		if (((*node)->flags & MAILBOX_FLAG_MATCHED) != 0)
-			return *node;
-
-		if ((*node)->children != NULL) {
-			len = str_len(path);
-			if (len != 0)
-				str_append_c(path, hierarchy_sep);
-			str_append(path, (*node)->name);
-
-			child = find_next(&(*node)->children, path,
-					  hierarchy_sep);
-			if (child != NULL)
-				return child;
-
-			str_truncate(path, len);
-		}
-
-		*node = (*node)->next;
-	}
-
-	return NULL;
-}
-
 struct mailbox_info *
 maildir_list_iter_next(struct mailbox_list_iterate_context *_ctx)
 {
@@ -332,34 +302,13 @@
 		(struct maildir_list_iterate_context *)_ctx;
 	struct mailbox_node *node;
 
-	for (node = ctx->next_node; node != NULL; node = node->next) {
-		if ((node->flags & MAILBOX_FLAG_MATCHED) != 0)
-			break;
-	}
-
-	if (node == NULL) {
-		if (ctx->root == NULL)
-			return NULL;
-
-		str_truncate(ctx->node_path, 0);
-		node = find_next(&ctx->root, ctx->node_path,
-				 ctx->ctx.list->hierarchy_sep);
-                ctx->parent_pos = str_len(ctx->node_path);
+	if (ctx->ctx.failed)
+		return NULL;
 
-		if (node == NULL)
-			return NULL;
-	}
-	ctx->next_node = node->next;
+	node = mailbox_tree_iterate_next(ctx->tree_iter, &ctx->info.name);
+	if (node == NULL)
+		return NULL;
 
-	i_assert((node->flags & MAILBOX_FLAG_MATCHED) != 0);
-	node->flags &= ~MAILBOX_FLAG_MATCHED;
-
-	str_truncate(ctx->node_path, ctx->parent_pos);
-	if (ctx->parent_pos != 0)
-		str_append_c(ctx->node_path, ctx->ctx.list->hierarchy_sep);
-	str_append(ctx->node_path, node->name);
-
-	ctx->info.name = str_c(ctx->node_path);
 	ctx->info.flags = node->flags;
 	return &ctx->info;
 }

--- a/src/lib-storage/mailbox-tree.c	Wed Apr 11 20:40:18 2007 +0300
+++ b/src/lib-storage/mailbox-tree.c	Wed Apr 11 22:07:15 2007 +0300
@@ -1,6 +1,7 @@
-/* Copyright (C) 2003 Timo Sirainen */
+/* Copyright (C) 2003-2007 Timo Sirainen */
 
 #include "lib.h"
+#include "array.h"
 #include "str.h"
 #include "mailbox-tree.h"
 
@@ -10,26 +11,42 @@
 	struct mailbox_node *nodes;
 };
 
+struct mailbox_tree_iterate_context {
+	struct mailbox_node *root, *next_node;
+	unsigned int flags_mask;
+
+	char separator;
+
+	ARRAY_DEFINE(node_path, struct mailbox_node *);
+	string_t *path_str;
+	size_t parent_pos;
+
+	unsigned int first_child:1;
+};
+
 struct mailbox_tree_context *mailbox_tree_init(char separator)
 {
-	struct mailbox_tree_context *ctx;
+	struct mailbox_tree_context *tree;
 	pool_t pool;
 
 	pool = pool_alloconly_create(MEMPOOL_GROWING"mailbox_tree", 10240);
 
-	ctx = p_new(pool, struct mailbox_tree_context, 1);
-	ctx->pool = pool;
-	ctx->separator = separator;
-	return ctx;
+	tree = p_new(pool, struct mailbox_tree_context, 1);
+	tree->pool = pool;
+	tree->separator = separator;
+	return tree;
 }
 
-void mailbox_tree_deinit(struct mailbox_tree_context *ctx)
+void mailbox_tree_deinit(struct mailbox_tree_context **_tree)
 {
-	pool_unref(ctx->pool);
+	struct mailbox_tree_context *tree = *_tree;
+
+	*_tree = NULL;
+	pool_unref(tree->pool);
 }
 
 static struct mailbox_node *
-mailbox_tree_traverse(struct mailbox_tree_context *ctx, const char *path,
+mailbox_tree_traverse(struct mailbox_tree_context *tree, const char *path,
 		      bool create, bool *created)
 {
 	struct mailbox_node **node;
@@ -40,19 +57,19 @@
 		*created = FALSE;
 
 	if (path == NULL)
-		return ctx->nodes;
+		return tree->nodes;
 
 	t_push();
 
 	if (strncasecmp(path, "INBOX", 5) == 0 &&
-	    (path[5] == '\0' || path[5] == ctx->separator))
+	    (path[5] == '\0' || path[5] == tree->separator))
 		path = t_strdup_printf("INBOX%s", path+5);
 
-	node = &ctx->nodes;
+	node = &tree->nodes;
 
 	str = t_str_new(strlen(path)+1);
 	for (name = path;; path++) {
-		if (*path != ctx->separator && *path != '\0')
+		if (*path != tree->separator && *path != '\0')
 			continue;
 
 		str_truncate(str, 0);
@@ -72,8 +89,8 @@
 			if (!create)
 				break;
 
-			*node = p_new(ctx->pool, struct mailbox_node, 1);
-			(*node)->name = p_strdup(ctx->pool, name);
+			*node = p_new(tree->pool, struct mailbox_node, 1);
+			(*node)->name = p_strdup(tree->pool, name);
 
 			if (*path != '\0') {
 				(*node)->flags = MAILBOX_NONEXISTENT |
@@ -96,14 +113,107 @@
 }
 
 struct mailbox_node *
-mailbox_tree_get(struct mailbox_tree_context *ctx, const char *path,
+mailbox_tree_get(struct mailbox_tree_context *tree, const char *path,
 		 bool *created)
 {
-	return mailbox_tree_traverse(ctx, path, TRUE, created);
+	return mailbox_tree_traverse(tree, path, TRUE, created);
 }
 
 struct mailbox_node *
-mailbox_tree_update(struct mailbox_tree_context *ctx, const char *path)
+mailbox_tree_update(struct mailbox_tree_context *tree, const char *path)
+{
+	return mailbox_tree_traverse(tree, path, FALSE, NULL);
+}
+
+struct mailbox_tree_iterate_context *
+mailbox_tree_iterate_init(struct mailbox_tree_context *tree,
+			  struct mailbox_node *root, unsigned int flags_mask)
+{
+	struct mailbox_tree_iterate_context *ctx;
+
+	ctx = i_new(struct mailbox_tree_iterate_context, 1);
+	ctx->separator = tree->separator;
+	ctx->root = root != NULL ? root : mailbox_tree_get(tree, NULL, NULL);
+	ctx->flags_mask = flags_mask;
+	ctx->path_str = str_new(default_pool, 256);
+	i_array_init(&ctx->node_path, 16);
+
+	ctx->next_node = ctx->root;
+	return ctx;
+}
+
+static void
+mailbox_tree_iterate_set_next_node(struct mailbox_tree_iterate_context *ctx)
 {
-	return mailbox_tree_traverse(ctx, path, FALSE, NULL);
+	struct mailbox_node *node = ctx->next_node;
+	struct mailbox_node *const *nodes;
+	unsigned int i, count;
+
+	if (node->children != NULL) {
+		array_append(&ctx->node_path, &node, 1);
+		ctx->parent_pos = str_len(ctx->path_str);
+		node = node->children;
+		ctx->first_child = TRUE;
+	} else if (node->next != NULL) {
+		node = node->next;
+	} else {
+		nodes = array_get(&ctx->node_path, &count);
+		node = NULL;
+		for (i = count; i != 0; i--) {
+			unsigned int len = strlen(nodes[i-1]->name) + 1;
+
+			i_assert(len <= ctx->parent_pos);
+			ctx->parent_pos -= len;
+			if (nodes[i-1]->next != NULL) {
+				node = nodes[i-1]->next;
+				ctx->first_child = TRUE;
+				i--;
+
+				if (ctx->parent_pos != 0)
+					ctx->parent_pos--;
+				break;
+			}
+		}
+		array_delete(&ctx->node_path, i, count - i);
+	}
+
+	ctx->next_node = node;
 }
+
+struct mailbox_node *
+mailbox_tree_iterate_next(struct mailbox_tree_iterate_context *ctx,
+			  const char **path_r)
+{
+	struct mailbox_node *node;
+
+	do {
+		node = ctx->next_node;
+		if (node == NULL)
+			return NULL;
+
+		str_truncate(ctx->path_str, ctx->parent_pos);
+		if (ctx->first_child) {
+			ctx->first_child = FALSE;
+			if (ctx->parent_pos != 0) {
+				str_append_c(ctx->path_str, ctx->separator);
+				ctx->parent_pos++;
+			}
+		}
+		str_append(ctx->path_str, node->name);
+
+		mailbox_tree_iterate_set_next_node(ctx);
+	} while ((node->flags & ctx->flags_mask) != ctx->flags_mask);
+
+	*path_r = str_c(ctx->path_str);
+	return node;
+}
+
+void mailbox_tree_iterate_deinit(struct mailbox_tree_iterate_context **_ctx)
+{
+	struct mailbox_tree_iterate_context *ctx = *_ctx;
+
+	*_ctx = NULL;
+	str_free(&ctx->path_str);
+	array_free(&ctx->node_path);
+	i_free(ctx);
+}

--- a/src/lib-storage/mailbox-tree.h	Wed Apr 11 20:40:18 2007 +0300
+++ b/src/lib-storage/mailbox-tree.h	Wed Apr 11 22:07:15 2007 +0300
@@ -12,13 +12,21 @@
 };
 
 struct mailbox_tree_context *mailbox_tree_init(char separator);
-void mailbox_tree_deinit(struct mailbox_tree_context *ctx);
+void mailbox_tree_deinit(struct mailbox_tree_context **tree);
 
 struct mailbox_node *
-mailbox_tree_get(struct mailbox_tree_context *ctx, const char *path,
+mailbox_tree_get(struct mailbox_tree_context *tree, const char *path,
 		 bool *created);
 
 struct mailbox_node *
-mailbox_tree_update(struct mailbox_tree_context *ctx, const char *path);
+mailbox_tree_update(struct mailbox_tree_context *tree, const char *path);
+
+struct mailbox_tree_iterate_context *
+mailbox_tree_iterate_init(struct mailbox_tree_context *tree,
+			  struct mailbox_node *root, unsigned int flags_mask);
+struct mailbox_node *
+mailbox_tree_iterate_next(struct mailbox_tree_iterate_context *ctx,
+			  const char **path_r);
+void mailbox_tree_iterate_deinit(struct mailbox_tree_iterate_context **ctx);
 
 #endif