diff options
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | bftw.c | 132 | ||||
| -rw-r--r-- | bftw.h | 2 | ||||
| -rw-r--r-- | eval.c | 3 | ||||
| -rw-r--r-- | parse.c | 6 |
5 files changed, 142 insertions, 2 deletions
@@ -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" @@ -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; @@ -197,6 +197,8 @@ enum bftw_strategy { BFTW_BFS, /** Depth-first search. */ BFTW_DFS, + /** Iterative deepening search. */ + BFTW_IDS, }; /** @@ -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]; } @@ -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) { |