summaryrefslogtreecommitdiffstats
path: root/src/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/list.h')
-rw-r--r--src/list.h447
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