diff options
Diffstat (limited to 'src/list.h')
| -rw-r--r-- | src/list.h | 159 |
1 files changed, 91 insertions, 68 deletions
@@ -82,14 +82,17 @@ #ifndef BFS_LIST_H #define BFS_LIST_H +#include "bfs.h" #include "diag.h" + #include <stddef.h> +#include <stdint.h> #include <string.h> /** * Initialize a singly-linked list. * - * @param list + * @list * The list to initialize. * * --- @@ -116,9 +119,9 @@ /** * Initialize a singly-linked list item. * - * @param item + * @item * The item to initialize. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * * --- @@ -200,7 +203,7 @@ /** * Get the head of a singly-linked list. * - * @param list + * @list * The list in question. * @return * The first item in the list. @@ -227,9 +230,9 @@ /** * Get the tail of a singly-linked list. * - * @param list + * @list * The list in question. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * The last item in the list. @@ -246,11 +249,11 @@ /** * Check if an item is attached to a singly-linked list. * - * @param list + * @list * The list to check. - * @param item + * @item * The item to check. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * Whether the item is attached to the list. @@ -267,13 +270,13 @@ /** * Insert an item into a singly-linked list. * - * @param list + * @list * The list to modify. - * @param cursor + * @cursor * A pointer to the item to insert after, e.g. &list->head or list->tail. - * @param item + * @item * The item to insert. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * A cursor for the next item. @@ -294,11 +297,11 @@ /** * Add an item to the tail of a singly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to append. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. */ #define SLIST_APPEND(list, ...) \ @@ -310,11 +313,11 @@ /** * Add an item to the head of a singly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to prepend. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. */ #define SLIST_PREPEND(list, ...) \ @@ -326,11 +329,11 @@ /** * Splice a singly-linked list into another. * - * @param dest + * @dest * The destination list. - * @param cursor + * @cursor * A pointer to the item to splice after, e.g. &list->head or list->tail. - * @param src + * @src * The source list. */ #define SLIST_SPLICE(dest, cursor, src) \ @@ -345,9 +348,9 @@ /** * Add an entire singly-linked list to the tail of another. * - * @param dest + * @dest * The destination list. - * @param src + * @src * The source list. */ #define SLIST_EXTEND(dest, src) \ @@ -356,11 +359,11 @@ /** * Remove an item from a singly-linked list. * - * @param list + * @list * The list to modify. - * @param cursor + * @cursor * A pointer to the item to remove, either &list->head or &prev->next. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * The removed item. @@ -371,26 +374,31 @@ #define SLIST_REMOVE_(list, cursor, ...) \ SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__)) -#define SLIST_REMOVE__(list, cursor, next) \ - (list->tail = (*cursor)->next ? list->tail : 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, size_t size) { - // ret = *cursor; - // *cursor = ret->next; - memcpy(cursor, next, size); - // ret->next = NULL; - memset(next, 0, size); - return ret; +// Scratch variables for the type-safe SLIST_REMOVE() implementation. +// Not a pointer type due to https://github.com/llvm/llvm-project/issues/109718. +_maybe_unused +static thread_local uintptr_t _slist_prev, _slist_next; + +/** Suppress -Wunused-value. */ +_maybe_unused +static inline void *_slist_cast(uintptr_t ptr) { + return (void *)ptr; } +#define SLIST_REMOVE__(list, cursor, next) \ + (_slist_prev = (uintptr_t)(void *)*cursor, \ + _slist_next = (uintptr_t)(void *)(*cursor)->next, \ + (*cursor)->next = NULL, \ + *cursor = (void *)_slist_next, \ + list->tail = *cursor ? list->tail : cursor, \ + _slist_cast(_slist_prev)) + /** * Pop the head off a singly-linked list. * - * @param list + * @list * The list to modify. - * @param node (optional) + * @node (optional) * If specified, use head->node.next rather than head->next. * @return * The popped item, or NULL if the list was empty. @@ -407,13 +415,13 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Loop over the items in a singly-linked list. * - * @param type + * @type * The list item type. - * @param item + * @item * The induction variable name. - * @param list + * @list * The list to iterate. - * @param node (optional) + * @node (optional) * If specified, use head->node.next rather than head->next. */ #define for_slist(type, item, ...) \ @@ -428,9 +436,24 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ item = _next) /** + * Loop over a singly-linked list, popping each item. + * + * @type + * The list item type. + * @item + * The induction variable name. + * @list + * The list to drain. + * @node (optional) + * If specified, use head->node.next rather than head->next. + */ +#define drain_slist(type, item, ...) \ + for (type *item; (item = SLIST_POP(__VA_ARGS__));) + +/** * Initialize a doubly-linked list. * - * @param list + * @list * The list to initialize. */ #define LIST_INIT(list) \ @@ -449,9 +472,9 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Initialize a doubly-linked list item. * - * @param item + * @item * The item to initialize. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. */ #define LIST_ITEM_INIT(...) \ @@ -481,11 +504,11 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Add an item to the tail of a doubly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to append. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ #define LIST_APPEND(list, ...) \ @@ -494,11 +517,11 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Add an item to the head of a doubly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to prepend. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ #define LIST_PREPEND(list, ...) \ @@ -507,11 +530,11 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Check if an item is attached to a doubly-linked list. * - * @param list + * @list * The list to check. - * @param item + * @item * The item to check. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. * @return * Whether the item is attached to the list. @@ -528,13 +551,13 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Insert into a doubly-linked list after the given cursor. * - * @param list + * @list * The list to modify. - * @param cursor + * @cursor * Insert after this element. - * @param item + * @item * The item to insert. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ #define LIST_INSERT(list, cursor, ...) \ @@ -553,11 +576,11 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Remove an item from a doubly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to remove. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ #define LIST_REMOVE(list, ...) \ @@ -574,13 +597,13 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Loop over the items in a doubly-linked list. * - * @param type + * @type * The list item type. - * @param item + * @item * The induction variable name. - * @param list + * @list * The list to iterate. - * @param node (optional) + * @node (optional) * If specified, use head->node.next rather than head->next. */ #define for_list(type, item, ...) \ |