Split recursive directory iterator

The recursive part and the filter part are split up, the recursive
iterator wrapper is moved into libsquashfs and the libio iterator
is modified to use that internally instead of implementig the
recursion step.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

5 files changed, 553 insertions, 133 deletions

diff --git a/include/sqfs/io.h b/include/sqfs/io.h
index e851ea1..f148502 100644
--- a/include/sqfs/io.h
+++ b/include/sqfs/io.h
@@ -606,6 +606,23 @@ SQFS_API int sqfs_dir_iterator_create_native(sqfs_dir_iterator_t **out,
 					     const char *path,
 					     sqfs_u32 flags);
 
+/**
+ * @brief Construct a recursive directory iterator
+ *
+ * @memberof sqfs_dir_iterator_t
+ *
+ * The recursive directory iterator automatcally enters sub directories
+ * and adds the parent path as prefix to the entries. The "." and ".."
+ * entries are filtered out.
+ *
+ * @param out Returns a pointer to a recursive directory iterator
+ * @param base The root directory iterator used as base
+ *
+ * @return Zero on success, an @ref SQFS_ERROR code on failure.
+ */
+SQFS_API int sqfs_dir_iterator_create_recursive(sqfs_dir_iterator_t **out,
+						sqfs_dir_iterator_t *base);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/io/src/dir_tree_iterator.c b/lib/io/src/dir_tree_iterator.c
index 0ec478c..3c25529 100644
--- a/lib/io/src/dir_tree_iterator.c
+++ b/lib/io/src/dir_tree_iterator.c
@@ -13,53 +13,18 @@
 #include <stdlib.h>
 #include <string.h>
 
-typedef struct dir_stack_t {
-	struct dir_stack_t *next;
-	sqfs_dir_iterator_t *dir;
-	char name[];
-} dir_stack_t;
-
 typedef struct {
 	sqfs_dir_iterator_t base;
 
 	dir_tree_cfg_t cfg;
 	int state;
-	dir_stack_t *top;
+	sqfs_dir_iterator_t *rec;
 } dir_tree_iterator_t;
 
-static void pop(dir_tree_iterator_t *it)
-{
-	if (it->top != NULL) {
-		dir_stack_t *ent = it->top;
-		it->top = it->top->next;
-
-		sqfs_drop(ent->dir);
-		free(ent);
-	}
-}
-
-static int push(dir_tree_iterator_t *it, const char *name,
-		sqfs_dir_iterator_t *dir)
-{
-	dir_stack_t *ent = alloc_flex(sizeof(*ent), 1, strlen(name) + 1);
-
-	if (ent == NULL)
-		return SQFS_ERROR_ALLOC;
-
-	strcpy(ent->name, name);
-	ent->dir = sqfs_grab(dir);
-	ent->next = it->top;
-	it->top = ent;
-	return 0;
-}
-
 static bool should_skip(const dir_tree_iterator_t *dir, const sqfs_dir_entry_t *ent)
 {
 	unsigned int type_mask;
 
-	if (!strcmp(ent->name, ".") || !strcmp(ent->name, ".."))
-		return true;
-
 	if ((dir->cfg.flags & DIR_SCAN_ONE_FILESYSTEM)) {
 		if (ent->flags & SQFS_DIR_ENTRY_FLAG_MOUNT_POINT)
 			return true;
@@ -80,20 +45,11 @@ static bool should_skip(const dir_tree_iterator_t *dir, const sqfs_dir_entry_t *
 
 static sqfs_dir_entry_t *expand_path(const dir_tree_iterator_t *it, sqfs_dir_entry_t *ent)
 {
-	size_t slen = strlen(ent->name) + 1, plen = 0;
-	dir_stack_t *sit;
-	char *dst;
-
-	for (sit = it->top; sit != NULL; sit = sit->next) {
-		if (sit->name[0] != '\0')
-			plen += strlen(sit->name) + 1;
-	}
-
-	if (it->cfg.prefix != NULL && it->cfg.prefix[0] != '\0')
-		plen += strlen(it->cfg.prefix) + 1;
-
-	if (plen > 0) {
+	if (it->cfg.prefix != NULL && it->cfg.prefix[0] != '\0') {
+		size_t plen = strlen(it->cfg.prefix) + 1;
+		size_t slen = strlen(ent->name) + 1;
 		void *new = realloc(ent, sizeof(*ent) + plen + slen);
+
 		if (new == NULL) {
 			free(ent);
 			return NULL;
@@ -101,22 +57,9 @@ static sqfs_dir_entry_t *expand_path(const dir_tree_iterator_t *it, sqfs_dir_ent
 
 		ent = new;
 		memmove(ent->name + plen, ent->name, slen);
-		dst = ent->name + plen;
-
-		for (sit = it->top; sit != NULL; sit = sit->next) {
-			size_t len = strlen(sit->name);
-			if (len > 0) {
-				*(--dst) = '/';
-				dst -= len;
-				memcpy(dst, sit->name, len);
-			}
-		}
 
-		if (it->cfg.prefix != NULL && it->cfg.prefix[0] != '\0') {
-			size_t len = strlen(it->cfg.prefix);
-			memcpy(ent->name, it->cfg.prefix, len);
-			ent->name[len] = '/';
-		}
+		memcpy(ent->name, it->cfg.prefix, plen - 1);
+		ent->name[plen - 1] = '/';
 	}
 
 	return ent;
@@ -145,48 +88,36 @@ static void destroy(sqfs_object_t *obj)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)obj;
 
-	while (it->top != NULL)
-		pop(it);
-
+	sqfs_drop(it->rec);
 	free(it);
 }
 
 static int next(sqfs_dir_iterator_t *base, sqfs_dir_entry_t **out)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
-	sqfs_dir_iterator_t *sub;
 	sqfs_dir_entry_t *ent;
 	int ret;
+
+	if (it->state)
+		return it->state;
 retry:
 	*out = NULL;
-	sub = NULL;
 	ent = NULL;
 
-	if (it->state != 0)
-		return it->state;
-
 	for (;;) {
-		if (it->top == NULL) {
-			ret = 1;
-			goto fail;
-		}
-
-		ret = it->top->dir->next(it->top->dir, &ent);
-		if (ret < 0)
-			goto fail;
-
-		if (ret > 0) {
-			pop(it);
-			continue;
+		ret = it->rec->next(it->rec, &ent);
+		if (ret != 0) {
+			it->state = ret;
+			return ret;
 		}
 
-		if (should_skip(it, ent)) {
-			free(ent);
-			ent = NULL;
-			continue;
-		}
+		if (!should_skip(it, ent))
+			break;
 
-		break;
+		if (S_ISDIR(ent->mode))
+			it->rec->ignore_subdir(it->rec);
+		free(ent);
+		ent = NULL;
 	}
 
 	ent = expand_path(it, ent);
@@ -198,19 +129,8 @@ retry:
 	apply_changes(it, ent);
 
 	if (S_ISDIR(ent->mode)) {
-		if (!(it->cfg.flags & DIR_SCAN_NO_RECURSION)) {
-			const char *name = strrchr(ent->name, '/');
-			name = (name == NULL) ? ent->name : (name + 1);
-
-			ret = it->top->dir->open_subdir(it->top->dir, &sub);
-			if (ret != 0)
-				goto fail;
-
-			ret = push(it, name, sub);
-			sqfs_drop(sub);
-			if (ret != 0)
-				goto fail;
-		}
+		if (it->cfg.flags & DIR_SCAN_NO_RECURSION)
+			it->rec->ignore_subdir(it->rec);
 
 		if (it->cfg.flags & DIR_SCAN_NO_DIR) {
 			free(ent);
@@ -237,65 +157,54 @@ retry:
 
 	*out = ent;
 	return it->state;
-fail:
-	free(ent);
-	it->state = ret;
-	return it->state;
 }
 
 static int read_link(sqfs_dir_iterator_t *base, char **out)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
 
-	if (it->top == NULL) {
-		*out = NULL;
-		return SQFS_ERROR_NO_ENTRY;
-	}
+	if (it->state)
+		return it->state;
 
-	return it->top->dir->read_link(it->top->dir, out);
+	return it->rec->read_link(it->rec, out);
 }
 
 static int open_subdir(sqfs_dir_iterator_t *base, sqfs_dir_iterator_t **out)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
 
-	if (it->top == NULL) {
-		*out = NULL;
-		return SQFS_ERROR_NO_ENTRY;
-	}
+	if (it->state)
+		return it->state;
 
-	return it->top->dir->open_subdir(it->top->dir, out);
+	return it->rec->open_subdir(it->rec, out);
 }
 
 static void ignore_subdir(sqfs_dir_iterator_t *base)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
 
-	pop(it);
+	if (it->state == 0)
+		it->rec->ignore_subdir(it->rec);
 }
 
 static int open_file_ro(sqfs_dir_iterator_t *base, sqfs_istream_t **out)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
 
-	if (it->top == NULL) {
-		*out = NULL;
-		return SQFS_ERROR_NO_ENTRY;
-	}
+	if (it->state)
+		return it->state;
 
-	return it->top->dir->open_file_ro(it->top->dir, out);
+	return it->rec->open_file_ro(it->rec, out);
 }
 
 static int read_xattr(sqfs_dir_iterator_t *base, sqfs_xattr_t **out)
 {
 	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
 
-	if (it->top == NULL) {
-		*out = NULL;
-		return SQFS_ERROR_NO_ENTRY;
-	}
+	if (it->state)
+		return it->state;
 
-	return it->top->dir->read_xattr(it->top->dir, out);
+	return it->rec->read_xattr(it->rec, out);
 }
 
 sqfs_dir_iterator_t *dir_tree_iterator_create(const char *path,
@@ -318,9 +227,9 @@ sqfs_dir_iterator_t *dir_tree_iterator_create(const char *path,
 		goto fail;
 	}
 
-	ret = push(it, "", dir);
-	dir = sqfs_drop(dir);
-	if (ret != 0) {
+	ret = sqfs_dir_iterator_create_recursive(&it->rec, dir);
+	sqfs_drop(dir);
+	if (ret) {
 		fprintf(stderr, "%s: out of memory\n", path);
 		goto fail;
 	}
diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am
index 5005c48..053dab8 100644
--- a/lib/sqfs/Makemodule.am
+++ b/lib/sqfs/Makemodule.am
@@ -34,7 +34,8 @@ libsquashfs_la_SOURCES = $(LIBSQFS_HEARDS) lib/sqfs/src/id_table.c \
 	lib/sqfs/src/frag_table.c lib/sqfs/src/block_writer.c \
 	lib/sqfs/src/misc.c lib/sqfs/src/io/istream.c \
 	lib/sqfs/src/io/ostream.c lib/sqfs/src/io/file.c \
-	lib/sqfs/src/io/stream_api.c lib/sqfs/src/dir_entry.c
+	lib/sqfs/src/io/stream_api.c lib/sqfs/src/dir_entry.c \
+	lib/sqfs/src/io/dir_rec.c
 libsquashfs_la_CPPFLAGS = $(AM_CPPFLAGS)
 libsquashfs_la_LDFLAGS = $(AM_LDFLAGS) -version-info $(LIBSQUASHFS_SO_VERSION)
 libsquashfs_la_CFLAGS = $(AM_CFLAGS) $(PTHREAD_CFLAGS) $(ZLIB_CFLAGS)
@@ -136,9 +137,12 @@ test_istream_skip_LDADD = libsquashfs.la libio.a libutil.a libcompat.a
 test_stream_splice_SOURCES = lib/sqfs/test/stream_splice.c
 test_stream_splice_LDADD = libsquashfs.la libio.a libutil.a libcompat.a
 
+test_rec_dir_SOURCES = lib/sqfs/test/rec_dir.c
+test_rec_dir_LDADD = libsquashfs.la libio.a libutil.a libcompat.a
+
 LIBSQFS_TESTS = \
 	test_abi test_xattr test_table test_xattr_writer test_get_node_path \
-	test_istream_read test_istream_skip test_stream_splice
+	test_istream_read test_istream_skip test_stream_splice test_rec_dir
 noinst_PROGRAMS += xattr_benchmark
 
 check_PROGRAMS += $(LIBSQFS_TESTS)
diff --git a/lib/sqfs/src/io/dir_rec.c b/lib/sqfs/src/io/dir_rec.c
new file mode 100644
index 0000000..a5d53af
--- /dev/null
+++ b/lib/sqfs/src/io/dir_rec.c
@@ -0,0 +1,253 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * dir_rec.c
+ *
+ * Copyright (C) 2023 David Oberhollenzer <goliath@infraroot.at>
+ */
+#define SQFS_BUILDING_DLL
+#include "config.h"
+
+#include "util/util.h"
+#include "sqfs/dir_entry.h"
+#include "sqfs/error.h"
+#include "sqfs/io.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct dir_stack_t {
+	struct dir_stack_t *next;
+	sqfs_dir_iterator_t *dir;
+	char name[];
+} dir_stack_t;
+
+typedef struct {
+	sqfs_dir_iterator_t base;
+
+	int state;
+	dir_stack_t *top;
+
+	dir_stack_t *next_top;
+} dir_tree_iterator_t;
+
+static void pop(dir_tree_iterator_t *it)
+{
+	if (it->top != NULL) {
+		dir_stack_t *ent = it->top;
+		it->top = it->top->next;
+
+		sqfs_drop(ent->dir);
+		free(ent);
+	}
+}
+
+static sqfs_dir_entry_t *expand_path(const dir_tree_iterator_t *it,
+				     sqfs_dir_entry_t *ent)
+{
+	size_t slen = strlen(ent->name) + 1, plen = 0;
+	char *dst;
+	void *new;
+
+	for (dir_stack_t *sit = it->top; sit != NULL; sit = sit->next) {
+		if (sit->name[0] != '\0')
+			plen += strlen(sit->name) + 1;
+	}
+
+	if (plen == 0)
+		return ent;
+
+	new = realloc(ent, sizeof(*ent) + plen + slen);
+	if (new == NULL) {
+		free(ent);
+		return NULL;
+	}
+
+	ent = new;
+	memmove(ent->name + plen, ent->name, slen);
+	dst = ent->name + plen;
+
+	for (dir_stack_t *sit = it->top; sit != NULL; sit = sit->next) {
+		size_t len = strlen(sit->name);
+		if (len > 0) {
+			*(--dst) = '/';
+			dst -= len;
+			memcpy(dst, sit->name, len);
+		}
+	}
+
+	return ent;
+}
+
+/*****************************************************************************/
+
+static void destroy(sqfs_object_t *obj)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)obj;
+
+	while (it->top != NULL)
+		pop(it);
+
+	if (it->next_top != NULL) {
+		sqfs_drop(it->next_top->dir);
+		free(it->next_top);
+	}
+
+	free(it);
+}
+
+static int next(sqfs_dir_iterator_t *base, sqfs_dir_entry_t **out)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+	sqfs_dir_entry_t *ent = NULL;
+	int ret;
+
+	*out = NULL;
+	if (it->state != 0)
+		return it->state;
+
+	if (it->next_top != NULL) {
+		it->next_top->next = it->top;
+		it->top = it->next_top;
+		it->next_top = NULL;
+	}
+
+	for (;;) {
+		if (it->top == NULL) {
+			ret = 1;
+			goto fail;
+		}
+
+		ret = it->top->dir->next(it->top->dir, &ent);
+		if (ret < 0)
+			goto fail;
+
+		if (ret > 0) {
+			pop(it);
+			continue;
+		}
+
+		if (!strcmp(ent->name, ".") || !strcmp(ent->name, "..")) {
+			free(ent);
+			ent = NULL;
+			continue;
+		}
+
+		break;
+	}
+
+	ent = expand_path(it, ent);
+	if (ent == NULL) {
+		it->state = SQFS_ERROR_ALLOC;
+		return it->state;
+	}
+
+	if (S_ISDIR(ent->mode)) {
+		sqfs_dir_iterator_t *sub = NULL;
+		const char *name = strrchr(ent->name, '/');
+		name = (name == NULL) ? ent->name : (name + 1);
+
+		ret = it->top->dir->open_subdir(it->top->dir, &sub);
+		if (ret != 0)
+			goto fail;
+
+		it->next_top = alloc_flex(sizeof(*(it->next_top)), 1,
+					  strlen(name) + 1);
+		if (it->next_top == NULL) {
+			sqfs_drop(sub);
+			goto fail;
+		}
+
+		strcpy(it->next_top->name, name);
+		it->next_top->dir = sub;
+	}
+
+	*out = ent;
+	return it->state;
+fail:
+	free(ent);
+	it->state = ret;
+	return it->state;
+}
+
+static int read_link(sqfs_dir_iterator_t *base, char **out)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+
+	*out = NULL;
+	if (it->top == NULL)
+		return SQFS_ERROR_NO_ENTRY;
+
+	return it->top->dir->read_link(it->top->dir, out);
+}
+
+static int open_subdir(sqfs_dir_iterator_t *base, sqfs_dir_iterator_t **out)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+
+	*out = NULL;
+	if (it->top == NULL)
+		return SQFS_ERROR_NO_ENTRY;
+
+	return it->top->dir->open_subdir(it->top->dir, out);
+}
+
+static void ignore_subdir(sqfs_dir_iterator_t *base)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+
+	if (it->next_top != NULL) {
+		sqfs_drop(it->next_top->dir);
+		free(it->next_top);
+		it->next_top = NULL;
+	}
+}
+
+static int open_file_ro(sqfs_dir_iterator_t *base, sqfs_istream_t **out)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+
+	*out = NULL;
+	if (it->top == NULL)
+		return SQFS_ERROR_NO_ENTRY;
+
+	return it->top->dir->open_file_ro(it->top->dir, out);
+}
+
+static int read_xattr(sqfs_dir_iterator_t *base, sqfs_xattr_t **out)
+{
+	dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+
+	*out = NULL;
+	if (it->top == NULL)
+		return SQFS_ERROR_NO_ENTRY;
+
+	return it->top->dir->read_xattr(it->top->dir, out);
+}
+
+int sqfs_dir_iterator_create_recursive(sqfs_dir_iterator_t **out,
+				       sqfs_dir_iterator_t *base)
+{
+	dir_tree_iterator_t *it = calloc(1, sizeof(*it));
+
+	*out = NULL;
+	if (it == NULL)
+		return SQFS_ERROR_ALLOC;
+
+	it->next_top = calloc(1, sizeof(*(it->next_top)) + 1);
+	if (it->next_top == NULL) {
+		free(it);
+		return SQFS_ERROR_ALLOC;
+	}
+	it->next_top->dir = sqfs_grab(base);
+
+	sqfs_object_init(it, destroy, NULL);
+	((sqfs_dir_iterator_t *)it)->next = next;
+	((sqfs_dir_iterator_t *)it)->read_link = read_link;
+	((sqfs_dir_iterator_t *)it)->open_subdir = open_subdir;
+	((sqfs_dir_iterator_t *)it)->ignore_subdir = ignore_subdir;
+	((sqfs_dir_iterator_t *)it)->open_file_ro = open_file_ro;
+	((sqfs_dir_iterator_t *)it)->read_xattr = read_xattr;
+
+	*out = (sqfs_dir_iterator_t *)it;
+	return 0;
+}
diff --git a/lib/sqfs/test/rec_dir.c b/lib/sqfs/test/rec_dir.c
new file mode 100644
index 0000000..00e38aa
--- /dev/null
+++ b/lib/sqfs/test/rec_dir.c
@@ -0,0 +1,237 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * rec_dir.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/test.h"
+#include "sqfs/dir_entry.h"
+#include "sqfs/inode.h"
+#include "sqfs/io.h"
+#include "compat.h"
+
+typedef struct {
+	sqfs_dir_iterator_t obj;
+
+	bool current_is_dir;
+	size_t level;
+	size_t idx;
+} dummy_it_t;
+
+static int dummy_read_link(sqfs_dir_iterator_t *it, char **out)
+{
+	(void)it; (void)out;
+	TEST_ASSERT(0);
+	return 0;
+}
+
+static void dummy_ignore_subdir(sqfs_dir_iterator_t *it)
+{
+	(void)it;
+	TEST_ASSERT(0);
+}
+
+static int dummy_open_file_ro(sqfs_dir_iterator_t *it, sqfs_istream_t **out)
+{
+	(void)it; (void)out;
+	TEST_ASSERT(0);
+	return 0;
+}
+
+static int dummy_read_xattr(sqfs_dir_iterator_t *it, sqfs_xattr_t **out)
+{
+	(void)it; (void)out;
+	TEST_ASSERT(0);
+	return 0;
+}
+
+static void destroy(sqfs_object_t *obj)
+{
+	free(obj);
+}
+
+static int dummy_next(sqfs_dir_iterator_t *base, sqfs_dir_entry_t **out)
+{
+	dummy_it_t *it = (dummy_it_t *)base;
+	char buffer[3];
+
+	*out = NULL;
+	if (it->idx >= 4)
+		return 1;
+
+	buffer[0] = 'a' + it->idx;
+	buffer[1] = 'A' + it->idx;
+	buffer[2] = '\0';
+
+	if ((it->idx % 2) != 0 && it->level < 2) {
+		*out = sqfs_dir_entry_create(buffer,
+					     SQFS_INODE_MODE_DIR | 0755, 0);
+		it->current_is_dir = true;
+	} else {
+		*out = sqfs_dir_entry_create(buffer,
+					     SQFS_INODE_MODE_REG | 0644, 0);
+		it->current_is_dir = false;
+	}
+
+	it->idx += 1;
+	TEST_NOT_NULL((*out));
+	return 0;
+}
+
+static int dummy_open_subdir(sqfs_dir_iterator_t *base,
+			     sqfs_dir_iterator_t **out)
+{
+	dummy_it_t *it = (dummy_it_t *)base, *sub;
+
+	TEST_ASSERT(it->current_is_dir);
+
+	sub = calloc(1, sizeof(*sub));
+	TEST_NOT_NULL(sub);
+	sub->level = it->level + 1;
+
+	sqfs_object_init(sub, destroy, NULL);
+	((sqfs_dir_iterator_t *)sub)->read_link = dummy_read_link;
+	((sqfs_dir_iterator_t *)sub)->ignore_subdir = dummy_ignore_subdir;
+	((sqfs_dir_iterator_t *)sub)->open_file_ro = dummy_open_file_ro;
+	((sqfs_dir_iterator_t *)sub)->read_xattr = dummy_read_xattr;
+	((sqfs_dir_iterator_t *)sub)->next = dummy_next;
+	((sqfs_dir_iterator_t *)sub)->open_subdir = dummy_open_subdir;
+
+	*out = (sqfs_dir_iterator_t *)sub;
+	return 0;
+}
+
+static sqfs_dir_iterator_t *mkdummyit(void)
+{
+	dummy_it_t *it = calloc(1, sizeof(*it));
+	TEST_NOT_NULL(it);
+
+	sqfs_object_init(it, destroy, NULL);
+	((sqfs_dir_iterator_t *)it)->read_link = dummy_read_link;
+	((sqfs_dir_iterator_t *)it)->ignore_subdir = dummy_ignore_subdir;
+	((sqfs_dir_iterator_t *)it)->open_file_ro = dummy_open_file_ro;
+	((sqfs_dir_iterator_t *)it)->read_xattr = dummy_read_xattr;
+	((sqfs_dir_iterator_t *)it)->next = dummy_next;
+	((sqfs_dir_iterator_t *)it)->open_subdir = dummy_open_subdir;
+	return (sqfs_dir_iterator_t *)it;
+}
+
+static const struct {
+	const char *name;
+	bool isdir;
+} expect[] = {
+	{ "aA", false },
+	{ "bB", true },
+	{ "bB/aA", false },
+	{ "bB/bB", true },
+	{ "bB/bB/aA", false },
+	{ "bB/bB/bB", false },
+	{ "bB/bB/cC", false },
+	{ "bB/bB/dD", false },
+	{ "bB/cC", false },
+	{ "bB/dD", true },
+	{ "bB/dD/aA", false },
+	{ "bB/dD/bB", false },
+	{ "bB/dD/cC", false },
+	{ "bB/dD/dD", false },
+	{ "cC", false },
+	{ "dD", true },
+	{ "dD/aA", false },
+	{ "dD/bB", true },
+	{ "dD/bB/aA", false },
+	{ "dD/bB/bB", false },
+	{ "dD/bB/cC", false },
+	{ "dD/bB/dD", false },
+	{ "dD/cC", false },
+	{ "dD/dD", true },
+	{ "dD/dD/aA", false },
+	{ "dD/dD/bB", false },
+	{ "dD/dD/cC", false },
+	{ "dD/dD/dD", false },
+};
+
+int main(int argc, char **argv)
+{
+	sqfs_dir_iterator_t *it, *rec;
+	sqfs_dir_entry_t *ent;
+	int ret;
+	(void)argc; (void)argv;
+
+	/* simple test of the dummy iterator */
+	it = mkdummyit();
+
+	ret = it->next(it, &ent);
+	TEST_EQUAL_I(ret, 0);
+	TEST_STR_EQUAL(ent->name, "aA");
+	TEST_ASSERT(S_ISREG(ent->mode));
+	free(ent);
+
+	ret = it->next(it, &ent);
+	TEST_EQUAL_I(ret, 0);
+	TEST_STR_EQUAL(ent->name, "bB");
+	TEST_ASSERT(S_ISDIR(ent->mode));
+	free(ent);
+
+	ret = it->next(it, &ent);
+	TEST_EQUAL_I(ret, 0);
+	TEST_STR_EQUAL(ent->name, "cC");
+	TEST_ASSERT(S_ISREG(ent->mode));
+	free(ent);
+
+	ret = it->next(it, &ent);
+	TEST_EQUAL_I(ret, 0);
+	TEST_STR_EQUAL(ent->name, "dD");
+	TEST_ASSERT(S_ISDIR(ent->mode));
+	free(ent);
+
+	ret = it->next(it, &ent);
+	TEST_EQUAL_I(ret, 1);
+	TEST_NULL(ent);
+
+	sqfs_drop(it);
+
+	/* construct recursive iterator */
+	it = mkdummyit();
+
+	ret = sqfs_dir_iterator_create_recursive(&rec, it);
+	sqfs_drop(it);
+	TEST_EQUAL_I(ret, 0);
+	TEST_NOT_NULL(rec);
+	it = rec;
+
+	for (size_t i = 0; i < sizeof(expect) / sizeof(expect[0]); ++i) {
+		ret = it->next(it, &ent);
+		TEST_EQUAL_I(ret, 0);
+
+		if (strcmp(ent->name, expect[i].name) != 0) {
+			fprintf(stderr,
+				"Entry %u should be `%s`, but is `%s`\n",
+				(unsigned int)i, expect[i].name, ent->name);
+			return EXIT_FAILURE;
+		}
+
+		if (expect[i].isdir && !S_ISDIR(ent->mode)) {
+			fprintf(stderr,
+				"Entry %u (`%s`) should be dir: "
+				"mode is `%u`\n",
+				(unsigned int)i, ent->name, ent->mode);
+			return EXIT_FAILURE;
+		} else if (!expect[i].isdir && !S_ISREG(ent->mode)) {
+			fprintf(stderr,
+				"Entry %u (`%s`) should be file: "
+				"mode is `%u`\n",
+				(unsigned int)i, ent->name, ent->mode);
+			return EXIT_FAILURE;
+		}
+
+		free(ent);
+	}
+
+	ret = it->next(it, &ent);
+	TEST_EQUAL_I(ret, 1);
+
+	sqfs_drop(it);
+	return EXIT_SUCCESS;
+}