--- a/src/linked_list.c Sat Oct 11 11:55:46 2025 +0200
+++ b/src/linked_list.c Sat Oct 11 15:42:48 2025 +0200
@@ -258,117 +258,132 @@
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;
+ // 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;
- // special case: list is empty
- if (dest == NULL) {
- *begin = src;
- if (end != NULL) {
- *end = cx_linked_list_last(src, loc_next);
+ // 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);
}
- 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
- {
- 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;
- }
+ // 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_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);
+ cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
+ dup_end = source_argument;
}
}
-
- dest_prev = dest;
- dest = ll_next(dest);
- continue;
- }
- }
-
- // 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;
+ source_argument = ll_next(source_argument);
}
- // otherwise, we can insert one more
- end_of_chain = next_in_chain;
- next_in_chain = ll_next(next_in_chain);
+ } 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);
}
-
- // 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);
}
- // 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;
+ 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;
}
- } 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);
+ source_argument = ll_next(source_argument);
}
}
}
- // insert remaining items
- if (src != NULL) {
- cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
+ // null the next pointers at the end of the chain
+ ll_next(new_end) = NULL;
+ if (dup_end != NULL) {
+ ll_next(dup_end) = NULL;
}
- // determine new end of list, if requested
- if (end != NULL) {
- *end = cx_linked_list_last(
- dest != NULL ? dest : dest_prev, loc_next);
+ // null the optional prev pointers
+ if (loc_prev >= 0) {
+ ll_prev(new_begin) = NULL;
+ if (dup_begin != NULL) {
+ ll_prev(dup_begin) = NULL;
+ }
}
- if (dup_last != NULL) {
- ll_next(dup_last) = NULL;
+ // output
+ *begin = new_begin;
+ if (end != NULL) {
+ *end = new_end;
}
- return dup_start;
+ return dup_begin;
}
void cx_linked_list_insert_sorted_chain(
@@ -379,10 +394,9 @@
void *insert_begin,
cx_compare_func cmp_func
) {
- void *ret = cx_linked_list_insert_sorted_chain_impl(
+ 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(