--- a/ucx/linked_list.c Sat Apr 20 13:01:58 2024 +0200
+++ b/ucx/linked_list.c Thu May 23 22:35:45 2024 +0200
@@ -28,6 +28,7 @@
#include "cx/linked_list.h"
#include "cx/utils.h"
+#include "cx/compare.h"
#include <string.h>
#include <assert.h>
@@ -63,6 +64,23 @@
cx_compare_func cmp_func,
void const *elem
) {
+ 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,
+ void const *start,
+ ptrdiff_t loc_advance,
+ ptrdiff_t loc_data,
+ cx_compare_func cmp_func,
+ void const *elem
+) {
+ assert(result != NULL);
assert(start != NULL);
assert(loc_advance >= 0);
assert(loc_data >= 0);
@@ -73,11 +91,13 @@
do {
void *current = ll_data(node);
if (cmp_func(current, elem) == 0) {
+ *result = (void*) node;
return index;
}
node = ll_advance(node);
index++;
} while (node != NULL);
+ *result = NULL;
return -1;
}
@@ -460,8 +480,6 @@
// HIGH LEVEL LINKED LIST IMPLEMENTATION
-bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
-
typedef struct cx_linked_list_node cx_linked_list_node;
struct cx_linked_list_node {
cx_linked_list_node *prev;
@@ -483,10 +501,10 @@
cx_linked_list const *list,
size_t index
) {
- if (index >= list->base.size) {
+ if (index >= list->base.collection.size) {
return NULL;
- } else if (index > list->base.size / 2) {
- return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
+ } else if (index > list->base.collection.size / 2) {
+ return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
} else {
return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
}
@@ -499,15 +517,15 @@
) {
// create the new new_node
- cx_linked_list_node *new_node = cxMalloc(list->allocator,
- sizeof(cx_linked_list_node) + list->item_size);
+ cx_linked_list_node *new_node = cxMalloc(list->collection.allocator,
+ sizeof(cx_linked_list_node) + list->collection.elem_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->item_size);
+ memcpy(new_node->payload, elem, list->collection.elem_size);
// insert
cx_linked_list *ll = (cx_linked_list *) list;
@@ -518,7 +536,7 @@
);
// increase the size and return
- list->size++;
+ list->collection.size++;
return 0;
}
@@ -529,7 +547,7 @@
size_t n
) {
// out-of bounds and corner case check
- if (index > list->size || n == 0) return 0;
+ if (index > list->collection.size || n == 0) return 0;
// find position efficiently
cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
@@ -548,7 +566,7 @@
// 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->item_size;
+ source += list->collection.elem_size;
if (0 != cx_ll_insert_at(list, node, source)) {
return i;
}
@@ -583,44 +601,45 @@
CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
// adjust size
- list->size--;
+ list->collection.size--;
// free and return
- cxFree(list->allocator, node);
+ cxFree(list->collection.allocator, node);
return 0;
}
static void cx_ll_clear(struct cx_list_s *list) {
- if (list->size == 0) return;
+ if (list->collection.size == 0) return;
cx_linked_list *ll = (cx_linked_list *) list;
cx_linked_list_node *node = ll->begin;
while (node != NULL) {
cx_invoke_destructor(list, node->payload);
cx_linked_list_node *next = node->next;
- cxFree(list->allocator, node);
+ cxFree(list->collection.allocator, node);
node = next;
}
ll->begin = ll->end = NULL;
- list->size = 0;
+ list->collection.size = 0;
}
#ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
#define CX_LINKED_LIST_SWAP_SBO_SIZE 128
#endif
+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,
size_t j
) {
- if (i >= list->size || j >= list->size) return 1;
+ if (i >= list->collection.size || j >= list->collection.size) return 1;
if (i == j) return 0;
// perform an optimized search that finds both elements in one run
cx_linked_list *ll = (cx_linked_list *) list;
- size_t mid = list->size / 2;
+ size_t mid = list->collection.size / 2;
size_t left, right;
if (i < j) {
left = i;
@@ -633,6 +652,7 @@
if (left < mid && right < mid) {
// case 1: both items left from mid
nleft = cx_ll_node_at(ll, left);
+ assert(nleft != NULL);
nright = nleft;
for (size_t c = left; c < right; c++) {
nright = nright->next;
@@ -640,6 +660,7 @@
} else if (left >= mid && right >= mid) {
// case 2: both items right from mid
nright = cx_ll_node_at(ll, right);
+ assert(nright != NULL);
nleft = nright;
for (size_t c = right; c > left; c--) {
nleft = nleft->prev;
@@ -650,7 +671,7 @@
// chose the closest to begin / end
size_t closest;
size_t other;
- size_t diff2boundary = list->size - right - 1;
+ size_t diff2boundary = list->collection.size - right - 1;
if (left <= diff2boundary) {
closest = left;
other = right;
@@ -686,7 +707,7 @@
}
}
- if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
+ 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;
@@ -718,9 +739,9 @@
} else {
// swap payloads to avoid relinking
char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
- memcpy(buf, nleft->payload, list->item_size);
- memcpy(nleft->payload, nright->payload, list->item_size);
- memcpy(nright->payload, buf, list->item_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);
}
return 0;
@@ -735,20 +756,42 @@
return node == NULL ? NULL : node->payload;
}
-static ssize_t cx_ll_find(
- struct cx_list_s const *list,
- void const *elem
+static ssize_t cx_ll_find_remove(
+ struct cx_list_s *list,
+ void const *elem,
+ bool remove
) {
- return cx_linked_list_find(((cx_linked_list *) list)->begin,
- CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
- list->cmpfunc, elem);
+ 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
+ );
+ }
}
static void cx_ll_sort(struct cx_list_s *list) {
cx_linked_list *ll = (cx_linked_list *) list;
cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
- list->cmpfunc);
+ list->collection.cmpfunc);
}
static void cx_ll_reverse(struct cx_list_s *list) {
@@ -764,7 +807,7 @@
cx_linked_list *right = (cx_linked_list *) other;
return cx_linked_list_compare(left->begin, right->begin,
CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
- list->cmpfunc);
+ list->collection.cmpfunc);
}
static bool cx_ll_iter_valid(void const *it) {
@@ -773,21 +816,19 @@
}
static void cx_ll_iter_next(void *it) {
- struct cx_iterator_base_s *itbase = it;
- if (itbase->remove) {
- itbase->remove = false;
- struct cx_mut_iterator_s *iter = it;
- struct cx_list_s *list = iter->src_handle;
- cx_linked_list *ll = iter->src_handle;
+ struct cx_iterator_s *iter = it;
+ if (iter->base.remove) {
+ iter->base.remove = false;
+ struct cx_list_s *list = iter->src_handle.m;
+ cx_linked_list *ll = iter->src_handle.m;
cx_linked_list_node *node = iter->elem_handle;
iter->elem_handle = node->next;
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--;
- cxFree(list->allocator, node);
+ list->collection.size--;
+ cxFree(list->collection.allocator, node);
} else {
- struct cx_iterator_s *iter = it;
iter->index++;
cx_linked_list_node *node = iter->elem_handle;
iter->elem_handle = node->next;
@@ -795,22 +836,20 @@
}
static void cx_ll_iter_prev(void *it) {
- struct cx_iterator_base_s *itbase = it;
- if (itbase->remove) {
- itbase->remove = false;
- struct cx_mut_iterator_s *iter = it;
- struct cx_list_s *list = iter->src_handle;
- cx_linked_list *ll = iter->src_handle;
+ struct cx_iterator_s *iter = it;
+ if (iter->base.remove) {
+ iter->base.remove = false;
+ struct cx_list_s *list = iter->src_handle.m;
+ cx_linked_list *ll = iter->src_handle.m;
cx_linked_list_node *node = iter->elem_handle;
iter->elem_handle = node->prev;
iter->index--;
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--;
- cxFree(list->allocator, node);
+ list->collection.size--;
+ cxFree(list->collection.allocator, node);
} else {
- struct cx_iterator_s *iter = it;
iter->index--;
cx_linked_list_node *node = iter->elem_handle;
iter->elem_handle = node->prev;
@@ -823,16 +862,6 @@
return node->payload;
}
-static bool cx_ll_iter_flag_rm(void *it) {
- struct cx_iterator_base_s *iter = it;
- if (iter->mutating) {
- iter->remove = true;
- return true;
- } else {
- return false;
- }
-}
-
static CxIterator cx_ll_iterator(
struct cx_list_s const *list,
size_t index,
@@ -840,23 +869,24 @@
) {
CxIterator iter;
iter.index = index;
- iter.src_handle = list;
+ iter.src_handle.c = list;
iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
+ iter.elem_size = list->collection.elem_size;
+ iter.elem_count = list->collection.size;
iter.base.valid = cx_ll_iter_valid;
iter.base.current = cx_ll_iter_current;
iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
- iter.base.flag_removal = cx_ll_iter_flag_rm;
iter.base.mutating = false;
iter.base.remove = false;
return iter;
}
static int cx_ll_insert_iter(
- CxMutIterator *iter,
+ CxIterator *iter,
void const *elem,
int prepend
) {
- struct cx_list_s *list = iter->src_handle;
+ struct cx_list_s *list = iter->src_handle.m;
cx_linked_list_node *node = iter->elem_handle;
if (node != NULL) {
assert(prepend >= 0 && prepend <= 1);
@@ -865,8 +895,8 @@
iter->index += prepend * (0 == result);
return result;
} else {
- int result = cx_ll_insert_element(list, list->size, elem);
- iter->index = list->size;
+ int result = cx_ll_insert_element(list, list->collection.size, elem);
+ iter->index = list->collection.size;
return result;
}
}
@@ -878,11 +908,11 @@
while (node) {
cx_invoke_destructor(list, node->payload);
void *next = node->next;
- cxFree(list->allocator, node);
+ cxFree(list->collection.allocator, node);
node = next;
}
- cxFree(list->allocator, list);
+ cxFree(list->collection.allocator, list);
}
static cx_list_class cx_linked_list_class = {
@@ -894,7 +924,7 @@
cx_ll_clear,
cx_ll_swap,
cx_ll_at,
- cx_ll_find,
+ cx_ll_find_remove,
cx_ll_sort,
cx_ll_compare,
cx_ll_reverse,
@@ -904,7 +934,7 @@
CxList *cxLinkedListCreate(
CxAllocator const *allocator,
cx_compare_func comparator,
- size_t item_size
+ size_t elem_size
) {
if (allocator == NULL) {
allocator = cxDefaultAllocator;
@@ -914,12 +944,13 @@
if (list == NULL) return NULL;
list->base.cl = &cx_linked_list_class;
- list->base.allocator = allocator;
- list->base.cmpfunc = comparator;
+ list->base.collection.allocator = allocator;
- if (item_size > 0) {
- list->base.item_size = item_size;
+ 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);
}
