git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v5 3/6] dir_iterator: iterate over dir after its contents

From
Daniel Ferreira <bnmvco@gmail.com>
Date
Mar 30, 2017, 03:32 UTC
Message-ID
<1490844730-47634-4-git-send-email-bnmvco@gmail.com>
In-Reply-To
<1490844730-47634-1-git-send-email-bnmvco@gmail.com>

Create an option for the dir_iterator API to iterate over subdirectories only after having iterated through their contents. This feature was predicted, although not implemented by 0fe5043 ("dir_iterator: new API for iterating over a directory tree", 2016-06-18).

Add the "flags" parameter to dir_iterator_create, allowing for the aforementioned "depth-first" iteration mode to be enabled. Currently, the only acceptable flag is DIR_ITERATOR_DEPTH_FIRST.

This is useful for recursively removing a directory and calling rmdir() on a directory only after all of its contents have been wiped.

Amend a call to dir_iterator_begin() to pass the flags parameter introduced.

Signed-off-by: Daniel Ferreira <bnmvco@gmail.com>
---
 dir-iterator.c       | 53 ++++++++++++++++++++++++++++++++++++++++++++++++----
 dir-iterator.h       | 17 ++++++++++++-----
 refs/files-backend.c |  2 +-
 3 files changed, 62 insertions(+), 10 deletions(-)
diff --git a/dir-iterator.c b/dir-iterator.c
index 3ac984b..05d53d2 100644
--- a/dir-iterator.c
+++ b/dir-iterator.c
@@ -47,6 +47,9 @@ struct dir_iterator_int {
 	 * that will be included in this iteration.
 	 */
 	struct dir_iterator_level *levels;
+
+	/* Holds the flags passed to dir_iterator_begin(). */
+	unsigned flags;
 };
 
 static inline void push_dir_level(struct dir_iterator_int *iter, struct dir_iterator_level *level)
@@ -113,12 +116,14 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)
 					iter->base.path.buf, strerror(errno));
 				/* Popping the level is handled below */
 			}
-		} else if (S_ISDIR(iter->base.st.st_mode)) {
+		} else if (S_ISDIR(iter->base.st.st_mode) &&
+			!(iter->flags & DIR_ITERATOR_POST_ORDER_TRAVERSAL)) {
 			if (level->dir_state == DIR_STATE_ITER) {
 				/*
 				 * The directory was just iterated
 				 * over; now prepare to iterate into
-				 * it.
+				 * it (unless an option is set for us
+				 * to do otherwise).
 				 */
 				push_dir_level(iter, level);
 				continue;
@@ -152,7 +157,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)
 			de = readdir(level->dir);
 
 			if (!de) {
-				/* This level is exhausted; pop up a level. */
+				/* This level is exhausted  */
 				if (errno) {
 					warning("error reading directory %s: %s",
 						iter->base.path.buf, strerror(errno));
@@ -160,6 +165,32 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)
 					warning("error closing directory %s: %s",
 						iter->base.path.buf, strerror(errno));
 
+				if (iter->flags & DIR_ITERATOR_POST_ORDER_TRAVERSAL) {
+					/* If we are handling dirpaths after their contents,
+					 * we have to iterate over the directory now that we'll
+					 * have finished iterating into it. */
+					level->dir = NULL;
+
+					if (pop_dir_level(iter) == 0)
+						return dir_iterator_abort(dir_iterator);
+
+					level = &iter->levels[iter->levels_nr - 1];
+					/* Since we are iterating through the dirpath
+					 * after we have gone through it, we still need
+					 * to get rid of the trailing slash we appended.
+					 *
+					 * This may generate issues if we ever want to
+					 * iterate through the root directory AND have
+					 * post-order traversal enabled.
+					 */
+					strbuf_strip_suffix(&iter->base.path, "/");
+
+					if (set_iterator_data(iter, level))
+						continue;
+
+					return ITER_OK;
+				}
+
 				level->dir = NULL;
 				if (pop_dir_level(iter) == 0)
 					return dir_iterator_abort(dir_iterator);
@@ -174,6 +205,18 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator)
 			if (set_iterator_data(iter, level))
 				continue;
 
+			/*
+			 * If we want to iterate dirs after files, we shall
+			 * begin looking into them *before* we return the dir
+			 * itself.
+			 */
+			if (S_ISDIR(iter->base.st.st_mode) &&
+				(iter->flags & DIR_ITERATOR_POST_ORDER_TRAVERSAL)) {
+				push_dir_level(iter, level);
+
+				break;
+			}
+
 			return ITER_OK;
 		}
 	}
@@ -200,7 +243,7 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator)
 	return ITER_DONE;
 }
 
-struct dir_iterator *dir_iterator_begin(const char *path)
+struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags)
 {
 	struct dir_iterator_int *iter = xcalloc(1, sizeof(*iter));
 	struct dir_iterator *dir_iterator = &iter->base;
@@ -208,6 +251,8 @@ struct dir_iterator *dir_iterator_begin(const char *path)
 	if (!path || !*path)
 		die("BUG: empty path passed to dir_iterator_begin()");
 
+	iter->flags = flags;
+
 	strbuf_init(&iter->base.path, PATH_MAX);
 	strbuf_addstr(&iter->base.path, path);
 
diff --git a/dir-iterator.h b/dir-iterator.h
index 27739e6..649ccf6 100644
--- a/dir-iterator.h
+++ b/dir-iterator.h
@@ -11,8 +11,7 @@
  * Every time dir_iterator_advance() is called, update the members of
  * the dir_iterator structure to reflect the next path in the
  * iteration. The order that paths are iterated over within a
- * directory is undefined, but directory paths are always iterated
- * over before the subdirectory contents.
+ * directory is undefined.
  *
  * A typical iteration looks like this:
  *
@@ -38,6 +37,13 @@
  * dir_iterator_advance() again.
  */
 
+/* Possible flags for dir_iterator_begin().
+ *
+ * DIR_ITERATOR_POST_ORDER_TRAVERSAL: ensures subdirectories and
+ * their contents are iterated through before the containing directory.
+ */
+#define DIR_ITERATOR_POST_ORDER_TRAVERSAL (1 << 0)
+
 struct dir_iterator {
 	/* The current path: */
 	struct strbuf path;
@@ -57,15 +63,16 @@ struct dir_iterator {
 };
 
 /*
- * Start a directory iteration over path. Return a dir_iterator that
- * holds the internal state of the iteration.
+ * Start a directory iteration over path, with options specified in
+ * 'flags'. Return a dir_iterator that holds the internal state of
+ * the iteration.
  *
  * The iteration includes all paths under path, not including path
  * itself and not including "." or ".." entries.
  *
  * path is the starting directory. An internal copy will be made.
  */
-struct dir_iterator *dir_iterator_begin(const char *path);
+struct dir_iterator *dir_iterator_begin(const char *path, unsigned flags);
 
 /*
  * Advance the iterator to the first or next item and return ITER_OK.
diff --git a/refs/files-backend.c b/refs/files-backend.c
index 50188e9..b4bba74 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -3346,7 +3346,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st
 	files_downcast(ref_store, 0, "reflog_iterator_begin");
 
 	base_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);
-	iter->dir_iterator = dir_iterator_begin(git_path("logs"));
+	iter->dir_iterator = dir_iterator_begin(git_path("logs"), 0);
 	return ref_iterator;
 }
 

-- 
2.7.4 (Apple Git-66)
Previous: Michael HaggertyNext: Michael Haggerty
Message 5 of 19 in “[GSoC] remove_subtree(): reimplement using iterators”
  1. 0/6 [GSoC] remove_subtree(): reimplement using iteratorsDaniel Ferreira, Mar 30, 2017
  2. 1/6 dir_iterator: add helpers to dir_iterator_advanceDaniel Ferreira, Mar 30, 2017
  3. 2/6 dir_iterator: refactor state machine modelDaniel Ferreira, Mar 30, 2017
  4. Michael HaggertyMar 30, 2017
  5. 3/6 dir_iterator: iterate over dir after its contentsDaniel Ferreira, Mar 30, 2017
  6. Michael HaggertyMar 30, 2017
  7. 4/6 dir_iterator: add tests for dir_iterator APIDaniel Ferreira, Mar 30, 2017
  8. Michael HaggertyMar 30, 2017
  9. Daniel Ferreira (theiostream)Mar 30, 2017
  10. Jeff KingApr 1, 2017
  11. Junio C HamanoApr 1, 2017
  12. Michael HaggertyMar 30, 2017
  13. Michael HaggertyMar 30, 2017
  14. Daniel Ferreira (theiostream)Mar 30, 2017
  15. 5/6 remove_subtree(): reimplement using iteratorsDaniel Ferreira, Mar 30, 2017
  16. 6/6 remove_subtree(): test removing nested directoriesDaniel Ferreira, Mar 30, 2017
  17. Michael HaggertyMar 30, 2017
  18. Michael HaggertyMar 30, 2017
  19. Duy NguyenMar 30, 2017

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.