list: New generic linked list API

4 files changed, 351 insertions, 0 deletions

diff --git a/Makefile b/Makefile
index b509065..428a0f7 100644
--- a/Makefile
+++ b/Makefile
@@ -223,6 +223,7 @@ 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/config.h b/src/config.h
index 34ae11d..cee8511 100644
--- a/src/config.h
+++ b/src/config.h
@@ -147,6 +147,17 @@
  */
 #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
new file mode 100644
index 0000000..dffee19
--- /dev/null
+++ b/src/list.c
@@ -0,0 +1,169 @@
+// 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
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