Mercurial > hg > ucx / changeset

--- a/src/cx/array_list.h	Tue Sep 17 23:19:03 2024 +0200
+++ b/src/cx/array_list.h	Tue Sep 17 23:29:12 2024 +0200
@@ -348,8 +348,7 @@
     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) {
+    if (index < size && cmp_func(((char const *) arr) + index * elem_size, elem) == 0) {
         return index;
     } else {
         return size;
@@ -357,6 +356,45 @@
 }
 
 /**
+ * Searches the smallest upper bound in a sorted array.
+ *
+ * In other words, this function returns the index of the smallest element
+ * in \p arr that is greater or equal to \p elem with respect to \p cmp_func.
+ * When no such element exists, \p size is returned.
+ *
+ * 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 largest upper bound, or \p size
+ */
+__attribute__((__nonnull__))
+static inline size_t cx_array_binary_search_sup(
+        void const *arr,
+        size_t size,
+        size_t elem_size,
+        void const *elem,
+        cx_compare_func cmp_func
+) {
+    size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func);
+    if (inf == size) {
+        // no infimum means, first element is supremum
+        return 0;
+    } else if (cmp_func(((char const *) arr) + inf * elem_size, elem) == 0) {
+        return inf;
+    } else {
+        return inf + 1;
+    }
+}
+
+/**
  * Swaps two array elements.
  *
  * @param arr the array

--- a/tests/test_list.c	Tue Sep 17 23:19:03 2024 +0200
+++ b/tests/test_list.c	Tue Sep 17 23:29:12 2024 +0200
@@ -159,25 +159,33 @@
 
         int s = 58;
         CX_TEST_ASSERT(7 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(7 == cx_array_binary_search_sup(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));
+        CX_TEST_ASSERT(8 == cx_array_binary_search_sup(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(8 == cx_array_binary_search_sup(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(16 == cx_array_binary_search_sup(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(12 == cx_array_binary_search_sup(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(12 == cx_array_binary_search_sup(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 = 95;
         CX_TEST_ASSERT(17 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(18 == cx_array_binary_search_sup(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 = 30;
         CX_TEST_ASSERT(18 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int));
+        CX_TEST_ASSERT(0 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int));
         CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int));
     }
 }