src/linked_list.c

changeset 446
668757098b73
parent 441
7d5a06e32aa8
child 447
87b2cdd668ed
--- 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;

mercurial