list.h (2873B)
1 #ifndef LIST_H 2 #define LIST_H 3 4 #include <stddef.h> 5 #include <stdint.h> 6 7 #define TO_PARENT(ptr, T, member) \ 8 ((ptr) ? ((T *) (((uintptr_t) (ptr)) - offsetof(T, member))) : NULL) 9 10 struct list_node { 11 struct list_node *prev, *next; 12 }; 13 14 #define FROM_LIST_NODE(node, T, member) \ 15 TO_PARENT((node), T, member) 16 17 #define LIST_NODE_ENTRY(node, it, member) \ 18 FROM_LIST_NODE((node), __typeof__ (*(it)), member) 19 20 #define LIST_INIT(list) ((struct list_node) { &(list), &(list), }) 21 22 #define LIST_HEAD(list) ((list)->next) 23 #define LIST_TAIL(list) ((list)->prev) 24 #define LIST_EMPTY(list) ((list)->prev == (list) && (list)->next == (list)) 25 26 // iterate by list_node 27 #define LIST_NODE_ITER(list, it) \ 28 for ((it) = LIST_HEAD(list); (it) != (list); (it) = (it)->next) 29 30 // iterare by list_node in reverse 31 #define LIST_NODE_RITER(list, it) \ 32 for ((it) = LIST_TAIL(list); (it) != (list); (it) = (it)->prev) 33 34 // iterate by container type T 35 #define LIST_ENTRY_ITER(list, it, member) \ 36 for ((it) = LIST_NODE_ENTRY(LIST_HEAD(list), (it), member); \ 37 &(it)->member != (list); \ 38 (it) = LIST_NODE_ENTRY((it)->member.next, (it), member)) 39 40 // iterate by container type in reverse 41 #define LIST_ENTRY_RITER(list, it, member) \ 42 for ((it) = LIST_NODE_ENTRY(LIST_TAIL(list), (it), member); \ 43 &(it)->member != (list); \ 44 (it) = LIST_NODE_ENTRY((it)->member.prev, (it), member)) 45 46 inline void 47 list_node_link(struct list_node *node, struct list_node *prev, struct list_node *next) 48 { 49 prev->next = node; 50 node->prev = prev; 51 next->prev = node; 52 node->next = next; 53 } 54 55 inline struct list_node * 56 list_node_unlink(struct list_node *node) 57 { 58 node->prev->next = node->next; 59 node->next->prev = node->prev; 60 return node; 61 } 62 63 inline void 64 list_push_head(struct list_node *restrict list, struct list_node *restrict node) 65 { 66 list_node_link(node, list, LIST_HEAD(list)); 67 } 68 69 inline void 70 list_push_tail(struct list_node *restrict list, struct list_node *restrict node) 71 { 72 list_node_link(node, LIST_TAIL(list), list); 73 } 74 75 inline struct list_node * 76 list_pop_head(struct list_node *list) 77 { 78 struct list_node *res = list_node_unlink(LIST_HEAD(list)); 79 return res; 80 } 81 82 inline struct list_node * 83 list_pop_tail(struct list_node *list) 84 { 85 struct list_node *res = list_node_unlink(LIST_TAIL(list)); 86 return res; 87 } 88 89 #endif /* LIST_H */ 90 91 #ifdef HEADER_IMPL 92 93 extern inline void 94 list_node_link(struct list_node *node, struct list_node *prev, struct list_node *next); 95 96 extern inline struct list_node * 97 list_node_unlink(struct list_node *node); 98 99 extern inline void 100 list_push_head(struct list_node *restrict list, struct list_node *restrict node); 101 102 extern inline void 103 list_push_tail(struct list_node *restrict list, struct list_node *restrict node); 104 105 extern inline struct list_node * 106 list_pop_head(struct list_node *list); 107 108 extern inline struct list_node * 109 list_pop_tail(struct list_node *list); 110 111 #endif /* HEADER_IMPL */