Mercurial > hg > ucx / file diff

--- 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.
  *