Mercurial > hg > ucx / file diff

--- a/src/array_list.c	Fri Oct 10 12:26:43 2025 +0200
+++ b/src/array_list.c	Fri Oct 10 17:24:19 2025 +0200
@@ -335,7 +335,7 @@
     return 0;
 }
 
-int cx_array_insert_sorted(
+static int cx_array_insert_sorted_impl(
         void **target,
         size_t *size,
         size_t *capacity,
@@ -343,7 +343,8 @@
         const void *sorted_data,
         size_t elem_size,
         size_t elem_count,
-        CxArrayReallocator *reallocator
+        CxArrayReallocator *reallocator,
+        bool allow_duplicates
 ) {
     // assert pointers
     assert(target != NULL);
@@ -369,6 +370,7 @@
     // store some counts
     size_t old_size = *size;
     size_t old_capacity = *capacity;
+    // the necessary capacity is the worst case assumption, including duplicates
     size_t needed_capacity = old_size + elem_count;
 
     // if we need more than we have, try a reallocation
@@ -418,6 +420,16 @@
                 bptr,
                 cmp_func
         );
+        // handle the identical elements
+        size_t skip_len = 0;
+        while (copy_len < elem_count - si
+                && 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;
@@ -425,6 +437,12 @@
         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;
 
         // when all source elements are in place, we are done
         if (si >= elem_count) break;
@@ -443,7 +461,18 @@
         memmove(dest, bptr, bytes_copied);
         dest += bytes_copied;
         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? simply append them
@@ -451,12 +480,44 @@
         memcpy(dest, src, elem_size * (elem_count - si));
     }
 
-    // still buffer elements left?
-    // don't worry, we already moved them to the correct place
+    // buffered elements need to be moved when we skipped duplicates
+    size_t total_skipped = new_size - *size;
+    if (bi < new_size && total_skipped > 0) {
+        // move the remaining buffer to the end of the array
+        memmove(dest, bptr, elem_size * (new_size - bi));
+    }
 
     return 0;
 }
 
+int cx_array_insert_sorted(
+        void **target,
+        size_t *size,
+        size_t *capacity,
+        cx_compare_func cmp_func,
+        const void *sorted_data,
+        size_t elem_size,
+        size_t elem_count,
+        CxArrayReallocator *reallocator
+) {
+    return cx_array_insert_sorted_impl(target, size, capacity,
+        cmp_func, sorted_data, elem_size, elem_count, reallocator, true);
+}
+
+int cx_array_insert_unique(
+        void **target,
+        size_t *size,
+        size_t *capacity,
+        cx_compare_func cmp_func,
+        const void *sorted_data,
+        size_t elem_size,
+        size_t elem_count,
+        CxArrayReallocator *reallocator
+) {
+    return cx_array_insert_sorted_impl(target, size, capacity,
+        cmp_func, sorted_data, elem_size, elem_count, reallocator, false);
+}
+
 size_t cx_array_binary_search_inf(
         const void *arr,
         size_t size,
@@ -502,6 +563,13 @@
         result = cmp_func(elem, arr_elem);
         if (result == 0) {
             // found it!
+            // check previous elements;
+            // when they are equal, report the smallest index
+            arr_elem -= elem_size;
+            while (pivot_index > 0 && cmp_func(elem, arr_elem) == 0) {
+                pivot_index--;
+                arr_elem -= elem_size;
+            }
             return pivot_index;
         } else if (result < 0) {
             // element is smaller than pivot, continue search left
@@ -700,6 +768,31 @@
     }
 }
 
+static size_t cx_arl_insert_unique(
+        struct cx_list_s *list,
+        const void *sorted_data,
+        size_t n
+) {
+    // get a correctly typed pointer to the list
+    cx_array_list *arl = (cx_array_list *) list;
+
+    if (cx_array_insert_unique(
+            &arl->data,
+            &list->collection.size,
+            &arl->capacity,
+            list->collection.cmpfunc,
+            sorted_data,
+            list->collection.elem_size,
+            n,
+            &arl->reallocator
+    )) {
+        // array list implementation is "all or nothing"
+        return 0;
+    } else {
+        return n;
+    }
+}
+
 static void *cx_arl_insert_element(
         struct cx_list_s *list,
         size_t index,
@@ -993,6 +1086,7 @@
         cx_arl_insert_element,
         cx_arl_insert_array,
         cx_arl_insert_sorted,
+        cx_arl_insert_unique,
         cx_arl_insert_iter,
         cx_arl_remove,
         cx_arl_clear,