diff options
author | Tavian Barnes <tavianator@tavianator.com> | 2015-09-26 12:54:18 -0400 |
---|---|---|
committer | Tavian Barnes <tavianator@tavianator.com> | 2015-09-26 12:54:18 -0400 |
commit | d0243a72d56326af2c5ff7b7b3823dbe57b3bd4c (patch) | |
tree | 10a9f4223ca594252392b8bf46b80e031f9dbb86 | |
parent | 4bedd5a6f7b12e0923dd6fa180dcaad7e1f75fc2 (diff) |
Optimize -maxdepth in -depth mode.
-rw-r--r-- | bfs.c | 12 | ||||
-rw-r--r-- | bftw.c | 15 | ||||
-rw-r--r-- | bftw.h | 14 | ||||
-rwxr-xr-x | tests.sh | 12 |
4 files changed, 36 insertions, 17 deletions
@@ -891,7 +891,17 @@ static bftw_action cmdline_callback(struct BFTW *ftwbuf, void *ptr) { state.action = BFTW_SKIP_SUBTREE; } - if (ftwbuf->depth >= cl->mindepth && ftwbuf->depth <= cl->maxdepth) { + // In -depth mode, only handle directories on the BFTW_POST visit + bftw_visit expected_visit = BFTW_PRE; + if ((cl->flags & BFTW_DEPTH) + && ftwbuf->typeflag == BFTW_DIR + && ftwbuf->depth < cl->maxdepth) { + expected_visit = BFTW_POST; + } + + if (ftwbuf->visit == expected_visit + && ftwbuf->depth >= cl->mindepth + && ftwbuf->depth <= cl->maxdepth) { cl->expr->eval(cl->expr, &state); } @@ -593,6 +593,7 @@ static void bftw_init_buffers(bftw_state *state, const struct dirent *de) { ftwbuf->nameoff = 0; ftwbuf->error = 0; ftwbuf->depth = 0; + ftwbuf->visit = (state->status == BFTW_GC ? BFTW_POST : BFTW_PRE); ftwbuf->statbuf = NULL; ftwbuf->at_fd = AT_FDCWD; ftwbuf->at_path = ftwbuf->path; @@ -618,13 +619,6 @@ static void bftw_init_buffers(bftw_state *state, const struct dirent *de) { ftwbuf->typeflag = BFTW_UNKNOWN; } - // In BFTW_DEPTH mode, defer the stat() call for directories - if ((state->flags & BFTW_DEPTH) - && ftwbuf->typeflag == BFTW_DIR - && state->status == BFTW_CHILD) { - return; - } - if ((state->flags & BFTW_STAT) || ftwbuf->typeflag == BFTW_UNKNOWN) { if (ftwbuf_stat(ftwbuf, &state->statbuf) != 0) { state->error = errno; @@ -645,13 +639,6 @@ static int bftw_handle_path(bftw_state *state) { return BFTW_FAIL; } - // In BFTW_DEPTH mode, defer handling directories - if (state->ftwbuf.typeflag == BFTW_DIR - && (state->flags & BFTW_DEPTH) - && state->status != BFTW_GC) { - return BFTW_CONTINUE; - } - bftw_action action = state->fn(&state->ftwbuf, state->ptr); switch (action) { case BFTW_CONTINUE: @@ -40,6 +40,16 @@ typedef enum { } bftw_typeflag; /** + * Possible visit occurrences. + */ +typedef enum { + /** Pre-order visit. */ + BFTW_PRE, + /** Post-order visit. */ + BFTW_POST, +} bftw_visit; + +/** * Data about the current file for the bftw() callback. */ struct BFTW { @@ -50,6 +60,8 @@ struct BFTW { /** The depth of this file in the traversal. */ size_t depth; + /** Which visit this is. */ + bftw_visit visit; /** The file type. */ bftw_typeflag typeflag; @@ -93,7 +105,7 @@ typedef enum { BFTW_STAT = 1 << 0, /** Attempt to recover from encountered errors. */ BFTW_RECOVER = 1 << 1, - /** Visit all of a directory's descendants before the directory itself. */ + /** Visit directories in post-order as well as pre-order. */ BFTW_DEPTH = 1 << 2, } bftw_flags; @@ -54,10 +54,20 @@ function test_0006() { function test_0007() { basic_structure "$1" + find_diff "$1" -mindepth 2 -depth +} + +function test_0008() { + basic_structure "$1" find_diff "$1" -maxdepth 1 -depth } -for i in {1..7}; do +function test_0009() { + basic_structure "$1" + find_diff "$1" -maxdepth 2 -depth +} + +for i in {1..9}; do dir="$(mktemp -d "${TMPDIR:-/tmp}"/bfs.XXXXXXXXXX)" test="test_$(printf '%04d' $i)" "$test" "$dir" |