summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2015-09-26 12:54:18 -0400
committerTavian Barnes <tavianator@tavianator.com>2015-09-26 12:54:18 -0400
commitd0243a72d56326af2c5ff7b7b3823dbe57b3bd4c (patch)
tree10a9f4223ca594252392b8bf46b80e031f9dbb86
parent4bedd5a6f7b12e0923dd6fa180dcaad7e1f75fc2 (diff)
downloadbfs-d0243a72d56326af2c5ff7b7b3823dbe57b3bd4c.tar.xz
Optimize -maxdepth in -depth mode.
-rw-r--r--bfs.c12
-rw-r--r--bftw.c15
-rw-r--r--bftw.h14
-rwxr-xr-xtests.sh12
4 files changed, 36 insertions, 17 deletions
diff --git a/bfs.c b/bfs.c
index 5e166de..7669e6d 100644
--- a/bfs.c
+++ b/bfs.c
@@ -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);
}
diff --git a/bftw.c b/bftw.c
index 0bc49e1..d489bc8 100644
--- a/bftw.c
+++ b/bftw.c
@@ -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:
diff --git a/bftw.h b/bftw.h
index f3be182..2082390 100644
--- a/bftw.h
+++ b/bftw.h
@@ -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;
diff --git a/tests.sh b/tests.sh
index f7eb428..65e439b 100755
--- a/tests.sh
+++ b/tests.sh
@@ -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"