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