minix中二分查找bsearch的实现

在看minix中bsearch实现的源代码之前，先学习一下C 语言中void类型以及void*类型的使用方法与技巧。

void的含义：

void的字面意思是“无类型”，void *则为“无类型指针”，void *可以指向任何类型的数据。

void几乎只有“注释”和限制程序的作用，因为从来没有人会定义一个void变量，让我们试着来定义：

void a;

这行语句编译时会出错，提示“illegal use of type 'void'”。即使void a的编译不会出错，它也没有任何实际意义。

众所周知，如果指针p1和p2的类型相同，那么我们可以直接在p1和p2间互相赋值；如果p1和p2指向不同的数据类型，则必须使用强制类型转换运算符把赋值运算符右边的指针类型转换为左边指针的类型。

1 float *p1;
2 int *p2;
3 p1 = p2;
4 //其中p1 = p2语句会编译出错，
5 //提示“'=' : cannot convert from 'int *' to 'float *'”，必须改为：
6 p1 = (float *)p2;

而void *则不同，任何类型的指针都可以直接赋值给它，无需进行强制类型转换：

1 void *p1;
2 int *p2;
3 p1 = p2;

但这并不意味着，void *也可以无需强制类型转换地赋给其它类型的指针。因为“无类型”可以包容“有类型”，而“有类型”则不能包容“无类型”。

小心使用void指针类型:

按照ANSI(American National Standards Institute)标准，不能对void指针进行算法操作，即下列操作都是不合法的：

1 void * pvoid;
2 pvoid++; //ANSI：错误
3 pvoid += 1; //ANSI：错误
4 //ANSI标准之所以这样认定，是因为它坚持：进行算法操作的指针必须是确定知道其指向数据类型大小的。
5 //例如：
6 int *pint;
7 pint++; //ANSI：正确
8 pint++的结果是使其增大sizeof(int)。

但是GNU则不这么认定，它指定void *的算法操作与char *一致。因此下列语句在GNU编译器中皆正确：

1 pvoid++; //GNU：正确
2 pvoid += 1; //GNU：正确
3 pvoid++的执行结果是其增大了1。

在实际的程序设计中，为迎合ANSI标准，并提高程序的可移植性，我们可以这样编写实现同样功能的代码：

1 void * pvoid;
2 (char *)pvoid++; //ANSI：正确；GNU：正确
3 (char *)pvoid += 1; //ANSI：错误；GNU：正确

GNU和ANSI还有一些区别，总体而言，GNU较ANSI更“开放”，提供了对更多语法的支持。但是我们在真实设计时，还是应该尽可能地迎合ANSI标准。

如果函数的参数可以是任意类型指针，那么应声明其参数为void *

典型的如内存操作函数memcpy和memset的函数原型分别为：

1 void * memcpy(void *dest, const void *src, size_t len);
2 void * memset ( void * buffer, int c, size_t num );

这样，任何类型的指针都可以传入memcpy和memset中，这也真实地体现了内存操作函数的意义，因为它操作的对象仅仅是一片内存，而不论这片内存是什么类型。如果memcpy和memset的参数类型不是void *，而是char *，那才叫真的奇怪了！这样的memcpy和memset明显不是一个“纯粹的，脱离低级趣味的”函数！

　void的出现只是为了一种抽象的需要，如果你正确地理解了面向对象中“抽象基类”的概念，也很容易理解void数据类型。正如不能给抽象基类定义一个实例，我们也不能定义一个void（让我们类比的称void为“抽象数据类型”）变量。

下面是minix系统中提供的二分查找算法的源代码，可以进一步深入学习void*指针的使用：

 1 void * bsearch(register const void *key, register const void *base,
 2     register size_t nmemb, register size_t size,
 3     int (*compar)(const void *, const void *))
 4 {
 5     register const void *mid_point;
 6     register int  cmp;
 7 
 8     while (nmemb > 0) {
 9         mid_point = (char *)base + size * (nmemb >> 1);
10         if ((cmp = (*compar)(key, mid_point)) == 0)
11             return (void *)mid_point;
12         if (cmp >= 0) {
13             base  = (char *)mid_point + size;
14             nmemb = (nmemb - 1) >> 1;
15         } else
16             nmemb >>= 1;
17     }
18     return (void *)NULL;
19 }

下面是linux系统中提供的二分查找算法的源代码，可以进行对比：

 1 void *bsearch(const void *key, const void *base, size_t num, size_t size,
 2           int (*cmp)(const void *key, const void *elt))
 3 {
 4     size_t start = 0, end = num;
 5     int result;
 6 
 7     while (start < end) {
 8         size_t mid = start + (end - start) / 2;
 9 
10         result = cmp(key, base + mid * size);
11         if (result < 0)
12             end = mid;
13         else if (result > 0)
14             start = mid + 1;
15         else
16             return (void *)base + mid * size;
17     }
18 
19     return NULL;
20 }