summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/bftw.c136
-rw-r--r--src/config.h11
-rw-r--r--src/list.c169
-rw-r--r--src/list.h447
-rw-r--r--src/trie.c8
-rw-r--r--src/trie.h9
-rw-r--r--src/xspawn.c15
-rw-r--r--src/xspawn.h4
8 files changed, 401 insertions, 398 deletions
diff --git a/src/bftw.c b/src/bftw.c
index aa36b87..7bc724a 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -7,6 +7,8 @@
* - struct bftw_file: A file that has been encountered during the traversal.
* They have reference-counted links to their parents in the directory tree.
*
+ * - struct bftw_list: A linked list of bftw_file's.
+ *
* - struct bftw_cache: An LRU list of bftw_file's with open file descriptors,
* used for openat() to minimize the amount of path re-traversals.
*
@@ -39,11 +41,14 @@ struct bftw_file {
struct bftw_file *parent;
/** The root under which this file was found. */
struct bftw_file *root;
+ /** The next file in the queue, if any. */
+ struct bftw_file *next;
- /** Queue link. */
- struct slink link;
- /** LRU link. */
- struct link lru;
+ /** LRU list links. */
+ struct {
+ struct bftw_file *prev;
+ struct bftw_file *next;
+ } lru;
/** This file's depth in the walk. */
size_t depth;
@@ -68,36 +73,42 @@ struct bftw_file {
char name[];
};
-/** Move from a list entry to a bftw_file. */
-#define BFTW_FILE(...) \
- LIST_ITEM(struct bftw_file, __VA_ARGS__)
+/**
+ * A linked list of bftw_file's.
+ */
+struct bftw_list {
+ struct bftw_file *head;
+ struct bftw_file **tail;
+};
/**
* A cache of open directories.
*/
struct bftw_cache {
- /** The LRU list. */
- struct list list;
+ /** The head of the LRU list. */
+ struct bftw_file *head;
+ /** The tail of the LRU list. */
+ struct bftw_file *tail;
/** The insertion target for the LRU list. */
- struct link *target;
+ struct bftw_file *target;
/** The remaining capacity of the LRU list. */
size_t capacity;
};
/** Initialize a cache. */
static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
- list_init(&cache->list);
+ LIST_INIT(cache);
cache->target = NULL;
cache->capacity = capacity;
}
/** Remove a bftw_file from the cache. */
static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
- if (cache->target == &file->lru) {
- cache->target = cache->target->prev;
+ if (cache->target == file) {
+ cache->target = file->lru.prev;
}
- list_remove(&cache->list, &file->lru);
+ LIST_REMOVE(cache, file, lru);
++cache->capacity;
}
@@ -106,7 +117,7 @@ static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file)
static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
assert(file->fd >= 0);
- if (list_attached(&cache->list, &file->lru)) {
+ if (LIST_ATTACHED(cache, file, lru)) {
bftw_cache_remove(cache, file);
}
@@ -116,11 +127,11 @@ static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
/** Pop the least recently used directory from the cache. */
static int bftw_cache_pop(struct bftw_cache *cache) {
- if (list_is_empty(&cache->list)) {
+ struct bftw_file *file = cache->tail;
+ if (!file) {
return -1;
}
- struct bftw_file *file = BFTW_FILE(cache->list.tail, lru);
bftw_file_close(cache, file);
return 0;
}
@@ -138,11 +149,11 @@ static int bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
assert(cache->capacity > 0);
--cache->capacity;
- list_insert_after(&cache->list, cache->target, &file->lru);
+ LIST_INSERT(cache, cache->target, file, lru);
// Prefer to keep the root paths open by keeping them at the head of the list
if (file->depth == 0) {
- cache->target = &file->lru;
+ cache->target = file;
}
return 0;
@@ -159,8 +170,9 @@ static size_t bftw_child_nameoff(const struct bftw_file *parent) {
/** Destroy a cache. */
static void bftw_cache_destroy(struct bftw_cache *cache) {
+ assert(!cache->head);
+ assert(!cache->tail);
assert(!cache->target);
- assert(list_is_empty(&cache->list));
}
/** Create a new bftw_file. */
@@ -186,8 +198,8 @@ static struct bftw_file *bftw_file_new(struct bftw_file *parent, const char *nam
file->nameoff = 0;
}
- slink_init(&file->link);
- link_init(&file->lru);
+ file->next = NULL;
+ file->lru.prev = file->lru.next = NULL;
file->refcount = 1;
file->fd = -1;
@@ -280,16 +292,19 @@ static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, cons
}
// Handle ENAMETOOLONG by manually traversing the path component-by-component
- struct slist parents;
- slist_init(&parents);
- for (struct bftw_file *cur = file; cur != base; cur = cur->parent) {
- slist_prepend(&parents, &cur->link);
+ struct bftw_list parents;
+ SLIST_INIT(&parents);
+
+ struct bftw_file *cur;
+ for (cur = file; cur != base; cur = cur->parent) {
+ SLIST_PREPEND(&parents, cur);
}
- LIST_DRAIN(&parents, struct bftw_file, cur) {
+ while ((cur = parents.head)) {
if (!cur->parent || cur->parent->fd >= 0) {
bftw_file_openat(cache, cur, cur->parent, cur->name);
}
+ SLIST_POP(&parents);
}
return file->fd;
@@ -348,9 +363,9 @@ struct bftw_state {
/** The cache of open directories. */
struct bftw_cache cache;
/** The queue of files left to explore. */
- struct slist queue;
+ struct bftw_list queue;
/** A batch of files to enqueue. */
- struct slist batch;
+ struct bftw_list batch;
/** The current path. */
char *path;
@@ -396,8 +411,8 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg
bftw_cache_init(&state->cache, args->nopenfd);
- slist_init(&state->queue);
- slist_init(&state->batch);
+ SLIST_INIT(&state->queue);
+ SLIST_INIT(&state->batch);
state->file = NULL;
state->previous = NULL;
@@ -757,7 +772,7 @@ static int bftw_push(struct bftw_state *state, const char *name, bool fill_id) {
bftw_fill_id(file, &state->ftwbuf);
}
- slist_append(&state->batch, &file->link);
+ SLIST_APPEND(&state->batch, file);
return 0;
}
@@ -800,11 +815,12 @@ static int bftw_build_path(struct bftw_state *state) {
* Pop the next file from the queue.
*/
static int bftw_pop(struct bftw_state *state) {
- if (!state->queue.head) {
+ state->file = state->queue.head;
+ if (!state->file) {
return 0;
}
- state->file = BFTW_FILE(slist_pop(&state->queue));
+ SLIST_POP(&state->queue);
if (bftw_build_path(state) != 0) {
return -1;
@@ -940,8 +956,10 @@ static enum bftw_action bftw_gc_file(struct bftw_state *state, enum bftw_gc_flag
* Drain all the files from the queue.
*/
static void bftw_drain_queue(struct bftw_state *state) {
- LIST_DRAIN(&state->queue, struct bftw_file, file) {
- state->file = file;
+ while (state->queue.head) {
+ state->file = state->queue.head;
+ SLIST_POP(&state->queue);
+
bftw_gc_file(state, BFTW_VISIT_NONE);
}
}
@@ -966,21 +984,55 @@ static int bftw_state_destroy(struct bftw_state *state) {
return state->error ? -1 : 0;
}
-/** Comparison function for BFTW_SORT. */
-static bool bftw_file_cmp(struct slink *left, struct slink *right, const void *ptr) {
- return strcoll(BFTW_FILE(left)->name, BFTW_FILE(right)->name) <= 0;
+/** Sort a bftw_list by filename. */
+static void bftw_list_sort(struct bftw_list *queue) {
+ if (!queue->head || !queue->head->next) {
+ return;
+ }
+
+ struct bftw_list left, right;
+ SLIST_INIT(&left);
+ SLIST_INIT(&right);
+
+ // Split
+ for (struct bftw_file *hare = queue->head; hare && (hare = hare->next); hare = hare->next) {
+ struct bftw_file *tortoise = queue->head;
+ SLIST_POP(queue);
+ SLIST_APPEND(&left, tortoise);
+ }
+ SLIST_EXTEND(&right, queue);
+
+ // Recurse
+ bftw_list_sort(&left);
+ bftw_list_sort(&right);
+
+ // Merge
+ while (left.head && right.head) {
+ struct bftw_file *lf = left.head;
+ struct bftw_file *rf = right.head;
+
+ if (strcoll(lf->name, rf->name) <= 0) {
+ SLIST_POP(&left);
+ SLIST_APPEND(queue, lf);
+ } else {
+ SLIST_POP(&right);
+ SLIST_APPEND(queue, rf);
+ }
+ }
+ SLIST_EXTEND(queue, &left);
+ SLIST_EXTEND(queue, &right);
}
/** Finish adding a batch of files. */
static void bftw_batch_finish(struct bftw_state *state) {
if (state->flags & BFTW_SORT) {
- slist_sort(&state->batch, bftw_file_cmp, NULL);
+ bftw_list_sort(&state->batch);
}
if (state->strategy == BFTW_DFS) {
- slist_extend(&state->batch, &state->queue);
+ SLIST_EXTEND(&state->batch, &state->queue);
}
- slist_extend(&state->queue, &state->batch);
+ SLIST_EXTEND(&state->queue, &state->batch);
}
/**
diff --git a/src/config.h b/src/config.h
index cee8511..34ae11d 100644
--- a/src/config.h
+++ b/src/config.h
@@ -147,17 +147,6 @@
*/
#define BFS_COUNTOF(array) (sizeof(array) / sizeof(0[array]))
-// BFS_CONTAINER_OF() helper
-static inline char *bfs_container_offset(char *ptr, ptrdiff_t offset, size_t unused) {
- return ptr ? ptr - offset : NULL;
-}
-
-/**
- * Move a pointer from a field to its outer struct.
- */
-#define BFS_CONTAINER_OF(ptr, type, member) \
- ((type *)bfs_container_offset((char *)(ptr), offsetof(type, member), sizeof((ptr) - &((type *)NULL)->member)))
-
// Lower bound on BFS_FLEX_SIZEOF()
#define BFS_FLEX_LB(type, member, length) (offsetof(type, member) + sizeof(((type *)NULL)->member[0]) * (length))
diff --git a/src/list.c b/src/list.c
deleted file mode 100644
index dffee19..0000000
--- a/src/list.c
+++ /dev/null
@@ -1,169 +0,0 @@
-// Copyright © Tavian Barnes <tavianator@tavianator.com>
-// SPDX-License-Identifier: 0BSD
-
-#include "list.h"
-#include <assert.h>
-#include <stddef.h>
-
-void slink_init(struct slink *link) {
- link->next = NULL;
-}
-
-void slist_init(struct slist *list) {
- list->head = NULL;
- list->tail = &list->head;
-}
-
-bool slist_is_empty(const struct slist *list) {
- return !list->head;
-}
-
-void slist_append(struct slist *list, struct slink *link) {
- assert(!link->next);
- *list->tail = link;
- list->tail = &link->next;
-}
-
-void slist_prepend(struct slist *list, struct slink *link) {
- assert(!link->next);
- if (!list->head) {
- list->tail = &link->next;
- }
- link->next = list->head;
- list->head = link;
-}
-
-void slist_extend(struct slist *dest, struct slist *src) {
- if (src->head) {
- *dest->tail = src->head;
- dest->tail = src->tail;
- slist_init(src);
- }
-}
-
-struct slink *slist_pop(struct slist *list) {
- struct slink *head = list->head;
- if (!head) {
- return NULL;
- }
-
- list->head = head->next;
- if (!list->head) {
- list->tail = &list->head;
- }
-
- head->next = NULL;
- return head;
-}
-
-void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr) {
- if (!list->head || !list->head->next) {
- return;
- }
-
- struct slist left, right;
- slist_init(&left);
- slist_init(&right);
-
- // Split
- for (struct slink *hare = list->head; hare && (hare = hare->next); hare = hare->next) {
- slist_append(&left, slist_pop(list));
- }
- slist_extend(&right, list);
-
- // Recurse
- slist_sort(&left, cmp_fn, ptr);
- slist_sort(&right, cmp_fn, ptr);
-
- // Merge
- while (left.head && right.head) {
- if (cmp_fn(left.head, right.head, ptr)) {
- slist_append(list, slist_pop(&left));
- } else {
- slist_append(list, slist_pop(&right));
- }
- }
- slist_extend(list, &left);
- slist_extend(list, &right);
-}
-
-void link_init(struct link *link) {
- link->prev = NULL;
- link->next = NULL;
-}
-
-void list_init(struct list *list) {
- list->head = NULL;
- list->tail = NULL;
-}
-
-bool list_is_empty(const struct list *list) {
- return !list->head;
-}
-
-void list_append(struct list *list, struct link *link) {
- list_insert_after(list, list->tail, link);
-}
-
-void list_prepend(struct list *list, struct link *link) {
- list_insert_after(list, NULL, link);
-}
-
-void list_insert_after(struct list *list, struct link *target, struct link *link) {
- assert(!list_attached(list, link));
-
- if (target) {
- link->prev = target;
- link->next = target->next;
- } else {
- link->next = list->head;
- }
-
- if (link->prev) {
- link->prev->next = link;
- } else {
- list->head = link;
- }
-
- if (link->next) {
- link->next->prev = link;
- } else {
- list->tail = link;
- }
-}
-
-void list_remove(struct list *list, struct link *link) {
- if (link->prev) {
- assert(list->head != link);
- link->prev->next = link->next;
- } else {
- assert(list->head == link);
- list->head = link->next;
- }
-
- if (link->next) {
- assert(list->tail != link);
- link->next->prev = link->prev;
- } else {
- assert(list->tail == link);
- list->tail = link->prev;
- }
-
- link->prev = NULL;
- link->next = NULL;
-}
-
-struct link *list_pop(struct list *list) {
- struct link *head = list->head;
- if (!head) {
- return NULL;
- }
-
- list_remove(list, head);
- return head;
-}
-
-bool list_attached(const struct list *list, const struct link *link) {
- return link->prev || list->head == link
- || link->next || list->tail == link;
-}
diff --git a/src/list.h b/src/list.h
index b47bed7..c43be68 100644
--- a/src/list.h
+++ b/src/list.h
@@ -3,225 +3,354 @@
/**
* Intrusive linked lists.
+ *
+ * Singly-linked lists are declared like this:
+ *
+ * struct item {
+ * struct item *next;
+ * };
+ *
+ * struct list {
+ * struct item *head;
+ * struct item **tail;
+ * };
+ *
+ * The SLIST_*() macros manipulate singly-linked lists.
+ *
+ * struct list list;
+ * SLIST_INIT(&list);
+ *
+ * struct item item;
+ * SLIST_APPEND(&list, &item);
+ *
+ * Doubly linked lists are similar:
+ *
+ * struct item {
+ * struct item *next;
+ * struct item *prev;
+ * };
+ *
+ * struct list {
+ * struct item *head;
+ * struct item *tail;
+ * };
+ *
+ * struct list list;
+ * LIST_INIT(&list);
+ *
+ * struct item item;
+ * LIST_APPEND(&list, &item);
+ *
+ * Items can be on multiple lists at once:
+ *
+ * struct item {
+ * struct {
+ * struct item *next;
+ * } chain;
+ *
+ * struct {
+ * struct item *next;
+ * struct item *prev;
+ * } lru;
+ * };
+ *
+ * struct items {
+ * struct {
+ * struct item *head;
+ * struct item **tail;
+ * } queue;
+ *
+ * struct {
+ * struct item *head;
+ * struct item *tail;
+ * } cache;
+ * };
+ *
+ * struct items items;
+ * SLIST_INIT(&items.queue);
+ * LIST_INIT(&items.cache);
+ *
+ * struct item item;
+ * SLIST_APPEND(&items.queue, &item, chain);
+ * LIST_APPEND(&items.cache, &item, lru);
*/
#ifndef BFS_LIST_H
#define BFS_LIST_H
-#include "config.h"
-#include <stdbool.h>
+#include <stddef.h>
/**
- * A singly-linked list entry.
+ * Initialize a singly-linked list.
+ *
+ * @param list
+ * The list to initialize.
+ *
+ * ---
+ *
+ * Like many macros in this file, this macro delegates the bulk of its work to
+ * some helper macros. We explicitly parenthesize (list) here so the helpers
+ * don't have to.
*/
-struct slink {
- struct slink *next;
-};
+#define SLIST_INIT(list) \
+ LIST_BLOCK_(SLIST_INIT_((list)))
-/** Initialize a list entry. */
-void slink_init(struct slink *link);
+#define SLIST_INIT_(list) \
+ (list)->head = NULL; \
+ (list)->tail = &(list)->head;
/**
- * A singly-linked list.
+ * Wraps a group of statements in a block.
*/
-struct slist {
- struct slink *head;
- struct slink **tail;
-};
-
-/** Initialize an empty list. */
-void slist_init(struct slist *list);
-
-/** Check if a list is empty. */
-bool slist_is_empty(const struct slist *list);
-
-/** Add an entry at the tail of the list. */
-void slist_append(struct slist *list, struct slink *link);
-
-/** Add an entry at the head of the list. */
-void slist_prepend(struct slist *list, struct slink *link);
-
-/** Add an entire list at the tail of the list. */
-void slist_extend(struct slist *dest, struct slist *src);
-
-/** Remove the head of the list. */
-struct slink *slist_pop(struct slist *list);
+#define LIST_BLOCK_(block) do { block } while (0)
/**
- * Comparison function type for slist_sort().
+ * Add an item to the tail of a singly-linked list.
*
- * @param left
- * The left-hand side of the comparison.
- * @param right
- * The right-hand side of the comparison.
- * @param ptr
- * An arbitrary pointer passed to slist_sort().
- * @return
- * Whether left <= right.
+ * @param list
+ * The list to modify.
+ * @param item
+ * The item to append.
+ * @param link (optional)
+ * If specified, use item->link.next rather than item->next.
+ *
+ * ---
+ *
+ * We play some tricks with variadic macros to handle the optional parameter:
+ *
+ * SLIST_APPEND(list, item) => {
+ * *list->tail = item;
+ * list->tail = &item->next;
+ * }
+ *
+ * SLIST_APPEND(list, item, link) => {
+ * *list->tail = item;
+ * list->tail = &item->link.next;
+ * }
+ *
+ * The first trick is that
+ *
+ * #define SLIST_APPEND(list, item, ...)
+ *
+ * won't work because both commas are required (until C23; see N3033). As a
+ * workaround, we dispatch to another macro and add a trailing comma.
+ *
+ * SLIST_APPEND(list, item) => SLIST_APPEND_(list, item, )
+ * SLIST_APPEND(list, item, link) => SLIST_APPEND_(list, item, link, )
*/
-typedef bool slist_cmp_fn(struct slink *left, struct slink *right, const void *ptr);
+#define SLIST_APPEND(list, ...) SLIST_APPEND_(list, __VA_ARGS__, )
-/** Sort a list. */
-void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr);
+/**
+ * Now we need a way to generate either ->next or ->link.next depending on
+ * whether the link parameter was passed. The approach is based on
+ *
+ * #define FOO(...) BAR(__VA_ARGS__, 1, 2, )
+ * #define BAR(x, y, z, ...) z
+ *
+ * FOO(a) => 2
+ * FOO(a, b) => 1
+ *
+ * The LIST_NEXT_() macro uses this technique:
+ *
+ * LIST_NEXT_() => LIST_LINK_(next, )
+ * LIST_NEXT_(link, ) => LIST_LINK_(next, link, )
+ */
+#define LIST_NEXT_(...) LIST_LINK_(next, __VA_ARGS__)
/**
- * A doubly-linked list entry.
+ * LIST_LINK_() dispatches to yet another macro:
+ *
+ * LIST_LINK_(next, ) => LIST_LINK__(next, , , . , , )
+ * LIST_LINK_(next, link, ) => LIST_LINK__(next, link, , , . , , )
*/
-struct link {
- struct link *prev;
- struct link *next;
-};
+#define LIST_LINK_(dir, ...) LIST_LINK__(dir, __VA_ARGS__, , . , , )
-/** Initialize a list entry. */
-void link_init(struct link *link);
+/**
+ * And finally, LIST_LINK__() adds the link and the dot if necessary.
+ *
+ * dir link blank ignored dot
+ * v v v v v
+ * LIST_LINK__(next, , , . , , ) => next
+ * LIST_LINK__(next, link, , , . , , ) => link . next
+ * ^ ^ ^ ^ ^
+ * dir link blank ignored dot
+ */
+#define LIST_LINK__(dir, link, blank, ignored, dot, ...) link dot dir
/**
- * A doubly-linked list.
+ * SLIST_APPEND_() uses LIST_NEXT_() to generate the right name for the list
+ * link, and finally delegates to the actual implementation.
+ *
+ * SLIST_APPEND_(list, item, ) => SLIST_APPEND__((list), (item), next)
+ * SLIST_APPEND_(list, item, link, ) => SLIST_APPEND__((list), (item), link.next)
*/
-struct list {
- struct link *head;
- struct link *tail;
-};
+#define SLIST_APPEND_(list, item, ...) \
+ LIST_BLOCK_(SLIST_APPEND__((list), (item), LIST_NEXT_(__VA_ARGS__)))
-/** Initialize an empty list. */
-void list_init(struct list *list);
+#define SLIST_APPEND__(list, item, next) \
+ *list->tail = item; \
+ list->tail = &item->next;
-/** Check if a list is empty. */
-bool list_is_empty(const struct list *list);
+/**
+ * Add an item to the head of a singly-linked list.
+ *
+ * @param list
+ * The list to modify.
+ * @param item
+ * The item to prepend.
+ * @param link (optional)
+ * If specified, use item->link.next rather than item->next.
+ */
+#define SLIST_PREPEND(list, ...) SLIST_PREPEND_(list, __VA_ARGS__, )
-/** Add an entry at the tail of the list. */
-void list_append(struct list *list, struct link *link);
+#define SLIST_PREPEND_(list, item, ...) \
+ LIST_BLOCK_(SLIST_PREPEND__((list), (item), LIST_NEXT_(__VA_ARGS__)))
-/** Add an entry at the head of the list. */
-void list_prepend(struct list *list, struct link *link);
+#define SLIST_PREPEND__(list, item, next) \
+ list->tail = list->head ? list->tail : &item->next; \
+ item->next = list->head; \
+ list->head = item;
-/** Insert an entry after the target entry. */
-void list_insert_after(struct list *list, struct link *target, struct link *link);
+/**
+ * Add an entire singly-linked list to the tail of another.
+ *
+ * @param dest
+ * The destination list.
+ * @param src
+ * The source list.
+ */
+#define SLIST_EXTEND(dest, src) \
+ LIST_BLOCK_(SLIST_EXTEND_((dest), (src)))
-/** Remove an entry from a list. */
-void list_remove(struct list *list, struct link *link);
+#define SLIST_EXTEND_(dest, src) \
+ if (src->head) { \
+ *dest->tail = src->head; \
+ dest->tail = src->tail; \
+ SLIST_INIT(src); \
+ }
-/** Remove the head of the list. */
-struct link *list_pop(struct list *list);
+/**
+ * Pop the head off a singly-linked list.
+ *
+ * @param list
+ * The list to pop from.
+ * @param link (optional)
+ * If specified, use head->link.next rather than head->next.
+ */
+#define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, )
-/** Check if a link is attached to a list. */
-bool list_attached(const struct list *list, const struct link *link);
+#define SLIST_POP_(list, ...) \
+ LIST_BLOCK_(SLIST_POP__((list), LIST_NEXT_(__VA_ARGS__)))
-// LIST_ITEM() helper
-#define LIST_ITEM_IMPL(type, entry, member, ...) \
- BFS_CONTAINER_OF(entry, type, member)
+#define SLIST_POP__(list, next) \
+ void *_next = (void *)list->head->next; \
+ list->head->next = NULL; \
+ list->head = _next; \
+ list->tail = list->head ? list->tail : &list->head;
/**
- * Convert a list entry to its container.
+ * Initialize a doubly-linked list.
*
- * @param type
- * The type of the list entries.
- * @param entry
- * The list entry to convert.
- * @param member
- * The name of the list link field (default: link).
- * @return
- * The item that contains the given entry.
+ * @param list
+ * The list to initialize.
*/
-#define LIST_ITEM(...) \
- LIST_ITEM_IMPL(__VA_ARGS__, link,)
+#define LIST_INIT(list) \
+ LIST_BLOCK_(LIST_INIT_((list)))
-// LIST_NEXT() helper
-#define LIST_NEXT_IMPL(type, entry, member, ...) \
- LIST_ITEM(type, (entry)->member.next, member)
+#define LIST_INIT_(list) \
+ list->head = list->tail = NULL;
/**
- * Get the next item in a list.
- *
- * @param type
- * The type of the list entries.
- * @param entry
- * The current entry.
- * @param member
- * The name of the list link field (default: link).
- * @return
- * The next item in the list.
+ * LIST_PREV_() => prev
+ * LIST_PREV_(link, ) => link.prev
*/
-#define LIST_NEXT(...) \
- LIST_NEXT_IMPL(__VA_ARGS__, link,)
-
-// LIST_PREV() helper
-#define LIST_PREV_IMPL(type, entry, member, ...) \
- LIST_ITEM(type, (entry)->member.prev, member)
+#define LIST_PREV_(...) LIST_LINK_(prev, __VA_ARGS__)
/**
- * Get the previous entry in a list.
+ * Add an item to the tail of a doubly-linked list.
*
- * @param type
- * The type of the list entries.
- * @param entry
- * The current entry.
- * @param member
- * The name of the list link field (default: link).
- * @return
- * The previous item in the list.
+ * @param list
+ * The list to modify.
+ * @param item
+ * The item to append.
+ * @param link (optional)
+ * If specified, use item->link.{prev,next} rather than item->{prev,next}.
*/
-#define LIST_PREV(...) \
- LIST_PREV_IMPL(__VA_ARGS__, link,)
+#define LIST_APPEND(list, ...) LIST_INSERT(list, (list)->tail, __VA_ARGS__)
-// Helper for LIST_FOR_EACH_*()
-#define LIST_FOR_EACH_IMPL(entry, type, i, member, ...) \
- for (type *_next, *i = LIST_ITEM(type, entry, member); \
- i && (_next = LIST_NEXT(type, i, member), true); \
- i = _next)
+/**
+ * Add an item to the head of a doubly-linked list.
+ *
+ * @param list
+ * The list to modify.
+ * @param item
+ * The item to prepend.
+ * @param link (optional)
+ * If specified, use item->link.{prev,next} rather than item->{prev,next}.
+ */
+#define LIST_PREPEND(list, ...) LIST_INSERT(list, NULL, __VA_ARGS__)
/**
- * Iterate over a list from the given entry.
+ * Insert into a doubly-linked list after the given cursor.
*
- * @param entry
- * The entry to start from.
- * @param type
- * The type of the list entries.
- * @param i
- * The name of the loop variable, declared as type *i.
- * @param member
- * The name of the list link field (default: link).
+ * @param list
+ * The list to initialize.
+ * @param cursor
+ * Insert after this element.
+ * @param item
+ * The item to insert.
+ * @param link (optional)
+ * If specified, use item->link.{prev,next} rather than item->{prev,next}.
*/
-#define LIST_FOR_EACH_FROM(...) \
- LIST_FOR_EACH_IMPL(__VA_ARGS__, link,)
+#define LIST_INSERT(list, cursor, ...) LIST_INSERT_(list, cursor, __VA_ARGS__, )
+
+#define LIST_INSERT_(list, cursor, item, ...) \
+ LIST_BLOCK_(LIST_INSERT__((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)))
+
+#define LIST_INSERT__(list, cursor, item, prev, next) \
+ item->prev = cursor; \
+ item->next = cursor ? cursor->next : list->head; \
+ *(item->prev ? &item->prev->next : &list->head) = item; \
+ *(item->next ? &item->next->prev : &list->tail) = item;
/**
- * Iterate over a list.
+ * Remove an item from a doubly-linked list.
*
* @param list
- * The list to iterate over.
- * @param type
- * The type of the list entries.
- * @param i
- * The name of the loop variable, declared as type *i.
- * @param member
- * The name of the list link field (default: link).
+ * The list to modify.
+ * @param item
+ * The item to remove.
+ * @param link (optional)
+ * If specified, use item->link.{prev,next} rather than item->{prev,next}.
*/
-#define LIST_FOR_EACH(list, ...) \
- LIST_FOR_EACH_FROM((list)->head, __VA_ARGS__)
+#define LIST_REMOVE(list, ...) LIST_REMOVE_(list, __VA_ARGS__, )
-// Pop from a list or slist
-#define LIST_POP(l) _Generic((l), \
- struct list *: list_pop((struct list *)l), \
- struct slist *: slist_pop((struct slist *)l))
+#define LIST_REMOVE_(list, item, ...) \
+ LIST_BLOCK_(LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)))
-// Helper for LIST_DRAIN()
-#define LIST_DRAIN_IMPL(list, type, i, member, ...) \
- for (type *i; (i = LIST_ITEM(type, LIST_POP(list), member));)
+#define LIST_REMOVE__(list, item, prev, next) \
+ *(item->prev ? &item->prev->next : &list->head) = item->next; \
+ *(item->next ? &item->next->prev : &list->tail) = item->prev; \
+ item->prev = item->next = NULL;
/**
- * Drain the entries from a list.
+ * Check if an item is attached to a doubly-linked list.
*
* @param list
- * The list to drain.
- * @param type
- * The type of the list entries.
- * @param i
- * The name of the loop variable, declared as type *i.
- * @param member
- * The name of the list link field (default: link).
- */
-#define LIST_DRAIN(...) \
- LIST_DRAIN_IMPL(__VA_ARGS__, link,)
+ * The list to check.
+ * @param item
+ * The item to check.
+ * @param link (optional)
+ * If specified, use item->link.{prev,next} rather than item->{prev,next}.
+ * @return
+ * Whether the item is attached to the list.
+ */
+#define LIST_ATTACHED(list, ...) LIST_ATTACHED_(list, __VA_ARGS__, )
+
+#define LIST_ATTACHED_(list, item, ...) \
+ LIST_ATTACHED__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
+
+#define LIST_ATTACHED__(list, item, prev, next) \
+ (item->prev || item->next || list->head == item || list->tail == item)
#endif // BFS_LIST_H
diff --git a/src/trie.c b/src/trie.c
index 7b00f4b..43df9dc 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -83,6 +83,7 @@
#include "trie.h"
#include "config.h"
+#include "list.h"
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
@@ -163,7 +164,7 @@ static uintptr_t trie_encode_node(const struct trie_node *node) {
void trie_init(struct trie *trie) {
trie->root = 0;
- list_init(&trie->leaves);
+ LIST_INIT(trie);
}
/** Check if a number is a power of two. */
@@ -340,8 +341,7 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz
return NULL;
}
- link_init(&leaf->link);
- list_append(&trie->leaves, &leaf->link);
+ LIST_APPEND(trie, leaf);
leaf->value = NULL;
leaf->length = length;
@@ -352,7 +352,7 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz
/** Free a leaf. */
static void trie_leaf_free(struct trie *trie, struct trie_leaf *leaf) {
- list_remove(&trie->leaves, &leaf->link);
+ LIST_REMOVE(trie, leaf);
free(leaf);
}
diff --git a/src/trie.h b/src/trie.h
index 6e1e875..58974aa 100644
--- a/src/trie.h
+++ b/src/trie.h
@@ -5,7 +5,6 @@
#define BFS_TRIE_H
#include "config.h"
-#include "list.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
@@ -15,7 +14,7 @@
*/
struct trie_leaf {
/** Linked list of leaves, in insertion order. */
- struct link link;
+ struct trie_leaf *prev, *next;
/** An arbitrary value associated with this leaf. */
void *value;
/** The length of the key in bytes. */
@@ -31,7 +30,7 @@ struct trie {
/** Pointer to the root node/leaf. */
uintptr_t root;
/** Linked list of leaves. */
- struct list leaves;
+ struct trie_leaf *head, *tail;
};
/**
@@ -134,6 +133,8 @@ void trie_destroy(struct trie *trie);
* Iterate over the leaves of a trie.
*/
#define TRIE_FOR_EACH(trie, leaf) \
- LIST_FOR_EACH(&(trie)->leaves, struct trie_leaf, leaf)
+ for (struct trie_leaf *leaf = (trie)->head, *_next; \
+ leaf && (_next = leaf->next, true); \
+ leaf = _next)
#endif // BFS_TRIE_H
diff --git a/src/xspawn.c b/src/xspawn.c
index e6ce0de..a185200 100644
--- a/src/xspawn.c
+++ b/src/xspawn.c
@@ -33,7 +33,7 @@ enum bfs_spawn_op {
* A spawn action.
*/
struct bfs_spawn_action {
- struct slink link;
+ struct bfs_spawn_action *next;
enum bfs_spawn_op op;
int in_fd;
@@ -44,12 +44,14 @@ struct bfs_spawn_action {
int bfs_spawn_init(struct bfs_spawn *ctx) {
ctx->flags = 0;
- slist_init(&ctx->actions);
+ SLIST_INIT(ctx);
return 0;
}
int bfs_spawn_destroy(struct bfs_spawn *ctx) {
- LIST_DRAIN(&ctx->actions, struct bfs_spawn_action, action) {
+ while (ctx->head) {
+ struct bfs_spawn_action *action = ctx->head;
+ SLIST_POP(ctx);
free(action);
}
@@ -68,12 +70,12 @@ static struct bfs_spawn_action *bfs_spawn_add(struct bfs_spawn *ctx, enum bfs_sp
return NULL;
}
- slink_init(&action->link);
+ action->next = NULL;
action->op = op;
action->in_fd = -1;
action->out_fd = -1;
- slist_append(&ctx->actions, &action->link);
+ SLIST_APPEND(ctx, action);
return action;
}
@@ -138,8 +140,7 @@ int bfs_spawn_addsetrlimit(struct bfs_spawn *ctx, int resource, const struct rli
static void bfs_spawn_exec(const char *exe, const struct bfs_spawn *ctx, char **argv, char **envp, int pipefd[2]) {
xclose(pipefd[0]);
- const struct slink *head = ctx ? ctx->actions.head : NULL;
- LIST_FOR_EACH_FROM(head, struct bfs_spawn_action, action) {
+ for (const struct bfs_spawn_action *action = ctx ? ctx->head : NULL; action; action = action->next) {
// Move the error-reporting pipe out of the way if necessary...
if (action->out_fd == pipefd[1]) {
int fd = dup_cloexec(pipefd[1]);
diff --git a/src/xspawn.h b/src/xspawn.h
index 7e673f1..d9b4a2e 100644
--- a/src/xspawn.h
+++ b/src/xspawn.h
@@ -8,7 +8,6 @@
#ifndef BFS_XSPAWN_H
#define BFS_XSPAWN_H
-#include "list.h"
#include <sys/resource.h>
#include <sys/types.h>
@@ -25,7 +24,8 @@ enum bfs_spawn_flags {
*/
struct bfs_spawn {
enum bfs_spawn_flags flags;
- struct slist actions;
+ struct bfs_spawn_action *head;
+ struct bfs_spawn_action **tail;
};
/**