| 1 |
// Copyright (c) Meta Platforms, Inc. and affiliates. |
| 2 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 3 |
|
| 4 |
/** |
| 5 |
* @file |
| 6 |
* |
| 7 |
* Generic binary search macros. |
| 8 |
* |
| 9 |
* See @ref BinarySearch. |
| 10 |
*/ |
| 11 |
|
| 12 |
#ifndef DRGN_BISECT_H |
| 13 |
#define DRGN_BISECT_H |
| 14 |
|
| 15 |
#include <stdbool.h> |
| 16 |
#include <stddef.h> |
| 17 |
|
| 18 |
#include "pp.h" |
| 19 |
|
| 20 |
/** |
| 21 |
* @ingroup Internals |
| 22 |
* |
| 23 |
* @defgroup BinarySearch Binary search |
| 24 |
* |
| 25 |
* Generic binary search macros. |
| 26 |
* |
| 27 |
* @{ |
| 28 |
*/ |
| 29 |
|
| 30 |
#if DOXYGEN |
| 31 |
/** |
| 32 |
* Return the index of the first element greater than or equal to a given value |
| 33 |
* in a sorted array. |
| 34 |
* |
| 35 |
* If all elements are less than @p value, this returns @p size. |
| 36 |
* |
| 37 |
* This can be used to find an exact match: |
| 38 |
* |
| 39 |
* ``` |
| 40 |
* int array[] = { 1, 2, 3 }; |
| 41 |
* size_t size = 3; |
| 42 |
* int value = 2; |
| 43 |
* size_t i = binary_search_ge(array, size, &value, scalar_less); |
| 44 |
* if (i < size && array[i] == value) |
| 45 |
* printf("Found at %zu\n", i); |
| 46 |
* else |
| 47 |
* printf("Not found\n"); |
| 48 |
* ``` |
| 49 |
* |
| 50 |
* This is equivalent to Python's |
| 51 |
* [`bisect.bisect_left()`](https://docs.python.org/3/library/bisect.html#bisect.bisect_left) |
| 52 |
* and C++'s |
| 53 |
* [`std::lower_bound()`](https://en.cppreference.com/w/cpp/algorithm/lower_bound). |
| 54 |
* |
| 55 |
* @param[in] array Sorted array. (Technically, this only needs to be |
| 56 |
* partitioned such that all elements where `less(elem, value)` is `true` are |
| 57 |
* before all elements where `less(elem, value)` is `false`.) |
| 58 |
* @param[in] size Number of elements in @p array. |
| 59 |
* @param[in] value Pointer to value to compare elements to. |
| 60 |
* @param[in] less Comparison function or macro taking a pointer to an array |
| 61 |
* element and @p value and returning `true` if and only if the element is |
| 62 |
* ordered before (i.e., less than) the value. This may be evaluated/expanded |
| 63 |
* more than once. |
| 64 |
* @return `i` such that `less(&array[j], value)` is `true` for `0 <= j < i` and |
| 65 |
* `false` for `i <= j < size`. |
| 66 |
*/ |
| 67 |
size_t binary_search_ge(const E *array, size_t size, const V *value, |
| 68 |
bool (*less)(const E *, const V *)); |
| 69 |
#else |
| 70 |
#define binary_search_ge(array_arg, nmemb_arg, key_arg, less) \ |
| 71 |
binary_search_ge_i(array_arg, nmemb_arg, key_arg, less, \ |
| 72 |
PP_UNIQUE(array), PP_UNIQUE(key), PP_UNIQUE(lo), \ |
| 73 |
PP_UNIQUE(hi), PP_UNIQUE(mid)) |
| 74 |
#define binary_search_ge_i(array_arg, nmemb_arg, key_arg, less, array, key, lo, \ |
| 75 |
hi, mid) \ |
| 76 |
({ \ |
| 77 |
__auto_type key = (key_arg); \ |
| 78 |
__auto_type array = (array_arg); \ |
| 79 |
size_t lo = 0; \ |
| 80 |
size_t hi = (nmemb_arg); \ |
| 81 |
while (lo < hi) { \ |
| 82 |
size_t mid = lo + (hi - lo) / 2; \ |
| 83 |
if (less(&array[mid], key)) \ |
| 84 |
lo = mid + 1; \ |
| 85 |
else \ |
| 86 |
hi = mid; \ |
| 87 |
} \ |
| 88 |
lo; \ |
| 89 |
}) |
| 90 |
#endif |
| 91 |
|
| 92 |
#if DOXYGEN |
| 93 |
/** |
| 94 |
* Return the index of the first element greater than a given value in a sorted |
| 95 |
* array. |
| 96 |
* |
| 97 |
* If all elements are less than or equal to @p value, this returns @p size. |
| 98 |
* |
| 99 |
* This can be used to find the range containing a value in an array of range |
| 100 |
* starting points: |
| 101 |
* |
| 102 |
* ``` |
| 103 |
* int array[] = { 10, 20, 30 }; |
| 104 |
* size_t size = 3; |
| 105 |
* int value = 15; |
| 106 |
* size_t i = binary_search_gt(array, size, &value, scalar_less); |
| 107 |
* if (i > 0) |
| 108 |
* printf("Found in %zu\n", i - 1); |
| 109 |
* else |
| 110 |
* printf("Not found\n"); |
| 111 |
* ``` |
| 112 |
* |
| 113 |
* This is equivalent to Python's |
| 114 |
* [`bisect.bisect_right()`](https://docs.python.org/3/library/bisect.html#bisect.bisect_right) |
| 115 |
* and C++'s |
| 116 |
* [`std::upper_bound()`](https://en.cppreference.com/w/cpp/algorithm/upper_bound). |
| 117 |
* |
| 118 |
* @param[in] array Sorted array. (Technically, this only needs to be |
| 119 |
* partitioned such that all elements where `less(value, elem)` is `false` are |
| 120 |
* before all elements where `less(value, elem)` is `true`.) |
| 121 |
* @param[in] size Number of elements in @p array. |
| 122 |
* @param[in] value Pointer to value to compare elements to. |
| 123 |
* @param[in] less Comparison function or macro taking @p value and a pointer to |
| 124 |
* an array element and returning `true` if and only if the value is ordered |
| 125 |
* before (i.e., less than) the element. This may be evaluated/expanded more |
| 126 |
* than once. |
| 127 |
* @return `i` such that `less(value, &array[j])` is `false` for `0 <= j < i` |
| 128 |
* and `true` for `i <= j < size`. |
| 129 |
*/ |
| 130 |
size_t binary_search_gt(const E *array, size_t size, const V *value, |
| 131 |
bool (*less)(const V *, const E *)); |
| 132 |
#else |
| 133 |
#define binary_search_gt(array_arg, size_arg, value_arg, less) \ |
| 134 |
binary_search_gt_i(array_arg, size_arg, value_arg, less, \ |
| 135 |
PP_UNIQUE(array), PP_UNIQUE(value), PP_UNIQUE(lo), \ |
| 136 |
PP_UNIQUE(hi), PP_UNIQUE(mid)) |
| 137 |
#define binary_search_gt_i(array_arg, size_arg, value_arg, less, array, value, \ |
| 138 |
lo, hi, mid) \ |
| 139 |
({ \ |
| 140 |
__auto_type array = (array_arg); \ |
| 141 |
__auto_type value = (value_arg); \ |
| 142 |
size_t lo = 0; \ |
| 143 |
size_t hi = (size_arg); \ |
| 144 |
while (lo < hi) { \ |
| 145 |
size_t mid = lo + (hi - lo) / 2; \ |
| 146 |
if (less(value, &array[mid])) \ |
| 147 |
hi = mid; \ |
| 148 |
else \ |
| 149 |
lo = mid + 1; \ |
| 150 |
} \ |
| 151 |
lo; \ |
| 152 |
}) |
| 153 |
#endif |
| 154 |
|
| 155 |
/** |
| 156 |
* Compare two scalars (e.g., integers, floating-point numbers, pointers) for |
| 157 |
* @ref binary_search_ge() or @ref binary_search_gt(). |
| 158 |
*/ |
| 159 |
#define scalar_less(a, b) (*(a) < *(b)) |
| 160 |
|
| 161 |
/** @} */ |
| 162 |
|
| 163 |
#endif /* DRGN_BISECT_H */ |