summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2019-04-15 10:21:22 -0400
committerTavian Barnes <tavianator@tavianator.com>2019-04-20 14:18:03 -0400
commita559ffac8c65f469adefcd2d4a5c41790d7e6d05 (patch)
treeb2bacf4764570d755362ea372804aa84188fc8c4
parent60020d1f52d032c495785802c44226a63a217737 (diff)
downloadbfs-a559ffac8c65f469adefcd2d4a5c41790d7e6d05.tar.xz
[WIP] bftw: Push all files onto the queue before visiting themqueue-files
-rw-r--r--bftw.c308
-rw-r--r--bftw.h2
-rw-r--r--eval.c6
-rw-r--r--exec.c1
4 files changed, 131 insertions, 186 deletions
diff --git a/bftw.c b/bftw.c
index aee3689..ca0b06d 100644
--- a/bftw.c
+++ b/bftw.c
@@ -1,6 +1,6 @@
/****************************************************************************
* bfs *
- * Copyright (C) 2015-2018 Tavian Barnes <tavianator@tavianator.com> *
+ * Copyright (C) 2015-2019 Tavian Barnes <tavianator@tavianator.com> *
* *
* Permission to use, copy, modify, and/or distribute this software for any *
* purpose with or without fee is hereby granted. *
@@ -67,6 +67,8 @@ struct bftw_file {
/** An open descriptor to this file, or -1. */
int fd;
+ /** The type of the file. */
+ enum bftw_typeflag typeflag;
/** The device number, for cycle detection. */
dev_t dev;
/** The inode number, for cycle detection. */
@@ -315,6 +317,7 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil
file->refcount = 1;
file->fd = -1;
+ file->typeflag = BFTW_UNKNOWN;
file->dev = -1;
file->ino = -1;
@@ -531,7 +534,7 @@ struct bftw_reader {
/** The file object. */
struct bftw_file *file;
/** The path to the directory. */
- char *path;
+ const char *path;
/** The open handle to the directory. */
DIR *handle;
/** The current directory entry. */
@@ -541,17 +544,12 @@ struct bftw_reader {
};
/** Initialize a reader. */
-static int bftw_reader_init(struct bftw_reader *reader) {
- reader->path = dstralloc(0);
- if (!reader->path) {
- return -1;
- }
-
+static void bftw_reader_init(struct bftw_reader *reader) {
reader->file = NULL;
+ reader->path = NULL;
reader->handle = NULL;
reader->de = NULL;
reader->error = 0;
- return 0;
}
/** Read a directory entry. */
@@ -565,20 +563,15 @@ static int bftw_reader_read(struct bftw_reader *reader) {
}
/** Open a directory for reading. */
-static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file) {
+static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file, const char *path) {
assert(!reader->handle);
assert(!reader->de);
reader->file = file;
+ reader->path = path;
reader->error = 0;
- if (bftw_file_path(file, &reader->path) != 0) {
- reader->error = errno;
- dstresize(&reader->path, 0);
- return -1;
- }
-
- reader->handle = bftw_file_opendir(cache, file, reader->path);
+ reader->handle = bftw_file_opendir(cache, file, path);
if (!reader->handle) {
reader->error = errno;
return -1;
@@ -608,8 +601,6 @@ static void bftw_reader_destroy(struct bftw_reader *reader) {
if (reader->handle) {
bftw_reader_close(reader);
}
-
- dstrfree(reader->path);
}
/**
@@ -749,16 +740,6 @@ static enum bftw_typeflag bftw_dirent_typeflag(const struct dirent *de) {
return BFTW_UNKNOWN;
}
-/** Call stat() and use the results. */
-static int bftw_stat(struct BFTW *ftwbuf, struct bfs_stat *sb) {
- int ret = bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->at_flags, BFS_STAT_BROKEN_OK, sb);
- if (ret == 0) {
- ftwbuf->statbuf = sb;
- ftwbuf->typeflag = bftw_mode_typeflag(sb->mode);
- }
- return ret;
-}
-
/**
* Holds the current state of the bftw() traversal.
*/
@@ -780,6 +761,10 @@ struct bftw_state {
/** The queue of files left to explore. */
struct bftw_queue queue;
+ /** The current file. */
+ struct bftw_file *file;
+ /** The current path. */
+ char *path;
/** The reader for the current directory. */
struct bftw_reader reader;
/** Whether the current visit is pre- or post-order. */
@@ -818,10 +803,15 @@ static int bftw_state_init(struct bftw_state *state, const char *root, const str
bftw_queue_init(&state->queue);
- if (bftw_reader_init(&state->reader) != 0) {
+ state->file = NULL;
+
+ state->path = dstralloc(0);
+ if (!state->path) {
goto err_cache;
}
+ bftw_reader_init(&state->reader);
+
state->visit = BFTW_PRE;
return 0;
@@ -832,36 +822,6 @@ err:
return -1;
}
-/**
- * Update the path for the current file.
- */
-static int bftw_update_path(struct bftw_state *state) {
- struct bftw_reader *reader = &state->reader;
- struct bftw_file *file = reader->file;
- struct dirent *de = reader->de;
-
- size_t length = file->nameoff + file->namelen;
-
- if (dstrlen(reader->path) < length) {
- errno = reader->error;
- return -1;
- }
- dstresize(&reader->path, length);
-
- if (de) {
- if (reader->path[length - 1] != '/') {
- if (dstrapp(&reader->path, '/') != 0) {
- return -1;
- }
- }
- if (dstrcat(&reader->path, reader->de->d_name) != 0) {
- return -1;
- }
- }
-
- return 0;
-}
-
/** Check if a stat() call is needed for this visit. */
static bool bftw_need_stat(struct bftw_state *state) {
if (state->flags & BFTW_STAT) {
@@ -897,54 +857,57 @@ static bool bftw_need_stat(struct bftw_state *state) {
return false;
}
+/** Call stat() and use the results. */
+static int bftw_stat(struct bftw_state *state) {
+ struct BFTW *ftwbuf = &state->ftwbuf;
+ struct bfs_stat *statbuf = &state->statbuf;
+ struct bftw_file *file = state->file;
+
+ int ret = bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->at_flags, BFS_STAT_BROKEN_OK, statbuf);
+ if (ret == 0) {
+ ftwbuf->statbuf = statbuf;
+ ftwbuf->typeflag = bftw_mode_typeflag(statbuf->mode);
+ file->typeflag = ftwbuf->typeflag;
+ file->dev = statbuf->dev;
+ file->ino = statbuf->ino;
+ } else {
+ ftwbuf->typeflag = BFTW_ERROR;
+ ftwbuf->error = errno;
+ }
+ return ret;
+}
+
/**
* Initialize the buffers with data about the current path.
*/
static void bftw_prepare_visit(struct bftw_state *state) {
+ struct bftw_file *file = state->file;
struct bftw_reader *reader = &state->reader;
- struct bftw_file *file = reader->file;
- struct dirent *de = reader->de;
struct BFTW *ftwbuf = &state->ftwbuf;
- ftwbuf->path = file ? reader->path : state->root;
+ ftwbuf->path = state->path;
ftwbuf->root = state->root;
- ftwbuf->depth = 0;
+ ftwbuf->depth = file->depth;
ftwbuf->visit = state->visit;
+ ftwbuf->typeflag = file->typeflag;
ftwbuf->error = reader->error;
ftwbuf->statbuf = NULL;
ftwbuf->at_fd = AT_FDCWD;
ftwbuf->at_path = ftwbuf->path;
ftwbuf->at_flags = AT_SYMLINK_NOFOLLOW;
- if (file) {
- ftwbuf->depth = file->depth;
-
- if (de) {
- ftwbuf->nameoff = bftw_child_nameoff(file);
- ++ftwbuf->depth;
-
- ftwbuf->at_fd = file->fd;
- ftwbuf->at_path += ftwbuf->nameoff;
- } else {
- ftwbuf->nameoff = file->nameoff;
- bftw_file_base(file, &ftwbuf->at_fd, &ftwbuf->at_path);
- }
- }
-
if (ftwbuf->depth == 0) {
// Compute the name offset for root paths like "foo/bar"
ftwbuf->nameoff = xbasename(ftwbuf->path) - ftwbuf->path;
+ } else {
+ ftwbuf->nameoff = file->nameoff;
}
+ bftw_file_base(file, &ftwbuf->at_fd, &ftwbuf->at_path);
+
if (ftwbuf->error != 0) {
ftwbuf->typeflag = BFTW_ERROR;
return;
- } else if (de) {
- ftwbuf->typeflag = bftw_dirent_typeflag(de);
- } else if (ftwbuf->depth > 0) {
- ftwbuf->typeflag = BFTW_DIR;
- } else {
- ftwbuf->typeflag = BFTW_UNKNOWN;
}
int follow_flags = BFTW_LOGICAL;
@@ -957,9 +920,7 @@ static void bftw_prepare_visit(struct bftw_state *state) {
}
if (bftw_need_stat(state)) {
- if (bftw_stat(ftwbuf, &state->statbuf) != 0) {
- ftwbuf->typeflag = BFTW_ERROR;
- ftwbuf->error = errno;
+ if (bftw_stat(state) != 0) {
return;
}
}
@@ -982,29 +943,24 @@ static void bftw_prepare_visit(struct bftw_state *state) {
/**
* Invoke the callback.
*/
-static enum bftw_action bftw_visit_path(struct bftw_state *state) {
- if (state->reader.file) {
- if (bftw_update_path(state) != 0) {
- state->error = errno;
- return BFTW_STOP;
- }
- }
+static enum bftw_action bftw_visit(struct bftw_state *state) {
+ const struct bftw_file *file = state->file;
+ size_t pathlen = file->nameoff + file->namelen;
+ dstresize(&state->path, pathlen);
bftw_prepare_visit(state);
- // Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified
- if (state->ftwbuf.typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) {
+ if (file->typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) {
+ // Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified
state->error = state->ftwbuf.error;
return BFTW_STOP;
}
- // Defensive copy
- struct BFTW ftwbuf = state->ftwbuf;
-
- enum bftw_action action = state->callback(&ftwbuf, state->ptr);
+ enum bftw_action action = state->callback(&state->ftwbuf, state->ptr);
switch (action) {
case BFTW_CONTINUE:
- case BFTW_SKIP_SIBLINGS:
+ break;
+
case BFTW_SKIP_SUBTREE:
case BFTW_STOP:
return action;
@@ -1013,23 +969,31 @@ static enum bftw_action bftw_visit_path(struct bftw_state *state) {
state->error = EINVAL;
return BFTW_STOP;
}
+
+ if (file->typeflag != BFTW_DIR) {
+ return BFTW_SKIP_SUBTREE;
+ }
+
+ if ((state->flags & BFTW_XDEV) && file->parent && file->dev != file->parent->dev) {
+ return BFTW_SKIP_SUBTREE;
+ }
+
+ return BFTW_CONTINUE;
}
/**
* Push a new directory onto the queue.
*/
-static int bftw_push(struct bftw_state *state, const char *name) {
- struct bftw_file *parent = state->reader.file;
+static int bftw_push(struct bftw_state *state, const char *name, struct dirent *de) {
+ struct bftw_file *parent = state->file;
struct bftw_file *file = bftw_file_new(&state->cache, parent, name);
if (!file) {
state->error = errno;
return -1;
}
- const struct bfs_stat *statbuf = state->ftwbuf.statbuf;
- if (statbuf) {
- file->dev = statbuf->dev;
- file->ino = statbuf->ino;
+ if (de) {
+ file->typeflag = bftw_dirent_typeflag(de);
}
bftw_queue_push(&state->queue, file);
@@ -1037,46 +1001,54 @@ static int bftw_push(struct bftw_state *state, const char *name) {
}
/**
- * Pop a directory from the queue and start reading it.
+ * Pop a file from the queue.
*/
-static struct bftw_reader *bftw_pop(struct bftw_state *state) {
- struct bftw_reader *reader = &state->reader;
- struct bftw_file *file = bftw_queue_pop(&state->queue);
- bftw_reader_open(reader, &state->cache, file);
- return reader;
+static struct bftw_file *bftw_pop(struct bftw_state *state) {
+ state->file = bftw_queue_pop(&state->queue);
+
+ if (bftw_file_path(state->file, &state->path) == 0) {
+ return state->file;
+ } else {
+ dstresize(&state->path, 0);
+ return NULL;
+ }
+}
+
+/**
+ * Open the current directory.
+ */
+static struct bftw_reader *bftw_open(struct bftw_state *state) {
+ bftw_reader_open(&state->reader, &state->cache, state->file, state->path);
+ return &state->reader;
}
/**
* Finalize and free a file we're done with.
*/
-static enum bftw_action bftw_release_file(struct bftw_state *state, struct bftw_file *file, bool do_visit) {
+static enum bftw_action bftw_release_file(struct bftw_state *state, bool do_visit) {
enum bftw_action ret = BFTW_CONTINUE;
- if (!(state->flags & BFTW_DEPTH)) {
- do_visit = false;
- }
-
state->visit = BFTW_POST;
- while (file) {
- bftw_file_decref(&state->cache, file);
- if (file->refcount > 0) {
+ while (state->file) {
+ bftw_file_decref(&state->cache, state->file);
+ if (state->file->refcount > 0) {
break;
}
if (do_visit) {
- state->reader.file = file;
- if (bftw_visit_path(state) == BFTW_STOP) {
+ if (bftw_visit(state) == BFTW_STOP) {
ret = BFTW_STOP;
do_visit = false;
}
}
- struct bftw_file *parent = file->parent;
- bftw_file_free(&state->cache, file);
- file = parent;
+ struct bftw_file *parent = state->file->parent;
+ bftw_file_free(&state->cache, state->file);
+ state->file = parent;
}
+ state->file = NULL;
state->visit = BFTW_PRE;
return ret;
}
@@ -1094,20 +1066,13 @@ static enum bftw_action bftw_release_reader(struct bftw_state *state, bool do_vi
if (reader->error != 0) {
if (do_visit) {
- if (bftw_visit_path(state) == BFTW_STOP) {
- ret = BFTW_STOP;
- do_visit = false;
- }
+ ret = bftw_visit(state);
} else {
state->error = reader->error;
}
reader->error = 0;
}
- if (bftw_release_file(state, reader->file, do_visit) == BFTW_STOP) {
- ret = BFTW_STOP;
- }
-
reader->file = NULL;
return ret;
@@ -1126,10 +1091,16 @@ static int bftw_state_destroy(struct bftw_state *state) {
}
bftw_reader_destroy(reader);
+ if (state->file) {
+ bftw_release_file(state, false);
+ }
+
+ dstrfree(state->path);
+
struct bftw_queue *queue = &state->queue;
while (queue->head) {
- struct bftw_file *file = bftw_queue_pop(queue);
- bftw_release_file(state, file, false);
+ state->file = bftw_queue_pop(queue);
+ bftw_release_file(state, false);
}
bftw_cache_destroy(&state->cache);
@@ -1148,69 +1119,48 @@ int bftw(const char *path, const struct bftw_args *args) {
return -1;
}
- // Handle 'path' itself first
- switch (bftw_visit_path(&state)) {
- case BFTW_SKIP_SUBTREE:
- case BFTW_STOP:
- goto done;
- default:
- break;
- }
-
- if (state.ftwbuf.typeflag != BFTW_DIR) {
- goto done;
- }
-
- // Now start the breadth-first search
-
- if (bftw_push(&state, path) != 0) {
+ if (bftw_push(&state, path, NULL) != 0) {
goto done;
}
while (state.queue.head) {
- struct bftw_reader *reader = bftw_pop(&state);
+ struct bftw_file *file = bftw_pop(&state);
+ if (!file) {
+ goto done;
+ }
+ switch (bftw_visit(&state)) {
+ case BFTW_CONTINUE:
+ break;
+ case BFTW_SKIP_SUBTREE:
+ goto next;
+ case BFTW_STOP:
+ goto done;
+ }
+
+ struct bftw_reader *reader = bftw_open(&state);
while (reader->de) {
const char *name = reader->de->d_name;
if (name[0] == '.' && (name[1] == '\0' || (name[1] == '.' && name[2] == '\0'))) {
goto read;
}
- switch (bftw_visit_path(&state)) {
- case BFTW_CONTINUE:
- break;
-
- case BFTW_SKIP_SIBLINGS:
- goto next;
-
- case BFTW_SKIP_SUBTREE:
- goto read;
-
- case BFTW_STOP:
+ if (bftw_push(&state, name, reader->de) != 0) {
goto done;
}
- if (state.ftwbuf.typeflag == BFTW_DIR) {
- const struct bfs_stat *statbuf = state.ftwbuf.statbuf;
- if ((args->flags & BFTW_XDEV)
- && statbuf
- && statbuf->dev != reader->file->dev) {
- goto read;
- }
-
- if (bftw_push(&state, name) != 0) {
- goto done;
- }
- }
-
read:
bftw_reader_read(reader);
}
- next:
if (bftw_release_reader(&state, true) == BFTW_STOP) {
break;
}
+
+ next:
+ if (bftw_release_file(&state, true) == BFTW_STOP) {
+ break;
+ }
}
done:
diff --git a/bftw.h b/bftw.h
index e822523..eaeb92e 100644
--- a/bftw.h
+++ b/bftw.h
@@ -108,8 +108,6 @@ struct BFTW {
enum bftw_action {
/** Keep walking. */
BFTW_CONTINUE,
- /** Skip this path's siblings. */
- BFTW_SKIP_SIBLINGS,
/** Skip this path's children. */
BFTW_SKIP_SUBTREE,
/** Stop walking. */
diff --git a/eval.c b/eval.c
index 341b289..3b054fa 100644
--- a/eval.c
+++ b/eval.c
@@ -1206,7 +1206,6 @@ static const char *dump_bftw_visit(enum bftw_visit visit) {
static const char *dump_bftw_action(enum bftw_action action) {
static const char *actions[] = {
DUMP_BFTW_MAP(BFTW_CONTINUE),
- DUMP_BFTW_MAP(BFTW_SKIP_SIBLINGS),
DUMP_BFTW_MAP(BFTW_SKIP_SUBTREE),
DUMP_BFTW_MAP(BFTW_STOP),
};
@@ -1273,11 +1272,8 @@ static enum bftw_action cmdline_callback(struct BFTW *ftwbuf, void *ptr) {
state.action = BFTW_SKIP_SUBTREE;
}
- // In -depth mode, only handle directories on the BFTW_POST visit
enum bftw_visit expected_visit = BFTW_PRE;
- if ((cmdline->flags & BFTW_DEPTH)
- && ftwbuf->typeflag == BFTW_DIR
- && ftwbuf->depth < cmdline->maxdepth) {
+ if ((cmdline->flags & BFTW_DEPTH) && ftwbuf->depth < cmdline->maxdepth) {
expected_visit = BFTW_POST;
}
diff --git a/exec.c b/exec.c
index 3a35063..06703ad 100644
--- a/exec.c
+++ b/exec.c
@@ -265,6 +265,7 @@ static int bfs_exec_openwd(struct bfs_exec *execbuf, const struct BFTW *ftwbuf)
assert(execbuf->wd_fd < 0);
assert(!execbuf->wd_path);
+ assert(ftwbuf->depth == 0 || ftwbuf->at_path == xbasename(ftwbuf->path));
if (ftwbuf->at_fd != AT_FDCWD) {
execbuf->wd_fd = ftwbuf->at_fd;
if (!(execbuf->flags & BFS_EXEC_MULTI)) {