From 135b98c26456adbfbc72fb12e4753ee0716b1f92 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 28 Mar 2023 14:18:08 -0400
Subject: list: New generic linked list API

---
 src/list.h | 170 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 170 insertions(+)
 create mode 100644 src/list.h

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
new file mode 100644
index 0000000..1985413
--- /dev/null
+++ b/src/list.h
@@ -0,0 +1,170 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+/**
+ * Intrusive linked lists.
+ */
+
+#ifndef BFS_LIST_H
+#define BFS_LIST_H
+
+#include "config.h"
+#include <stdbool.h>
+
+/**
+ * A singly-linked list entry.
+ */
+struct slink {
+	struct slink *next;
+};
+
+/** Initialize a list entry. */
+void slink_init(struct slink *link);
+
+/**
+ * A singly-linked list.
+ */
+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);
+
+/**
+ * Comparison function type for slist_sort().
+ *
+ * @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.
+ */
+typedef bool slist_cmp_fn(struct slink *left, struct slink *right, const void *ptr);
+
+/** Sort a list. */
+void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr);
+
+/**
+ * A doubly-linked list entry.
+ */
+struct link {
+	struct link *prev;
+	struct link *next;
+};
+
+/** Initialize a list entry. */
+void link_init(struct link *link);
+
+/**
+ * A doubly-linked list.
+ */
+struct list {
+	struct link *head;
+	struct link *tail;
+};
+
+/** Initialize an empty list. */
+void list_init(struct list *list);
+
+/** Check if a list is empty. */
+bool list_is_empty(const struct list *list);
+
+/** Add an entry at the tail of the list. */
+void list_append(struct list *list, struct link *link);
+
+/** Add an entry at the head of the list. */
+void list_prepend(struct list *list, struct link *link);
+
+/** Insert an entry after the target entry. */
+void list_insert_after(struct list *list, struct link *target, struct link *link);
+
+/** Remove an entry from a list. */
+void list_remove(struct list *list, struct link *link);
+
+/** Remove the head of the list. */
+struct link *list_pop(struct list *list);
+
+/** Check if a link is attached to a list. */
+bool list_attached(const struct list *list, const struct link *link);
+
+// Helper for LIST_FOR_EACH_*()
+#define LIST_FOR_EACH_IMPL(entry, type, i, member, ...) \
+	for (type *_next, *i = BFS_CONTAINER_OF(entry, type, member); \
+	     i && (_next = BFS_CONTAINER_OF(i->member.next, type, member), true); \
+	     i = _next)
+
+/**
+ * Iterate over a list from the given entry.
+ *
+ * @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).
+ */
+#define LIST_FOR_EACH_FROM(...) \
+	LIST_FOR_EACH_IMPL(__VA_ARGS__, link,)
+
+/**
+ * Iterate over a 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).
+ */
+#define LIST_FOR_EACH(list, ...) \
+	LIST_FOR_EACH_FROM((list)->head, __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))
+
+// Helper for LIST_DRAIN()
+#define LIST_DRAIN_IMPL(list, type, i, member, ...) \
+	for (type *i; (i = BFS_CONTAINER_OF(LIST_POP(list), type, member));)
+
+/**
+ * Drain the entries from a 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,)
+
+#endif // BFS_LIST_H
-- 
cgit v1.2.3


From f75f3de63888702f29f48bcf2691291403720b9d Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 29 Mar 2023 13:25:18 -0400
Subject: list: New helper macros for converting entries to items

---
 src/bftw.c | 18 +++++-------------
 src/list.h | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 65 insertions(+), 16 deletions(-)

(limited to 'src/list.h')

diff --git a/src/bftw.c b/src/bftw.c
index 9ff526d..aa36b87 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -69,14 +69,8 @@ struct bftw_file {
 };
 
 /** Move from a list entry to a bftw_file. */
-static struct bftw_file *bftw_file_entry(struct slink *link) {
-	return BFS_CONTAINER_OF(link, struct bftw_file, link);
-}
-
-/** Move from an LRU entry to a bftw_file. */
-static struct bftw_file *bftw_lru_file(struct link *link) {
-	return BFS_CONTAINER_OF(link, struct bftw_file, lru);
-}
+#define BFTW_FILE(...) \
+	LIST_ITEM(struct bftw_file, __VA_ARGS__)
 
 /**
  * A cache of open directories.
@@ -126,7 +120,7 @@ static int bftw_cache_pop(struct bftw_cache *cache) {
 		return -1;
 	}
 
-	struct bftw_file *file = bftw_lru_file(cache->list.tail);
+	struct bftw_file *file = BFTW_FILE(cache->list.tail, lru);
 	bftw_file_close(cache, file);
 	return 0;
 }
@@ -810,7 +804,7 @@ static int bftw_pop(struct bftw_state *state) {
 		return 0;
 	}
 
-	state->file = bftw_file_entry(slist_pop(&state->queue));
+	state->file = BFTW_FILE(slist_pop(&state->queue));
 
 	if (bftw_build_path(state) != 0) {
 		return -1;
@@ -974,9 +968,7 @@ static int bftw_state_destroy(struct bftw_state *state) {
 
 /** Comparison function for BFTW_SORT. */
 static bool bftw_file_cmp(struct slink *left, struct slink *right, const void *ptr) {
-	struct bftw_file *lfile = bftw_file_entry(left);
-	struct bftw_file *rfile = bftw_file_entry(right);
-	return strcoll(lfile->name, rfile->name) <= 0;
+	return strcoll(BFTW_FILE(left)->name, BFTW_FILE(right)->name) <= 0;
 }
 
 /** Finish adding a batch of files. */
diff --git a/src/list.h b/src/list.h
index 1985413..b47bed7 100644
--- a/src/list.h
+++ b/src/list.h
@@ -107,10 +107,67 @@ struct link *list_pop(struct list *list);
 /** Check if a link is attached to a list. */
 bool list_attached(const struct list *list, const struct link *link);
 
+// LIST_ITEM() helper
+#define LIST_ITEM_IMPL(type, entry, member, ...) \
+	BFS_CONTAINER_OF(entry, type, member)
+
+/**
+ * Convert a list entry to its container.
+ *
+ * @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.
+ */
+#define LIST_ITEM(...) \
+	LIST_ITEM_IMPL(__VA_ARGS__, link,)
+
+// LIST_NEXT() helper
+#define LIST_NEXT_IMPL(type, entry, member, ...) \
+	LIST_ITEM(type, (entry)->member.next, member)
+
+/**
+ * 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.
+ */
+#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)
+
+/**
+ * Get the previous entry 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 previous item in the list.
+ */
+#define LIST_PREV(...) \
+	LIST_PREV_IMPL(__VA_ARGS__, link,)
+
 // Helper for LIST_FOR_EACH_*()
 #define LIST_FOR_EACH_IMPL(entry, type, i, member, ...) \
-	for (type *_next, *i = BFS_CONTAINER_OF(entry, type, member); \
-	     i && (_next = BFS_CONTAINER_OF(i->member.next, type, member), true); \
+	for (type *_next, *i = LIST_ITEM(type, entry, member);	\
+	     i && (_next = LIST_NEXT(type, i, member), true); \
 	     i = _next)
 
 /**
@@ -150,7 +207,7 @@ bool list_attached(const struct list *list, const struct link *link);
 
 // Helper for LIST_DRAIN()
 #define LIST_DRAIN_IMPL(list, type, i, member, ...) \
-	for (type *i; (i = BFS_CONTAINER_OF(LIST_POP(list), type, member));)
+	for (type *i; (i = LIST_ITEM(type, LIST_POP(list), member));)
 
 /**
  * Drain the entries from a list.
-- 
cgit v1.2.3


From 86f4b4f7180bca73a734249e67dada708f8275ff Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Fri, 31 Mar 2023 16:19:45 -0400
Subject: list: Use macros instead of type-erased lists

---
 Makefile     |   1 -
 src/bftw.c   | 136 ++++++++++++------
 src/config.h |  11 --
 src/list.c   | 169 ----------------------
 src/list.h   | 447 ++++++++++++++++++++++++++++++++++++++---------------------
 src/trie.c   |   8 +-
 src/trie.h   |   9 +-
 src/xspawn.c |  15 +-
 src/xspawn.h |   4 +-
 tests/trie.c |   2 +
 10 files changed, 403 insertions(+), 399 deletions(-)
 delete mode 100644 src/list.c

(limited to 'src/list.h')

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);
-- 
cgit v1.2.3


From 536c7e7af3777bc8b8d7f919402aaff51b7cda9d Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 1 Apr 2023 14:25:00 -0400
Subject: list: Simplify some macros

---
 src/list.h | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index c43be68..39510e0 100644
--- a/src/list.h
+++ b/src/list.h
@@ -96,8 +96,8 @@
 	LIST_BLOCK_(SLIST_INIT_((list)))
 
 #define SLIST_INIT_(list) \
-	(list)->head = NULL; \
-	(list)->tail = &(list)->head;
+	list->head = NULL; \
+	list->tail = &list->head;
 
 /**
  * Wraps a group of statements in a block.
@@ -160,22 +160,22 @@
 /**
  * LIST_LINK_() dispatches to yet another macro:
  *
- *     LIST_LINK_(next, )       => LIST_LINK__(next,     , , . ,   , )
- *     LIST_LINK_(next, link, ) => LIST_LINK__(next, link, ,   , . , , )
+ *     LIST_LINK_(next, )       => LIST_LINK__(next,     , . ,   , )
+ *     LIST_LINK_(next, link, ) => LIST_LINK__(next, link,   , . , , )
  */
-#define LIST_LINK_(dir, ...) LIST_LINK__(dir, __VA_ARGS__, , . , , )
+#define LIST_LINK_(dir, ...) LIST_LINK__(dir, __VA_ARGS__, . , , )
 
 /**
  * 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
+ *                 dir   link ignored dot
+ *                  v     v      v     v
+ *     LIST_LINK__(next,     ,   .   ,   , )   => next
+ *     LIST_LINK__(next, link,       , . , , ) => link . next
+ *                  ^     ^      ^     ^
+ *                 dir   link ignored dot
  */
-#define LIST_LINK__(dir, link, blank, ignored, dot, ...) link dot dir
+#define LIST_LINK__(dir, link, ignored, dot, ...) link dot dir
 
 /**
  * SLIST_APPEND_() uses LIST_NEXT_() to generate the right name for the list
-- 
cgit v1.2.3


From 10e8327badb15bd8dd229a7a25bdcd28c5629e1c Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 1 Apr 2023 14:25:06 -0400
Subject: list: Implement SLIST_REMOVE()

---
 src/list.h | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 39510e0..95917e7 100644
--- a/src/list.h
+++ b/src/list.h
@@ -229,6 +229,27 @@
 		SLIST_INIT(src); \
 	}
 
+/**
+ * Remove an item from a singly-linked list.
+ *
+ * @param list
+ *         The list to remove from.
+ * @param ptr
+ *         A pointer to the item to remove, either &list->head or &prev->next.
+ * @param link (optional)
+ *         If specified, use item->link.next rather than item->next.
+ */
+#define SLIST_REMOVE(list, ...) SLIST_REMOVE_(__VA_ARGS__, )
+
+#define SLIST_REMOVE_(list, ptr, ...) \
+	LIST_BLOCK_(SLIST_REMOVE__((list), (ptr), LIST_NEXT_(__VA_ARGS__)))
+
+#define SLIST_REMOVE__(list, ptr, next) \
+	void *_next = (void *)(*ptr)->next; \
+	(*ptr)->next = NULL; \
+	*ptr = _next; \
+	list->tail = list->head ? list->tail : &list->head;
+
 /**
  * Pop the head off a singly-linked list.
  *
@@ -239,14 +260,9 @@
  */
 #define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, )
 
-#define SLIST_POP_(list, ...) \
-	LIST_BLOCK_(SLIST_POP__((list), LIST_NEXT_(__VA_ARGS__)))
+#define SLIST_POP_(list, ...) SLIST_POP__((list), LIST_NEXT_(__VA_ARGS__))
 
-#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;
+#define SLIST_POP__(list, next) SLIST_REMOVE__(list, (&list->head), next)
 
 /**
  * Initialize a doubly-linked list.
-- 
cgit v1.2.3


From ecbc4a7572cb67802b1cb99d8914c19f1fb4f2c4 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 1 Apr 2023 14:45:15 -0400
Subject: list: Fix a typo in SLIST_REMOVE()

---
 src/list.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 95917e7..08f97ab 100644
--- a/src/list.h
+++ b/src/list.h
@@ -239,7 +239,7 @@
  * @param link (optional)
  *         If specified, use item->link.next rather than item->next.
  */
-#define SLIST_REMOVE(list, ...) SLIST_REMOVE_(__VA_ARGS__, )
+#define SLIST_REMOVE(list, ...) SLIST_REMOVE_(list, __VA_ARGS__, )
 
 #define SLIST_REMOVE_(list, ptr, ...) \
 	LIST_BLOCK_(SLIST_REMOVE__((list), (ptr), LIST_NEXT_(__VA_ARGS__)))
-- 
cgit v1.2.3


From c4a4d397ccc124f50b851cfa52b9937ba7485b2b Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 1 Apr 2023 18:09:48 -0400
Subject: list: Fix SLIST_REMOVE() on the tail

---
 src/list.h | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 08f97ab..a674aaf 100644
--- a/src/list.h
+++ b/src/list.h
@@ -234,21 +234,21 @@
  *
  * @param list
  *         The list to remove from.
- * @param ptr
+ * @param cursor
  *         A pointer to the item to remove, either &list->head or &prev->next.
  * @param link (optional)
  *         If specified, use item->link.next rather than item->next.
  */
 #define SLIST_REMOVE(list, ...) SLIST_REMOVE_(list, __VA_ARGS__, )
 
-#define SLIST_REMOVE_(list, ptr, ...) \
-	LIST_BLOCK_(SLIST_REMOVE__((list), (ptr), LIST_NEXT_(__VA_ARGS__)))
+#define SLIST_REMOVE_(list, cursor, ...) \
+	LIST_BLOCK_(SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__)))
 
-#define SLIST_REMOVE__(list, ptr, next) \
-	void *_next = (void *)(*ptr)->next; \
-	(*ptr)->next = NULL; \
-	*ptr = _next; \
-	list->tail = list->head ? list->tail : &list->head;
+#define SLIST_REMOVE__(list, cursor, next) \
+	void *_next = (void *)(*cursor)->next; \
+	(*cursor)->next = NULL; \
+	*cursor = _next; \
+	list->tail = _next ? list->tail : cursor;
 
 /**
  * Pop the head off a singly-linked list.
-- 
cgit v1.2.3


From 17f2d430b4927c5862afdd038a629c71fae8771d Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 12 Apr 2023 10:03:46 -0400
Subject: list: s/link/node/

---
 src/list.h | 80 +++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 40 insertions(+), 40 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index a674aaf..55242a3 100644
--- a/src/list.h
+++ b/src/list.h
@@ -111,8 +111,8 @@
  *         The list to modify.
  * @param item
  *         The item to append.
- * @param link (optional)
- *         If specified, use item->link.next rather than item->next.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
  *
  * ---
  *
@@ -123,9 +123,9 @@
  *             list->tail = &item->next;
  *     }
  *
- *     SLIST_APPEND(list, item, link) => {
+ *     SLIST_APPEND(list, item, node) => {
  *             *list->tail = item;
- *             list->tail = &item->link.next;
+ *             list->tail = &item->node.next;
  *     }
  *
  * The first trick is that
@@ -136,13 +136,13 @@
  * 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, )
+ *     SLIST_APPEND(list, item, node) => SLIST_APPEND_(list, item, node, )
  */
 #define SLIST_APPEND(list, ...) SLIST_APPEND_(list, __VA_ARGS__, )
 
 /**
- * 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
+ * Now we need a way to generate either ->next or ->node.next depending on
+ * whether the node parameter was passed.  The approach is based on
  *
  *     #define FOO(...) BAR(__VA_ARGS__, 1, 2, )
  *     #define BAR(x, y, z, ...) z
@@ -152,37 +152,37 @@
  *
  * The LIST_NEXT_() macro uses this technique:
  *
- *     LIST_NEXT_()       => LIST_LINK_(next, )
- *     LIST_NEXT_(link, ) => LIST_LINK_(next, link, )
+ *     LIST_NEXT_()       => LIST_NODE_(next, )
+ *     LIST_NEXT_(node, ) => LIST_NODE_(next, node, )
  */
-#define LIST_NEXT_(...) LIST_LINK_(next, __VA_ARGS__)
+#define LIST_NEXT_(...) LIST_NODE_(next, __VA_ARGS__)
 
 /**
- * LIST_LINK_() dispatches to yet another macro:
+ * LIST_NODE_() dispatches to yet another macro:
  *
- *     LIST_LINK_(next, )       => LIST_LINK__(next,     , . ,   , )
- *     LIST_LINK_(next, link, ) => LIST_LINK__(next, link,   , . , , )
+ *     LIST_NODE_(next, )       => LIST_NODE__(next,     , . ,   , )
+ *     LIST_NODE_(next, node, ) => LIST_NODE__(next, node,   , . , , )
  */
-#define LIST_LINK_(dir, ...) LIST_LINK__(dir, __VA_ARGS__, . , , )
+#define LIST_NODE_(dir, ...) LIST_NODE__(dir, __VA_ARGS__, . , , )
 
 /**
- * And finally, LIST_LINK__() adds the link and the dot if necessary.
+ * And finally, LIST_NODE__() adds the node and the dot if necessary.
  *
- *                 dir   link ignored dot
+ *                 dir   node ignored dot
  *                  v     v      v     v
- *     LIST_LINK__(next,     ,   .   ,   , )   => next
- *     LIST_LINK__(next, link,       , . , , ) => link . next
+ *     LIST_NODE__(next,     ,   .   ,   , )   => next
+ *     LIST_NODE__(next, node,       , . , , ) => node . next
  *                  ^     ^      ^     ^
- *                 dir   link ignored dot
+ *                 dir   node ignored dot
  */
-#define LIST_LINK__(dir, link, ignored, dot, ...) link dot dir
+#define LIST_NODE__(dir, node, ignored, dot, ...) node dot dir
 
 /**
  * SLIST_APPEND_() uses LIST_NEXT_() to generate the right name for the list
- * link, and finally delegates to the actual implementation.
+ * node, 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)
+ *     SLIST_APPEND_(list, item, node, ) => SLIST_APPEND__((list), (item), node.next)
  */
 #define SLIST_APPEND_(list, item, ...) \
 	LIST_BLOCK_(SLIST_APPEND__((list), (item), LIST_NEXT_(__VA_ARGS__)))
@@ -198,8 +198,8 @@
  *         The list to modify.
  * @param item
  *         The item to prepend.
- * @param link (optional)
- *         If specified, use item->link.next rather than item->next.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
  */
 #define SLIST_PREPEND(list, ...) SLIST_PREPEND_(list, __VA_ARGS__, )
 
@@ -236,8 +236,8 @@
  *         The list to remove from.
  * @param cursor
  *         A pointer to the item to remove, either &list->head or &prev->next.
- * @param link (optional)
- *         If specified, use item->link.next rather than item->next.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
  */
 #define SLIST_REMOVE(list, ...) SLIST_REMOVE_(list, __VA_ARGS__, )
 
@@ -255,8 +255,8 @@
  *
  * @param list
  *         The list to pop from.
- * @param link (optional)
- *         If specified, use head->link.next rather than head->next.
+ * @param node (optional)
+ *         If specified, use head->node.next rather than head->next.
  */
 #define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, )
 
@@ -278,9 +278,9 @@
 
 /**
  * LIST_PREV_()       => prev
- * LIST_PREV_(link, ) => link.prev
+ * LIST_PREV_(node, ) => node.prev
  */
-#define LIST_PREV_(...) LIST_LINK_(prev, __VA_ARGS__)
+#define LIST_PREV_(...) LIST_NODE_(prev, __VA_ARGS__)
 
 /**
  * Add an item to the tail of a doubly-linked list.
@@ -289,8 +289,8 @@
  *         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}.
+ * @param node (optional)
+ *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
 #define LIST_APPEND(list, ...) LIST_INSERT(list, (list)->tail, __VA_ARGS__)
 
@@ -301,8 +301,8 @@
  *         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}.
+ * @param node (optional)
+ *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
 #define LIST_PREPEND(list, ...) LIST_INSERT(list, NULL, __VA_ARGS__)
 
@@ -315,8 +315,8 @@
  *         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}.
+ * @param node (optional)
+ *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
 #define LIST_INSERT(list, cursor, ...) LIST_INSERT_(list, cursor, __VA_ARGS__, )
 
@@ -336,8 +336,8 @@
  *         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}.
+ * @param node (optional)
+ *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
 #define LIST_REMOVE(list, ...) LIST_REMOVE_(list, __VA_ARGS__, )
 
@@ -356,8 +356,8 @@
  *         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}.
+ * @param node (optional)
+ *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  * @return
  *         Whether the item is attached to the list.
  */
-- 
cgit v1.2.3


From a812c5c8c9aabf6e0fd934bd55ec553c6dbb60c2 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 12 Apr 2023 10:32:06 -0400
Subject: list: New SLIST_INSERT() macro

---
 src/list.h | 71 ++++++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 41 insertions(+), 30 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 55242a3..87e2bf2 100644
--- a/src/list.h
+++ b/src/list.h
@@ -105,12 +105,14 @@
 #define LIST_BLOCK_(block) do { block } while (0)
 
 /**
- * Add an item to the tail of a singly-linked list.
+ * Insert an item into a singly-linked list.
  *
  * @param list
- *         The list to modify.
+ *         The list to remove from.
+ * @param cursor
+ *         A pointer to the item to insert after, e.g. &list->head or list->tail.
  * @param item
- *         The item to append.
+ *         The item to insert.
  * @param node (optional)
  *         If specified, use item->node.next rather than item->next.
  *
@@ -118,27 +120,29 @@
  *
  * We play some tricks with variadic macros to handle the optional parameter:
  *
- *     SLIST_APPEND(list, item) => {
- *             *list->tail = item;
- *             list->tail = &item->next;
+ *     SLIST_INSERT(list, cursor, item) => {
+ *             item->next = *cursor;
+ *             *cursor = item;
+ *             list->tail = item->next ? list->tail : &item->next;
  *     }
  *
- *     SLIST_APPEND(list, item, node) => {
- *             *list->tail = item;
- *             list->tail = &item->node.next;
+ *     SLIST_INSERT(list, cursor, item, node) => {
+ *             item->node.next = *cursor;
+ *             *cursor = item;
+ *             list->tail = item->node.next ? list->tail : &item->node.next;
  *     }
  *
  * The first trick is that
  *
- *     #define SLIST_APPEND(list, item, ...)
+ *     #define SLIST_INSERT(list, item, cursor, ...)
  *
  * 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, node) => SLIST_APPEND_(list, item, node, )
+ *     SLIST_INSERT(list, cursor, item)       => SLIST_INSERT_(list, cursor, item, )
+ *     SLIST_INSERT(list, cursor, item, node) => SLIST_INSERT_(list, cursor, item, node, )
  */
-#define SLIST_APPEND(list, ...) SLIST_APPEND_(list, __VA_ARGS__, )
+#define SLIST_INSERT(list, cursor, ...) SLIST_INSERT_(list, cursor, __VA_ARGS__, )
 
 /**
  * Now we need a way to generate either ->next or ->node.next depending on
@@ -178,18 +182,31 @@
 #define LIST_NODE__(dir, node, ignored, dot, ...) node dot dir
 
 /**
- * SLIST_APPEND_() uses LIST_NEXT_() to generate the right name for the list
+ * SLIST_INSERT_() uses LIST_NEXT_() to generate the right name for the list
  * node, and finally delegates to the actual implementation.
+ */
+#define SLIST_INSERT_(list, cursor, item, ...) \
+	LIST_BLOCK_(SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__)))
+
+#define SLIST_INSERT__(list, cursor, item, next) \
+	item->next = *cursor; \
+	*cursor = item; \
+	list->tail = item->next ? list->tail : &item->next;
+
+/**
+ * Add an item to the tail of a singly-linked list.
  *
- *     SLIST_APPEND_(list, item, )       => SLIST_APPEND__((list), (item), next)
- *     SLIST_APPEND_(list, item, node, ) => SLIST_APPEND__((list), (item), node.next)
+ * @param list
+ *         The list to modify.
+ * @param item
+ *         The item to append.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
  */
-#define SLIST_APPEND_(list, item, ...) \
-	LIST_BLOCK_(SLIST_APPEND__((list), (item), LIST_NEXT_(__VA_ARGS__)))
+#define SLIST_APPEND(list, ...) SLIST_APPEND_(list, __VA_ARGS__, )
 
-#define SLIST_APPEND__(list, item, next) \
-	*list->tail = item; \
-	list->tail = &item->next;
+#define SLIST_APPEND_(list, item, ...) \
+	SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__)
 
 /**
  * Add an item to the head of a singly-linked list.
@@ -204,12 +221,7 @@
 #define SLIST_PREPEND(list, ...) SLIST_PREPEND_(list, __VA_ARGS__, )
 
 #define SLIST_PREPEND_(list, item, ...) \
-	LIST_BLOCK_(SLIST_PREPEND__((list), (item), LIST_NEXT_(__VA_ARGS__)))
-
-#define SLIST_PREPEND__(list, item, next) \
-	list->tail = list->head ? list->tail : &item->next; \
-	item->next = list->head; \
-	list->head = item;
+	SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__)
 
 /**
  * Add an entire singly-linked list to the tail of another.
@@ -260,9 +272,8 @@
  */
 #define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, )
 
-#define SLIST_POP_(list, ...) SLIST_POP__((list), LIST_NEXT_(__VA_ARGS__))
-
-#define SLIST_POP__(list, next) SLIST_REMOVE__(list, (&list->head), next)
+#define SLIST_POP_(list, ...) \
+	SLIST_REMOVE_(list, &(list)->head, __VA_ARGS__)
 
 /**
  * Initialize a doubly-linked list.
-- 
cgit v1.2.3


From bc952b51f48905392cec5685853fbb44565057a8 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 20 May 2023 14:37:56 -0400
Subject: list: Return the removed item from SLIST_POP()

---
 src/bftw.c   |  6 ++----
 src/list.h   | 21 ++++++++++++++++-----
 src/xspawn.c |  4 +---
 3 files changed, 19 insertions(+), 12 deletions(-)

(limited to 'src/list.h')

diff --git a/src/bftw.c b/src/bftw.c
index 6ec5cfa..966f03d 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -780,8 +780,7 @@ static bool bftw_pop_dir(struct bftw_state *state) {
 		return false;
 	}
 
-	state->file = state->dirs.head;
-	SLIST_POP(&state->dirs);
+	state->file = SLIST_POP(&state->dirs);
 	return true;
 }
 
@@ -952,8 +951,7 @@ static void bftw_list_sort(struct bftw_list *list) {
 
 	// Split
 	for (struct bftw_file *hare = list->head; hare && (hare = hare->next); hare = hare->next) {
-		struct bftw_file *tortoise = list->head;
-		SLIST_POP(list);
+		struct bftw_file *tortoise = SLIST_POP(list);
 		SLIST_APPEND(&left, tortoise);
 	}
 	SLIST_EXTEND(&right, list);
diff --git a/src/list.h b/src/list.h
index 87e2bf2..89f00ed 100644
--- a/src/list.h
+++ b/src/list.h
@@ -79,6 +79,7 @@
 #define BFS_LIST_H
 
 #include <stddef.h>
+#include <string.h>
 
 /**
  * Initialize a singly-linked list.
@@ -250,17 +251,27 @@
  *         A pointer to the item to remove, either &list->head or &prev->next.
  * @param node (optional)
  *         If specified, use item->node.next rather than item->next.
+ * @return
+ *         The removed item.
  */
 #define SLIST_REMOVE(list, ...) SLIST_REMOVE_(list, __VA_ARGS__, )
 
 #define SLIST_REMOVE_(list, cursor, ...) \
-	LIST_BLOCK_(SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__)))
+	SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__))
 
 #define SLIST_REMOVE__(list, cursor, next) \
-	void *_next = (void *)(*cursor)->next; \
-	(*cursor)->next = NULL; \
-	*cursor = _next; \
-	list->tail = _next ? list->tail : cursor;
+	(list->tail = (*cursor)->next ? list->tail : cursor, \
+	 slist_remove_impl(*cursor, cursor, &(*cursor)->next, list->tail, sizeof(*cursor)))
+
+// Helper for SLIST_REMOVE()
+static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void *tail, size_t size) {
+	// ret = *cursor;
+	// *cursor = ret->next;
+	memcpy(cursor, next, size);
+	// ret->next = *list->tail; (NULL)
+	memcpy(next, tail, size);
+	return ret;
+}
 
 /**
  * Pop the head off a singly-linked list.
diff --git a/src/xspawn.c b/src/xspawn.c
index 00fb76e..740e38e 100644
--- a/src/xspawn.c
+++ b/src/xspawn.c
@@ -49,9 +49,7 @@ int bfs_spawn_init(struct bfs_spawn *ctx) {
 
 int bfs_spawn_destroy(struct bfs_spawn *ctx) {
 	while (ctx->head) {
-		struct bfs_spawn_action *action = ctx->head;
-		SLIST_POP(ctx);
-		free(action);
+		free(SLIST_POP(ctx));
 	}
 
 	return 0;
-- 
cgit v1.2.3


From eef75524aec3910097cb6923c30b898ad98179fe Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 24 May 2023 11:54:33 -0400
Subject: list: Allow popping from an empty list

---
 src/bftw.c | 19 +++----------------
 src/list.h |  4 +++-
 2 files changed, 6 insertions(+), 17 deletions(-)

(limited to 'src/list.h')

diff --git a/src/bftw.c b/src/bftw.c
index 966f03d..916a56b 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -299,11 +299,10 @@ static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, cons
 		SLIST_PREPEND(&parents, cur);
 	}
 
-	while ((cur = parents.head)) {
+	while ((cur = SLIST_POP(&parents))) {
 		if (!cur->parent || cur->parent->fd >= 0) {
 			bftw_file_openat(cache, cur, cur->parent, cur->name);
 		}
-		SLIST_POP(&parents);
 	}
 
 	return file->fd;
@@ -772,29 +771,17 @@ static enum bftw_action bftw_call_back(struct bftw_state *state, const char *nam
 static bool bftw_pop_dir(struct bftw_state *state) {
 	bfs_assert(!state->file);
 
-	if (!state->dirs.head) {
-		return false;
-	}
-
 	if (state->files.head && state->strategy == BFTW_BFS) {
 		return false;
 	}
 
-	state->file = SLIST_POP(&state->dirs);
-	return true;
+	return (state->file = SLIST_POP(&state->dirs));
 }
 
 /** Pop a file to visit from the queue. */
 static bool bftw_pop_file(struct bftw_state *state) {
 	bfs_assert(!state->file);
-
-	state->file = state->files.head;
-	if (state->file) {
-		SLIST_POP(&state->files);
-		return true;
-	} else {
-		return false;
-	}
+	return (state->file = SLIST_POP(&state->files));
 }
 
 /**
diff --git a/src/list.h b/src/list.h
index 89f00ed..a284c25 100644
--- a/src/list.h
+++ b/src/list.h
@@ -280,11 +280,13 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  *         The list to pop from.
  * @param node (optional)
  *         If specified, use head->node.next rather than head->next.
+ * @return
+ *         The popped item, or NULL if the list was empty.
  */
 #define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, )
 
 #define SLIST_POP_(list, ...) \
-	SLIST_REMOVE_(list, &(list)->head, __VA_ARGS__)
+	((list)->head ? SLIST_REMOVE_(list, &(list)->head, __VA_ARGS__) : NULL)
 
 /**
  * Initialize a doubly-linked list.
-- 
cgit v1.2.3


From 4a6e24764b4248a1a97a338138fa71c2c8c4d1d0 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 4 Jul 2023 13:30:10 -0400
Subject: list: Fix some parameter docs

---
 src/list.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index a284c25..3b53fab 100644
--- a/src/list.h
+++ b/src/list.h
@@ -109,7 +109,7 @@
  * Insert an item into a singly-linked list.
  *
  * @param list
- *         The list to remove from.
+ *         The list to modify.
  * @param cursor
  *         A pointer to the item to insert after, e.g. &list->head or list->tail.
  * @param item
@@ -246,7 +246,7 @@
  * Remove an item from a singly-linked list.
  *
  * @param list
- *         The list to remove from.
+ *         The list to modify.
  * @param cursor
  *         A pointer to the item to remove, either &list->head or &prev->next.
  * @param node (optional)
@@ -277,7 +277,7 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * Pop the head off a singly-linked list.
  *
  * @param list
- *         The list to pop from.
+ *         The list to modify.
  * @param node (optional)
  *         If specified, use head->node.next rather than head->next.
  * @return
@@ -334,7 +334,7 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * Insert into a doubly-linked list after the given cursor.
  *
  * @param list
- *         The list to initialize.
+ *         The list to modify.
  * @param cursor
  *         Insert after this element.
  * @param item
-- 
cgit v1.2.3


From 1f663544495ed520bfd98345a86c92fa53efb747 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 25 Sep 2023 13:03:51 -0400
Subject: list: Use (void)(...) rather than do { ... } while (0)

This makes everything usable in expression contexts.
---
 src/list.h | 61 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 30 insertions(+), 31 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 3b53fab..0aebd4c 100644
--- a/src/list.h
+++ b/src/list.h
@@ -94,16 +94,19 @@
  * don't have to.
  */
 #define SLIST_INIT(list) \
-	LIST_BLOCK_(SLIST_INIT_((list)))
+	SLIST_INIT_((list))
 
-#define SLIST_INIT_(list) \
-	list->head = NULL; \
-	list->tail = &list->head;
+/**
+ * Helper for SLIST_INIT().
+ */
+#define SLIST_INIT_(list) LIST_VOID_( \
+	list->head = NULL, \
+	list->tail = &list->head)
 
 /**
- * Wraps a group of statements in a block.
+ * Cast a list of expressions to void.
  */
-#define LIST_BLOCK_(block) do { block } while (0)
+#define LIST_VOID_(...) ((void)(__VA_ARGS__))
 
 /**
  * Insert an item into a singly-linked list.
@@ -187,12 +190,12 @@
  * node, and finally delegates to the actual implementation.
  */
 #define SLIST_INSERT_(list, cursor, item, ...) \
-	LIST_BLOCK_(SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__)))
+	SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__))
 
-#define SLIST_INSERT__(list, cursor, item, next) \
-	item->next = *cursor; \
-	*cursor = item; \
-	list->tail = item->next ? list->tail : &item->next;
+#define SLIST_INSERT__(list, cursor, item, next) LIST_VOID_( \
+	item->next = *cursor, \
+	*cursor = item, \
+	list->tail = item->next ? list->tail : &item->next)
 
 /**
  * Add an item to the tail of a singly-linked list.
@@ -233,14 +236,10 @@
  *         The source list.
  */
 #define SLIST_EXTEND(dest, src) \
-	LIST_BLOCK_(SLIST_EXTEND_((dest), (src)))
+	SLIST_EXTEND_((dest), (src))
 
 #define SLIST_EXTEND_(dest, src) \
-	if (src->head) { \
-		*dest->tail = src->head; \
-		dest->tail = src->tail; \
-		SLIST_INIT(src); \
-	}
+	(src->head ? (*dest->tail = src->head, dest->tail = src->tail, SLIST_INIT(src)) : (void)0)
 
 /**
  * Remove an item from a singly-linked list.
@@ -295,10 +294,10 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  *         The list to initialize.
  */
 #define LIST_INIT(list) \
-	LIST_BLOCK_(LIST_INIT_((list)))
+	LIST_INIT_((list))
 
-#define LIST_INIT_(list) \
-	list->head = list->tail = NULL;
+#define LIST_INIT_(list) LIST_VOID_( \
+	list->head = list->tail = NULL)
 
 /**
  * LIST_PREV_()       => prev
@@ -345,13 +344,13 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #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__)))
+	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;
+#define LIST_INSERT__(list, cursor, item, prev, next) LIST_VOID_( \
+	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)
 
 /**
  * Remove an item from a doubly-linked list.
@@ -366,12 +365,12 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define LIST_REMOVE(list, ...) LIST_REMOVE_(list, __VA_ARGS__, )
 
 #define LIST_REMOVE_(list, item, ...) \
-	LIST_BLOCK_(LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)))
+	LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
 
-#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;
+#define LIST_REMOVE__(list, item, prev, next) LIST_VOID_( \
+	*(item->prev ? &item->prev->next : &list->head) = item->next, \
+	*(item->next ? &item->next->prev : &list->tail) = item->prev, \
+	item->prev = item->next = NULL)
 
 /**
  * Check if an item is attached to a doubly-linked list.
-- 
cgit v1.2.3


From 72ea07d8c200bd6cd34ce02121165f3888624ac6 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 25 Sep 2023 13:16:35 -0400
Subject: list: New [S]LIST_ITEM_INIT() macros

---
 src/list.h | 74 +++++++++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 52 insertions(+), 22 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 0aebd4c..9f8fd20 100644
--- a/src/list.h
+++ b/src/list.h
@@ -21,6 +21,7 @@
  *     SLIST_INIT(&list);
  *
  *     struct item item;
+ *     SLIST_ITEM_INIT(&item);
  *     SLIST_APPEND(&list, &item);
  *
  * Doubly linked lists are similar:
@@ -39,6 +40,7 @@
  *     LIST_INIT(&list);
  *
  *     struct item item;
+ *     LIST_ITEM_INIT(&item);
  *     LIST_APPEND(&list, &item);
  *
  * Items can be on multiple lists at once:
@@ -71,7 +73,9 @@
  *     LIST_INIT(&items.cache);
  *
  *     struct item item;
+ *     SLIST_ITEM_INIT(&item, chain);
  *     SLIST_APPEND(&items.queue, &item, chain);
+ *     LIST_ITEM_INIT(&item, lru);
  *     LIST_APPEND(&items.cache, &item, lru);
  */
 
@@ -109,14 +113,10 @@
 #define LIST_VOID_(...) ((void)(__VA_ARGS__))
 
 /**
- * Insert an item into a singly-linked list.
+ * Initialize a singly-linked list item.
  *
- * @param list
- *         The list to modify.
- * @param cursor
- *         A pointer to the item to insert after, e.g. &list->head or list->tail.
  * @param item
- *         The item to insert.
+ *         The item to initialize.
  * @param node (optional)
  *         If specified, use item->node.next rather than item->next.
  *
@@ -124,29 +124,21 @@
  *
  * We play some tricks with variadic macros to handle the optional parameter:
  *
- *     SLIST_INSERT(list, cursor, item) => {
- *             item->next = *cursor;
- *             *cursor = item;
- *             list->tail = item->next ? list->tail : &item->next;
- *     }
- *
- *     SLIST_INSERT(list, cursor, item, node) => {
- *             item->node.next = *cursor;
- *             *cursor = item;
- *             list->tail = item->node.next ? list->tail : &item->node.next;
- *     }
+ *     SLIST_ITEM_INIT(item)       => item->next = NULL
+ *     SLIST_ITEM_INIT(item, node) => item->node.next = NULL
  *
  * The first trick is that
  *
- *     #define SLIST_INSERT(list, item, cursor, ...)
+ *     #define SLIST_ITEM_INIT(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_INSERT(list, cursor, item)       => SLIST_INSERT_(list, cursor, item, )
- *     SLIST_INSERT(list, cursor, item, node) => SLIST_INSERT_(list, cursor, item, node, )
+ *     SLIST_ITEM_INIT(item)       => SLIST_ITEM_INIT_(item, )
+ *     SLIST_ITEM_INIT(item, node) => SLIST_ITEM_INIT_(item, node, )
  */
-#define SLIST_INSERT(list, cursor, ...) SLIST_INSERT_(list, cursor, __VA_ARGS__, )
+#define SLIST_ITEM_INIT(...) \
+	SLIST_ITEM_INIT_(__VA_ARGS__, )
 
 /**
  * Now we need a way to generate either ->next or ->node.next depending on
@@ -186,9 +178,30 @@
 #define LIST_NODE__(dir, node, ignored, dot, ...) node dot dir
 
 /**
- * SLIST_INSERT_() uses LIST_NEXT_() to generate the right name for the list
+ * SLIST_ITEM_INIT_() uses LIST_NEXT_() to generate the right name for the list
  * node, and finally delegates to the actual implementation.
  */
+#define SLIST_ITEM_INIT_(item, ...) \
+	SLIST_ITEM_INIT__((item), LIST_NEXT_(__VA_ARGS__))
+
+#define SLIST_ITEM_INIT__(item, next) \
+	LIST_VOID_(item->next = NULL)
+
+/**
+ * Insert an item into a singly-linked list.
+ *
+ * @param list
+ *         The list to modify.
+ * @param cursor
+ *         A pointer to the item to insert after, e.g. &list->head or list->tail.
+ * @param item
+ *         The item to insert.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
+ */
+#define SLIST_INSERT(list, cursor, ...) \
+	SLIST_INSERT_(list, cursor, __VA_ARGS__, )
+
 #define SLIST_INSERT_(list, cursor, item, ...) \
 	SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__))
 
@@ -305,6 +318,23 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  */
 #define LIST_PREV_(...) LIST_NODE_(prev, __VA_ARGS__)
 
+/**
+ * Initialize a doubly-linked list item.
+ *
+ * @param item
+ *         The item to initialize.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
+ */
+#define LIST_ITEM_INIT(...) \
+	LIST_ITEM_INIT_(__VA_ARGS__, )
+
+#define LIST_ITEM_INIT_(item, ...) \
+	LIST_ITEM_INIT__((item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
+
+#define LIST_ITEM_INIT__(item, prev, next) \
+	LIST_VOID_(item->prev = item->next = NULL)
+
 /**
  * Add an item to the tail of a doubly-linked list.
  *
-- 
cgit v1.2.3


From 4343832097996886d085fe1139abcec363afc9ee Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 25 Sep 2023 13:29:03 -0400
Subject: list: New [S]LIST_EMPTY() macros

---
 src/list.h | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 9f8fd20..5cb6264 100644
--- a/src/list.h
+++ b/src/list.h
@@ -187,6 +187,15 @@
 #define SLIST_ITEM_INIT__(item, next) \
 	LIST_VOID_(item->next = NULL)
 
+/**
+ * Check if a singly-linked list is empty.
+ */
+#define SLIST_EMPTY(list) \
+	SLIST_EMPTY_((list))
+
+#define SLIST_EMPTY_(list) \
+	((void)sizeof(list->tail - &list->head), !list->head)
+
 /**
  * Insert an item into a singly-linked list.
  *
@@ -335,6 +344,15 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define LIST_ITEM_INIT__(item, prev, next) \
 	LIST_VOID_(item->prev = item->next = NULL)
 
+/**
+ * Check if a doubly-linked list is empty.
+ */
+#define LIST_EMPTY(list) \
+	LIST_EMPTY_((list))
+
+#define LIST_EMPTY_(list) \
+	((void)sizeof(list->tail - list->head), !list->head)
+
 /**
  * Add an item to the tail of a doubly-linked list.
  *
-- 
cgit v1.2.3


From 6b341c9a7ed531cfd84301b59d2da0fd9d5474b1 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 25 Sep 2023 13:34:17 -0400
Subject: list: Unify formatting

---
 src/list.h | 48 ++++++++++++++++++++++++++++++++----------------
 1 file changed, 32 insertions(+), 16 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 5cb6264..235dc55 100644
--- a/src/list.h
+++ b/src/list.h
@@ -155,7 +155,8 @@
  *     LIST_NEXT_()       => LIST_NODE_(next, )
  *     LIST_NEXT_(node, ) => LIST_NODE_(next, node, )
  */
-#define LIST_NEXT_(...) LIST_NODE_(next, __VA_ARGS__)
+#define LIST_NEXT_(...) \
+	LIST_NODE_(next, __VA_ARGS__)
 
 /**
  * LIST_NODE_() dispatches to yet another macro:
@@ -163,7 +164,8 @@
  *     LIST_NODE_(next, )       => LIST_NODE__(next,     , . ,   , )
  *     LIST_NODE_(next, node, ) => LIST_NODE__(next, node,   , . , , )
  */
-#define LIST_NODE_(dir, ...) LIST_NODE__(dir, __VA_ARGS__, . , , )
+#define LIST_NODE_(dir, ...) \
+	LIST_NODE__(dir, __VA_ARGS__, . , , )
 
 /**
  * And finally, LIST_NODE__() adds the node and the dot if necessary.
@@ -175,7 +177,8 @@
  *                  ^     ^      ^     ^
  *                 dir   node ignored dot
  */
-#define LIST_NODE__(dir, node, ignored, dot, ...) node dot dir
+#define LIST_NODE__(dir, node, ignored, dot, ...) \
+	node dot dir
 
 /**
  * SLIST_ITEM_INIT_() uses LIST_NEXT_() to generate the right name for the list
@@ -229,7 +232,8 @@
  * @param node (optional)
  *         If specified, use item->node.next rather than item->next.
  */
-#define SLIST_APPEND(list, ...) SLIST_APPEND_(list, __VA_ARGS__, )
+#define SLIST_APPEND(list, ...) \
+	SLIST_APPEND_(list, __VA_ARGS__, )
 
 #define SLIST_APPEND_(list, item, ...) \
 	SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__)
@@ -244,7 +248,8 @@
  * @param node (optional)
  *         If specified, use item->node.next rather than item->next.
  */
-#define SLIST_PREPEND(list, ...) SLIST_PREPEND_(list, __VA_ARGS__, )
+#define SLIST_PREPEND(list, ...) \
+	SLIST_PREPEND_(list, __VA_ARGS__, )
 
 #define SLIST_PREPEND_(list, item, ...) \
 	SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__)
@@ -275,7 +280,8 @@
  * @return
  *         The removed item.
  */
-#define SLIST_REMOVE(list, ...) SLIST_REMOVE_(list, __VA_ARGS__, )
+#define SLIST_REMOVE(list, ...) \
+	SLIST_REMOVE_(list, __VA_ARGS__, )
 
 #define SLIST_REMOVE_(list, cursor, ...) \
 	SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__))
@@ -304,10 +310,14 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * @return
  *         The popped item, or NULL if the list was empty.
  */
-#define SLIST_POP(...) SLIST_POP_(__VA_ARGS__, )
+#define SLIST_POP(...) \
+	SLIST_POP_(__VA_ARGS__, )
 
 #define SLIST_POP_(list, ...) \
-	((list)->head ? SLIST_REMOVE_(list, &(list)->head, __VA_ARGS__) : NULL)
+	SLIST_POP__((list), __VA_ARGS__)
+
+#define SLIST_POP__(list, ...) \
+	(list->head ? SLIST_REMOVE_(list, &list->head, __VA_ARGS__) : NULL)
 
 /**
  * Initialize a doubly-linked list.
@@ -318,14 +328,15 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define LIST_INIT(list) \
 	LIST_INIT_((list))
 
-#define LIST_INIT_(list) LIST_VOID_( \
-	list->head = list->tail = NULL)
+#define LIST_INIT_(list) \
+	LIST_VOID_(list->head = list->tail = NULL)
 
 /**
  * LIST_PREV_()       => prev
  * LIST_PREV_(node, ) => node.prev
  */
-#define LIST_PREV_(...) LIST_NODE_(prev, __VA_ARGS__)
+#define LIST_PREV_(...) \
+	LIST_NODE_(prev, __VA_ARGS__)
 
 /**
  * Initialize a doubly-linked list item.
@@ -363,7 +374,8 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * @param node (optional)
  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
-#define LIST_APPEND(list, ...) LIST_INSERT(list, (list)->tail, __VA_ARGS__)
+#define LIST_APPEND(list, ...) \
+	LIST_INSERT(list, (list)->tail, __VA_ARGS__)
 
 /**
  * Add an item to the head of a doubly-linked list.
@@ -375,7 +387,8 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * @param node (optional)
  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
-#define LIST_PREPEND(list, ...) LIST_INSERT(list, NULL, __VA_ARGS__)
+#define LIST_PREPEND(list, ...) \
+	LIST_INSERT(list, NULL, __VA_ARGS__)
 
 /**
  * Insert into a doubly-linked list after the given cursor.
@@ -389,7 +402,8 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * @param node (optional)
  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
-#define LIST_INSERT(list, cursor, ...) LIST_INSERT_(list, cursor, __VA_ARGS__, )
+#define LIST_INSERT(list, cursor, ...) \
+	LIST_INSERT_(list, cursor, __VA_ARGS__, )
 
 #define LIST_INSERT_(list, cursor, item, ...) \
 	LIST_INSERT__((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
@@ -410,7 +424,8 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * @param node (optional)
  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
  */
-#define LIST_REMOVE(list, ...) LIST_REMOVE_(list, __VA_ARGS__, )
+#define LIST_REMOVE(list, ...) \
+	LIST_REMOVE_(list, __VA_ARGS__, )
 
 #define LIST_REMOVE_(list, item, ...) \
 	LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
@@ -432,7 +447,8 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
  * @return
  *         Whether the item is attached to the list.
  */
-#define LIST_ATTACHED(list, ...) LIST_ATTACHED_(list, __VA_ARGS__, )
+#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__))
-- 
cgit v1.2.3


From e4304e8b9e74577947647743fd51937ac51956c9 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 25 Sep 2023 13:53:15 -0400
Subject: list: New for_[s]list() macros

---
 src/list.h | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 60 insertions(+), 2 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 235dc55..5587543 100644
--- a/src/list.h
+++ b/src/list.h
@@ -190,6 +190,12 @@
 #define SLIST_ITEM_INIT__(item, next) \
 	LIST_VOID_(item->next = NULL)
 
+/**
+ * Type-checking macro for singly-linked lists.
+ */
+#define SLIST_CHECK_(list) \
+	(void)sizeof(list->tail - &list->head)
+
 /**
  * Check if a singly-linked list is empty.
  */
@@ -197,7 +203,7 @@
 	SLIST_EMPTY_((list))
 
 #define SLIST_EMPTY_(list) \
-	((void)sizeof(list->tail - &list->head), !list->head)
+	(SLIST_CHECK_(list), !list->head)
 
 /**
  * Insert an item into a singly-linked list.
@@ -319,6 +325,29 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define SLIST_POP__(list, ...) \
 	(list->head ? SLIST_REMOVE_(list, &list->head, __VA_ARGS__) : NULL)
 
+/**
+ * Loop over the items in a singly-linked list.
+ *
+ * @param type
+ *         The list item type.
+ * @param item
+ *         The induction variable name.
+ * @param list
+ *         The list to iterate.
+ * @param node (optional)
+ *         If specified, use head->node.next rather than head->next.
+ */
+#define for_slist(type, item, ...) \
+	for_slist_(type, item, __VA_ARGS__, )
+
+#define for_slist_(type, item, list, ...) \
+	for_slist__(type, item, (list), LIST_NEXT_(__VA_ARGS__))
+
+#define for_slist__(type, item, list, next) \
+	for (type *item = list->head, *_next; \
+	     item && (SLIST_CHECK_(list), _next = item->next, true); \
+	     item = _next)
+
 /**
  * Initialize a doubly-linked list.
  *
@@ -355,6 +384,12 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define LIST_ITEM_INIT__(item, prev, next) \
 	LIST_VOID_(item->prev = item->next = NULL)
 
+/**
+ * Type-checking macro for doubly-linked lists.
+ */
+#define LIST_CHECK_(list) \
+	(void)sizeof(list->tail - list->head)
+
 /**
  * Check if a doubly-linked list is empty.
  */
@@ -362,7 +397,7 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 	LIST_EMPTY_((list))
 
 #define LIST_EMPTY_(list) \
-	((void)sizeof(list->tail - list->head), !list->head)
+	(LIST_CHECK_(list), !list->head)
 
 /**
  * Add an item to the tail of a doubly-linked list.
@@ -456,4 +491,27 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define LIST_ATTACHED__(list, item, prev, next) \
 	(item->prev || item->next || list->head == item || list->tail == item)
 
+/**
+ * Loop over the items in a doubly-linked list.
+ *
+ * @param type
+ *         The list item type.
+ * @param item
+ *         The induction variable name.
+ * @param list
+ *         The list to iterate.
+ * @param node (optional)
+ *         If specified, use head->node.next rather than head->next.
+ */
+#define for_list(type, item, ...) \
+	for_list_(type, item, __VA_ARGS__, )
+
+#define for_list_(type, item, list, ...) \
+	for_list__(type, item, (list), LIST_NEXT_(__VA_ARGS__))
+
+#define for_list__(type, item, list, next) \
+	for (type *item = list->head, *_next; \
+	     item && (LIST_CHECK_(list), _next = item->next, true); \
+	     item = _next)
+
 #endif // BFS_LIST_H
-- 
cgit v1.2.3


From 1addab1e5f12cb0fddfa92872bf45653352cc212 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Thu, 12 Oct 2023 13:18:00 -0400
Subject: list: Assert that we're not inserting already-attached nodes

---
 src/list.h | 66 ++++++++++++++++++++++++++++++++++++++++++--------------------
 src/trie.c |  1 +
 2 files changed, 46 insertions(+), 21 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 5587543..61c22e3 100644
--- a/src/list.h
+++ b/src/list.h
@@ -82,6 +82,7 @@
 #ifndef BFS_LIST_H
 #define BFS_LIST_H
 
+#include "diag.h"
 #include <stddef.h>
 #include <string.h>
 
@@ -205,6 +206,27 @@
 #define SLIST_EMPTY_(list) \
 	(SLIST_CHECK_(list), !list->head)
 
+/**
+ * Check if an item is attached to a singly-linked list.
+ *
+ * @param list
+ *         The list to check.
+ * @param item
+ *         The item to check.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
+ * @return
+ *         Whether the item is attached to the list.
+ */
+#define SLIST_ATTACHED(list, ...) \
+	SLIST_ATTACHED_(list, __VA_ARGS__, )
+
+#define SLIST_ATTACHED_(list, item, ...) \
+	SLIST_ATTACHED__((list), (item), LIST_NEXT_(__VA_ARGS__))
+
+#define SLIST_ATTACHED__(list, item, next) \
+	(item->next || list->tail == &item->next)
+
 /**
  * Insert an item into a singly-linked list.
  *
@@ -224,6 +246,7 @@
 	SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__))
 
 #define SLIST_INSERT__(list, cursor, item, next) LIST_VOID_( \
+	bfs_assert(!SLIST_ATTACHED__(list, item, next)), \
 	item->next = *cursor, \
 	*cursor = item, \
 	list->tail = item->next ? list->tail : &item->next)
@@ -425,6 +448,27 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 #define LIST_PREPEND(list, ...) \
 	LIST_INSERT(list, NULL, __VA_ARGS__)
 
+/**
+ * Check if an item is attached to a doubly-linked list.
+ *
+ * @param list
+ *         The list to check.
+ * @param item
+ *         The item to check.
+ * @param node (optional)
+ *         If specified, use item->node.{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)
+
 /**
  * Insert into a doubly-linked list after the given cursor.
  *
@@ -444,6 +488,7 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 	LIST_INSERT__((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
 
 #define LIST_INSERT__(list, cursor, item, prev, next) LIST_VOID_( \
+	bfs_assert(!LIST_ATTACHED__(list, item, prev, next)), \
 	item->prev = cursor, \
 	item->next = cursor ? cursor->next : list->head, \
 	*(item->prev ? &item->prev->next : &list->head) = item, \
@@ -470,27 +515,6 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void
 	*(item->next ? &item->next->prev : &list->tail) = item->prev, \
 	item->prev = item->next = NULL)
 
-/**
- * Check if an item is attached to a doubly-linked list.
- *
- * @param list
- *         The list to check.
- * @param item
- *         The item to check.
- * @param node (optional)
- *         If specified, use item->node.{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)
-
 /**
  * Loop over the items in a doubly-linked list.
  *
diff --git a/src/trie.c b/src/trie.c
index 55544e6..23b70ff 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -325,6 +325,7 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz
 		return NULL;
 	}
 
+	LIST_ITEM_INIT(leaf);
 	LIST_APPEND(trie, leaf);
 
 	leaf->value = NULL;
-- 
cgit v1.2.3


From ffa465b759204272a5e94d851ce3696c827e9d96 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Thu, 9 Nov 2023 14:34:40 -0500
Subject: list: Simplify slist_remove_impl()

We now assume that all-bits-zero is a null pointer, so memset is fine.
---
 src/list.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 61c22e3..91f416f 100644
--- a/src/list.h
+++ b/src/list.h
@@ -317,15 +317,15 @@
 
 #define SLIST_REMOVE__(list, cursor, next) \
 	(list->tail = (*cursor)->next ? list->tail : cursor, \
-	 slist_remove_impl(*cursor, cursor, &(*cursor)->next, list->tail, sizeof(*cursor)))
+	 slist_remove_impl(*cursor, cursor, &(*cursor)->next, sizeof(*cursor)))
 
 // Helper for SLIST_REMOVE()
-static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void *tail, size_t size) {
+static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_t size) {
 	// ret = *cursor;
 	// *cursor = ret->next;
 	memcpy(cursor, next, size);
-	// ret->next = *list->tail; (NULL)
-	memcpy(next, tail, size);
+	// ret->next = NULL;
+	memset(next, 0, size);
 	return ret;
 }
 
-- 
cgit v1.2.3


From 70acbc194fa1cc4972293d4e3affee5ba6fe5539 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sun, 7 Jan 2024 12:11:04 -0500
Subject: list: New SLIST_HEAD() and SLIST_TAIL() macros

---
 src/list.h | 43 ++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 40 insertions(+), 3 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 91f416f..02a7ba2 100644
--- a/src/list.h
+++ b/src/list.h
@@ -197,14 +197,51 @@
 #define SLIST_CHECK_(list) \
 	(void)sizeof(list->tail - &list->head)
 
+/**
+ * Get the head of a singly-linked list.
+ *
+ * @param list
+ *         The list in question.
+ * @return
+ *         The first item in the list.
+ */
+#define SLIST_HEAD(list) \
+	SLIST_HEAD_((list))
+
+#define SLIST_HEAD_(list) \
+	(SLIST_CHECK_(list), list->head)
+
 /**
  * Check if a singly-linked list is empty.
  */
 #define SLIST_EMPTY(list) \
-	SLIST_EMPTY_((list))
+	(!SLIST_HEAD(list))
+
+/**
+ * Like container_of(), but using the head pointer instead of offsetof() since
+ * we don't have the type around.
+ */
+#define SLIST_CONTAINER_(tail, head, next) \
+	(void *)((char *)tail - ((char *)&head->next - (char *)head))
+
+/**
+ * Get the tail of a singly-linked list.
+ *
+ * @param list
+ *         The list in question.
+ * @param node (optional)
+ *         If specified, use item->node.next rather than item->next.
+ * @return
+ *         The last item in the list.
+ */
+#define SLIST_TAIL(...) \
+	SLIST_TAIL_(__VA_ARGS__, )
+
+#define SLIST_TAIL_(list, ...) \
+	SLIST_TAIL__((list), LIST_NEXT_(__VA_ARGS__))
 
-#define SLIST_EMPTY_(list) \
-	(SLIST_CHECK_(list), !list->head)
+#define SLIST_TAIL__(list, next) \
+	(list->head ? SLIST_CONTAINER_(list->tail, list->head, next) : NULL)
 
 /**
  * Check if an item is attached to a singly-linked list.
-- 
cgit v1.2.3


From 6f0091981e38210e36ee830694f61cb695f2b99b Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 30 Jan 2024 12:49:28 -0500
Subject: list: Return the next cursor from SLIST_INSERT()

---
 src/list.h | 17 ++++++++++-------
 1 file changed, 10 insertions(+), 7 deletions(-)

(limited to 'src/list.h')

diff --git a/src/list.h b/src/list.h
index 02a7ba2..61d0e5b 100644
--- a/src/list.h
+++ b/src/list.h
@@ -275,6 +275,8 @@
  *         The item to insert.
  * @param node (optional)
  *         If specified, use item->node.next rather than item->next.
+ * @return
+ *         A cursor for the next item.
  */
 #define SLIST_INSERT(list, cursor, ...) \
 	SLIST_INSERT_(list, cursor, __VA_ARGS__, )
@@ -282,11 +284,12 @@
 #define SLIST_INSERT_(list, cursor, item, ...) \
 	SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__))
 
-#define SLIST_INSERT__(list, cursor, item, next) LIST_VOID_( \
-	bfs_assert(!SLIST_ATTACHED__(list, item, next)), \
-	item->next = *cursor, \
-	*cursor = item, \
-	list->tail = item->next ? list->tail : &item->next)
+#define SLIST_INSERT__(list, cursor, item, next) \
+	(bfs_assert(!SLIST_ATTACHED__(list, item, next)), \
+	 item->next = *cursor, \
+	 *cursor = item, \
+	 list->tail = item->next ? list->tail : &item->next, \
+	 &item->next)
 
 /**
  * Add an item to the tail of a singly-linked list.
@@ -302,7 +305,7 @@
 	SLIST_APPEND_(list, __VA_ARGS__, )
 
 #define SLIST_APPEND_(list, item, ...) \
-	SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__)
+	LIST_VOID_(SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__))
 
 /**
  * Add an item to the head of a singly-linked list.
@@ -318,7 +321,7 @@
 	SLIST_PREPEND_(list, __VA_ARGS__, )
 
 #define SLIST_PREPEND_(list, item, ...) \
-	SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__)
+	LIST_VOID_(SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__))
 
 /**
  * Add an entire singly-linked list to the tail of another.
-- 
cgit v1.2.3