search.ha (1049B)
1 // License: MPL-2.0 2 // (c) 2021 Drew DeVault <sir@cmpwn.com> 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 void, 8 sz: size, 9 key: const *void, 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: *[*]const void: uintptr); 23 return (offs / sz: uintptr): size; 24 }; 25 }; 26 return void; 27 }; 28 29 // Performs a binary search over a sorted slice of strings. Sorting is done with 30 // respect to Unicode codepoints; see [[strings::compare]]. The index of the 31 // matching item in the slice is returned if found, otherwise void is returned. 32 export fn searchstrings(in: []const str, key: str) (size | void) = { 33 return search(in, size(str), &key, &scmp); 34 };