From 1cc323eb88242bc7be7177ba4cb037a58c754763 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sun, 31 Mar 2019 17:36:30 -0400 Subject: bftw: Visit multiple roots breadth-first This makes `bfs a b` treat `a` and `b` as siblings. --- bftw.c | 44 ++++++++++++++++++++++------------------ bftw.h | 8 +++++--- cmdline.h | 16 ++++----------- eval.c | 69 ++++++++++++++++++++++++++++++--------------------------------- parse.c | 42 +++++++++++++++++--------------------- 5 files changed, 85 insertions(+), 94 deletions(-) diff --git a/bftw.c b/bftw.c index 0a7180b..9016aba 100644 --- a/bftw.c +++ b/bftw.c @@ -59,6 +59,8 @@ struct bftw_dir { struct bftw_dir *parent; /** This directory's depth in the walk. */ size_t depth; + /** The root path this directory was found from. */ + const char *root; /** The next directory in the queue, if any. */ struct bftw_dir *next; @@ -305,10 +307,12 @@ static struct bftw_dir *bftw_dir_new(struct bftw_cache *cache, struct bftw_dir * if (parent) { dir->depth = parent->depth + 1; + dir->root = parent->root; dir->nameoff = parent->nameoff + parent->namelen; bftw_dir_incref(cache, parent); } else { dir->depth = 0; + dir->root = name; dir->nameoff = 0; } @@ -641,8 +645,6 @@ static int bftw_reader_close(struct bftw_reader *reader) { * Holds the current state of the bftw() traversal. */ struct bftw_state { - /** The root path of the walk. */ - const char *root; /** bftw() callback. */ bftw_callback *callback; /** bftw() callback data. */ @@ -672,8 +674,7 @@ struct bftw_state { /** * Initialize the bftw() state. */ -static int bftw_state_init(struct bftw_state *state, const char *root, const struct bftw_args *args) { - state->root = root; +static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) { state->callback = args->callback; state->ptr = args->ptr; state->flags = args->flags; @@ -868,7 +869,7 @@ static int bftw_update_path(struct bftw_state *state, const struct bftw_dir *dir length = dir->nameoff + dir->namelen; } else if (dir->depth == 0) { // Use exactly the string passed to bftw(), including any trailing slashes - length = strlen(state->root); + length = strlen(dir->root); } else { // -1 to trim the trailing slash length = dir->nameoff + dir->namelen - 1; @@ -936,7 +937,7 @@ static void bftw_init_ftwbuf(struct bftw_state *state, struct bftw_dir *dir, enu struct BFTW *ftwbuf = &state->ftwbuf; ftwbuf->path = state->path; - ftwbuf->root = state->root; + ftwbuf->root = dir ? dir->root : ftwbuf->path; ftwbuf->depth = 0; ftwbuf->visit = visit; ftwbuf->error = reader->error; @@ -1180,27 +1181,32 @@ static int bftw_state_destroy(struct bftw_state *state) { return state->error ? -1 : 0; } -int bftw(const char *path, const struct bftw_args *args) { +int bftw(const struct bftw_args *args) { struct bftw_state state; - if (bftw_state_init(&state, path, args) != 0) { + if (bftw_state_init(&state, args) != 0) { return -1; } - // Handle 'path' itself first - switch (bftw_visit(&state, NULL, path, BFTW_PRE)) { - case BFTW_CONTINUE: - case BFTW_SKIP_SIBLINGS: - break; - default: - goto done; - } + for (size_t i = 0; i < args->npaths; ++i) { + const char *path = args->paths[i]; - // Now start the breadth-first search + switch (bftw_visit(&state, NULL, path, BFTW_PRE)) { + case BFTW_CONTINUE: + break; + case BFTW_SKIP_SIBLINGS: + goto start; + case BFTW_SKIP_SUBTREE: + continue; + case BFTW_STOP: + goto done; + } - if (bftw_push(&state, path) != 0) { - goto done; + if (bftw_push(&state, path) != 0) { + goto done; + } } +start: while (state.queue.head) { struct bftw_reader *reader = bftw_pop(&state); if (!reader) { diff --git a/bftw.h b/bftw.h index 568db9a..6f5ad6d 100644 --- a/bftw.h +++ b/bftw.h @@ -193,6 +193,10 @@ enum bftw_flags { * Structure for holding the arguments passed to bftw(). */ struct bftw_args { + /** The path(s) to start from. */ + const char **paths; + /** The number of starting paths. */ + size_t npaths; /** The callback to invoke. */ bftw_callback *callback; /** A pointer which is passed to the callback. */ @@ -212,13 +216,11 @@ struct bftw_args { * and invokes a callback for each path it encounters. However, bftw() operates * breadth-first. * - * @param path - * The starting path. * @param args * The arguments that control the walk. * @return * 0 on success, or -1 on failure. */ -int bftw(const char *path, const struct bftw_args *args); +int bftw(const struct bftw_args *args); #endif // BFS_BFTW_H diff --git a/cmdline.h b/cmdline.h index bb36a8d..e1811fd 100644 --- a/cmdline.h +++ b/cmdline.h @@ -46,16 +46,6 @@ enum debug_flags { DEBUG_ALL = (1 << 7) - 1, }; -/** - * A root path to explore. - */ -struct root { - /** The root path itself. */ - const char *path; - /** The next path in the list. */ - struct root *next; -}; - /** * The parsed command line. */ @@ -63,8 +53,10 @@ struct cmdline { /** The unparsed command line arguments. */ char **argv; - /** The list of root paths. */ - struct root *roots; + /** The root paths. */ + const char **paths; + /** The number of root paths. */ + size_t npaths; /** Color data. */ struct colors *colors; diff --git a/eval.c b/eval.c index bd69b67..5784219 100644 --- a/eval.c +++ b/eval.c @@ -1245,20 +1245,14 @@ done: } if (cmdline->debug & DEBUG_SEARCH) { - fprintf(stderr, - "cmdline_callback({ " - ".path = \"%s\", " - ".depth = %zu, " - ".visit = %s, " - ".typeflag = %s, " - ".error = %d " - "}) == %s\n", - ftwbuf->path, - ftwbuf->depth, - dump_bftw_visit(ftwbuf->visit), - dump_bftw_typeflag(ftwbuf->typeflag), - ftwbuf->error, - dump_bftw_action(state.action)); + fprintf(stderr, "cmdline_callback({\n"); + fprintf(stderr, "\t.path = \"%s\",\n", ftwbuf->path); + fprintf(stderr, "\t.root = \"%s\",\n", ftwbuf->root); + fprintf(stderr, "\t.depth = %zu,\n", ftwbuf->depth); + fprintf(stderr, "\t.visit = %s,\n", dump_bftw_visit(ftwbuf->visit)); + fprintf(stderr, "\t.typeflag = %s,\n", dump_bftw_typeflag(ftwbuf->typeflag)); + fprintf(stderr, "\t.error = %d,\n", ftwbuf->error); + fprintf(stderr, "}) == %s\n", dump_bftw_action(state.action)); } return state.action; @@ -1352,6 +1346,8 @@ int eval_cmdline(const struct cmdline *cmdline) { } struct bftw_args bftw_args = { + .paths = cmdline->paths, + .npaths = cmdline->npaths, .callback = cmdline_callback, .ptr = &args, .nopenfd = infer_fdlimit(cmdline), @@ -1359,30 +1355,31 @@ int eval_cmdline(const struct cmdline *cmdline) { .mtab = cmdline->mtab, }; - for (struct root *root = cmdline->roots; root && !args.quit; root = root->next) { - if (cmdline->debug & DEBUG_SEARCH) { - fprintf(stderr, - "bftw(\"%s\", { " - ".callback = cmdline_callback, " - ".ptr = &args, " - ".nopenfd = %d, " - ".flags = ", - root->path, - bftw_args.nopenfd); - dump_bftw_flags(bftw_args.flags); - fprintf(stderr, ", .mtab = "); - if (bftw_args.mtab) { - fprintf(stderr, "cmdline->mtab"); - } else { - fprintf(stderr, "NULL"); - } - fprintf(stderr, " })\n"); + if (cmdline->debug & DEBUG_SEARCH) { + fprintf(stderr, "bftw({\n"); + fprintf(stderr, "\t.paths = {\n"); + for (size_t i = 0; i < bftw_args.npaths; ++i) { + fprintf(stderr, "\t\t\"%s\",\n", bftw_args.paths[i]); } - - if (bftw(root->path, &bftw_args) != 0) { - args.ret = EXIT_FAILURE; - perror("bftw()"); + fprintf(stderr, "\t},\n"); + fprintf(stderr, "\t.npaths = %zu,\n", bftw_args.npaths); + fprintf(stderr, "\t.callback = cmdline_callback,\n"); + fprintf(stderr, "\t.ptr = &args,\n"); + fprintf(stderr, "\t.nopenfd = %d,\n", bftw_args.nopenfd); + fprintf(stderr, "\t.flags = "); + dump_bftw_flags(bftw_args.flags); + fprintf(stderr, ",\n\t.mtab = "); + if (bftw_args.mtab) { + fprintf(stderr, "cmdline->mtab"); + } else { + fprintf(stderr, "NULL"); } + fprintf(stderr, ",\n})\n"); + } + + if (bftw(&bftw_args) != 0) { + args.ret = EXIT_FAILURE; + perror("bftw()"); } if (eval_exec_finish(cmdline->expr, cmdline) != 0) { diff --git a/parse.c b/parse.c index 77bfbc7..7ca50ae 100644 --- a/parse.c +++ b/parse.c @@ -289,14 +289,7 @@ int free_cmdline(struct cmdline *cmdline) { cfclose(cerr); free_colors(cmdline->colors); - - struct root *root = cmdline->roots; - while (root) { - struct root *next = root->next; - free(root); - root = next; - } - + free(cmdline->paths); free(cmdline->argv); free(cmdline); } @@ -323,8 +316,6 @@ struct parser_state { char **argv; /** The name of this program. */ const char *command; - /** The current tail of the root path list. */ - struct root **roots_tail; /** The current regex flags to use. */ int regex_flags; @@ -504,16 +495,18 @@ static char **parser_advance(struct parser_state *state, enum token_type type, s * Parse a root path. */ static int parse_root(struct parser_state *state, const char *path) { - struct root *root = malloc(sizeof(struct root)); - if (!root) { - perror("malloc()"); - return -1; + struct cmdline *cmdline = state->cmdline; + size_t i = cmdline->npaths; + if ((i & (i + 1)) == 0) { + const char **paths = realloc(cmdline->paths, 2*(i + 1)*sizeof(*paths)); + if (!paths) { + return -1; + } + cmdline->paths = paths; } - root->path = path; - root->next = NULL; - *state->roots_tail = root; - state->roots_tail = &root->next; + cmdline->paths[i] = path; + cmdline->npaths = i + 1; return 0; } @@ -3067,12 +3060,13 @@ void dump_cmdline(const struct cmdline *cmdline, bool verbose) { cfprintf(cerr, " "); } - for (struct root *root = cmdline->roots; root; root = root->next) { - char c = root->path[0]; + for (size_t i = 0; i < cmdline->npaths; ++i) { + const char *path = cmdline->paths[i]; + char c = path[0]; if (c == '-' || c == '(' || c == ')' || c == '!' || c == ',') { cfprintf(cerr, "${cyn}-f${rs} "); } - cfprintf(cerr, "${mag}%s${rs} ", root->path); + cfprintf(cerr, "${mag}%s${rs} ", path); } if (cmdline->cout->colors) { @@ -3148,7 +3142,8 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) { } cmdline->argv = NULL; - cmdline->roots = NULL; + cmdline->paths = NULL; + cmdline->npaths = 0; cmdline->colors = NULL; cmdline->cout = NULL; cmdline->cerr = NULL; @@ -3208,7 +3203,6 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) { .cmdline = cmdline, .argv = cmdline->argv + 1, .command = cmdline->argv[0], - .roots_tail = &cmdline->roots, .regex_flags = 0, .interactive = stderr_tty && stdin_tty, .use_color = use_color, @@ -3238,7 +3232,7 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) { goto fail; } - if (!cmdline->roots) { + if (cmdline->npaths == 0) { if (parse_root(&state, ".") != 0) { goto fail; } -- cgit v1.2.3