summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2019-03-31 17:36:30 -0400
committerTavian Barnes <tavianator@tavianator.com>2019-05-28 20:49:54 -0400
commit1cc323eb88242bc7be7177ba4cb037a58c754763 (patch)
treee5d88f0a88ebb0305482f98fbdcfdad518157b76
parent97ad2f4786b39cb4bf2189350efba4bce42ab6ea (diff)
downloadbfs-1cc323eb88242bc7be7177ba4cb037a58c754763.tar.xz
bftw: Visit multiple roots breadth-first
This makes `bfs a b` treat `a` and `b` as siblings.
-rw-r--r--bftw.c44
-rw-r--r--bftw.h8
-rw-r--r--cmdline.h16
-rw-r--r--eval.c69
-rw-r--r--parse.c42
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
@@ -47,24 +47,16 @@ enum debug_flags {
};
/**
- * 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.
*/
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;
}