Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Tue Sep 17 19:38:41 2024 +0200
+++ b/src/array_list.c	Tue Sep 17 23:11:17 2024 +0200
@@ -236,6 +236,57 @@
     return CX_ARRAY_SUCCESS;
 }
 
+size_t cx_array_binary_search_inf(
+        void const *arr,
+        size_t size,
+        size_t elem_size,
+        void const *elem,
+        cx_compare_func cmp_func
+) {
+    // declare a variable that will contain the compare results
+    int result;
+
+    // cast the array pointer to something we can use offsets with
+    char const *array = arr;
+
+    // check the first array element
+    result = cmp_func(elem, array);
+    if (result <= 0) {
+        return 0;
+    }
+
+    // check the last array element
+    result = cmp_func(elem, array + elem_size * (size - 1));
+    if (result >= 0) {
+        return size - 1;
+    }
+
+    // the element is now guaranteed to be somewhere in the list
+    // so start the binary search
+    size_t left_index = 1;
+    size_t right_index = size - 1;
+    size_t pivot_index;
+
+    while (left_index <= right_index) {
+        pivot_index = left_index + (right_index - left_index) / 2;
+        char const *arr_elem = array + pivot_index * elem_size;
+        result = cmp_func(elem, arr_elem);
+        if (result == 0) {
+            // found it!
+            return pivot_index;
+        } else if (result < 0) {
+            // element is smaller than pivot, continue search left
+            right_index = pivot_index - 1;
+        } else {
+            // element is larger than pivot, continue search right
+            left_index = pivot_index + 1;
+        }
+    }
+
+    // report the largest upper bound
+    return result < 0 ? (pivot_index - 1) : pivot_index;
+}
+
 #ifndef CX_ARRAY_SWAP_SBO_SIZE
 #define CX_ARRAY_SWAP_SBO_SIZE 128
 #endif

--- a/src/cx/array_list.h	Tue Sep 17 19:38:41 2024 +0200
+++ b/src/cx/array_list.h	Tue Sep 17 23:11:17 2024 +0200
@@ -294,6 +294,67 @@
     cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \
         cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator)
 
+
+/**
+ * Searches the largest lower bound in a sorted array.
+ *
+ * In other words, this function returns the index of the largest element
+ * in \p arr that is less or equal to \p elem with respect to \p cmp_func.
+ *
+ * If \p elem is contained in the array, this is identical to
+ * #cx_array_binary_search().
+ *
+ * If the array is not sorted with respect to the \p cmp_func, the behavior
+ * is undefined.
+ *
+ * @param arr the array to search
+ * @param size the size of the array
+ * @param elem_size the size of one element
+ * @param elem the element to find
+ * @param cmp_func the compare function
+ * @return the index of the closest element in the array
+ */
+size_t cx_array_binary_search_inf(
+        void const *arr,
+        size_t size,
+        size_t elem_size,
+        void const *elem,
+        cx_compare_func cmp_func
+) __attribute__((__nonnull__));
+
+/**
+ * Searches an item in a sorted array.
+ *
+ * If the array is not sorted with respect to the \p cmp_func, the behavior
+ * is undefined.
+ *
+ * @param arr the array to search
+ * @param size the size of the array
+ * @param elem_size the size of one element
+ * @param elem the element to find
+ * @param cmp_func the compare function
+ * @return the index of the element in the array, or \p size if the element
+ * cannot be found
+ */
+__attribute__((__nonnull__))
+static inline size_t cx_array_binary_search(
+        void const *arr,
+        size_t size,
+        size_t elem_size,
+        void const *elem,
+        cx_compare_func cmp_func
+) {
+    size_t index = cx_array_binary_search_inf(
+            arr, size, elem_size, elem, cmp_func
+    );
+    char const *found = ((char const *) arr) + index * elem_size;
+    if (cmp_func(found, elem) == 0) {
+        return index;
+    } else {
+        return size;
+    }
+}
+
 /**
  * Swaps two array elements.
  *

--- a/tests/test_list.c	Tue Sep 17 19:38:41 2024 +0200
+++ b/tests/test_list.c	Tue Sep 17 23:11:17 2024 +0200
@@ -146,6 +146,36 @@
     }
 }
 
+CX_TEST(test_array_binary_search) {
+    int array[18] = {
+            40, 50, 51, 52, 54, 56, 57, 58, 60,
+            62, 64, 65, 70, 75, 77, 78, 80, 90
+    };
+
+    CX_TEST_DO {
+        cx_for_n(i, 18) {
+            CX_TEST_ASSERT(i == cx_array_binary_search(array, 18, sizeof(int), &array[i], cx_cmp_int));
+        }
+
+        int s = 58;
+        CX_TEST_ASSERT(7 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        s = 60;
+        CX_TEST_ASSERT(8 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        s = 59;
+        CX_TEST_ASSERT(7 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int));
+        s = 79;
+        CX_TEST_ASSERT(15 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int));
+        s = 66;
+        CX_TEST_ASSERT(11 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int));
+        s = 69;
+        CX_TEST_ASSERT(11 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int));
+    }
+}
+
 typedef struct node {
     struct node *next;
     struct node *prev;
@@ -1582,6 +1612,7 @@
 
     cx_test_register(suite, test_array_add);
     cx_test_register(suite, test_array_insert_sorted);
+    cx_test_register(suite, test_array_binary_search);
 
     cx_test_register(suite, test_list_arl_create);
     cx_test_register(suite, test_list_arl_create_simple);