#pragma once #include #include #include #define TLL_PASTE2( a, b) a##b #define TLL_PASTE( a, b) TLL_PASTE2( a, b) /* Utility macro to generate a list element struct with a unique struct tag */ #define TLL_UNIQUE_INNER_STRUCT(TYPE, ID) \ struct TLL_PASTE(__tllist_ , ID) { \ TYPE item; \ struct TLL_PASTE(__tllist_, ID) *prev; \ struct TLL_PASTE(__tllist_, ID) *next; \ } *head, *tail; /* * Defines a new typed-list type, or directly instantiate a typed-list variable * * Example a, declare a variable (list of integers): * tll(int) my_list; * * Example b, declare a type, and then use the type: * tll(int, my_list_type); * struct my_list_type my_list; */ #define tll(TYPE) \ struct { \ TLL_UNIQUE_INNER_STRUCT(TYPE, __COUNTER__) \ size_t length; \ } /* Initializer: tll(int) my_list = tll_init(); */ #define tll_init() {.head = NULL, .tail = NULL, .length = 0} /* Length/size of list: printf("size: %zu\n", tll_length(my_list)); */ #define tll_length(list) (list).length /* Adds a new item to the back of the list */ #define tll_push_back(list, new_item) \ do { \ tll_insert_after(list, (list).tail, new_item); \ if ((list).head == NULL) \ (list).head = (list).tail; \ } while (0) /* Adds a new item to the front of the list */ #define tll_push_front(list, new_item) \ do { \ tll_insert_before(list, (list).head, new_item); \ if ((list).tail == NULL) \ (list).tail = (list).head; \ } while (0) /* * Iterates the list. is an iterator pointer. You can access the * list item with ->item: * * tll(int) my_list = vinit(); * tll_push_back(my_list, 5); * * tll_foreach(my_list i) { * printf("%d\n", i->item); * } */ #define tll_foreach(list, it) \ for (__typeof__(*(list).head) *it = (list).head, \ *it_next = it != NULL ? it->next : NULL; \ it != NULL; \ it = it_next, \ it_next = it_next != NULL ? it_next->next : NULL) /* Same as tll_foreach(), but iterates backwards */ #define tll_rforeach(list, it) \ for (__typeof__(*(list).tail) *it = (list).tail, \ *it_prev = it != NULL ? it->prev : NULL; \ it != NULL; \ it = it_prev, \ it_prev = it_prev != NULL ? it_prev->prev : NULL) /* * Inserts a new item after , which is an iterator. I.e. you can * only call this from inside a tll_foreach() or tll_rforeach() loop. */ #define tll_insert_after(list, it, new_item) \ do { \ __typeof__((list).head) __e = malloc(sizeof(*__e)); \ __e->item = (new_item); \ __e->prev = (it); \ __e->next = (it) != NULL ? (it)->next : NULL; \ if ((it) != NULL) { \ if ((it)->next != NULL) \ (it)->next->prev = __e; \ (it)->next = __e; \ } \ if ((it) == (list).tail) \ (list).tail = __e; \ (list).length++; \ } while (0) /* * Inserts a new item before , which is an iterator. I.e. you can * only call this from inside a tll_foreach() or tll_rforeach() loop. */ #define tll_insert_before(list, it, new_item) \ do { \ __typeof__((list).head) __e = malloc(sizeof(*__e)); \ __e->item = (new_item); \ __e->prev = (it) != NULL ? (it)->prev : NULL; \ __e->next = (it); \ if ((it) != NULL) { \ if ((it)->prev != NULL) \ (it)->prev->next = __e; \ (it)->prev = __e; \ } \ if ((it) == (list).head) \ (list).head = __e; \ (list).length++; \ } while (0) /* * Removes an entry from the list. is an iterator. I.e. you can * only call this from inside a tll_foreach() or tll_rforeach() loop. */ #define tll_remove(list, it) \ do { \ assert((list).length > 0); \ __typeof__((list).head) __prev = it->prev; \ __typeof__((list).head) __next = it->next; \ if (__prev != NULL) \ __prev->next = __next; \ else \ (list).head = __next; \ if (__next != NULL) \ __next->prev = __prev; \ else \ (list).tail = __prev; \ free(it); \ (list).length--; \ } while (0) /* Same as tll_remove(), but calls free_callback(it->item) */ #define tll_remove_and_free(list, it, free_callback) \ do { \ free_callback((it)->item); \ tll_remove((list), (it)); \ } while (0) #define tll_front(list) (list).head->item #define tll_back(list) (list).tail->item /* * Removes the first element from the list, and returns it (note: * returns the *actual* item, not an iterator. */ #define tll_pop_front(list) __extension__ \ ({ \ __typeof__((list).head) it = (list).head; \ __typeof__((list).head->item) __ret = it->item; \ tll_remove((list), it); \ __ret; \ }) /* Same as tll_pop_front(), but returns/removes the *last* element */ #define tll_pop_back(list) __extension__ \ ({ \ __typeof__((list).tail) it = (list).tail; \ __typeof__((list).tail->item) __ret = it->item; \ tll_remove((list), it); \ __ret; \ }) /* Frees the list. This call is *not* needed if the list is already empty. */ #define tll_free(list) \ do { \ tll_foreach(list, __it) \ free(__it); \ (list).length = 0; \ (list).head = (list).tail = NULL; \ } while (0) /* Same as tll_free(), but also calls free_callback(item) for every item */ #define tll_free_and_free(list, free_callback) \ do { \ tll_foreach(list, __it) { \ free_callback(__it->item); \ free(__it); \ } \ (list).length = 0; \ (list).head = (list).tail = NULL; \ } while (0) #define tll_sort(list, cmp) \ do { \ __typeof((list).head) __p; \ __typeof((list).head) __q; \ __typeof((list).head) __e; \ __typeof((list).head) __t; \ int __insize, __nmerges, __p_size, __q_size; \ if ((list).head == NULL) \ break; \ __insize = 1; \ while (1) { \ __p = (list).head; \ (list).head = NULL; \ __t = NULL; \ __nmerges = 0; \ while (__p != NULL) { \ __nmerges++; \ __q = __p; \ __p_size = 0; \ for (int _i = 0; _i < __insize; _i++) { \ __p_size++; \ __q = __q->next; \ if (__q == NULL) \ break; \ } \ __q_size = __insize; \ while (__p_size > 0 || (__q_size > 0 && __q != NULL)) { \ if (__p_size == 0) { \ __e = __q; \ __q = __q->next; \ __q_size--; \ } else if (__q_size == 0 || __q == NULL) { \ __e = __p; \ __p = __p->next; \ __p_size--; \ } else if (cmp(__p->item, __q->item) <= 0) { \ __e = __p; \ __p = __p->next; \ __p_size--; \ } else { \ __e = __q; \ __q = __q->next; \ __q_size--; \ } \ if (__t != NULL) { \ __t->next = __e; \ } else { \ (list).head = __e; \ } \ __e->prev = __t; \ __t = __e; \ } \ __p = __q; \ } \ (list).tail = __t; \ __t->next = NULL; \ __insize *= 2; \ if (__nmerges <= 1) \ break; \ } \ } while (0)