[TOC]

include/linux/bsearch.h 二分查找

bsearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * bsearch - 对元素数组进行二进制搜索
 * @key：指向正在搜索的项目的指针
 * @base：指向要搜索的第一个元素的指针
 * @num：元件数量
 * @size：每个元素的大小
 * @cmp：指向比较功能的指针
 *
 * 此函数对给定数组进行二进制搜索。 数组的内容应该已经在提供的比较函数下按升序排序。
 *
 * 请注意，键不必与数组中的元素具有相同的类型，e.g. key可以是字符串，比较函数可以将字符串与结构体的 name 字段进行比较。 但是，如果数组中的键和元素属于同一类型，则可以对 sort（） 和 bsearch（） 使用相同的比较函数。
 */
void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
{
	return __inline_bsearch(key, base, num, size, cmp);
}
EXPORT_SYMBOL(bsearch);
NOKPROBE_SYMBOL(bsearch);

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