# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1726610538 -7200
# Node ID f549fd9fbd8f3a17fe8209ba38289254f9a766fb
# Parent  6f44b1f1275c0705f8c67f23589261607ce012ca
apply binary search in cx_array_insert_sorted()

resolves #416
relates to #424

diff -r 6f44b1f1275c -r f549fd9fbd8f src/array_list.c
--- a/src/array_list.c	Tue Sep 17 23:37:15 2024 +0200
+++ b/src/array_list.c	Wed Sep 18 00:02:18 2024 +0200
@@ -170,13 +170,8 @@
     char *dest = *target;
 
     // find the first insertion point
-    while (di < old_size) {
-        if (cmp_func(src, dest) < 0) {
-            break;
-        }
-        di++;
-        dest += elem_size;
-    }
+    di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
+    dest += di * elem_size;
 
     // move the remaining elements in the array completely to the right
     // we will call it the "buffer" for parked elements
@@ -189,40 +184,40 @@
     // copy them interleaving
     while (si < elem_count && bi < new_size) {
         // determine how many source elements can be inserted
-        size_t copy_len = 1;
-        si++;
-        char const *next_src = src + elem_size;
-        while (si < elem_count) {
-            if (cmp_func(bptr, next_src) < 0) {
-                break;
-            }
-            copy_len++;
-            si++;
-            next_src += elem_size;
-        }
+        size_t copy_len, bytes_copied;
+        copy_len = cx_array_binary_search_sup(
+                src,
+                elem_count - si,
+                elem_size,
+                bptr,
+                cmp_func
+        );
 
         // copy the source elements
-        memcpy(dest, src, copy_len * elem_size);
-        dest += copy_len * elem_size;
-        src = next_src;
+        bytes_copied = copy_len * elem_size;
+        memcpy(dest, src, bytes_copied);
+        dest += bytes_copied;
+        src += bytes_copied;
+        si += copy_len;
+
+        // when all source elements are in place, we are done
+        if (si >= elem_count) break;
 
         // determine how many buffered elements need to be restored
-        copy_len = 1;
-        bi++;
-        char *next_bptr = bptr + elem_size;
-        while (bi < new_size) {
-            if (cmp_func(src, next_bptr) < 0) {
-                break;
-            }
-            copy_len++;
-            bi++;
-            next_bptr += elem_size;
-        }
+        copy_len = cx_array_binary_search_sup(
+                bptr,
+                new_size - bi,
+                elem_size,
+                src,
+                cmp_func
+        );
 
         // restore the buffered elements
-        memmove(dest, bptr, copy_len * elem_size);
-        dest += copy_len * elem_size;
-        bptr = next_bptr;
+        bytes_copied = copy_len * elem_size;
+        memmove(dest, bptr, bytes_copied);
+        dest += bytes_copied;
+        bptr += bytes_copied;
+        bi += copy_len;
     }
 
     // still source elements left? simply append them