list.h (4352B)
1 #ifndef LIST_H 2 #define LIST_H 3 4 #include <stddef.h> 5 #include <stdint.h> 6 #include <stdio.h> 7 #include <stdlib.h> 8 9 /* we define an "intrusive" list, meaning that out data struct contains a 10 * list_node member. this allows a type-generic list implementation, but 11 * necessitates need a way to get from a pointer to this list_node, to a 12 * pointer to the parent struct 13 */ 14 #define TO_PARENT(ptr, T, member) \ 15 ((T *) ((uintptr_t) (ptr) - offsetof(T, member))) 16 17 /* we choose to implement a doubly-linked list for simplicity and flexible 18 * use in situations that require either singly-linked or doubly-linked lists 19 */ 20 struct list_node { 21 struct list_node *prev, *next; 22 }; 23 24 /* shorthands for getting the head and tail members of a list 25 */ 26 #define LIST_HEAD(list) ((list)->next) 27 #define LIST_TAIL(list) ((list)->prev) 28 29 /* instead of having NULL signify an empty list, we have the list itself be the 30 * "sentinel value". this approach simplifys some of the code (as we always 31 * point to a valid instance in our next and prev fields). this makes checking 32 * whether a list is empty slightly convoluted unfortunately. 33 */ 34 #define LIST_INIT(list) ((struct list_node) { .prev = &(list), .next = &(list), }) 35 #define LIST_EMTPY(list) (LIST_HEAD(list) == (list) && LIST_TAIL(list) == (list)) 36 37 38 inline void 39 list_node_link(struct list_node *node, struct list_node *prev, struct list_node *next) 40 { 41 node->prev = prev; 42 prev->next = node; 43 node->next = next; 44 next->prev = node; 45 } 46 47 inline struct list_node * 48 list_node_unlink(struct list_node *node) 49 { 50 node->prev->next = node->next; 51 node->next->prev = node->prev; 52 return node; 53 } 54 55 /* some helpers to push and pop a node to and from an existing list 56 */ 57 inline void 58 list_push_head(struct list_node *restrict list, struct list_node *restrict node) 59 { 60 list_node_link(node, list, LIST_HEAD(list)); 61 } 62 63 inline void 64 list_push_tail(struct list_node *restrict list, struct list_node *restrict node) 65 { 66 list_node_link(node, LIST_TAIL(list), list); 67 } 68 69 inline struct list_node * 70 list_pop_head(struct list_node *list) 71 { 72 struct list_node *node = list_node_unlink(LIST_HEAD(list)); 73 return node; 74 } 75 76 inline struct list_node * 77 list_pop_tail(struct list_node *list) 78 { 79 struct list_node *node = list_node_unlink(LIST_TAIL(list)); 80 return node; 81 } 82 83 /* helper macros to allow simple iteration over the list_node instances, or 84 * over the parent types that comprise the list. 85 */ 86 #define LIST_ITER(list, it) \ 87 for ((it) = LIST_HEAD(list); (it) != (list); (it) = (it)->next) 88 89 #define LIST_RITER(list, it) \ 90 for ((it) = LIST_TAIL(list); (it) != (list); (it) = (it)->prev) 91 92 #define LIST_NODE_ENTRY(ptr, T, member) TO_PARENT(ptr, T, member) 93 94 #define LIST_ENTRY_ITER(list, it, member) \ 95 for ((it) = LIST_NODE_ENTRY(LIST_HEAD(list), __typeof__ (*(it)), member); \ 96 &(it)->member != (list); \ 97 (it) = LIST_NODE_ENTRY((it)->member.next, __typeof__ (*(it)), member)) 98 99 #define LIST_ENTRY_RITER(list, it, member) \ 100 for ((it) = LIST_NODE_ENTRY(LIST_TAIL(list), __typeof__ (*(it)), member); \ 101 &(it)->member != (list); \ 102 (it) = LIST_NODE_ENTRY((it)->member.prev, __typeof__ (*(it)), member)) 103 104 inline void 105 list_print(struct list_node const *list, int reversed) 106 { 107 fprintf(stderr, "list: %p, head: %p, tail: %p\n", 108 (void *) list, (void *) LIST_HEAD(list), (void *) LIST_TAIL(list)); 109 110 struct list_node *it; 111 if (reversed) { 112 LIST_ITER(list, it) { 113 fprintf(stderr, "\t{ %p, prev: %p, next: %p }\n", 114 (void *) it, (void *) it->prev, (void *) it->next); 115 } 116 } else { 117 LIST_RITER(list, it) { 118 fprintf(stderr, "\t{ %p, prev: %p, next: %p }\n", 119 (void *) it, (void *) it->prev, (void *) it->next); 120 } 121 } 122 } 123 124 #endif /* LIST_H */ 125 126 #ifdef HEADER_IMPL 127 128 extern inline void 129 list_node_link(struct list_node *restrict node, 130 struct list_node *restrict prev, struct list_node *restrict next); 131 132 extern inline struct list_node * 133 list_node_unlink(struct list_node *node); 134 135 extern inline void 136 list_push_head(struct list_node *restrict list, struct list_node *restrict node); 137 138 extern inline void 139 list_push_tail(struct list_node *restrict list, struct list_node *restrict node); 140 141 extern inline struct list_node * 142 list_pop_head(struct list_node *list); 143 144 extern inline struct list_node * 145 list_pop_tail(struct list_node *list); 146 147 extern inline void 148 list_print(struct list_node const *list, int reversed); 149 150 #endif /* HEADER_IMPL */