summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-06-12 13:18:45 -0400
committerTavian Barnes <tavianator@tavianator.com>2020-06-12 13:18:45 -0400
commit30969de9bfe7d565e70eef6c23095741ffb9b285 (patch)
tree9f416ca81859ac7b367c90f4caf4d32d19e6ebe0
parent174f98fca012215238554c29b199e4b0377e416f (diff)
downloadbfs-30969de9bfe7d565e70eef6c23095741ffb9b285.tar.xz
bftw: Make iterative deepening actually do depth-first search
bftw_stream() was always pushing to the end of the queue, resulting in breadth-first behaviour even when BFTW_DFS was set. This made iterative deepening a "worst of both worlds" with the same memory use as BFS, but much slower due to re-traversals. Fix it by re-using bftw_batch_{start,finish} from bftw_batch().
-rw-r--r--bftw.c36
1 files changed, 21 insertions, 15 deletions
diff --git a/bftw.c b/bftw.c
index 35f086d..87f629b 100644
--- a/bftw.c
+++ b/bftw.c
@@ -1346,6 +1346,21 @@ static int bftw_state_destroy(struct bftw_state *state) {
return state->error ? -1 : 0;
}
+/** Start a batch of files. */
+static void bftw_batch_start(struct bftw_state *state) {
+ if (state->strategy == BFTW_DFS) {
+ state->queue.target = &state->queue.head;
+ }
+ state->batch = state->queue.target;
+}
+
+/** Finish adding a batch of files. */
+static void bftw_batch_finish(struct bftw_state *state) {
+ if (state->flags & BFTW_SORT) {
+ state->queue.target = bftw_sort_files(state->batch, state->queue.target);
+ }
+}
+
/**
* Streaming mode: visit files as they are encountered.
*/
@@ -1355,6 +1370,9 @@ static int bftw_stream(const struct bftw_args *args) {
return -1;
}
+ assert(!(state.flags & BFTW_SORT));
+
+ bftw_batch_start(&state);
for (size_t i = 0; i < args->npaths; ++i) {
const char *path = args->paths[i];
@@ -1371,10 +1389,12 @@ static int bftw_stream(const struct bftw_args *args) {
goto done;
}
}
+ bftw_batch_finish(&state);
while (bftw_pop(&state) > 0) {
struct bftw_reader *reader = bftw_open(&state);
+ bftw_batch_start(&state);
while (bftw_reader_read(reader) > 0) {
const char *name = reader->de->d_name;
@@ -1391,6 +1411,7 @@ static int bftw_stream(const struct bftw_args *args) {
goto done;
}
}
+ bftw_batch_finish(&state);
if (bftw_release_reader(&state, BFTW_VISIT_ALL) == BFTW_STOP) {
goto done;
@@ -1404,21 +1425,6 @@ done:
return bftw_state_destroy(&state);
}
-/** Start a batch of files. */
-static void bftw_batch_start(struct bftw_state *state) {
- if (state->strategy == BFTW_DFS) {
- state->queue.target = &state->queue.head;
- }
- state->batch = state->queue.target;
-}
-
-/** Finish adding a batch of files. */
-static void bftw_batch_finish(struct bftw_state *state) {
- if (state->flags & BFTW_SORT) {
- state->queue.target = bftw_sort_files(state->batch, state->queue.target);
- }
-}
-
/**
* Batching mode: queue up all children before visiting them.
*/