--- a/ucx/linked_list.c Sun Aug 31 14:39:13 2025 +0200
+++ b/ucx/linked_list.c Sat Nov 08 23:06:11 2025 +0100
@@ -244,6 +244,147 @@
begin, end, loc_prev, loc_next, new_node, cmp_func);
}
+static void *cx_linked_list_insert_sorted_chain_impl(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *insert_begin,
+ cx_compare_func cmp_func,
+ bool allow_duplicates
+) {
+ assert(begin != NULL);
+ assert(loc_next >= 0);
+ assert(insert_begin != NULL);
+
+ // strategy: build completely new chains from scratch
+ void *source_original = *begin;
+ void *source_argument = insert_begin;
+ void *new_begin = NULL;
+ void *new_end = NULL;
+ void *dup_begin = NULL;
+ void *dup_end = NULL;
+
+ // determine the new start
+ {
+ int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument);
+ if (d <= 0) {
+ // the new chain starts with the original chain
+ new_begin = new_end = source_original;
+ source_original = ll_next(source_original);
+ if (d == 0) {
+ if (allow_duplicates) {
+ // duplicate allowed, append it to the chain
+ cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
+ new_end = source_argument;
+ } else {
+ // duplicate is not allowed, start a duplicate chain with the argument
+ dup_begin = dup_end = source_argument;
+ }
+ source_argument = ll_next(source_argument);
+ }
+ } else {
+ // input is smaller, or there is no original chain;
+ // start the new chain with the source argument
+ new_begin = new_end = source_argument;
+ source_argument = ll_next(source_argument);
+ }
+ }
+
+ // now successively compare the elements and add them to the correct chains
+ while (source_original != NULL && source_argument != NULL) {
+ int d = cmp_func(source_original, source_argument);
+ if (d <= 0) {
+ // the original is not larger, add it to the chain
+ cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
+ new_end = source_original;
+ source_original = ll_next(source_original);
+ if (d == 0) {
+ if (allow_duplicates) {
+ // duplicate allowed, append it to the chain
+ cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
+ new_end = source_argument;
+ } else {
+ // duplicate is not allowed, append it to the duplicate chain
+ if (dup_end == NULL) {
+ dup_begin = dup_end = source_argument;
+ } else {
+ cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
+ dup_end = source_argument;
+ }
+ }
+ source_argument = ll_next(source_argument);
+ }
+ } else {
+ // the original is larger, append the source argument to the chain
+ // check if we must discard the source argument as duplicate
+ if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) {
+ if (dup_end == NULL) {
+ dup_begin = dup_end = source_argument;
+ } else {
+ cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
+ dup_end = source_argument;
+ }
+ } else {
+ // no duplicate or duplicates allowed
+ cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
+ new_end = source_argument;
+ }
+ source_argument = ll_next(source_argument);
+ }
+ }
+
+ if (source_original != NULL) {
+ // something is left from the original chain, append it
+ cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
+ new_end = cx_linked_list_last(source_original, loc_next);
+ } else if (source_argument != NULL) {
+ // something is left from the input chain;
+ // when we allow duplicates, append it
+ if (allow_duplicates) {
+ cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
+ new_end = cx_linked_list_last(source_argument, loc_next);
+ } else {
+ // otherwise we must check one-by-one
+ while (source_argument != NULL) {
+ if (cmp_func(new_end, source_argument) == 0) {
+ if (dup_end == NULL) {
+ dup_begin = dup_end = source_argument;
+ } else {
+ cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
+ dup_end = source_argument;
+ }
+ } else {
+ cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
+ new_end = source_argument;
+ }
+ source_argument = ll_next(source_argument);
+ }
+ }
+ }
+
+ // null the next pointers at the end of the chain
+ ll_next(new_end) = NULL;
+ if (dup_end != NULL) {
+ ll_next(dup_end) = NULL;
+ }
+
+ // null the optional prev pointers
+ if (loc_prev >= 0) {
+ ll_prev(new_begin) = NULL;
+ if (dup_begin != NULL) {
+ ll_prev(dup_begin) = NULL;
+ }
+ }
+
+ // output
+ *begin = new_begin;
+ if (end != NULL) {
+ *end = new_end;
+ }
+ return dup_begin;
+}
+
void cx_linked_list_insert_sorted_chain(
void **begin,
void **end,
@@ -252,72 +393,35 @@
void *insert_begin,
cx_compare_func cmp_func
) {
- assert(begin != NULL);
- assert(loc_next >= 0);
- assert(insert_begin != NULL);
-
- // track currently observed nodes
- void *dest_prev = NULL;
- void *dest = *begin;
- void *src = insert_begin;
-
- // special case: list is empty
- if (dest == NULL) {
- *begin = src;
- if (end != NULL) {
- *end = cx_linked_list_last(src, loc_next);
- }
- return;
- }
-
- // search the list for insertion points
- while (dest != NULL && src != NULL) {
- // compare current list node with source node
- // if less or equal, skip
- if (cmp_func(dest, src) <= 0) {
- dest_prev = dest;
- dest = ll_next(dest);
- continue;
- }
+ cx_linked_list_insert_sorted_chain_impl(
+ begin, end, loc_prev, loc_next,
+ insert_begin, cmp_func, true);
+}
- // determine chain of elements that can be inserted
- void *end_of_chain = src;
- void *next_in_chain = ll_next(src);
- while (next_in_chain != NULL) {
- // once we become larger than the list elem, break
- if (cmp_func(dest, next_in_chain) <= 0) {
- break;
- }
- // otherwise, we can insert one more
- end_of_chain = next_in_chain;
- next_in_chain = ll_next(next_in_chain);
- }
+int cx_linked_list_insert_unique(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *new_node,
+ cx_compare_func cmp_func
+) {
+ assert(ll_next(new_node) == NULL);
+ return NULL != cx_linked_list_insert_unique_chain(
+ begin, end, loc_prev, loc_next, new_node, cmp_func);
+}
- // insert the elements
- if (dest_prev == NULL) {
- // new begin
- *begin = src;
- } else {
- cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
- }
- cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
-
- // continue with next
- src = next_in_chain;
- dest_prev = dest;
- dest = ll_next(dest);
- }
-
- // insert remaining items
- if (src != NULL) {
- cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
- }
-
- // determine new end of list, if requested
- if (end != NULL) {
- *end = cx_linked_list_last(
- dest != NULL ? dest : dest_prev, loc_next);
- }
+void *cx_linked_list_insert_unique_chain(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *insert_begin,
+ cx_compare_func cmp_func
+) {
+ return cx_linked_list_insert_sorted_chain_impl(
+ begin, end, loc_prev, loc_next,
+ insert_begin, cmp_func, false);
}
size_t cx_linked_list_remove_chain(
@@ -370,6 +474,16 @@
return removed;
}
+void cx_linked_list_remove(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *node
+) {
+ cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1);
+}
+
size_t cx_linked_list_size(
const void *node,
ptrdiff_t loc_next
@@ -401,7 +515,7 @@
) {
void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
- malloc(sizeof(void *) * length) : sbo;
+ cxMallocDefault(sizeof(void *) * length) : sbo;
if (sorted == NULL) abort();
void *rc, *lc;
@@ -439,7 +553,7 @@
*begin = sorted[0];
*end = sorted[length - 1];
if (sorted != sbo) {
- free(sorted);
+ cxFreeDefault(sorted);
}
}
@@ -564,62 +678,46 @@
// HIGH LEVEL LINKED LIST IMPLEMENTATION
-typedef struct cx_linked_list_node cx_linked_list_node;
-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;
- memcpy(new_node->payload, elem, list->collection.elem_size);
+ // copy the data
+ if (elem != NULL) {
+ 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
);
@@ -638,7 +736,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;
@@ -647,32 +745,119 @@
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 (source != NULL) {
+ 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;
}
-static int cx_ll_insert_element(
+static void *cx_ll_insert_element(
struct cx_list_s *list,
size_t index,
const void *element
) {
- return 1 != cx_ll_insert_array(list, index, element, 1);
+ // out-of-bounds check
+ if (index > list->collection.size) return NULL;
+
+ // find position efficiently
+ 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 (char*)(ll->begin) + ll->loc_data;
+ } else {
+ 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_impl(
+ struct cx_list_s *list,
+ const void *array,
+ size_t n,
+ bool allow_duplicates
+) {
+ cx_linked_list *ll = (cx_linked_list *) list;
+
+ // special case
+ if (n == 0) return 0;
+
+ // create a new chain of nodes
+ void *chain = cx_ll_malloc_node(ll);
+ if (chain == NULL) return 0;
+
+ memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size);
+
+ // add all elements from the array to that chain
+ void *prev = chain;
+ const char *src = array;
+ size_t inserted = 1;
+ for (; inserted < n; inserted++) {
+ void *next = cx_ll_malloc_node(ll);
+ if (next == NULL) break;
+ src += list->collection.elem_size;
+ 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;
+ }
+ CX_LL_PTR(prev, ll->loc_next) = NULL;
+
+ // invoke the low level function
+ cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
+ cx_ll_insert_sorted_loc_data = ll->loc_data;
+ if (allow_duplicates) {
+ cx_linked_list_insert_sorted_chain(
+ &ll->begin,
+ &ll->end,
+ ll->loc_prev,
+ ll->loc_next,
+ chain,
+ cx_ll_insert_sorted_cmp_helper
+ );
+ list->collection.size += inserted;
+ } else {
+ void *duplicates = cx_linked_list_insert_unique_chain(
+ &ll->begin,
+ &ll->end,
+ ll->loc_prev,
+ ll->loc_next,
+ chain,
+ cx_ll_insert_sorted_cmp_helper
+ );
+ list->collection.size += inserted;
+ // free the nodes that did not make it into the list
+ while (duplicates != NULL) {
+ void *next = CX_LL_PTR(duplicates, ll->loc_next);
+ cxFree(list->collection.allocator, duplicates);
+ duplicates = next;
+ list->collection.size--;
+ }
+ }
+
+ return inserted;
}
static size_t cx_ll_insert_sorted(
@@ -680,48 +865,15 @@
const void *array,
size_t n
) {
- // special case
- if (n == 0) return 0;
-
- // create a new chain of nodes
- cx_linked_list_node *chain = cx_ll_malloc_node(list);
- if (chain == NULL) return 0;
-
- memcpy(chain->payload, array, list->collection.elem_size);
- chain->prev = NULL;
- chain->next = NULL;
+ return cx_ll_insert_sorted_impl(list, array, n, true);
+}
- // add all elements from the array to that chain
- cx_linked_list_node *prev = chain;
- const char *src = array;
- size_t inserted = 1;
- for (; inserted < n; inserted++) {
- cx_linked_list_node *next = cx_ll_malloc_node(list);
- if (next == NULL) break;
- src += list->collection.elem_size;
- memcpy(next->payload, src, list->collection.elem_size);
- prev->next = next;
- next->prev = prev;
- prev = next;
- }
- prev->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_linked_list_insert_sorted_chain(
- (void **) &ll->begin,
- (void **) &ll->end,
- CX_LL_LOC_PREV,
- CX_LL_LOC_NEXT,
- chain,
- cx_ll_insert_sorted_cmp_helper
- );
-
- // adjust the list metadata
- list->collection.size += inserted;
-
- return inserted;
+static size_t cx_ll_insert_unique(
+ struct cx_list_s *list,
+ const void *array,
+ size_t n
+) {
+ return cx_ll_insert_sorted_impl(list, array, n, false);
}
static size_t cx_ll_remove(
@@ -731,7 +883,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;
@@ -740,8 +892,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
);
@@ -751,28 +903,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;
}
@@ -785,10 +937,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;
}
@@ -815,14 +967,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
@@ -830,7 +982,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
@@ -856,12 +1008,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 {
@@ -874,33 +1026,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;
@@ -911,8 +1063,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(
@@ -920,11 +1072,13 @@
const void *elem,
bool remove
) {
+ 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
);
@@ -932,9 +1086,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);
}
@@ -943,14 +1097,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(
@@ -959,8 +1113,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);
}
@@ -971,49 +1127,52 @@
static void cx_ll_iter_next(void *it) {
struct cx_iterator_s *iter = it;
+ cx_linked_list *ll = iter->src_handle;
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);
+ struct cx_list_s *list = iter->src_handle;
+ 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--;
+ iter->elem_count--;
cxFree(list->collection.allocator, node);
} else {
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);
}
}
static void cx_ll_iter_prev(void *it) {
struct cx_iterator_s *iter = it;
+ cx_linked_list *ll = iter->src_handle;
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;
+ struct cx_list_s *list = iter->src_handle;
+ 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--;
+ iter->elem_count--;
cxFree(list->collection.allocator, node);
} else {
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;
+ char *node = iter->elem_handle;
+ return node + ll->loc_data;
}
static CxIterator cx_ll_iterator(
@@ -1023,14 +1182,14 @@
) {
CxIterator iter;
iter.index = index;
- iter.src_handle.c = list;
+ iter.src_handle = (void*)list;
iter.elem_handle = cx_ll_node_at((const cx_linked_list *) 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.mutating = false;
+ iter.base.allow_remove = true;
iter.base.remove = false;
return iter;
}
@@ -1040,11 +1199,12 @@
const void *elem,
int prepend
) {
- struct cx_list_s *list = iter->src_handle.m;
- cx_linked_list_node *node = iter->elem_handle;
+ struct cx_list_s *list = iter->src_handle;
+ cx_linked_list *ll = iter->src_handle;
+ 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++;
@@ -1054,22 +1214,22 @@
}
return result;
} else {
- int result = cx_ll_insert_element(list, list->collection.size, elem);
- if (result == 0) {
- iter->elem_count++;
- iter->index = list->collection.size;
+ if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) {
+ return 1;
}
- return result;
+ iter->elem_count++;
+ iter->index = list->collection.size;
+ return 0;
}
}
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;
}
@@ -1082,6 +1242,7 @@
cx_ll_insert_element,
cx_ll_insert_array,
cx_ll_insert_sorted,
+ cx_ll_insert_unique,
cx_ll_insert_iter,
cx_ll_remove,
cx_ll_clear,
@@ -1105,6 +1266,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);
