| 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 |
}; |