list: Use macros instead of type-erased lists

1 files changed, 288 insertions, 159 deletions

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