list: Use macros instead of type-erased lists

10 files changed, 403 insertions, 399 deletions

diff --git a/Makefile b/Makefile
index 428a0f7..b509065 100644
--- a/Makefile
+++ b/Makefile
@@ -223,7 +223,6 @@ LIBBFS := \
     $(OBJ)/src/eval.o \
     $(OBJ)/src/exec.o \
     $(OBJ)/src/fsade.o \
-    $(OBJ)/src/list.o \
     $(OBJ)/src/mtab.o \
     $(OBJ)/src/opt.o \
     $(OBJ)/src/parse.o \
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;
 };
 
 /**
diff --git a/tests/trie.c b/tests/trie.c
index 65660a9..c2af18a 100644
--- a/tests/trie.c
+++ b/tests/trie.c
@@ -74,6 +74,8 @@ int main(void) {
 		size_t i = 0;
 		TRIE_FOR_EACH(&trie, leaf) {
 			assert(leaf == trie_find_str(&trie, keys[i]));
+			assert(!leaf->prev || leaf->prev->next == leaf);
+			assert(!leaf->next || leaf->next->prev == leaf);
 			++i;
 		}
 		assert(i == nkeys);