summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--Makefile1
-rw-r--r--bftw.c132
-rw-r--r--bftw.h2
-rw-r--r--eval.c3
-rw-r--r--parse.c6
5 files changed, 142 insertions, 2 deletions
diff --git a/Makefile b/Makefile
index e81b509..718899a 100644
--- a/Makefile
+++ b/Makefile
@@ -100,6 +100,7 @@ tests/mksock: tests/mksock.o
check: all
./tests.sh --bfs="$(realpath bfs)"
./tests.sh --bfs="$(realpath bfs) -dfs"
+ ./tests.sh --bfs="$(realpath bfs) -ids"
distcheck:
+$(MAKE) -Bs check CFLAGS="$(CFLAGS) -fsanitize=undefined -fsanitize=address"
diff --git a/bftw.c b/bftw.c
index 89ba083..6772408 100644
--- a/bftw.c
+++ b/bftw.c
@@ -39,6 +39,7 @@
#include "bftw.h"
#include "dstring.h"
#include "stat.h"
+#include "trie.h"
#include "util.h"
#include <assert.h>
#include <dirent.h>
@@ -1336,12 +1337,143 @@ static int bftw_dfs(const struct bftw_args *args) {
return ret;
}
+/**
+ * Iterative deepening search state.
+ */
+struct bftw_ids_state {
+ /** The wrapped callback. */
+ bftw_callback *delegate;
+ /** The wrapped callback arguments. */
+ void *ptr;
+ /** Which visit this search corresponds to. */
+ enum bftw_visit visit;
+ /** The current target depth. */
+ size_t depth;
+ /** The set of pruned paths. */
+ struct trie *pruned;
+ /** An error code to report. */
+ int error;
+ /** Whether the bottom has been found. */
+ bool bottom;
+ /** Whether to quit the search. */
+ bool quit;
+};
+
+/** Iterative deepening callback function. */
+static enum bftw_action bftw_ids_callback(const struct BFTW *ftwbuf, void *ptr) {
+ struct bftw_ids_state *state = ptr;
+
+ struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
+ mutbuf->visit = state->visit;
+
+ if (ftwbuf->typeflag == BFTW_ERROR) {
+ if (state->depth - ftwbuf->depth <= 1) {
+ return state->delegate(ftwbuf, state->ptr);
+ } else {
+ return BFTW_SKIP_SUBTREE;
+ }
+ }
+
+ if (ftwbuf->depth < state->depth) {
+ if (trie_find_str(state->pruned, ftwbuf->path)) {
+ return BFTW_SKIP_SUBTREE;
+ } else {
+ return BFTW_CONTINUE;
+ }
+ } else if (state->visit == BFTW_POST) {
+ if (trie_find_str(state->pruned, ftwbuf->path)) {
+ return BFTW_SKIP_SUBTREE;
+ }
+ }
+
+ state->bottom = false;
+
+ enum bftw_action ret = state->delegate(ftwbuf, state->ptr);
+
+ switch (ret) {
+ case BFTW_CONTINUE:
+ ret = BFTW_SKIP_SUBTREE;
+ break;
+ case BFTW_SKIP_SIBLINGS:
+ // Can't be easily supported in this mode
+ state->error = EINVAL;
+ state->quit = true;
+ ret = BFTW_STOP;
+ break;
+ case BFTW_SKIP_SUBTREE:
+ if (ftwbuf->typeflag == BFTW_DIR) {
+ if (!trie_insert_str(state->pruned, ftwbuf->path)) {
+ state->error = errno;
+ state->quit = true;
+ ret = BFTW_STOP;
+ }
+ }
+ break;
+ case BFTW_STOP:
+ state->quit = true;
+ break;
+ }
+
+ return ret;
+}
+
+/**
+ * Iterative deepening bftw() wrapper.
+ */
+static int bftw_ids(const struct bftw_args *args) {
+ struct trie pruned;
+ trie_init(&pruned);
+
+ struct bftw_ids_state state = {
+ .delegate = args->callback,
+ .ptr = args->ptr,
+ .visit = BFTW_PRE,
+ .depth = 0,
+ .pruned = &pruned,
+ .bottom = false,
+ };
+
+ struct bftw_args ids_args = *args;
+ ids_args.callback = bftw_ids_callback;
+ ids_args.ptr = &state;
+ ids_args.flags &= ~BFTW_DEPTH;
+ ids_args.strategy = BFTW_DFS;
+
+ int ret = 0;
+
+ while (ret == 0 && !state.quit && !state.bottom) {
+ state.bottom = true;
+ ret = bftw_impl(&ids_args);
+ ++state.depth;
+ }
+
+ if (args->flags & BFTW_DEPTH) {
+ state.visit = BFTW_POST;
+
+ while (ret == 0 && !state.quit && state.depth > 0) {
+ --state.depth;
+ ret = bftw_impl(&ids_args);
+ }
+ }
+
+ if (state.error) {
+ ret = -1;
+ } else {
+ state.error = errno;
+ }
+ trie_destroy(&pruned);
+ errno = state.error;
+ return ret;
+}
+
int bftw(const struct bftw_args *args) {
switch (args->strategy) {
case BFTW_BFS:
return bftw_impl(args);
case BFTW_DFS:
return bftw_dfs(args);
+ case BFTW_IDS:
+ return bftw_ids(args);
}
errno = EINVAL;
diff --git a/bftw.h b/bftw.h
index f9d1aa0..570a79f 100644
--- a/bftw.h
+++ b/bftw.h
@@ -197,6 +197,8 @@ enum bftw_strategy {
BFTW_BFS,
/** Depth-first search. */
BFTW_DFS,
+ /** Iterative deepening search. */
+ BFTW_IDS,
};
/**
diff --git a/eval.c b/eval.c
index 6d13970..c075343 100644
--- a/eval.c
+++ b/eval.c
@@ -1228,7 +1228,7 @@ static enum bftw_action cmdline_callback(const struct BFTW *ftwbuf, void *ptr) {
// In -depth mode, only handle directories on the BFTW_POST visit
enum bftw_visit expected_visit = BFTW_PRE;
if ((cmdline->flags & BFTW_DEPTH)
- && ftwbuf->typeflag == BFTW_DIR
+ && (cmdline->strategy == BFTW_IDS || ftwbuf->typeflag == BFTW_DIR)
&& ftwbuf->depth < cmdline->maxdepth) {
expected_visit = BFTW_POST;
}
@@ -1332,6 +1332,7 @@ static const char *dump_bftw_strategy(enum bftw_strategy strategy) {
static const char *strategies[] = {
DUMP_BFTW_MAP(BFTW_BFS),
DUMP_BFTW_MAP(BFTW_DFS),
+ DUMP_BFTW_MAP(BFTW_IDS),
};
return strategies[strategy];
}
diff --git a/parse.c b/parse.c
index 7d98ffe..b8ef413 100644
--- a/parse.c
+++ b/parse.c
@@ -2150,7 +2150,7 @@ static struct expr *parse_samefile(struct parser_state *state, int arg1, int arg
}
/**
- * Parse -bfs, -dfs.
+ * Parse -bfs, -dfs, -ids.
*/
static struct expr *parse_search_strategy(struct parser_state *state, int strategy, int arg2) {
struct cmdline *cmdline = state->cmdline;
@@ -2660,6 +2660,7 @@ static const struct table_entry parse_table[] = {
{"-group", false, parse_group},
{"-help", false, parse_help},
{"-hidden", false, parse_hidden},
+ {"-ids", false, parse_search_strategy, BFTW_IDS},
{"-ignore_readdir_race", false, parse_ignore_races, true},
{"-ilname", false, parse_lname, true},
{"-iname", false, parse_name, true},
@@ -3049,6 +3050,9 @@ void dump_cmdline(const struct cmdline *cmdline, bool verbose) {
case BFTW_DFS:
cfprintf(cerr, "${cyn}-dfs${rs} ");
break;
+ case BFTW_IDS:
+ cfprintf(cerr, "${cyn}-ids${rs} ");
+ break;
}
if (cmdline->flags & BFTW_LOGICAL) {