bftw: Visit multiple roots breadth-first

This makes `bfs a b` treat `a` and `b` as siblings.

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;
 		}