diff -r 26ae21face39 -r 668757098b73 src/linked_list.c --- a/src/linked_list.c Tue Sep 28 18:09:25 2021 +0200 +++ b/src/linked_list.c Tue Sep 28 18:22:00 2021 +0200 @@ -36,7 +36,7 @@ void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { size_t i = start_index; - void* cur = start; + void *cur = start; while (i != index && cur != NULL) { cur = *CX_LL_PTR(cur, loc_advance); i < index ? i++ : i--; @@ -93,45 +93,42 @@ /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ -struct cx_linked_list_node { +typedef struct { void *prev; void *next; char payload[]; -}; +} cx_linked_list_node; -#define CX_LL_LOC_PREV offsetof(struct cx_linked_list_node, prev) -#define CX_LL_LOC_NEXT offsetof(struct cx_linked_list_node, next) +#define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) +#define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) typedef struct { cx_list_s base; - void *begin; - void *end; - ptrdiff_t loc_prev; - ptrdiff_t loc_next; + cx_linked_list_node *begin; + cx_linked_list_node *end; } cx_linked_list; static int cx_ll_add(cx_list_s *list, void *elem) { cx_linked_list *ll = (cx_linked_list *) list; - struct cx_linked_list_node *node = cxMalloc(list->allocator, - sizeof(struct cx_linked_list_node) + list->itemsize); + cx_linked_list_node *node = cxMalloc(list->allocator, + sizeof(cx_linked_list_node) + list->itemsize); if (node == NULL) return 1; - node->next = node->prev = NULL; memcpy(node->payload, elem, list->itemsize); + node->next = NULL; - int ret = cx_linked_list_add( - &ll->begin, &ll->end, - CX_LL_LOC_PREV, CX_LL_LOC_NEXT, - node - ); - if (ret == 0) { - list->size++; - return 0; + if (ll->begin == NULL) { + ll->begin = ll->end = node; } else { - return ret; + // per contract of this linked list we know that end must be non-null + ll->end->next = node; + ll->end = node; } + list->size++; + + return 0; } static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { @@ -151,7 +148,7 @@ static void *cx_ll_at(cx_list_s *list, size_t index) { cx_linked_list *ll = (cx_linked_list *) list; - struct cx_linked_list_node *node; + cx_linked_list_node *node; if (index >= list->size) { node = NULL; } else if (index > list->size / 2) { @@ -167,9 +164,9 @@ cx_linked_list *ll = (cx_linked_list *) list; size_t index; - struct cx_linked_list_node* node = ll->begin; - for (index = 0 ; index < list->size ; index++) { - void* current = node->payload; + cx_linked_list_node *node = ll->begin; + for (index = 0; index < list->size; index++) { + void *current = node->payload; if (cmp(current, elem) == 0) { return index; } @@ -180,7 +177,7 @@ static void *cx_ll_last(cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; - struct cx_linked_list_node *last = cx_linked_list_last(NULL, &ll->end, CX_LL_LOC_NEXT); + cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT); return &last->payload; } @@ -194,7 +191,7 @@ }; CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { - cx_linked_list* list = cxMalloc(allocator, sizeof(cx_linked_list)); + cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); if (list == NULL) return NULL; @@ -207,18 +204,16 @@ list->begin = NULL; list->end = NULL; - list->loc_prev = CX_LL_LOC_PREV; - list->loc_next = CX_LL_LOC_NEXT; return (CxList) list; } void cxLinkedListDestroy(CxList list) { - cx_linked_list* ll = (cx_linked_list*) list; + cx_linked_list *ll = (cx_linked_list *) list; - struct cx_linked_list_node* node = ll->begin; + cx_linked_list_node *node = ll->begin; while (node) { - void* next = node->next; + void *next = node->next; cxFree(list->allocator, node); node = next; } @@ -234,13 +229,13 @@ ll->end = NULL; return 0; } else { - void *cur = ll->begin; - void *last; + cx_linked_list_node *cur = ll->begin; + cx_linked_list_node *last; size_t size = 0; do { last = cur; size++; - } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL); + } while ((cur = cur->next) != NULL); ll->end = last; ll->base.size = size; return size;