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