Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Sun Nov 23 12:19:24 2025 +0100
+++ b/src/array_list.c	Sun Nov 23 13:15:19 2025 +0100
@@ -417,21 +417,23 @@
     // while there are both source and buffered elements left,
     // copy them interleaving
     while (si < elem_count && bi < new_size) {
-        // determine how many source elements can be inserted
+        // determine how many source elements can be inserted.
+        // the first element that shall not be inserted is the smallest element
+        // that is strictly larger than the first buffered element
+        // (located at the index of the infimum plus one).
+        // the infimum is guaranteed to exist:
+        // - if all src elements are larger,
+        //   there is no buffer, and this loop is skipped
+        // - if any src element is smaller or equal, the infimum exists
+        // - when all src elements that are smaller are copied, the second part
+        //   of this loop body will copy the remaining buffer (emptying it)
+        // Therefore, the buffer can never contain an element that is smaller
+        // than any element in the source and the infimum exists.
         size_t copy_len, bytes_copied;
-        copy_len = cx_array_binary_search_sup(
-                src,
-                elem_count - si,
-                elem_size,
-                bptr,
-                cmp_func
+        copy_len = cx_array_binary_search_inf(
+            src, elem_count - si, elem_size, bptr, cmp_func
         );
-        // 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++;
-        }
+        copy_len++;
 
         // copy the source elements
         if (copy_len > 0) {

--- a/tests/test_list.c	Sun Nov 23 12:19:24 2025 +0100
+++ b/tests/test_list.c	Sun Nov 23 13:15:19 2025 +0100
@@ -315,9 +315,11 @@
     int d8 = 90;
     int d9 = 56;
     int d10a[3] = {67, 75, 90};
-    int expected[22] = {
-            40, 50, 51, 52, 54, 56, 56, 57, 58, 60,
-            62, 64, 65, 67, 70, 75, 75, 77, 78, 80, 90, 90
+    int d11a[6] = {58, 59, 71, 71, 72, 75};
+    int d12a[3] = {10, 120, 130};
+    int expected[31] = {
+            10, 40, 50, 51, 52, 54, 56, 56, 57, 58, 58, 59, 60, 62, 64, 65, 67,
+            70, 71, 71, 72, 75, 75, 75, 77, 78, 80, 90, 90, 120, 130
     };
 
     CX_ARRAY_DECLARE(int, array);
@@ -354,8 +356,14 @@
         CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d10a, 3, cx_cmp_int));
         CX_TEST_ASSERT(array_size == 22);
         CX_TEST_ASSERT(array_capacity >= 22);
-
-        CX_TEST_ASSERT(0 == memcmp(array, expected, 22 * sizeof(int)));
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d11a, 6, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 28);
+        CX_TEST_ASSERT(array_capacity >= 28);
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d12a, 3, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 31);
+        CX_TEST_ASSERT(array_capacity >= 31);
+
+        CX_TEST_ASSERT(0 == memcmp(array, expected, 31 * sizeof(int)));
     }
     cxFreeDefault(array);
 }
@@ -371,9 +379,10 @@
     int d8 = 90;
     int d9 = 56;
     int d10a[3] = {67, 75, 90};
-    int expected[19] = {
-            40, 50, 51, 52, 54, 56, 57, 58, 60,
-            62, 64, 65, 67, 70, 75, 77, 78, 80, 90
+    int d11a[8] = {90, 90, 90, 95, 95, 100, 110, 110};
+    int expected[22] = {
+            40, 50, 51, 52, 54, 56, 57, 58, 60, 62, 64,
+            65, 67, 70, 75, 77, 78, 80, 90, 95, 100, 110
     };
 
     CX_ARRAY_DECLARE(int, array);
@@ -410,8 +419,11 @@
         CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d10a, 3, cx_cmp_int));
         CX_TEST_ASSERT(array_size == 19);
         CX_TEST_ASSERT(array_capacity >= 19);
-
-        CX_TEST_ASSERT(0 == memcmp(array, expected, 19 * sizeof(int)));
+        CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d11a, 8, cx_cmp_int));
+        CX_TEST_ASSERT(array_size == 22);
+        CX_TEST_ASSERT(array_capacity >= 22);
+
+        CX_TEST_ASSERT(0 == memcmp(array, expected, 22 * sizeof(int)));
     }
     cxFreeDefault(array);
 }