# HG changeset patch # User Mike Becker # Date 1726607477 -7200 # Node ID d375d8056262c3cb9cedf7af5e5591710ca699ed # Parent 3012e9b4214e8b94447c19b3c7f4364ae1dd45f5 add cx_array_binary_search() - fixes #424 diff -r 3012e9b4214e -r d375d8056262 src/array_list.c --- 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 diff -r 3012e9b4214e -r d375d8056262 src/cx/array_list.h --- 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. * diff -r 3012e9b4214e -r d375d8056262 tests/test_list.c --- 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);