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