1 #pragma once 2 3 #include <stddef.h> 4 5 /* 6 * Doubly linked list macros. All of these require that each list item is a 7 * struct, that contains a field, that is another struct with prev/next fields: 8 * 9 * struct example_item { 10 * struct { 11 * struct example_item *prev, *next; 12 * } mylist; 13 * }; 14 * 15 * And a struct somewhere that represents the "list" and has head/tail fields: 16 * 17 * struct { 18 * struct example_item *head, *tail; 19 * } mylist_var; 20 * 21 * Then you can e.g. insert elements like this: 22 * 23 * struct example_item item; 24 * LL_APPEND(mylist, &mylist_var, &item); 25 * 26 * The first macro argument is always the name if the field in the item that 27 * contains the prev/next pointers, in this case struct example_item.mylist. 28 * This was done so that a single item can be in multiple lists. 29 * 30 * The list is started/terminated with NULL. Nothing ever points _to_ the 31 * list head, so the list head memory location can be safely moved. 32 * 33 * General rules are: 34 * - list head is initialized by setting head/tail to NULL 35 * - list items do not need to be initialized before inserting them 36 * - next/prev fields of list items are not cleared when they are removed 37 * - there's no way to know whether an item is in the list or not (unless 38 * you clear prev/next on init/removal, _and_ check whether items with 39 * prev/next==NULL are referenced by head/tail) 40 */ 41 42 // Insert item at the end of the list (list->tail == item). 43 // Undefined behavior if item is already in the list. 44 #define LL_APPEND(field, list, item) do { \ 45 (item)->field.prev = (list)->tail; \ 46 (item)->field.next = NULL; \ 47 LL_RELINK_(field, list, item) \ 48 } while (0) 49 50 // Insert item enew after eprev (i.e. eprev->next == enew). If eprev is NULL, 51 // then insert it as head (list->head == enew). 52 // Undefined behavior if enew is already in the list, or eprev isn't. 53 #define LL_INSERT_AFTER(field, list, eprev, enew) do { \ 54 (enew)->field.prev = (eprev); \ 55 (enew)->field.next = (eprev) ? (eprev)->field.next : (list)->head; \ 56 LL_RELINK_(field, list, enew) \ 57 } while (0) 58 59 // Insert item at the start of the list (list->head == item). 60 // Undefined behavior if item is already in the list. 61 #define LL_PREPEND(field, list, item) do { \ 62 (item)->field.prev = NULL; \ 63 (item)->field.next = (list)->head; \ 64 LL_RELINK_(field, list, item) \ 65 } while (0) 66 67 // Insert item enew before enext (i.e. enew->next == enext). If enext is NULL, 68 // then insert it as tail (list->tail == enew). 69 // Undefined behavior if enew is already in the list, or enext isn't. 70 #define LL_INSERT_BEFORE(field, list, enext, enew) do { \ 71 (enew)->field.prev = (enext) ? (enext)->field.prev : (list)->tail; \ 72 (enew)->field.next = (enext); \ 73 LL_RELINK_(field, list, enew) \ 74 } while (0) 75 76 // Remove the item from the list. 77 // Undefined behavior if item is not in the list. 78 #define LL_REMOVE(field, list, item) do { \ 79 if ((item)->field.prev) { \ 80 (item)->field.prev->field.next = (item)->field.next; \ 81 } else { \ 82 (list)->head = (item)->field.next; \ 83 } \ 84 if ((item)->field.next) { \ 85 (item)->field.next->field.prev = (item)->field.prev; \ 86 } else { \ 87 (list)->tail = (item)->field.prev; \ 88 } \ 89 } while (0) 90 91 // Remove all items from the list. 92 #define LL_CLEAR(field, list) do { \ 93 (list)->head = (list)->tail = NULL; \ 94 } while (0) 95 96 // Internal helper. 97 #define LL_RELINK_(field, list, item) \ 98 if ((item)->field.prev) { \ 99 (item)->field.prev->field.next = (item); \ 100 } else { \ 101 (list)->head = (item); \ 102 } \ 103 if ((item)->field.next) { \ 104 (item)->field.next->field.prev = (item); \ 105 } else { \ 106 (list)->tail = (item); \ 107 } 108