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);
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) {
node = ll_advance(node);
index++;
} while (node != NULL);
- return index;
+ return -1;
}
void *cx_linked_list_first(
#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,
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 ?
}
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
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);
// 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;
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);
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;
}
}
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;
// 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;
// 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;
}
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,
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(
}
}
- 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;
} 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;
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
) {
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--;
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--;
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 = {
CxList *cxLinkedListCreate(
CxAllocator const *allocator,
- CxListComparator comparator,
+ cx_compare_func comparator,
size_t item_size
) {
if (allocator == NULL) {
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);
}
develop.uap-core.de/git / uwplayer.git / blobdiff