1 #pragma once 2 3 #include <stdlib.h> 4 #include <stddef.h> 5 #include <assert.h> 6 7 #define TLL_PASTE2( a, b) a##b 8 #define TLL_PASTE( a, b) TLL_PASTE2( a, b) 9 10 /* Utility macro to generate a list element struct with a unique struct tag */ 11 #define TLL_UNIQUE_INNER_STRUCT(TYPE, ID) \ 12 struct TLL_PASTE(__tllist_ , ID) { \ 13 TYPE item; \ 14 struct TLL_PASTE(__tllist_, ID) *prev; \ 15 struct TLL_PASTE(__tllist_, ID) *next; \ 16 } *head, *tail; 17 18 /* 19 * Defines a new typed-list type, or directly instantiate a typed-list variable 20 * 21 * Example a, declare a variable (list of integers): 22 * tll(int) my_list; 23 * 24 * Example b, declare a type, and then use the type: 25 * tll(int, my_list_type); 26 * struct my_list_type my_list; 27 */ 28 #define tll(TYPE) \ 29 struct { \ 30 TLL_UNIQUE_INNER_STRUCT(TYPE, __COUNTER__) \ 31 size_t length; \ 32 } 33 34 /* Initializer: tll(int) my_list = tll_init(); */ 35 #define tll_init() {.head = NULL, .tail = NULL, .length = 0} 36 37 /* Length/size of list: printf("size: %zu\n", tll_length(my_list)); */ 38 #define tll_length(list) (list).length 39 40 /* Adds a new item to the back of the list */ 41 #define tll_push_back(list, new_item) \ 42 do { \ 43 tll_insert_after(list, (list).tail, new_item); \ 44 if ((list).head == NULL) \ 45 (list).head = (list).tail; \ 46 } while (0) 47 48 /* Adds a new item to the front of the list */ 49 #define tll_push_front(list, new_item) \ 50 do { \ 51 tll_insert_before(list, (list).head, new_item); \ 52 if ((list).tail == NULL) \ 53 (list).tail = (list).head; \ 54 } while (0) 55 56 /* 57 * Iterates the list. <it> is an iterator pointer. You can access the 58 * list item with ->item: 59 * 60 * tll(int) my_list = vinit(); 61 * tll_push_back(my_list, 5); 62 * 63 * tll_foreach(my_list i) { 64 * printf("%d\n", i->item); 65 * } 66 */ 67 #define tll_foreach(list, it) \ 68 for (__typeof__(*(list).head) *it = (list).head, \ 69 *it_next = it != NULL ? it->next : NULL; \ 70 it != NULL; \ 71 it = it_next, \ 72 it_next = it_next != NULL ? it_next->next : NULL) 73 74 /* Same as tll_foreach(), but iterates backwards */ 75 #define tll_rforeach(list, it) \ 76 for (__typeof__(*(list).tail) *it = (list).tail, \ 77 *it_prev = it != NULL ? it->prev : NULL; \ 78 it != NULL; \ 79 it = it_prev, \ 80 it_prev = it_prev != NULL ? it_prev->prev : NULL) 81 82 /* 83 * Inserts a new item after <it>, which is an iterator. I.e. you can 84 * only call this from inside a tll_foreach() or tll_rforeach() loop. 85 */ 86 #define tll_insert_after(list, it, new_item) \ 87 do { \ 88 __typeof__((list).head) __e = malloc(sizeof(*__e)); \ 89 __e->item = (new_item); \ 90 __e->prev = (it); \ 91 __e->next = (it) != NULL ? (it)->next : NULL; \ 92 if ((it) != NULL) { \ 93 if ((it)->next != NULL) \ 94 (it)->next->prev = __e; \ 95 (it)->next = __e; \ 96 } \ 97 if ((it) == (list).tail) \ 98 (list).tail = __e; \ 99 (list).length++; \ 100 } while (0) 101 102 /* 103 * Inserts a new item before <it>, which is an iterator. I.e. you can 104 * only call this from inside a tll_foreach() or tll_rforeach() loop. 105 */ 106 #define tll_insert_before(list, it, new_item) \ 107 do { \ 108 __typeof__((list).head) __e = malloc(sizeof(*__e)); \ 109 __e->item = (new_item); \ 110 __e->prev = (it) != NULL ? (it)->prev : NULL; \ 111 __e->next = (it); \ 112 if ((it) != NULL) { \ 113 if ((it)->prev != NULL) \ 114 (it)->prev->next = __e; \ 115 (it)->prev = __e; \ 116 } \ 117 if ((it) == (list).head) \ 118 (list).head = __e; \ 119 (list).length++; \ 120 } while (0) 121 122 /* 123 * Removes an entry from the list. <it> is an iterator. I.e. you can 124 * only call this from inside a tll_foreach() or tll_rforeach() loop. 125 */ 126 #define tll_remove(list, it) \ 127 do { \ 128 assert((list).length > 0); \ 129 __typeof__((list).head) __prev = it->prev; \ 130 __typeof__((list).head) __next = it->next; \ 131 if (__prev != NULL) \ 132 __prev->next = __next; \ 133 else \ 134 (list).head = __next; \ 135 if (__next != NULL) \ 136 __next->prev = __prev; \ 137 else \ 138 (list).tail = __prev; \ 139 free(it); \ 140 (list).length--; \ 141 } while (0) 142 143 /* Same as tll_remove(), but calls free_callback(it->item) */ 144 #define tll_remove_and_free(list, it, free_callback) \ 145 do { \ 146 free_callback((it)->item); \ 147 tll_remove((list), (it)); \ 148 } while (0) 149 150 #define tll_front(list) (list).head->item 151 #define tll_back(list) (list).tail->item 152 153 /* 154 * Removes the first element from the list, and returns it (note: 155 * returns the *actual* item, not an iterator. 156 */ 157 #define tll_pop_front(list) __extension__ \ 158 ({ \ 159 __typeof__((list).head) it = (list).head; \ 160 __typeof__((list).head->item) __ret = it->item; \ 161 tll_remove((list), it); \ 162 __ret; \ 163 }) 164 165 /* Same as tll_pop_front(), but returns/removes the *last* element */ 166 #define tll_pop_back(list) __extension__ \ 167 ({ \ 168 __typeof__((list).tail) it = (list).tail; \ 169 __typeof__((list).tail->item) __ret = it->item; \ 170 tll_remove((list), it); \ 171 __ret; \ 172 }) 173 174 /* Frees the list. This call is *not* needed if the list is already empty. */ 175 #define tll_free(list) \ 176 do { \ 177 tll_foreach(list, __it) \ 178 free(__it); \ 179 (list).length = 0; \ 180 (list).head = (list).tail = NULL; \ 181 } while (0) 182 183 /* Same as tll_free(), but also calls free_callback(item) for every item */ 184 #define tll_free_and_free(list, free_callback) \ 185 do { \ 186 tll_foreach(list, __it) { \ 187 free_callback(__it->item); \ 188 free(__it); \ 189 } \ 190 (list).length = 0; \ 191 (list).head = (list).tail = NULL; \ 192 } while (0) 193