diff options
| author |   Peter Zijlstra <peterz@infradead.org> | 2020-02-19 18:25:09 +0100 |
|---|---|---|
| committer |   Thomas Gleixner <tglx@linutronix.de> | 2020-06-11 15:14:53 +0200 |
| commit | df65bba1dcd8ffadd922a71196b78c6d7630c33b (patch) | |
| tree | 4e63ec64b11079ba25d827122b7e25b97423a3b1 /include | |
| parent | x86/int3: Avoid atomic instrumentation (diff) | |
| download | wireguard-linux-df65bba1dcd8ffadd922a71196b78c6d7630c33b.tar.xz wireguard-linux-df65bba1dcd8ffadd922a71196b78c6d7630c33b.zip | |
lib/bsearch: Provide __always_inline variant
For code that needs the ultimate performance (it can inline the @cmp
function too) or simply needs to avoid calling external functions for
whatever reason, provide an __always_inline variant of bsearch().
[ tglx: Renamed to __inline_bsearch() as suggested by Andy ]
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Reviewed-by: Alexandre Chartre <alexandre.chartre@oracle.com>
Acked-by: Andy Lutomirski <luto@kernel.org>
Link: https://lkml.kernel.org/r/20200505135313.624443814@linutronix.de
Diffstat (limited to 'include')
| -rw-r--r-- | include/linux/bsearch.h | 26 |
1 files changed, 24 insertions, 2 deletions
diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h index 8ed53d7524ea..e66b711d091e 100644 --- a/include/linux/bsearch.h +++ b/include/linux/bsearch.h @@ -4,7 +4,29 @@ #include <linux/types.h> -void *bsearch(const void *key, const void *base, size_t num, size_t size, - cmp_func_t cmp); +static __always_inline +void *__inline_bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp) +{ + const char *pivot; + int result; + + while (num > 0) { + pivot = base + (num >> 1) * size; + result = cmp(key, pivot); + + if (result == 0) + return (void *)pivot; + + if (result > 0) { + base = pivot + size; + num--; + } + num >>= 1; + } + + return NULL; +} + +extern void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp); #endif /* _LINUX_BSEARCH_H */ |