search.ha (708B)
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 };