--- a/src/linked_list.c Mon Sep 08 22:48:48 2025 +0200
+++ b/src/linked_list.c Tue Sep 09 22:30:18 2025 +0200
@@ -564,65 +564,46 @@
// HIGH LEVEL LINKED LIST IMPLEMENTATION
-typedef struct cx_linked_list_node cx_linked_list_node;
-// IMPORTANT: the layout must stay exactly like this, because kv_list.c uses that!
-struct cx_linked_list_node {
- cx_linked_list_node *prev;
- cx_linked_list_node *next;
- char payload[];
-};
-
-#define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
-#define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
-#define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
-
-typedef struct {
- struct cx_list_s base;
- cx_linked_list_node *begin;
- cx_linked_list_node *end;
-} cx_linked_list;
-
-static cx_linked_list_node *cx_ll_node_at(
+static void *cx_ll_node_at(
const cx_linked_list *list,
size_t index
) {
if (index >= list->base.collection.size) {
return NULL;
} 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);
+ return cx_linked_list_at(list->end, list->base.collection.size - 1, list->loc_prev, index);
} else {
- return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
+ return cx_linked_list_at(list->begin, 0, list->loc_next, index);
}
}
-static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
- return cxMalloc(list->collection.allocator,
- sizeof(cx_linked_list_node) + list->collection.elem_size);
+static void *cx_ll_malloc_node(const cx_linked_list *list) {
+ return cxZalloc(list->base.collection.allocator,
+ list->loc_data + list->base.collection.elem_size + list->extra_data_len);
}
static int cx_ll_insert_at(
struct cx_list_s *list,
- cx_linked_list_node *node,
+ void *node,
const void *elem
) {
+ cx_linked_list *ll = (cx_linked_list *) list;
// create the new new_node
- cx_linked_list_node *new_node = cx_ll_malloc_node(list);
+ void *new_node = cx_ll_malloc_node(ll);
// sortir if failed
if (new_node == NULL) return 1;
- // initialize new new_node
- new_node->prev = new_node->next = NULL;
+ // copy the data
if (elem != NULL) {
- memcpy(new_node->payload, elem, list->collection.elem_size);
+ memcpy((char*)new_node + ll->loc_data, elem, list->collection.elem_size);
}
// insert
- cx_linked_list *ll = (cx_linked_list *) list;
cx_linked_list_insert_chain(
- (void **) &ll->begin, (void **) &ll->end,
- CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
+ &ll->begin, &ll->end,
+ ll->loc_prev, ll->loc_next,
node, new_node, new_node
);
@@ -641,7 +622,7 @@
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);
+ void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
// perform first insert
if (0 != cx_ll_insert_at(list, node, array)) return 1;
@@ -650,14 +631,15 @@
if (n == 1) return 1;
// we now know exactly where we are
- node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
+ cx_linked_list *ll = (cx_linked_list *) list;
+ node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next);
// we can add the remaining nodes and immediately advance to the inserted node
const char *source = array;
for (size_t i = 1; i < n; i++) {
source += list->collection.elem_size;
if (0 != cx_ll_insert_at(list, node, source)) return i;
- node = node->next;
+ node = CX_LL_PTR(node, ll->loc_next);
}
return n;
}
@@ -671,25 +653,28 @@
if (index > list->collection.size) return NULL;
// find position efficiently
- cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
+ void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
// perform first insert
if (cx_ll_insert_at(list, node, element)) return NULL;
// return a pointer to the data of the inserted node
+ cx_linked_list *ll = (cx_linked_list *) list;
if (node == NULL) {
- return ((cx_linked_list *) list)->begin->payload;
+ return (char*)(ll->begin) + ll->loc_data;
} else {
- return node->next->payload;
+ char *next = CX_LL_PTR(node, ll->loc_next);
+ return next + ll->loc_data;
}
}
static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
+static _Thread_local off_t cx_ll_insert_sorted_loc_data;
static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
- const cx_linked_list_node *left = l;
- const cx_linked_list_node *right = r;
- return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
+ const char *left = (const char*)l + cx_ll_insert_sorted_loc_data;
+ const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
+ return cx_ll_insert_sorted_cmp_func(left, right);
}
static size_t cx_ll_insert_sorted(
@@ -697,40 +682,40 @@
const void *array,
size_t n
) {
+ cx_linked_list *ll = (cx_linked_list *) list;
+
// special case
if (n == 0) return 0;
// create a new chain of nodes
- cx_linked_list_node *chain = cx_ll_malloc_node(list);
+ void *chain = cx_ll_malloc_node(ll);
if (chain == NULL) return 0;
- memcpy(chain->payload, array, list->collection.elem_size);
- chain->prev = NULL;
- chain->next = NULL;
+ memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size);
// add all elements from the array to that chain
- cx_linked_list_node *prev = chain;
+ void *prev = chain;
const char *src = array;
size_t inserted = 1;
for (; inserted < n; inserted++) {
- cx_linked_list_node *next = cx_ll_malloc_node(list);
+ void *next = cx_ll_malloc_node(ll);
if (next == NULL) break;
src += list->collection.elem_size;
- memcpy(next->payload, src, list->collection.elem_size);
- prev->next = next;
- next->prev = prev;
+ memcpy((char*)next + ll->loc_data, src, list->collection.elem_size);
+ CX_LL_PTR(prev, ll->loc_next) = next;
+ CX_LL_PTR(next, ll->loc_prev) = prev;
prev = next;
}
- prev->next = NULL;
+ CX_LL_PTR(prev, ll->loc_next) = NULL;
// invoke the low level function
- cx_linked_list *ll = (cx_linked_list *) list;
cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
+ cx_ll_insert_sorted_loc_data = ll->loc_data;
cx_linked_list_insert_sorted_chain(
- (void **) &ll->begin,
- (void **) &ll->end,
- CX_LL_LOC_PREV,
- CX_LL_LOC_NEXT,
+ &ll->begin,
+ &ll->end,
+ ll->loc_prev,
+ ll->loc_next,
chain,
cx_ll_insert_sorted_cmp_helper
);
@@ -748,7 +733,7 @@
void *targetbuf
) {
cx_linked_list *ll = (cx_linked_list *) list;
- cx_linked_list_node *node = cx_ll_node_at(ll, index);
+ void *node = cx_ll_node_at(ll, index);
// out-of-bounds check
if (node == NULL) return 0;
@@ -757,8 +742,8 @@
size_t removed = cx_linked_list_remove_chain(
(void **) &ll->begin,
(void **) &ll->end,
- CX_LL_LOC_PREV,
- CX_LL_LOC_NEXT,
+ ll->loc_prev,
+ ll->loc_next,
node,
num
);
@@ -768,28 +753,28 @@
// copy or destroy the removed chain
if (targetbuf == NULL) {
- cx_linked_list_node *n = node;
+ char *n = node;
for (size_t i = 0; i < removed; i++) {
// element destruction
- cx_invoke_destructor(list, n->payload);
+ cx_invoke_destructor(list, n + ll->loc_data);
// free the node and advance
- void *next = n->next;
+ void *next = CX_LL_PTR(n, ll->loc_next);
cxFree(list->collection.allocator, n);
n = next;
}
} else {
char *dest = targetbuf;
- cx_linked_list_node *n = node;
+ char *n = node;
for (size_t i = 0; i < removed; i++) {
// copy payload
- memcpy(dest, n->payload, list->collection.elem_size);
+ memcpy(dest, n + ll->loc_data, list->collection.elem_size);
// advance target buffer
dest += list->collection.elem_size;
// free the node and advance
- void *next = n->next;
+ void *next = CX_LL_PTR(n, ll->loc_next);
cxFree(list->collection.allocator, n);
n = next;
}
@@ -802,10 +787,10 @@
if (list->collection.size == 0) return;
cx_linked_list *ll = (cx_linked_list *) list;
- cx_linked_list_node *node = ll->begin;
+ char *node = ll->begin;
while (node != NULL) {
- cx_invoke_destructor(list, node->payload);
- cx_linked_list_node *next = node->next;
+ cx_invoke_destructor(list, node + ll->loc_data);
+ void *next = CX_LL_PTR(node, ll->loc_next);
cxFree(list->collection.allocator, node);
node = next;
}
@@ -832,14 +817,14 @@
left = j;
right = i;
}
- cx_linked_list_node *nleft = NULL, *nright = NULL;
+ void *nleft = NULL, *nright = NULL;
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;
+ nright = CX_LL_PTR(nright, ll->loc_next);
}
} else if (left >= mid && right >= mid) {
// case 2: both items right from mid
@@ -847,7 +832,7 @@
assert(nright != NULL);
nleft = nright;
for (size_t c = right; c > left; c--) {
- nleft = nleft->prev;
+ nleft = CX_LL_PTR(nleft, ll->loc_prev);
}
} else {
// case 3: one item left, one item right
@@ -873,12 +858,12 @@
if (closest == left) {
nright = nleft;
for (size_t c = left; c < right; c++) {
- nright = nright->next;
+ nright = CX_LL_PTR(nright, ll->loc_next);
}
} else {
nleft = nright;
for (size_t c = right; c > left; c--) {
- nleft = nleft->prev;
+ nleft = CX_LL_PTR(nleft, ll->loc_prev);
}
}
} else {
@@ -891,33 +876,33 @@
}
}
- 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;
+ void *prev = CX_LL_PTR(nleft, ll->loc_prev);
+ void *next = CX_LL_PTR(nright, ll->loc_next);
+ void *midstart = CX_LL_PTR(nleft, ll->loc_next);
+ void *midend = CX_LL_PTR(nright, ll->loc_prev);
if (prev == NULL) {
ll->begin = nright;
} else {
- prev->next = nright;
+ CX_LL_PTR(prev, ll->loc_next) = nright;
}
- nright->prev = prev;
+ CX_LL_PTR(nright, ll->loc_prev) = prev;
if (midstart == nright) {
// special case: both nodes are adjacent
- nright->next = nleft;
- nleft->prev = nright;
+ CX_LL_PTR(nright, ll->loc_next) = nleft;
+ CX_LL_PTR(nleft, ll->loc_prev) = nright;
} else {
// likely case: a chain is between the two nodes
- nright->next = midstart;
- midstart->prev = nright;
- midend->next = nleft;
- nleft->prev = midend;
+ CX_LL_PTR(nright, ll->loc_next) = midstart;
+ CX_LL_PTR(midstart, ll->loc_prev) = nright;
+ CX_LL_PTR(midend, ll->loc_next) = nleft;
+ CX_LL_PTR(nleft, ll->loc_prev) = midend;
}
- nleft->next = next;
+ CX_LL_PTR(nleft, ll->loc_next) = next;
if (next == NULL) {
ll->end = nleft;
} else {
- next->prev = nleft;
+ CX_LL_PTR(next, ll->loc_prev) = nleft;
}
return 0;
@@ -928,8 +913,8 @@
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 : node->payload;
+ char *node = cx_ll_node_at(ll, index);
+ return node == NULL ? NULL : node + ll->loc_data;
}
static size_t cx_ll_find_remove(
@@ -940,10 +925,10 @@
if (list->collection.size == 0) return 0;
size_t index;
- cx_linked_list *ll = ((cx_linked_list *) list);
- cx_linked_list_node *node = cx_linked_list_find(
+ cx_linked_list *ll = (cx_linked_list *) list;
+ char *node = cx_linked_list_find(
ll->begin,
- CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+ ll->loc_next, ll->loc_data,
list->collection.cmpfunc, elem,
&index
);
@@ -951,9 +936,9 @@
return list->collection.size;
}
if (remove) {
- 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);
+ cx_invoke_destructor(list, node + ll->loc_data);
+ cx_linked_list_remove(&ll->begin, &ll->end,
+ ll->loc_prev, ll->loc_next, node);
list->collection.size--;
cxFree(list->collection.allocator, node);
}
@@ -962,14 +947,14 @@
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,
+ cx_linked_list_sort(&ll->begin, &ll->end,
+ ll->loc_prev, ll->loc_next, ll->loc_data,
list->collection.cmpfunc);
}
static void cx_ll_reverse(struct cx_list_s *list) {
cx_linked_list *ll = (cx_linked_list *) list;
- cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
+ cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
}
static int cx_ll_compare(
@@ -978,8 +963,10 @@
) {
cx_linked_list *left = (cx_linked_list *) list;
cx_linked_list *right = (cx_linked_list *) other;
+ assert(left->loc_next == right->loc_next);
+ assert(left->loc_data == right->loc_data);
return cx_linked_list_compare(left->begin, right->begin,
- CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+ left->loc_next, left->loc_data,
list->collection.cmpfunc);
}
@@ -994,17 +981,18 @@
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);
+ char *node = iter->elem_handle;
+ iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
+ cx_invoke_destructor(list, node + ll->loc_data);
+ cx_linked_list_remove(&ll->begin, &ll->end,
+ ll->loc_prev, ll->loc_next, node);
list->collection.size--;
cxFree(list->collection.allocator, node);
} else {
+ const cx_linked_list *ll = iter->src_handle.c;
iter->index++;
- cx_linked_list_node *node = iter->elem_handle;
- iter->elem_handle = node->next;
+ void *node = iter->elem_handle;
+ iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
}
}
@@ -1014,25 +1002,27 @@
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;
+ char *node = iter->elem_handle;
+ iter->elem_handle = CX_LL_PTR(node, ll->loc_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);
+ cx_invoke_destructor(list, node + ll->loc_data);
+ cx_linked_list_remove(&ll->begin, &ll->end,
+ ll->loc_prev, ll->loc_next, node);
list->collection.size--;
cxFree(list->collection.allocator, node);
} else {
+ const cx_linked_list *ll = iter->src_handle.c;
iter->index--;
- cx_linked_list_node *node = iter->elem_handle;
- iter->elem_handle = node->prev;
+ char *node = iter->elem_handle;
+ iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
}
}
static void *cx_ll_iter_current(const void *it) {
const struct cx_iterator_s *iter = it;
- cx_linked_list_node *node = iter->elem_handle;
- return node->payload;
+ const cx_linked_list *ll = iter->src_handle.c;
+ char *node = iter->elem_handle;
+ return node + ll->loc_data;
}
static CxIterator cx_ll_iterator(
@@ -1060,10 +1050,11 @@
int prepend
) {
struct cx_list_s *list = iter->src_handle.m;
- cx_linked_list_node *node = iter->elem_handle;
+ cx_linked_list *ll = iter->src_handle.m;
+ void *node = iter->elem_handle;
if (node != NULL) {
assert(prepend >= 0 && prepend <= 1);
- cx_linked_list_node *choice[2] = {node, node->prev};
+ void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)};
int result = cx_ll_insert_at(list, choice[prepend], elem);
if (result == 0) {
iter->elem_count++;
@@ -1085,10 +1076,10 @@
static void cx_ll_destructor(CxList *list) {
cx_linked_list *ll = (cx_linked_list *) list;
- cx_linked_list_node *node = ll->begin;
+ char *node = ll->begin;
while (node) {
- cx_invoke_destructor(list, node->payload);
- void *next = node->next;
+ cx_invoke_destructor(list, node + ll->loc_data);
+ void *next = CX_LL_PTR(node, ll->loc_next);
cxFree(list->collection.allocator, node);
node = next;
}
@@ -1124,6 +1115,10 @@
cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
if (list == NULL) return NULL;
+ list->extra_data_len = 0;
+ list->loc_prev = 0;
+ list->loc_next = sizeof(void*);
+ list->loc_data = sizeof(void*)*2;
cx_list_init((CxList*)list, &cx_linked_list_class,
allocator, comparator, elem_size);
