diff options
Diffstat (limited to 'src/list.h')
| -rw-r--r-- | src/list.h | 451 |
1 files changed, 334 insertions, 117 deletions
@@ -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,20 +73,24 @@ * 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); */ #ifndef BFS_LIST_H #define BFS_LIST_H +#include "diag.h" + #include <stddef.h> #include <string.h> /** * Initialize a singly-linked list. * - * @param list + * @list * The list to initialize. * * --- @@ -94,56 +100,47 @@ * 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. + * 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. - * @param node (optional) + * @item + * The item to initialize. + * @node (optional) * If specified, use item->node.next rather than item->next. * * --- * * 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 @@ -160,7 +157,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: @@ -168,7 +166,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. @@ -180,217 +179,435 @@ * ^ ^ ^ ^ * 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_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) + +/** + * Type-checking macro for singly-linked lists. + */ +#define SLIST_CHECK_(list) \ + (void)sizeof(list->tail - &list->head) + +/** + * Get the head of a singly-linked list. + * + * @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_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. + * + * @list + * The list in question. + * @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_TAIL__(list, next) \ + (list->head ? SLIST_CONTAINER_(list->tail, list->head, next) : NULL) + +/** + * Check if an item is attached to a singly-linked list. + * + * @list + * The list to check. + * @item + * The item to check. + * @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. + * + * @list + * The list to modify. + * @cursor + * A pointer to the item to insert after, e.g. &list->head or list->tail. + * @item + * The item to insert. + * @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__, ) + #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; + (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. * - * @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, ...) 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__) + LIST_VOID_(SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__)) /** * 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, ...) 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__) + LIST_VOID_(SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__)) + +/** + * Splice a singly-linked list into another. + * + * @dest + * The destination list. + * @cursor + * A pointer to the item to splice after, e.g. &list->head or list->tail. + * @src + * The source list. + */ +#define SLIST_SPLICE(dest, cursor, src) \ + LIST_VOID_(SLIST_SPLICE_((dest), (cursor), (src))) + +#define SLIST_SPLICE_(dest, cursor, src) \ + *src->tail = *cursor, \ + *cursor = src->head, \ + dest->tail = *dest->tail ? src->tail : dest->tail, \ + SLIST_INIT(src) /** * 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) \ - LIST_BLOCK_(SLIST_EXTEND_((dest), (src))) - -#define SLIST_EXTEND_(dest, src) \ - if (src->head) { \ - *dest->tail = src->head; \ - dest->tail = src->tail; \ - SLIST_INIT(src); \ - } + SLIST_SPLICE(dest, (dest)->tail, src) /** * 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. */ -#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__)) #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_(*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_(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; } /** * 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. */ -#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) + +/** + * Loop over the items in a singly-linked list. + * + * @type + * The list item type. + * @item + * The induction variable name. + * @list + * The list to iterate. + * @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) + +/** + * 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) \ - LIST_BLOCK_(LIST_INIT_((list))) + LIST_INIT_((list)) #define LIST_INIT_(list) \ - list->head = list->tail = NULL; + 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. + * + * @item + * The item to initialize. + * @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) + +/** + * 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. + */ +#define LIST_EMPTY(list) \ + LIST_EMPTY_((list)) + +#define LIST_EMPTY_(list) \ + (LIST_CHECK_(list), !list->head) /** * 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, ...) 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. * - * @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, ...) LIST_INSERT(list, NULL, __VA_ARGS__) +#define LIST_PREPEND(list, ...) \ + LIST_INSERT(list, NULL, __VA_ARGS__) + +/** + * Check if an item is attached to a doubly-linked list. + * + * @list + * The list to check. + * @item + * The item to check. + * @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. * - * @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, ...) LIST_INSERT_(list, cursor, __VA_ARGS__, ) +#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_( \ + 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, \ + *(item->next ? &item->next->prev : &list->tail) = item) /** * 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, ...) LIST_REMOVE_(list, __VA_ARGS__, ) +#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. - * - * @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. + * Loop over the items in a doubly-linked list. + * + * @type + * The list item type. + * @item + * The induction variable name. + * @list + * The list to iterate. + * @node (optional) + * If specified, use head->node.next rather than head->next. */ -#define LIST_ATTACHED(list, ...) LIST_ATTACHED_(list, __VA_ARGS__, ) +#define for_list(type, item, ...) \ + for_list_(type, item, __VA_ARGS__, ) -#define LIST_ATTACHED_(list, item, ...) \ - LIST_ATTACHED__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) +#define for_list_(type, item, list, ...) \ + for_list__(type, item, (list), LIST_NEXT_(__VA_ARGS__)) -#define LIST_ATTACHED__(list, item, prev, next) \ - (item->prev || item->next || list->head == item || list->tail == item) +#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 |