summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2023-07-18 12:14:07 -0400
committerTavian Barnes <tavianator@tavianator.com>2023-07-18 12:14:07 -0400
commit0e72e5c985db9a131aea3f3e9238a8916c470d8e (patch)
treedea00230919ada30fe269331e6c6e49897d3dda4
parent0d5bcc9e5c53f64024afbad19b1a01ae9b2937af (diff)
downloadbfs-0e72e5c985db9a131aea3f3e9238a8916c470d8e.tar.xz
bftw: Use bftw_file->next for multiple lists
A file can be on the to_open and to_read lists at the same time, but otherwise only one list, so we can save memory by sharing the pointers.
-rw-r--r--src/bftw.c50
1 files changed, 21 insertions, 29 deletions
diff --git a/src/bftw.c b/src/bftw.c
index c66e607..5d28612 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -115,14 +115,10 @@ struct bftw_file {
/** The root under which this file was found. */
struct bftw_file *root;
- /** The next directory to open. */
- struct { struct bftw_file *next; } to_open;
+ /** The next file to open/close/visit. */
+ struct bftw_file *next;
/** The next directory to read. */
struct { struct bftw_file *next; } to_read;
- /** The next directory to close. */
- struct { struct bftw_file *next; } to_close;
- /** The next file to visit. */
- struct { struct bftw_file *next; } to_visit;
/** LRU list node. */
struct {
@@ -336,10 +332,8 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil
file->nameoff = 0;
}
- file->to_open.next = NULL;
+ file->next = NULL;
file->to_read.next = NULL;
- file->to_close.next = NULL;
- file->to_visit.next = NULL;
file->lru.prev = file->lru.next = NULL;
file->refcount = 1;
@@ -536,7 +530,7 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
if (parent) {
bftw_cache_unpin(cache, parent);
if (parent->pincount == 0 && parent->dir) {
- SLIST_APPEND(&state->to_close, parent, to_close);
+ SLIST_APPEND(&state->to_close, parent);
}
}
@@ -665,10 +659,10 @@ static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, cons
struct bftw_file *cur;
for (cur = file; cur != base; cur = cur->parent) {
- SLIST_PREPEND(&parents, cur, to_open);
+ SLIST_PREPEND(&parents, cur);
}
- while ((cur = SLIST_POP(&parents, to_open))) {
+ while ((cur = SLIST_POP(&parents))) {
if (!cur->parent || cur->parent->fd >= 0) {
bftw_file_openat(state, cur, cur->parent, cur->name);
}
@@ -824,7 +818,7 @@ fail:
static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) {
bfs_assert(file->type == BFS_DIR);
- SLIST_APPEND(&state->to_open, file, to_open);
+ SLIST_APPEND(&state->to_open, file);
if (state->flags & BFTW_SORT) {
// When sorting, directories are kept in order on the to_read
@@ -834,7 +828,7 @@ static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) {
while (state->to_open.head) {
if (bftw_ioq_opendir(state, state->to_open.head) == 0) {
- SLIST_POP(&state->to_open, to_open);
+ SLIST_POP(&state->to_open);
} else {
break;
}
@@ -867,7 +861,7 @@ static bool bftw_pop_dir(struct bftw_state *state) {
struct bftw_file *file = SLIST_POP(&state->to_read, to_read);
if (!file || file == state->to_open.head) {
- file = SLIST_POP(&state->to_open, to_open);
+ file = SLIST_POP(&state->to_open);
}
if (!file) {
return false;
@@ -888,7 +882,7 @@ static bool bftw_pop_dir(struct bftw_state *state) {
/** Pop a file to visit from the queue. */
static bool bftw_pop_file(struct bftw_state *state) {
bfs_assert(!state->file);
- state->file = SLIST_POP(&state->to_visit, to_visit);
+ state->file = SLIST_POP(&state->to_visit);
return state->file;
}
@@ -1232,7 +1226,7 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
struct bftw_file *file = state->file;
if (file && file->dir) {
bftw_cache_unpin(&state->cache, file);
- SLIST_APPEND(&state->to_close, file, to_close);
+ SLIST_APPEND(&state->to_close, file);
}
state->dir = NULL;
state->de = NULL;
@@ -1249,7 +1243,7 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
}
state->direrror = 0;
- while ((file = SLIST_POP(&state->to_close, to_close))) {
+ while ((file = SLIST_POP(&state->to_close))) {
bftw_unwrapdir(state, file);
}
@@ -1285,7 +1279,7 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
/** Sort a bftw_list by filename. */
static void bftw_list_sort(struct bftw_list *list) {
- if (!list->head || !list->head->to_visit.next) {
+ if (!list->head || !list->head->next) {
return;
}
@@ -1294,11 +1288,9 @@ static void bftw_list_sort(struct bftw_list *list) {
SLIST_INIT(&right);
// Split
- for (struct bftw_file *hare = list->head;
- hare && (hare = hare->to_visit.next);
- hare = hare->to_visit.next) {
- struct bftw_file *tortoise = SLIST_POP(list, to_visit);
- SLIST_APPEND(&left, tortoise, to_visit);
+ for (struct bftw_file *hare = list->head; hare && (hare = hare->next); hare = hare->next) {
+ struct bftw_file *tortoise = SLIST_POP(list);
+ SLIST_APPEND(&left, tortoise);
}
SLIST_EXTEND(&right, list);
@@ -1312,11 +1304,11 @@ static void bftw_list_sort(struct bftw_list *list) {
struct bftw_file *rf = right.head;
if (strcoll(lf->name, rf->name) <= 0) {
- SLIST_POP(&left, to_visit);
- SLIST_APPEND(list, lf, to_visit);
+ SLIST_POP(&left);
+ SLIST_APPEND(list, lf);
} else {
- SLIST_POP(&right, to_visit);
- SLIST_APPEND(list, rf, to_visit);
+ SLIST_POP(&right);
+ SLIST_APPEND(list, rf);
}
}
SLIST_EXTEND(list, &left);
@@ -1374,7 +1366,7 @@ static int bftw_visit(struct bftw_state *state, const char *name) {
file->type = state->de->type;
}
- SLIST_APPEND(&state->batch, file, to_visit);
+ SLIST_APPEND(&state->batch, file);
return 0;
}