From 30969de9bfe7d565e70eef6c23095741ffb9b285 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Fri, 12 Jun 2020 13:18:45 -0400 Subject: 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(). --- bftw.c | 36 +++++++++++++++++++++--------------- 1 file 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. */ -- cgit v1.2.3