X-Git-Url: https://develop.uap-core.de/gitweb/uwplayer.git/blobdiff_plain/5cb490b04836ef624cdd0ba975ee5c2ff2e51a23..01d5015ba093f8c5fdb18b669943c7da6450e72f:/ucx/linked_list.c

diff --git a/ucx/linked_list.c b/ucx/linked_list.c
index c74da5f..7a8d33d 100644
--- a/ucx/linked_list.c
+++ b/ucx/linked_list.c
@@ -56,11 +56,11 @@ void *cx_linked_list_at(
     return (void *) cur;
 }
 
-size_t cx_linked_list_find(
+ssize_t cx_linked_list_find(
         void const *start,
         ptrdiff_t loc_advance,
         ptrdiff_t loc_data,
-        CxListComparator cmp_func,
+        cx_compare_func cmp_func,
         void const *elem
 ) {
     assert(start != NULL);
@@ -69,7 +69,7 @@ size_t cx_linked_list_find(
     assert(cmp_func);
 
     void const *node = start;
-    size_t index = 0;
+    ssize_t index = 0;
     do {
         void *current = ll_data(node);
         if (cmp_func(current, elem) == 0) {
@@ -78,7 +78,7 @@ size_t cx_linked_list_find(
         node = ll_advance(node);
         index++;
     } while (node != NULL);
-    return index;
+    return -1;
 }
 
 void *cx_linked_list_first(
@@ -283,7 +283,7 @@ size_t cx_linked_list_size(
 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
 #endif
 
-static void *cx_linked_list_sort_merge(
+static void cx_linked_list_sort_merge(
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next,
         ptrdiff_t loc_data,
@@ -291,7 +291,9 @@ static void *cx_linked_list_sort_merge(
         void *ls,
         void *le,
         void *re,
-        CxListComparator cmp_func
+        cx_compare_func cmp_func,
+        void **begin,
+        void **end
 ) {
     void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
     void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
@@ -330,11 +332,11 @@ static void *cx_linked_list_sort_merge(
     }
     ll_next(sorted[length - 1]) = NULL;
 
-    void *ret = sorted[0];
+    *begin = sorted[0];
+    *end = sorted[length-1];
     if (sorted != sbo) {
         free(sorted);
     }
-    return ret;
 }
 
 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
@@ -343,7 +345,7 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next,
         ptrdiff_t loc_data,
-        CxListComparator cmp_func
+        cx_compare_func cmp_func
 ) {
     assert(begin != NULL);
     assert(loc_next >= 0);
@@ -355,6 +357,9 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun
     // set start node
     ls = *begin;
 
+    // early exit when this list is empty
+    if (ls == NULL) return;
+
     // check how many elements are already sorted
     lc = ls;
     size_t ln = 1;
@@ -377,8 +382,10 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun
         re = ll_next(rc);
 
         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
-        void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
-                                                 ln + rn, ls, le, re, cmp_func);
+        void *sorted_begin, *sorted_end;
+        cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
+                                  ln + rn, ls, le, re, cmp_func,
+                                  &sorted_begin, &sorted_end);
 
         // Something left? Sort it!
         size_t remainder_length = cx_linked_list_size(re, loc_next);
@@ -387,14 +394,13 @@ void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive fun
             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
 
             // merge sorted list with (also sorted) remainder
-            *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
-                                               ln + rn + remainder_length,
-                                               sorted, remainder, NULL, cmp_func);
-        } else {
-            // no remainder - we've got our sorted list
-            *begin = sorted;
+            cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
+                                      ln + rn + remainder_length,
+                                      sorted_begin, remainder, NULL, cmp_func,
+                                      &sorted_begin, &sorted_end);
         }
-        if (end) *end = cx_linked_list_last(sorted, loc_next);
+        *begin = sorted_begin;
+        if (end) *end = sorted_end;
     }
 }
 
@@ -403,7 +409,7 @@ int cx_linked_list_compare(
         void const *begin_right,
         ptrdiff_t loc_advance,
         ptrdiff_t loc_data,
-        CxListComparator cmp_func
+        cx_compare_func cmp_func
 ) {
     void const *left = begin_left, *right = begin_right;
 
@@ -494,14 +500,14 @@ static int cx_ll_insert_at(
 
     // create the new new_node
     cx_linked_list_node *new_node = cxMalloc(list->allocator,
-                                             sizeof(cx_linked_list_node) + list->itemsize);
+                                             sizeof(cx_linked_list_node) + list->item_size);
 
     // sortir if failed
     if (new_node == NULL) return 1;
 
     // initialize new new_node
     new_node->prev = new_node->next = NULL;
-    memcpy(new_node->payload, elem, list->itemsize);
+    memcpy(new_node->payload, elem, list->item_size);
 
     // insert
     cx_linked_list *ll = (cx_linked_list *) list;
@@ -542,7 +548,7 @@ static size_t cx_ll_insert_array(
     // we can add the remaining nodes and immedately advance to the inserted node
     char const *source = array;
     for (size_t i = 1; i < n; i++) {
-        source += list->itemsize;
+        source += list->item_size;
         if (0 != cx_ll_insert_at(list, node, source)) {
             return i;
         }
@@ -570,9 +576,7 @@ static int cx_ll_remove(
     if (node == NULL) return 1;
 
     // element destruction
-    if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
-        cx_list_invoke_destructor(list, node->payload);
-    }
+    cx_invoke_destructor(list, node->payload);
 
     // remove
     cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
@@ -592,44 +596,18 @@ static void cx_ll_clear(struct cx_list_s *list) {
 
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *node = ll->begin;
-
-    // looks super redundant, but avoids repeatedly checking
-    // the destructor type for each element
-    switch (list->content_destructor_type) {
-        case CX_DESTRUCTOR_SIMPLE: {
-            while (node != NULL) {
-                cx_list_invoke_simple_destructor(list, node->payload);
-                cx_linked_list_node *next = node->next;
-                cxFree(list->allocator, node);
-                node = next;
-            }
-            break;
-        }
-        case CX_DESTRUCTOR_ADVANCED: {
-            while (node != NULL) {
-                cx_list_invoke_advanced_destructor(list, node->payload);
-                cx_linked_list_node *next = node->next;
-                cxFree(list->allocator, node);
-                node = next;
-            }
-            break;
-        }
-        case CX_DESTRUCTOR_NONE: {
-            while (node != NULL) {
-                cx_linked_list_node *next = node->next;
-                cxFree(list->allocator, node);
-                node = next;
-            }
-            break;
-        }
+    while (node != NULL) {
+        cx_invoke_destructor(list, node->payload);
+        cx_linked_list_node *next = node->next;
+        cxFree(list->allocator, node);
+        node = next;
     }
-
     ll->begin = ll->end = NULL;
     list->size = 0;
 }
 
 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
-#define CX_LINKED_LIST_SWAP_SBO_SIZE 16
+#define CX_LINKED_LIST_SWAP_SBO_SIZE 128
 #endif
 
 static int cx_ll_swap(
@@ -708,7 +686,7 @@ static int cx_ll_swap(
         }
     }
 
-    if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
+    if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
         cx_linked_list_node *prev = nleft->prev;
         cx_linked_list_node *next = nright->next;
         cx_linked_list_node *midstart = nleft->next;
@@ -740,9 +718,9 @@ static int cx_ll_swap(
     } else {
         // swap payloads to avoid relinking
         char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
-        memcpy(buf, nleft->payload, list->itemsize);
-        memcpy(nleft->payload, nright->payload, list->itemsize);
-        memcpy(nright->payload, buf, list->itemsize);
+        memcpy(buf, nleft->payload, list->item_size);
+        memcpy(nleft->payload, nright->payload, list->item_size);
+        memcpy(nright->payload, buf, list->item_size);
     }
 
     return 0;
@@ -757,7 +735,7 @@ static void *cx_ll_at(
     return node == NULL ? NULL : node->payload;
 }
 
-static size_t cx_ll_find(
+static ssize_t cx_ll_find(
         struct cx_list_s const *list,
         void const *elem
 ) {
@@ -803,9 +781,7 @@ static void cx_ll_iter_next(void *it) {
         cx_linked_list *ll = iter->src_handle;
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->next;
-        if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
-            cx_list_invoke_destructor(list, node->payload);
-        }
+        cx_invoke_destructor(list, node->payload);
         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
         list->size--;
@@ -828,9 +804,7 @@ static void cx_ll_iter_prev(void *it) {
         cx_linked_list_node *node = iter->elem_handle;
         iter->elem_handle = node->prev;
         iter->index--;
-        if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
-            cx_list_invoke_destructor(list, node->payload);
-        }
+        cx_invoke_destructor(list, node->payload);
         cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
                               CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
         list->size--;
@@ -902,11 +876,13 @@ static void cx_ll_destructor(CxList *list) {
 
     cx_linked_list_node *node = ll->begin;
     while (node) {
+        cx_invoke_destructor(list, node->payload);
         void *next = node->next;
         cxFree(list->allocator, node);
         node = next;
     }
-    // do not free the list pointer, this is just a destructor!
+
+    cxFree(list->allocator, list);
 }
 
 static cx_list_class cx_linked_list_class = {
@@ -927,7 +903,7 @@ static cx_list_class cx_linked_list_class = {
 
 CxList *cxLinkedListCreate(
         CxAllocator const *allocator,
-        CxListComparator comparator,
+        cx_compare_func comparator,
         size_t item_size
 ) {
     if (allocator == NULL) {
@@ -940,10 +916,9 @@ CxList *cxLinkedListCreate(
     list->base.cl = &cx_linked_list_class;
     list->base.allocator = allocator;
     list->base.cmpfunc = comparator;
-    list->base.capacity = SIZE_MAX;
 
     if (item_size > 0) {
-        list->base.itemsize = item_size;
+        list->base.item_size = item_size;
     } else {
         cxListStorePointers((CxList *) list);
     }