1b2441318SGreg Kroah-Hartman /* SPDX-License-Identifier: GPL-2.0 */
21a94dc35STim Abbott #ifndef _LINUX_BSEARCH_H
31a94dc35STim Abbott #define _LINUX_BSEARCH_H
41a94dc35STim Abbott
51a94dc35STim Abbott #include <linux/types.h>
61a94dc35STim Abbott
7*df65bba1SPeter Zijlstra static __always_inline
__inline_bsearch(const void * key,const void * base,size_t num,size_t size,cmp_func_t cmp)8*df65bba1SPeter Zijlstra void *__inline_bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
9*df65bba1SPeter Zijlstra {
10*df65bba1SPeter Zijlstra const char *pivot;
11*df65bba1SPeter Zijlstra int result;
12*df65bba1SPeter Zijlstra
13*df65bba1SPeter Zijlstra while (num > 0) {
14*df65bba1SPeter Zijlstra pivot = base + (num >> 1) * size;
15*df65bba1SPeter Zijlstra result = cmp(key, pivot);
16*df65bba1SPeter Zijlstra
17*df65bba1SPeter Zijlstra if (result == 0)
18*df65bba1SPeter Zijlstra return (void *)pivot;
19*df65bba1SPeter Zijlstra
20*df65bba1SPeter Zijlstra if (result > 0) {
21*df65bba1SPeter Zijlstra base = pivot + size;
22*df65bba1SPeter Zijlstra num--;
23*df65bba1SPeter Zijlstra }
24*df65bba1SPeter Zijlstra num >>= 1;
25*df65bba1SPeter Zijlstra }
26*df65bba1SPeter Zijlstra
27*df65bba1SPeter Zijlstra return NULL;
28*df65bba1SPeter Zijlstra }
29*df65bba1SPeter Zijlstra
30*df65bba1SPeter Zijlstra extern void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp);
311a94dc35STim Abbott
321a94dc35STim Abbott #endif /* _LINUX_BSEARCH_H */
33