summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2017-03-22 19:14:50 -0400
committerTavian Barnes <tavianator@tavianator.com>2017-03-22 19:40:58 -0400
commit998ba6f6d119608b0844c0ca735044746ea1fd0f (patch)
treee48079cded830b57c4e412d620bb7b1607b04499
parentc32385d4c8eb0e54af27712ff3fc82df1bda01e8 (diff)
downloadbfs-998ba6f6d119608b0844c0ca735044746ea1fd0f.tar.xz
bftw: Only rebuild the part of the path that changes
Quadratic complexity is still possible for directory structures like root -- a -- a -- a -- a ... | +- b -- b -- b -- b ... But for most realistic directory structures, bfs should now spend less time building paths. (Of course if you print every path, overall complexity is quadratic anyway.)
-rw-r--r--bftw.c87
1 files changed, 50 insertions, 37 deletions
diff --git a/bftw.c b/bftw.c
index c0c1c05..0dba4b2 100644
--- a/bftw.c
+++ b/bftw.c
@@ -247,33 +247,6 @@ static struct dircache_entry *dircache_add(struct dircache *cache, struct dircac
}
/**
- * Get the full path to a dircache_entry.
- *
- * @param entry
- * The entry to look up.
- * @param[out] path
- * Will hold the full path to the entry, with a trailing '/'.
- */
-static int dircache_entry_path(const struct dircache_entry *entry, char **path) {
- size_t namelen = entry->namelen;
- size_t pathlen = entry->nameoff + namelen;
-
- if (dstresize(path, pathlen) != 0) {
- return -1;
- }
-
- // Build the path backwards
- do {
- char *segment = *path + entry->nameoff;
- namelen = entry->namelen;
- memcpy(segment, entry->name, namelen);
- entry = entry->parent;
- } while (entry);
-
- return 0;
-}
-
-/**
* Get the appropriate (fd, path) pair for the *at() family of functions.
*
* @param cache
@@ -333,7 +306,7 @@ static bool dircache_should_retry(struct dircache *cache, const struct dircache_
* @param entry
* The entry to open.
* @param path
- * The full path to the entry (see dircache_entry_path()).
+ * The full path to the entry.
* @return
* The opened DIR *, or NULL on error.
*/
@@ -624,6 +597,8 @@ struct bftw_state {
struct dirqueue queue;
/** The current dircache entry. */
struct dircache_entry *current;
+ /** The previous dircache entry. */
+ struct dircache_entry *last;
/** The currently open directory. */
DIR *dir;
/** The current traversal status. */
@@ -666,6 +641,7 @@ static int bftw_state_init(struct bftw_state *state, const char *root, bftw_fn *
}
state->current = NULL;
+ state->last = NULL;
state->dir = NULL;
state->status = BFTW_CURRENT;
@@ -685,6 +661,42 @@ err:
}
/**
+ * Compute the path to the current dircache_entry.
+ */
+static int bftw_build_path(struct bftw_state *state) {
+ const struct dircache_entry *entry = state->current;
+ size_t namelen = entry->namelen;
+ size_t pathlen = entry->nameoff + namelen;
+
+ if (dstresize(&state->path, pathlen) != 0) {
+ return -1;
+ }
+
+ // Only rebuild the part of the path that changes
+ const struct dircache_entry *last = state->last;
+ while (last && last->depth > entry->depth) {
+ last = last->parent;
+ }
+
+ // Build the path backwards
+ char *path = state->path;
+ while (entry != last) {
+ char *segment = path + entry->nameoff;
+ namelen = entry->namelen;
+ memcpy(segment, entry->name, namelen);
+
+ if (last && last->depth == entry->depth) {
+ last = last->parent;
+ }
+ entry = entry->parent;
+ }
+
+ state->last = state->current;
+
+ return 0;
+}
+
+/**
* Concatenate a subpath to the current path.
*/
static int bftw_path_concat(struct bftw_state *state, const char *subpath) {
@@ -719,6 +731,7 @@ static void bftw_path_trim(struct bftw_state *state) {
if (current->namelen > 1) {
// Trim the trailing slash
--length;
+ state->last = current->parent;
}
}
dstresize(&state->path, length);
@@ -909,7 +922,7 @@ static int bftw_gc(struct bftw_state *state, struct dircache_entry *entry, bool
}
if (entry && invoke_callback) {
- if (dircache_entry_path(entry, &state->path) != 0) {
+ if (bftw_build_path(state) != 0) {
ret = BFTW_FAIL;
invoke_callback = false;
}
@@ -918,16 +931,14 @@ static int bftw_gc(struct bftw_state *state, struct dircache_entry *entry, bool
state->status = BFTW_GC;
while (entry) {
- struct dircache_entry *current = entry;
- entry = entry->parent;
-
- dircache_entry_decref(&state->cache, current);
- if (current->refcount > 0) {
+ dircache_entry_decref(&state->cache, entry);
+ if (entry->refcount > 0) {
+ state->last = entry;
break;
}
if (invoke_callback) {
- state->current = current;
+ state->current = entry;
bftw_path_trim(state);
bftw_init_buffers(state, NULL);
@@ -946,7 +957,9 @@ static int bftw_gc(struct bftw_state *state, struct dircache_entry *entry, bool
}
}
- dircache_entry_free(&state->cache, current);
+ struct dircache_entry *parent = entry->parent;
+ dircache_entry_free(&state->cache, entry);
+ entry = parent;
}
return ret;
@@ -1037,7 +1050,7 @@ int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void
}
do {
- if (dircache_entry_path(state.current, &state.path) != 0) {
+ if (bftw_build_path(&state) != 0) {
goto fail;
}