Debian Codegraph @

sort/search.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // Performs a binary search over a sorted slice. If the key is found, index of
5 // the matching item in the slice is returned. Otherwise, void is returned.
6 export fn search(
7 in: []const opaque,
8 sz: size,
9 key: const *opaque,
10 cmp: *cmpfunc,
11 ) (size | void) = {
12 let ba = in: *[*]u8;
13 for (let nmemb = len(in); nmemb > 0) {
14 let v = &ba[nmemb / 2 * sz];
15 let r = cmp(key, v);
16 if (r < 0) {
17 nmemb /= 2;
18 } else if (r > 0) {
19 ba = (v: uintptr + sz: uintptr): *[*]u8;
20 nmemb -= nmemb / 2 + 1;
21 } else {
22 const offs = (v: uintptr - in: *[*]u8: uintptr);
23 return (offs / sz: uintptr): size;
24 };
25 };
26 return void;
27 };