aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2023-04-21 23:02:32 +0200
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2023-04-29 00:26:32 +0200
commit1b832b6dfb8d9da2b94f07ccc95c03614b378786 (patch)
tree953d52de8ccf3573f6cf68740c64d017623578d9 /lib
parent9caccbfec112c53133aff09119eda623ae0644fe (diff)
libutil: Add a stacked, recursive directory tree iterator
The concept is simple: Use the existing, platform dependent iterator to walk a directory. If a directory entry is encountered, recurse into it using the open_subdir handler, reconstruct the full path for any entries discovered using the directory stack. An additional function is added to skip a sub-hierarchy. Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>
Diffstat (limited to 'lib')
-rw-r--r--lib/util/Makemodule.am13
-rw-r--r--lib/util/src/dir_tree_iterator.c215
-rw-r--r--lib/util/test/dir_iterator.c36
-rw-r--r--lib/util/test/dir_tree_iterator.c197
-rw-r--r--lib/util/test/testdir/dirb/dirx/file_x00
-rw-r--r--lib/util/test/testdir/dirb/dirx/file_x10
-rw-r--r--lib/util/test/testdir/dirb/dirx/file_x20
7 files changed, 444 insertions, 17 deletions
diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am
index 04c5989..26056ea 100644
--- a/lib/util/Makemodule.am
+++ b/lib/util/Makemodule.am
@@ -2,14 +2,15 @@ libutil_a_SOURCES = include/util/util.h include/util/str_table.h \
include/util/hash_table.h include/util/test.h include/util/rbtree.h \
include/util/array.h include/util/threadpool.h \
include/util/w32threadwrap.h include/util/mempool.h \
- include/util/dir_iterator.h \
+ include/util/dir_iterator.h include/util/dir_tree_iterator.h \
lib/util/src/str_table.c lib/util/src/alloc.c lib/util/src/rbtree.c \
lib/util/src/array.c lib/util/src/xxhash.c lib/util/src/hash_table.c \
lib/util/src/fast_urem_by_const.h lib/util/src/threadpool_serial.c \
lib/util/src/is_memory_zero.c lib/util/src/mkdir_p.c \
lib/util/src/canonicalize_name.c lib/util/src/filename_sane.c \
lib/util/src/source_date_epoch.c lib/util/src/file_cmp.c \
- lib/util/src/hex_decode.c lib/util/src/base64_decode.c
+ lib/util/src/hex_decode.c lib/util/src/base64_decode.c \
+ lib/util/src/dir_tree_iterator.c
libutil_a_CFLAGS = $(AM_CFLAGS)
libutil_a_CPPFLAGS = $(AM_CPPFLAGS)
@@ -85,10 +86,16 @@ test_dir_iterator_LDADD = libutil.a libcompat.a
test_dir_iterator_CPPFLAGS = $(AM_CPPFLAGS)
test_dir_iterator_CPPFLAGS += -DTESTPATH=$(top_srcdir)/lib/util/test/testdir
+test_dir_tree_iterator_SOURCES = lib/util/test/dir_tree_iterator.c
+test_dir_tree_iterator_LDADD = libutil.a libcompat.a
+test_dir_tree_iterator_CPPFLAGS = $(AM_CPPFLAGS)
+test_dir_tree_iterator_CPPFLAGS += -DTESTPATH=$(top_srcdir)/lib/util/test/testdir
+
LIBUTIL_TESTS = \
test_str_table test_rbtree test_xxhash test_threadpool test_ismemzero \
test_canonicalize_name test_filename_sane test_filename_sane_w32 \
- test_sdate_epoch test_hex_decode test_base64_decode test_dir_iterator
+ test_sdate_epoch test_hex_decode test_base64_decode test_dir_iterator \
+ test_dir_tree_iterator
check_PROGRAMS += $(LIBUTIL_TESTS)
TESTS += $(LIBUTIL_TESTS)
diff --git a/lib/util/src/dir_tree_iterator.c b/lib/util/src/dir_tree_iterator.c
new file mode 100644
index 0000000..88b6840
--- /dev/null
+++ b/lib/util/src/dir_tree_iterator.c
@@ -0,0 +1,215 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * dir_tree_iterator.c
+ *
+ * Copyright (C) 2023 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/dir_tree_iterator.h"
+#include "util/util.h"
+#include "sqfs/error.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct dir_stack_t {
+ struct dir_stack_t *next;
+ dir_iterator_t *dir;
+ char name[];
+} dir_stack_t;
+
+typedef struct {
+ dir_iterator_t base;
+
+ int state;
+ dir_stack_t *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 int push(dir_tree_iterator_t *it, const char *name, 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 void destroy(sqfs_object_t *obj)
+{
+ dir_tree_iterator_t *it = (dir_tree_iterator_t *)obj;
+
+ while (it->top != NULL)
+ pop(it);
+
+ free(it);
+}
+
+static int next(dir_iterator_t *base, dir_entry_t **out)
+{
+ dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+ dir_iterator_t *sub = NULL;
+ dir_entry_t *ent = NULL;
+ dir_stack_t *sit = NULL;
+ size_t plen = 0;
+ int ret;
+
+ *out = 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;
+ }
+
+ if (!strcmp(ent->name, ".") || !strcmp(ent->name, "..")) {
+ free(ent);
+ ent = NULL;
+ continue;
+ }
+
+ break;
+ }
+
+ for (sit = it->top; sit != NULL; sit = sit->next) {
+ size_t len = strlen(sit->name);
+ if (len > 0)
+ plen += len + 1;
+ }
+
+ if (plen > 0) {
+ size_t slen = strlen(ent->name) + 1;
+ void *new = realloc(ent, sizeof(*ent) + plen + slen);
+ char *dst;
+
+ if (new == NULL) {
+ ret = SQFS_ERROR_ALLOC;
+ goto fail;
+ }
+
+ 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 (S_ISDIR(ent->mode)) {
+ ret = it->top->dir->open_subdir(it->top->dir, &sub);
+ if (ret != 0)
+ goto fail;
+
+ ret = push(it, ent->name + plen, sub);
+ sqfs_drop(sub);
+ if (ret != 0)
+ goto fail;
+ }
+
+ *out = ent;
+ return it->state;
+fail:
+ free(ent);
+ it->state = ret;
+ return it->state;
+}
+
+static int read_link(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;
+ }
+
+ return it->top->dir->read_link(it->top->dir, out);
+}
+
+static int open_subdir(dir_iterator_t *base, 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;
+ }
+
+ return it->top->dir->open_subdir(it->top->dir, out);
+}
+
+dir_iterator_t *dir_tree_iterator_create(const char *path)
+{
+ dir_tree_iterator_t *it = calloc(1, sizeof(*it));
+ dir_iterator_t *dir;
+ int ret;
+
+ if (it == NULL) {
+ perror(path);
+ return NULL;
+ }
+
+ dir = dir_iterator_create(path);
+ if (dir == NULL)
+ goto fail;
+
+ ret = push(it, "", dir);
+ dir = sqfs_drop(dir);
+ if (ret != 0) {
+ fprintf(stderr, "%s: out of memory\n", path);
+ goto fail;
+ }
+
+ sqfs_object_init(it, destroy, NULL);
+ ((dir_iterator_t *)it)->dev = it->top->dir->dev;
+ ((dir_iterator_t *)it)->next = next;
+ ((dir_iterator_t *)it)->read_link = read_link;
+ ((dir_iterator_t *)it)->open_subdir = open_subdir;
+
+ return (dir_iterator_t *)it;
+fail:
+ free(it);
+ return NULL;
+}
+
+void dir_tree_iterator_skip(dir_iterator_t *base)
+{
+ dir_tree_iterator_t *it = (dir_tree_iterator_t *)base;
+
+ pop(it);
+}
diff --git a/lib/util/test/dir_iterator.c b/lib/util/test/dir_iterator.c
index d209afd..5ebdaf7 100644
--- a/lib/util/test/dir_iterator.c
+++ b/lib/util/test/dir_iterator.c
@@ -144,25 +144,31 @@ int main(int argc, char **argv)
TEST_EQUAL_I(ret, 0);
ret = dir->next(dir, &ent[5]);
- TEST_NULL(ent[5]);
+ TEST_NOT_NULL(ent[5]);
+ TEST_EQUAL_I(ret, 0);
+
+ ret = dir->next(dir, &dent);
+ TEST_NULL(dent);
TEST_ASSERT(ret > 0);
dir = sqfs_drop(dir);
- qsort(ent, 5, sizeof(ent[0]), compare_entries);
+ qsort(ent, 6, sizeof(ent[0]), compare_entries);
TEST_STR_EQUAL(ent[0]->name, ".");
TEST_ASSERT(S_ISDIR(ent[0]->mode));
TEST_STR_EQUAL(ent[1]->name, "..");
TEST_ASSERT(S_ISDIR(ent[1]->mode));
- TEST_STR_EQUAL(ent[2]->name, "file_b0");
- TEST_ASSERT(S_ISREG(ent[2]->mode));
- TEST_STR_EQUAL(ent[3]->name, "file_b1");
+ TEST_STR_EQUAL(ent[2]->name, "dirx");
+ TEST_ASSERT(S_ISDIR(ent[2]->mode));
+ TEST_STR_EQUAL(ent[3]->name, "file_b0");
TEST_ASSERT(S_ISREG(ent[3]->mode));
- TEST_STR_EQUAL(ent[4]->name, "file_b2");
+ TEST_STR_EQUAL(ent[4]->name, "file_b1");
TEST_ASSERT(S_ISREG(ent[4]->mode));
+ TEST_STR_EQUAL(ent[5]->name, "file_b2");
+ TEST_ASSERT(S_ISREG(ent[5]->mode));
- for (i = 0; i < 5; ++i)
+ for (i = 0; i < 6; ++i)
free(ent[i]);
/* scan first sub hierarchy */
@@ -288,7 +294,7 @@ int main(int argc, char **argv)
free(ent[i]);
/* sub iterator b */
- for (i = 0; i < 5; ++i) {
+ for (i = 0; i < 6; ++i) {
ret = subb->next(subb, &ent[i]);
TEST_NOT_NULL(ent[0]);
TEST_EQUAL_I(ret, 0);
@@ -305,20 +311,22 @@ int main(int argc, char **argv)
TEST_ASSERT(ret > 0);
subb = sqfs_drop(subb);
- qsort(ent, 5, sizeof(ent[0]), compare_entries);
+ qsort(ent, 6, sizeof(ent[0]), compare_entries);
TEST_STR_EQUAL(ent[0]->name, ".");
TEST_ASSERT(S_ISDIR(ent[0]->mode));
TEST_STR_EQUAL(ent[1]->name, "..");
TEST_ASSERT(S_ISDIR(ent[1]->mode));
- TEST_STR_EQUAL(ent[2]->name, "file_b0");
- TEST_ASSERT(S_ISREG(ent[2]->mode));
- TEST_STR_EQUAL(ent[3]->name, "file_b1");
+ TEST_STR_EQUAL(ent[2]->name, "dirx");
+ TEST_ASSERT(S_ISDIR(ent[2]->mode));
+ TEST_STR_EQUAL(ent[3]->name, "file_b0");
TEST_ASSERT(S_ISREG(ent[3]->mode));
- TEST_STR_EQUAL(ent[4]->name, "file_b2");
+ TEST_STR_EQUAL(ent[4]->name, "file_b1");
TEST_ASSERT(S_ISREG(ent[4]->mode));
+ TEST_STR_EQUAL(ent[5]->name, "file_b2");
+ TEST_ASSERT(S_ISREG(ent[5]->mode));
- for (i = 0; i < 5; ++i)
+ for (i = 0; i < 6; ++i)
free(ent[i]);
/* sub iterator c */
diff --git a/lib/util/test/dir_tree_iterator.c b/lib/util/test/dir_tree_iterator.c
new file mode 100644
index 0000000..e47efed
--- /dev/null
+++ b/lib/util/test/dir_tree_iterator.c
@@ -0,0 +1,197 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * dir_tree_iterator.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/dir_tree_iterator.h"
+#include "sqfs/error.h"
+#include "util/test.h"
+#include "compat.h"
+
+static int compare_entries(const void *a, const void *b)
+{
+ const dir_entry_t *const *lhs = a;
+ const dir_entry_t *const *rhs = b;
+
+ return strcmp((*lhs)->name, (*rhs)->name);
+}
+
+int main(int argc, char **argv)
+{
+ dir_entry_t *ent[17];
+ dir_iterator_t *dir;
+ size_t i;
+ int ret;
+ (void)argc; (void)argv;
+
+ dir = dir_tree_iterator_create(TEST_PATH);
+ TEST_NOT_NULL(dir);
+
+ for (i = 0; i < 16; ++i) {
+ ret = dir->next(dir, &ent[i]);
+ TEST_NOT_NULL(ent[i]);
+ TEST_EQUAL_I(ret, 0);
+ printf("READ %s\n", ent[i]->name);
+ }
+
+ ret = dir->next(dir, &ent[16]);
+ TEST_NULL(ent[16]);
+ TEST_ASSERT(ret > 0);
+
+ dir = sqfs_drop(dir);
+
+ qsort(ent, 16, sizeof(ent[0]), compare_entries);
+
+ printf("After sort:\n");
+ for (i = 0; i < 16; ++i)
+ printf("%s\n", ent[i]->name);
+
+ TEST_STR_EQUAL(ent[0]->name, "dira");
+ TEST_ASSERT(S_ISDIR(ent[0]->mode));
+ TEST_STR_EQUAL(ent[1]->name, "dira/file_a0");
+ TEST_ASSERT(S_ISREG(ent[1]->mode));
+ TEST_STR_EQUAL(ent[2]->name, "dira/file_a1");
+ TEST_ASSERT(S_ISREG(ent[2]->mode));
+ TEST_STR_EQUAL(ent[3]->name, "dira/file_a2");
+ TEST_ASSERT(S_ISREG(ent[3]->mode));
+ TEST_STR_EQUAL(ent[4]->name, "dirb");
+ TEST_ASSERT(S_ISDIR(ent[4]->mode));
+ TEST_STR_EQUAL(ent[5]->name, "dirb/dirx");
+ TEST_ASSERT(S_ISDIR(ent[5]->mode));
+ TEST_STR_EQUAL(ent[6]->name, "dirb/dirx/file_x0");
+ TEST_ASSERT(S_ISREG(ent[6]->mode));
+ TEST_STR_EQUAL(ent[7]->name, "dirb/dirx/file_x1");
+ TEST_ASSERT(S_ISREG(ent[7]->mode));
+ TEST_STR_EQUAL(ent[8]->name, "dirb/dirx/file_x2");
+ TEST_ASSERT(S_ISREG(ent[8]->mode));
+ TEST_STR_EQUAL(ent[9]->name, "dirb/file_b0");
+ TEST_ASSERT(S_ISREG(ent[9]->mode));
+ TEST_STR_EQUAL(ent[10]->name, "dirb/file_b1");
+ TEST_ASSERT(S_ISREG(ent[10]->mode));
+ TEST_STR_EQUAL(ent[11]->name, "dirb/file_b2");
+ TEST_ASSERT(S_ISREG(ent[11]->mode));
+ TEST_STR_EQUAL(ent[12]->name, "dirc");
+ TEST_ASSERT(S_ISDIR(ent[12]->mode));
+ TEST_STR_EQUAL(ent[13]->name, "dirc/file_c0");
+ TEST_ASSERT(S_ISREG(ent[13]->mode));
+ TEST_STR_EQUAL(ent[14]->name, "dirc/file_c1");
+ TEST_ASSERT(S_ISREG(ent[14]->mode));
+ TEST_STR_EQUAL(ent[15]->name, "dirc/file_c2");
+ TEST_ASSERT(S_ISREG(ent[15]->mode));
+
+ for (i = 0; i < 16; ++i)
+ free(ent[i]);
+
+ /* retry with skipping */
+ printf("**********\n");
+
+ dir = dir_tree_iterator_create(TEST_PATH);
+ TEST_NOT_NULL(dir);
+
+ for (i = 0; i < 13; ++i) {
+ ret = dir->next(dir, &ent[i]);
+ TEST_NOT_NULL(ent[i]);
+ TEST_EQUAL_I(ret, 0);
+ printf("READ %s\n", ent[i]->name);
+
+ if (!strcmp(ent[i]->name, "dirb/dirx"))
+ dir_tree_iterator_skip(dir);
+ }
+
+ ret = dir->next(dir, &ent[13]);
+ TEST_NULL(ent[13]);
+ TEST_ASSERT(ret > 0);
+
+ dir = sqfs_drop(dir);
+
+ qsort(ent, 13, sizeof(ent[0]), compare_entries);
+
+ printf("After sort:\n");
+ for (i = 0; i < 13; ++i)
+ printf("%s\n", ent[i]->name);
+
+ TEST_STR_EQUAL(ent[0]->name, "dira");
+ TEST_ASSERT(S_ISDIR(ent[0]->mode));
+ TEST_STR_EQUAL(ent[1]->name, "dira/file_a0");
+ TEST_ASSERT(S_ISREG(ent[1]->mode));
+ TEST_STR_EQUAL(ent[2]->name, "dira/file_a1");
+ TEST_ASSERT(S_ISREG(ent[2]->mode));
+ TEST_STR_EQUAL(ent[3]->name, "dira/file_a2");
+ TEST_ASSERT(S_ISREG(ent[3]->mode));
+ TEST_STR_EQUAL(ent[4]->name, "dirb");
+ TEST_ASSERT(S_ISDIR(ent[4]->mode));
+ TEST_STR_EQUAL(ent[5]->name, "dirb/dirx");
+ TEST_ASSERT(S_ISDIR(ent[5]->mode));
+ TEST_STR_EQUAL(ent[6]->name, "dirb/file_b0");
+ TEST_ASSERT(S_ISREG(ent[6]->mode));
+ TEST_STR_EQUAL(ent[7]->name, "dirb/file_b1");
+ TEST_ASSERT(S_ISREG(ent[7]->mode));
+ TEST_STR_EQUAL(ent[8]->name, "dirb/file_b2");
+ TEST_ASSERT(S_ISREG(ent[8]->mode));
+ TEST_STR_EQUAL(ent[9]->name, "dirc");
+ TEST_ASSERT(S_ISDIR(ent[9]->mode));
+ TEST_STR_EQUAL(ent[10]->name, "dirc/file_c0");
+ TEST_ASSERT(S_ISREG(ent[10]->mode));
+ TEST_STR_EQUAL(ent[11]->name, "dirc/file_c1");
+ TEST_ASSERT(S_ISREG(ent[11]->mode));
+ TEST_STR_EQUAL(ent[12]->name, "dirc/file_c2");
+ TEST_ASSERT(S_ISREG(ent[12]->mode));
+
+ for (i = 0; i < 13; ++i)
+ free(ent[i]);
+
+ /* retry with skipping */
+ printf("**********\n");
+
+ dir = dir_tree_iterator_create(TEST_PATH);
+ TEST_NOT_NULL(dir);
+
+ for (i = 0; i < 9; ++i) {
+ ret = dir->next(dir, &ent[i]);
+ TEST_NOT_NULL(ent[i]);
+ TEST_EQUAL_I(ret, 0);
+ printf("READ %s\n", ent[i]->name);
+
+ if (!strcmp(ent[i]->name, "dirb"))
+ dir_tree_iterator_skip(dir);
+ }
+
+ ret = dir->next(dir, &ent[9]);
+ TEST_NULL(ent[9]);
+ TEST_ASSERT(ret > 0);
+
+ dir = sqfs_drop(dir);
+
+ qsort(ent, 9, sizeof(ent[0]), compare_entries);
+
+ printf("After sort:\n");
+ for (i = 0; i < 9; ++i)
+ printf("%s\n", ent[i]->name);
+
+ TEST_STR_EQUAL(ent[0]->name, "dira");
+ TEST_ASSERT(S_ISDIR(ent[0]->mode));
+ TEST_STR_EQUAL(ent[1]->name, "dira/file_a0");
+ TEST_ASSERT(S_ISREG(ent[1]->mode));
+ TEST_STR_EQUAL(ent[2]->name, "dira/file_a1");
+ TEST_ASSERT(S_ISREG(ent[2]->mode));
+ TEST_STR_EQUAL(ent[3]->name, "dira/file_a2");
+ TEST_ASSERT(S_ISREG(ent[3]->mode));
+ TEST_STR_EQUAL(ent[4]->name, "dirb");
+ TEST_ASSERT(S_ISDIR(ent[4]->mode));
+ TEST_STR_EQUAL(ent[5]->name, "dirc");
+ TEST_ASSERT(S_ISDIR(ent[5]->mode));
+ TEST_STR_EQUAL(ent[6]->name, "dirc/file_c0");
+ TEST_ASSERT(S_ISREG(ent[6]->mode));
+ TEST_STR_EQUAL(ent[7]->name, "dirc/file_c1");
+ TEST_ASSERT(S_ISREG(ent[7]->mode));
+ TEST_STR_EQUAL(ent[8]->name, "dirc/file_c2");
+ TEST_ASSERT(S_ISREG(ent[8]->mode));
+
+ for (i = 0; i < 9; ++i)
+ free(ent[i]);
+
+ return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/testdir/dirb/dirx/file_x0 b/lib/util/test/testdir/dirb/dirx/file_x0
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/lib/util/test/testdir/dirb/dirx/file_x0
diff --git a/lib/util/test/testdir/dirb/dirx/file_x1 b/lib/util/test/testdir/dirb/dirx/file_x1
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/lib/util/test/testdir/dirb/dirx/file_x1
diff --git a/lib/util/test/testdir/dirb/dirx/file_x2 b/lib/util/test/testdir/dirb/dirx/file_x2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/lib/util/test/testdir/dirb/dirx/file_x2