--- a/src/linked_list.c Fri Oct 10 12:26:43 2025 +0200
+++ b/src/linked_list.c Fri Oct 10 17:24:19 2025 +0200
@@ -30,6 +30,7 @@
#include "cx/compare.h"
#include <string.h>
#include <assert.h>
+#include <unistd.h>
// LOW LEVEL LINKED LIST FUNCTIONS
@@ -244,19 +245,22 @@
begin, end, loc_prev, loc_next, new_node, cmp_func);
}
-void cx_linked_list_insert_sorted_chain(
+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
+ cx_compare_func cmp_func,
+ bool allow_duplicates
) {
assert(begin != NULL);
assert(loc_next >= 0);
assert(insert_begin != NULL);
// track currently observed nodes
+ void *dup_start = NULL;
+ void *dup_last = NULL;
void *dest_prev = NULL;
void *dest = *begin;
void *src = insert_begin;
@@ -267,17 +271,38 @@
if (end != NULL) {
*end = cx_linked_list_last(src, loc_next);
}
- return;
+ return NULL;
}
// 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;
+ {
+ int d = cmp_func(dest, src);
+ if (d <= 0) {
+ if (!allow_duplicates && d == 0) {
+ if (dup_last == NULL) {
+ dup_start = src;
+ dup_last = src;
+ if (loc_prev >= 0) {
+ ll_prev(dup_start) = NULL;
+ }
+ } else {
+ cx_linked_list_link(dup_last, src, loc_prev, loc_next);
+ dup_last = src;
+ }
+ src = ll_next(src);
+ while (src != NULL && cmp_func(dest, src) == 0) {
+ dup_last = src;
+ src = ll_next(src);
+ }
+ }
+
+ dest_prev = dest;
+ dest = ll_next(dest);
+ continue;
+ }
}
// determine chain of elements that can be inserted
@@ -308,6 +333,27 @@
dest = ll_next(dest);
}
+ // skip duplicates in the remaining items
+ if (!allow_duplicates && src != NULL) {
+ if (cmp_func(dest_prev, src) == 0) {
+ if (dup_last == NULL) {
+ dup_start = src;
+ dup_last = src;
+ if (loc_prev >= 0) {
+ ll_prev(dup_start) = NULL;
+ }
+ } else {
+ cx_linked_list_link(dup_last, src, loc_prev, loc_next);
+ dup_last = src;
+ }
+ src = ll_next(src);
+ while (src != NULL && cmp_func(dest_prev, src) == 0) {
+ dup_last = src;
+ src = ll_next(src);
+ }
+ }
+ }
+
// insert remaining items
if (src != NULL) {
cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
@@ -318,6 +364,51 @@
*end = cx_linked_list_last(
dest != NULL ? dest : dest_prev, loc_next);
}
+
+ if (dup_last != NULL) {
+ ll_next(dup_last) = NULL;
+ }
+ return dup_start;
+}
+
+void cx_linked_list_insert_sorted_chain(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *insert_begin,
+ cx_compare_func cmp_func
+) {
+ void *ret = cx_linked_list_insert_sorted_chain_impl(
+ begin, end, loc_prev, loc_next,
+ insert_begin, cmp_func, true);
+ assert(ret == NULL);
+}
+
+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);
+}
+
+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(
@@ -677,10 +768,11 @@
return cx_ll_insert_sorted_cmp_func(left, right);
}
-static size_t cx_ll_insert_sorted(
+static size_t cx_ll_insert_sorted_impl(
struct cx_list_s *list,
const void *array,
- size_t n
+ size_t n,
+ bool allow_duplicates
) {
cx_linked_list *ll = (cx_linked_list *) list;
@@ -711,21 +803,54 @@
// invoke the low level function
cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
cx_ll_insert_sorted_loc_data = ll->loc_data;
- cx_linked_list_insert_sorted_chain(
- &ll->begin,
- &ll->end,
- ll->loc_prev,
- ll->loc_next,
- chain,
- cx_ll_insert_sorted_cmp_helper
- );
-
- // adjust the list metadata
- list->collection.size += inserted;
+ 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(
+ struct cx_list_s *list,
+ const void *array,
+ size_t n
+) {
+ return cx_ll_insert_sorted_impl(list, array, n, true);
+}
+
+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(
struct cx_list_s *list,
size_t index,
@@ -1094,6 +1219,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,