--- a/src/array_list.c Sat Oct 11 11:55:46 2025 +0200
+++ b/src/array_list.c Sat Oct 11 15:42:48 2025 +0200
@@ -291,7 +291,7 @@
*target, oldcap, newcap, elem_size, reallocator
);
if (newmem == NULL) {
- return 1;
+ return 1; // LCOV_EXCL_LINE
}
// repair src pointer, if necessary
@@ -420,29 +420,60 @@
bptr,
cmp_func
);
- // handle the identical elements
- size_t skip_len = 0;
- while (copy_len < elem_count - si
+ // binary search gives us the smallest index;
+ // we also want to include equal elements here
+ while (si + copy_len < elem_count
&& cmp_func(bptr, src+copy_len*elem_size) == 0) {
copy_len++;
- if (!allow_duplicates) {
- skip_len++;
- }
}
- copy_len -= skip_len;
// copy the source elements
- bytes_copied = copy_len * elem_size;
- memcpy(dest, src, bytes_copied);
- dest += bytes_copied;
- src += bytes_copied;
- si += copy_len;
- di += copy_len;
-
- // skip duplicates when they are not allowed
- src += skip_len * elem_size;
- si += skip_len;
- *size -= skip_len;
+ if (copy_len > 0) {
+ if (allow_duplicates) {
+ // we can copy the entire chunk
+ bytes_copied = copy_len * elem_size;
+ memcpy(dest, src, bytes_copied);
+ dest += bytes_copied;
+ src += bytes_copied;
+ si += copy_len;
+ di += copy_len;
+ } else {
+ // first, check the end of the source chunk
+ // for being a duplicate of the bptr
+ const char *end_of_src = src + (copy_len - 1) * elem_size;
+ size_t skip_len = 0;
+ while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) {
+ end_of_src -= elem_size;
+ skip_len++;
+ copy_len--;
+ }
+ char *last = dest == *target ? NULL : dest - elem_size;
+ // then iterate through the source chunk
+ // and skip all duplicates with the last element in the array
+ size_t more_skipped = 0;
+ for (unsigned j = 0; j < copy_len; j++) {
+ if (last != NULL && cmp_func(last, src) == 0) {
+ // duplicate - skip
+ src += elem_size;
+ si++;
+ more_skipped++;
+ } else {
+ memcpy(dest, src, elem_size);
+ src += elem_size;
+ last = dest;
+ dest += elem_size;
+ si++;
+ di++;
+ }
+ }
+ // skip the previously identified elements as well
+ src += skip_len * elem_size;
+ si += skip_len;
+ skip_len += more_skipped;
+ // reduce the actual size by the number of skipped elements
+ *size -= skip_len;
+ }
+ }
// when all source elements are in place, we are done
if (si >= elem_count) break;
@@ -463,23 +494,63 @@
bptr += bytes_copied;
di += copy_len;
bi += copy_len;
+ }
- // check if the last restored element is a duplicate of the next source
- if (!allow_duplicates && copy_len > 0) {
- char *last = dest - elem_size;
- while (si < elem_count && cmp_func(last, src) == 0) {
- src += elem_size;
- si++;
- (*size)--;
+ // still source elements left?
+ if (si < elem_count) {
+ if (allow_duplicates) {
+ // duplicates allowed or nothing inserted yet: simply copy everything
+ memcpy(dest, src, elem_size * (elem_count - si));
+ } else {
+ if (dest != *target) {
+ // skip all source elements that equal the last element
+ char *last = dest - elem_size;
+ while (si < elem_count) {
+ if (last != NULL && cmp_func(last, src) == 0) {
+ src += elem_size;
+ si++;
+ (*size)--;
+ } else {
+ break;
+ }
+ }
+ }
+ // we must check the elements in the chunk one by one
+ while (si < elem_count) {
+ // find a chain of elements that can be copied
+ size_t copy_len = 1, skip_len = 0;
+ {
+ const char *left_src = src;
+ while (si + copy_len < elem_count) {
+ const char *right_src = left_src + elem_size;
+ int d = cmp_func(left_src, right_src);
+ if (d < 0) {
+ if (skip_len > 0) {
+ // new larger element found;
+ // handle it in the next cycle
+ break;
+ }
+ left_src += elem_size;
+ copy_len++;
+ } else if (d == 0) {
+ left_src += elem_size;
+ skip_len++;
+ } else {
+ break;
+ }
+ }
+ }
+ size_t bytes_copied = copy_len * elem_size;
+ memcpy(dest, src, bytes_copied);
+ dest += bytes_copied;
+ src += bytes_copied + skip_len * elem_size;
+ si += copy_len + skip_len;
+ di += copy_len;
+ *size -= skip_len;
}
}
}
- // still source elements left? simply append them
- if (si < elem_count) {
- memcpy(dest, src, elem_size * (elem_count - si));
- }
-
// buffered elements need to be moved when we skipped duplicates
size_t total_skipped = new_size - *size;
if (bi < new_size && total_skipped > 0) {