Mercurial > hg > ucx / file diff

--- a/src/array_list.c	Sat Nov 22 19:16:27 2025 +0100
+++ b/src/array_list.c	Sun Nov 23 12:19:24 2025 +0100
@@ -595,7 +595,8 @@
         cmp_func, sorted_data, elem_size, elem_count, reallocator, false);
 }
 
-size_t cx_array_binary_search_inf(
+// implementation that finds ANY index
+static size_t cx_array_binary_search_inf_impl(
         const void *arr,
         size_t size,
         size_t elem_size,
@@ -640,13 +641,6 @@
         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
@@ -661,6 +655,24 @@
     return result < 0 ? (pivot_index - 1) : pivot_index;
 }
 
+size_t cx_array_binary_search_inf(
+        const void *arr,
+        size_t size,
+        size_t elem_size,
+        const void *elem,
+        cx_compare_func cmp_func
+) {
+    size_t index = cx_array_binary_search_inf_impl(
+        arr, size, elem_size, elem, cmp_func);
+    // in case of equality, report the largest index
+    const char *e = ((const char *) arr) + (index + 1) * elem_size;
+    while (index + 1 < size && cmp_func(e, elem) == 0) {
+        e += elem_size;
+        index++;
+    }
+    return index;
+}
+
 size_t cx_array_binary_search(
         const void *arr,
         size_t size,
@@ -686,16 +698,25 @@
         const void *elem,
         cx_compare_func cmp_func
 ) {
-    size_t inf = cx_array_binary_search_inf(
+    size_t index = cx_array_binary_search_inf_impl(
             arr, size, elem_size, elem, cmp_func
     );
-    if (inf == size) {
-        // no infimum means, first element is supremum
+    const char *e = ((const char *) arr) + index * elem_size;
+    if (index == size) {
+        // no infimum means the first element is supremum
         return 0;
-    } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) {
-        return inf;
+    } else if (cmp_func(e, elem) == 0) {
+        // found an equal element, search the smallest index
+        e -= elem_size; // e now contains the element at index-1
+        while (index > 0 && cmp_func(e, elem) == 0) {
+            e -= elem_size;
+            index--;
+        }
+        return index;
     } else {
-        return inf + 1;
+        // we already have the largest index of the infimum (by design)
+        // the next element is the supremum (or there is no supremum)
+        return index + 1;
     }
 }