--- a/src/ucx/linked_list.c Sat Mar 25 17:18:51 2023 +0100
+++ b/src/ucx/linked_list.c Fri May 05 18:02:11 2023 +0200
@@ -28,7 +28,6 @@
#include "cx/linked_list.h"
#include "cx/utils.h"
-#include <stdint.h>
#include <string.h>
#include <assert.h>
@@ -38,8 +37,7 @@
#define ll_prev(node) CX_LL_PTR(node, loc_prev)
#define ll_next(node) CX_LL_PTR(node, loc_next)
#define ll_advance(node) CX_LL_PTR(node, loc_advance)
-#define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data))
-#define ll_data(node) ll_data_f(node,follow_ptr)
+#define ll_data(node) (((char*)(node))+loc_data)
void *cx_linked_list_at(
void const *start,
@@ -58,12 +56,11 @@
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,
- bool follow_ptr,
- CxListComparator cmp_func,
+ cx_compare_func cmp_func,
void const *elem
) {
assert(start != NULL);
@@ -72,7 +69,7 @@
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) {
@@ -81,7 +78,7 @@
node = ll_advance(node);
index++;
} while (node != NULL);
- return index;
+ return -1;
}
void *cx_linked_list_first(
@@ -282,20 +279,23 @@
return size;
}
+#ifndef CX_LINKED_LIST_SORT_SBO_SIZE
+#define CX_LINKED_LIST_SORT_SBO_SIZE 1024
+#endif
+
static void *cx_linked_list_sort_merge(
ptrdiff_t loc_prev,
ptrdiff_t loc_next,
ptrdiff_t loc_data,
- bool follow_ptr,
size_t length,
void *ls,
void *le,
void *re,
- CxListComparator cmp_func
+ cx_compare_func cmp_func
) {
- const size_t sbo_len = 1024;
- void *sbo[sbo_len];
- void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
+ void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
+ void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
+ malloc(sizeof(void *) * length) : sbo;
if (sorted == NULL) abort();
void *rc, *lc;
@@ -343,8 +343,7 @@
ptrdiff_t loc_prev,
ptrdiff_t loc_next,
ptrdiff_t loc_data,
- bool follow_ptr,
- CxListComparator cmp_func
+ cx_compare_func cmp_func
) {
assert(begin != NULL);
assert(loc_next >= 0);
@@ -378,17 +377,17 @@
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, follow_ptr,
+ void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
ln + rn, ls, le, re, cmp_func);
// Something left? Sort it!
size_t remainder_length = cx_linked_list_size(re, loc_next);
if (remainder_length > 0) {
void *remainder = re;
- cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
+ 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, follow_ptr,
+ *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
ln + rn + remainder_length,
sorted, remainder, NULL, cmp_func);
} else {
@@ -404,15 +403,13 @@
void const *begin_right,
ptrdiff_t loc_advance,
ptrdiff_t loc_data,
- bool follow_ptr_left,
- bool follow_ptr_right,
- CxListComparator cmp_func
+ cx_compare_func cmp_func
) {
void const *left = begin_left, *right = begin_right;
while (left != NULL && right != NULL) {
- void const *left_data = ll_data_f(left, follow_ptr_left);
- void const *right_data = ll_data_f(right, follow_ptr_right);
+ void const *left_data = ll_data(left);
+ void const *right_data = ll_data(right);
int result = cmp_func(left_data, right_data);
if (result != 0) return result;
left = ll_advance(left);
@@ -457,6 +454,8 @@
// 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;
@@ -472,7 +471,6 @@
struct cx_list_s base;
cx_linked_list_node *begin;
cx_linked_list_node *end;
- bool follow_ptr;
} cx_linked_list;
static cx_linked_list_node *cx_ll_node_at(
@@ -496,14 +494,14 @@
// 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;
@@ -518,55 +516,47 @@
return 0;
}
-static int cx_ll_insert(
+static size_t cx_ll_insert_array(
struct cx_list_s *list,
size_t index,
- void const *elem
+ void const *array,
+ size_t n
) {
- // out-of bounds check
- if (index > list->size) return 1;
+ // out-of bounds and corner case check
+ if (index > list->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);
- // perform insert
- return cx_ll_insert_at(list, node, elem);
-}
+ // perform first insert
+ if (0 != cx_ll_insert_at(list, node, array)) {
+ return 1;
+ }
+
+ // is there more?
+ if (n == 1) return 1;
-static int cx_ll_add(
- struct cx_list_s *list,
- void const *elem
-) {
- return cx_ll_insert(list, list->size, elem);
-}
+ // we now know exactly where we are
+ node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
-static size_t cx_ll_add_array(
- struct cx_list_s *list,
- void const *array,
- size_t n
-) {
- // TODO: redirect to cx_ll_insert_array
- cx_for_n (i, n) {
- if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
+ // 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;
+ if (0 != cx_ll_insert_at(list, node, source)) {
return i;
}
+ node = node->next;
}
return n;
}
-static int cx_pll_insert(
+static int cx_ll_insert_element(
struct cx_list_s *list,
size_t index,
- void const *elem
+ void const *element
) {
- return cx_ll_insert(list, index, &elem);
-}
-
-static int cx_pll_add(
- struct cx_list_s *list,
- void const *elem
-) {
- return cx_ll_insert(list, list->size, &elem);
+ return 1 != cx_ll_insert_array(list, index, element, 1);
}
static int cx_ll_remove(
@@ -579,6 +569,9 @@
// out-of-bounds check
if (node == NULL) return 1;
+ // element destruction
+ cx_invoke_destructor(list, node->payload);
+
// remove
cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
@@ -592,6 +585,141 @@
return 0;
}
+static void cx_ll_clear(struct cx_list_s *list) {
+ if (list->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);
+ 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
+#endif
+
+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 == 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 left, right;
+ if (i < j) {
+ left = i;
+ right = j;
+ } else {
+ left = j;
+ right = i;
+ }
+ cx_linked_list_node *nleft, *nright;
+ if (left < mid && right < mid) {
+ // case 1: both items left from mid
+ nleft = cx_ll_node_at(ll, left);
+ nright = nleft;
+ for (size_t c = left; c < right; c++) {
+ nright = nright->next;
+ }
+ } else if (left >= mid && right >= mid) {
+ // case 2: both items right from mid
+ nright = cx_ll_node_at(ll, right);
+ nleft = nright;
+ for (size_t c = right; c > left; c--) {
+ nleft = nleft->prev;
+ }
+ } else {
+ // case 3: one item left, one item right
+
+ // chose the closest to begin / end
+ size_t closest;
+ size_t other;
+ size_t diff2boundary = list->size - right - 1;
+ if (left <= diff2boundary) {
+ closest = left;
+ other = right;
+ nleft = cx_ll_node_at(ll, left);
+ } else {
+ closest = right;
+ other = left;
+ diff2boundary = left;
+ nright = cx_ll_node_at(ll, right);
+ }
+
+ // is other element closer to us or closer to boundary?
+ if (right - left <= diff2boundary) {
+ // search other element starting from already found element
+ if (closest == left) {
+ nright = nleft;
+ for (size_t c = left; c < right; c++) {
+ nright = nright->next;
+ }
+ } else {
+ nleft = nright;
+ for (size_t c = right; c > left; c--) {
+ nleft = nleft->prev;
+ }
+ }
+ } else {
+ // search other element starting at the boundary
+ if (closest == left) {
+ nright = cx_ll_node_at(ll, other);
+ } else {
+ nleft = cx_ll_node_at(ll, other);
+ }
+ }
+ }
+
+ 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;
+ 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;
+ }
+ } 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);
+ }
+
+ return 0;
+}
+
static void *cx_ll_at(
struct cx_list_s const *list,
size_t index
@@ -601,30 +729,20 @@
return node == NULL ? NULL : node->payload;
}
-static void *cx_pll_at(
- struct cx_list_s const *list,
- size_t index
-) {
- cx_linked_list *ll = (cx_linked_list *) list;
- cx_linked_list_node *node = cx_ll_node_at(ll, index);
- return node == NULL ? NULL : *(void **) 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 = (cx_linked_list *) list;
return cx_linked_list_find(((cx_linked_list *) list)->begin,
CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
- ll->follow_ptr, list->cmpfunc, elem);
+ list->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,
- ll->follow_ptr, list->cmpfunc);
+ list->cmpfunc);
}
static void cx_ll_reverse(struct cx_list_s *list) {
@@ -640,7 +758,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,
- left->follow_ptr, right->follow_ptr, list->cmpfunc);
+ list->cmpfunc);
}
static bool cx_ll_iter_valid(void const *it) {
@@ -653,13 +771,15 @@
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;
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);
- ll->base.size--;
- cxFree(ll->base.allocator, node);
+ list->size--;
+ cxFree(list->allocator, node);
} else {
struct cx_iterator_s *iter = it;
iter->index++;
@@ -668,18 +788,35 @@
}
}
+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;
+ 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);
+ } else {
+ struct cx_iterator_s *iter = it;
+ iter->index--;
+ cx_linked_list_node *node = iter->elem_handle;
+ iter->elem_handle = node->prev;
+ }
+}
+
static void *cx_ll_iter_current(void const *it) {
struct cx_iterator_s const *iter = it;
cx_linked_list_node *node = iter->elem_handle;
return node->payload;
}
-static void *cx_pll_iter_current(void const *it) {
- struct cx_iterator_s const *iter = it;
- cx_linked_list_node *node = iter->elem_handle;
- return *(void **) node->payload;
-}
-
static bool cx_ll_iter_flag_rm(void *it) {
struct cx_iterator_base_s *iter = it;
if (iter->mutating) {
@@ -692,7 +829,8 @@
static CxIterator cx_ll_iterator(
struct cx_list_s const *list,
- size_t index
+ size_t index,
+ bool backwards
) {
CxIterator iter;
iter.index = index;
@@ -700,44 +838,13 @@
iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
iter.base.valid = cx_ll_iter_valid;
iter.base.current = cx_ll_iter_current;
- iter.base.next = cx_ll_iter_next;
+ 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 CxIterator cx_pll_iterator(
- struct cx_list_s const *list,
- size_t index
-) {
- CxIterator iter = cx_ll_iterator(list, index);
- iter.base.current = cx_pll_iter_current;
- return iter;
-}
-
-static CxMutIterator cx_ll_mut_iterator(
- struct cx_list_s *list,
- size_t index
-) {
- CxIterator it = cx_ll_iterator(list, index);
- it.base.mutating = true;
-
- // we know the iterators share the same memory layout
- CxMutIterator iter;
- memcpy(&iter, &it, sizeof(CxMutIterator));
- return iter;
-}
-
-static CxMutIterator cx_pll_mut_iterator(
- struct cx_list_s *list,
- size_t index
-) {
- CxMutIterator iter = cx_ll_mut_iterator(list, index);
- iter.base.current = cx_pll_iter_current;
- return iter;
-}
-
static int cx_ll_insert_iter(
CxMutIterator *iter,
void const *elem,
@@ -752,20 +859,12 @@
iter->index += prepend * (0 == result);
return result;
} else {
- int result = cx_ll_insert(list, list->size, elem);
+ int result = cx_ll_insert_element(list, list->size, elem);
iter->index = list->size;
return result;
}
}
-static int cx_pll_insert_iter(
- CxMutIterator *iter,
- void const *elem,
- int prepend
-) {
- return cx_ll_insert_iter(iter, &elem, prepend);
-}
-
static void cx_ll_destructor(CxList *list) {
cx_linked_list *ll = (cx_linked_list *) list;
@@ -780,67 +879,41 @@
static cx_list_class cx_linked_list_class = {
cx_ll_destructor,
- cx_ll_add,
- cx_ll_add_array,
- cx_ll_insert,
+ cx_ll_insert_element,
+ cx_ll_insert_array,
cx_ll_insert_iter,
cx_ll_remove,
+ cx_ll_clear,
+ cx_ll_swap,
cx_ll_at,
cx_ll_find,
cx_ll_sort,
cx_ll_compare,
cx_ll_reverse,
cx_ll_iterator,
- cx_ll_mut_iterator,
-};
-
-static cx_list_class cx_pointer_linked_list_class = {
- cx_ll_destructor,
- cx_pll_add,
- cx_ll_add_array,
- cx_pll_insert,
- cx_pll_insert_iter,
- cx_ll_remove,
- cx_pll_at,
- cx_ll_find,
- cx_ll_sort,
- cx_ll_compare,
- cx_ll_reverse,
- cx_pll_iterator,
- cx_pll_mut_iterator,
};
CxList *cxLinkedListCreate(
CxAllocator const *allocator,
- CxListComparator comparator,
+ cx_compare_func comparator,
size_t item_size
) {
+ if (allocator == NULL) {
+ allocator = cxDefaultAllocator;
+ }
+
cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
if (list == NULL) return NULL;
- list->follow_ptr = false;
list->base.cl = &cx_linked_list_class;
list->base.allocator = allocator;
list->base.cmpfunc = comparator;
- list->base.itemsize = item_size;
- list->base.capacity = SIZE_MAX;
+
+ if (item_size > 0) {
+ list->base.item_size = item_size;
+ } else {
+ cxListStorePointers((CxList *) list);
+ }
return (CxList *) list;
}
-
-CxList *cxPointerLinkedListCreate(
- CxAllocator const *allocator,
- CxListComparator comparator
-) {
- cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
- if (list == NULL) return NULL;
-
- list->follow_ptr = true;
- list->base.cl = &cx_pointer_linked_list_class;
- list->base.allocator = allocator;
- list->base.cmpfunc = comparator;
- list->base.itemsize = sizeof(void *);
- list->base.capacity = SIZE_MAX;
-
- return (CxList *) list;
-}