Debian Codegraph @

libdrgn/binary_search.h

raw
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 */