--- a/ucx/linked_list.c Sat Feb 22 18:10:36 2025 +0100
+++ b/ucx/linked_list.c Sun Feb 23 14:28:47 2025 +0100
@@ -56,48 +56,33 @@
return (void *) cur;
}
-ssize_t cx_linked_list_find(
+void *cx_linked_list_find(
const void *start,
ptrdiff_t loc_advance,
ptrdiff_t loc_data,
cx_compare_func cmp_func,
- const void *elem
+ const void *elem,
+ size_t *found_index
) {
- void *dummy;
- return cx_linked_list_find_node(
- &dummy, start,
- loc_advance, loc_data,
- cmp_func, elem
- );
-}
-
-ssize_t cx_linked_list_find_node(
- void **result,
- const void *start,
- ptrdiff_t loc_advance,
- ptrdiff_t loc_data,
- cx_compare_func cmp_func,
- const void *elem
-) {
- assert(result != NULL);
assert(start != NULL);
assert(loc_advance >= 0);
assert(loc_data >= 0);
assert(cmp_func);
- const void *node = start;
- ssize_t index = 0;
+ void *node = (void*) start;
+ size_t index = 0;
do {
void *current = ll_data(node);
if (cmp_func(current, elem) == 0) {
- *result = (void *) node;
- return index;
+ if (found_index != NULL) {
+ *found_index = index;
+ }
+ return node;
}
node = ll_advance(node);
index++;
} while (node != NULL);
- *result = NULL;
- return -1;
+ return NULL;
}
void *cx_linked_list_first(
@@ -811,11 +796,6 @@
list->collection.size = 0;
}
-#ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
-#define CX_LINKED_LIST_SWAP_SBO_SIZE 128
-#endif
-const unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
-
static int cx_ll_swap(
struct cx_list_s *list,
size_t i,
@@ -894,41 +874,33 @@
}
}
- if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
- cx_linked_list_node *prev = nleft->prev;
- cx_linked_list_node *next = nright->next;
- cx_linked_list_node *midstart = nleft->next;
- cx_linked_list_node *midend = nright->prev;
+ cx_linked_list_node *prev = nleft->prev;
+ cx_linked_list_node *next = nright->next;
+ cx_linked_list_node *midstart = nleft->next;
+ cx_linked_list_node *midend = nright->prev;
- if (prev == NULL) {
- ll->begin = nright;
- } else {
- prev->next = nright;
- }
- nright->prev = prev;
- if (midstart == nright) {
- // special case: both nodes are adjacent
- nright->next = nleft;
- nleft->prev = nright;
- } else {
- // likely case: a chain is between the two nodes
- nright->next = midstart;
- midstart->prev = nright;
- midend->next = nleft;
- nleft->prev = midend;
- }
- nleft->next = next;
- if (next == NULL) {
- ll->end = nleft;
- } else {
- next->prev = nleft;
- }
+ if (prev == NULL) {
+ ll->begin = nright;
+ } else {
+ prev->next = nright;
+ }
+ nright->prev = prev;
+ if (midstart == nright) {
+ // special case: both nodes are adjacent
+ nright->next = nleft;
+ nleft->prev = nright;
} else {
- // swap payloads to avoid relinking
- char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
- memcpy(buf, nleft->payload, list->collection.elem_size);
- memcpy(nleft->payload, nright->payload, list->collection.elem_size);
- memcpy(nright->payload, buf, list->collection.elem_size);
+ // likely case: a chain is between the two nodes
+ nright->next = midstart;
+ midstart->prev = nright;
+ midend->next = nleft;
+ nleft->prev = midend;
+ }
+ nleft->next = next;
+ if (next == NULL) {
+ ll->end = nleft;
+ } else {
+ next->prev = nleft;
}
return 0;
@@ -943,35 +915,30 @@
return node == NULL ? NULL : node->payload;
}
-static ssize_t cx_ll_find_remove(
+static size_t cx_ll_find_remove(
struct cx_list_s *list,
const void *elem,
bool remove
) {
+ size_t index;
+ cx_linked_list *ll = ((cx_linked_list *) list);
+ cx_linked_list_node *node = cx_linked_list_find(
+ ll->begin,
+ CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+ list->collection.cmpfunc, elem,
+ &index
+ );
+ if (node == NULL) {
+ return list->collection.size;
+ }
if (remove) {
- cx_linked_list *ll = ((cx_linked_list *) list);
- cx_linked_list_node *node;
- ssize_t index = cx_linked_list_find_node(
- (void **) &node,
- ll->begin,
- CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
- list->collection.cmpfunc, elem
- );
- if (node != NULL) {
- 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->collection.size--;
- cxFree(list->collection.allocator, node);
- }
- return index;
- } else {
- return cx_linked_list_find(
- ((cx_linked_list *) list)->begin,
- CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
- list->collection.cmpfunc, elem
- );
+ 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->collection.size--;
+ cxFree(list->collection.allocator, node);
}
+ return index;
}
static void cx_ll_sort(struct cx_list_s *list) {
@@ -1138,17 +1105,8 @@
cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
if (list == NULL) return NULL;
-
- list->base.cl = &cx_linked_list_class;
- list->base.collection.allocator = allocator;
-
- if (elem_size > 0) {
- list->base.collection.elem_size = elem_size;
- list->base.collection.cmpfunc = comparator;
- } else {
- list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
- cxListStorePointers((CxList *) list);
- }
+ cx_list_init((CxList*)list, &cx_linked_list_class,
+ allocator, comparator, elem_size);
return (CxList *) list;
}