From d0243a72d56326af2c5ff7b7b3823dbe57b3bd4c Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 26 Sep 2015 12:54:18 -0400
Subject: Optimize -maxdepth in -depth mode.

---
 bfs.c    | 12 +++++++++++-
 bftw.c   | 15 +--------------
 bftw.h   | 14 +++++++++++++-
 tests.sh | 12 +++++++++++-
 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
@@ -39,6 +39,16 @@ typedef enum {
 	BFTW_ERROR,
 } 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.
  */
@@ -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
@@ -53,11 +53,21 @@ 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"
-- 
cgit v1.2.3