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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
/* Tests of branch logic. Number of probing is checked.
$Id: bsearch-2.c,v 1.1 2007/02/06 12:36:58 dmix Exp $
*/
#include <stdlib.h>
/* Calculate max number of compare function calls, depends of nmemb */
int max_calls (size_t nmemb)
{
int n = 0; /* result */
size_t exp = 1; /* margin: 1,2,4,8... */
do {
if (exp > nmemb) break;
n += 1;
} while (exp *= 2);
return (n ? n : 1);
}
int cmp_calls;
int cmp (const void *p1, const void *p2)
{
cmp_calls += 1;
return *(unsigned char *)p1 - *(unsigned char *)p2;
}
int main ()
{
unsigned char arr[33], key;
size_t nmemb;
int i;
/* max_calls verify */
if ( max_calls(1) != 1
|| max_calls(2) != 2
|| max_calls(3) != 2
|| max_calls(7) != 3
|| max_calls(8) != 4 ) exit (__LINE__);
/* Filling of arr: 1,3,5... */
for (i= 0; i < (int)sizeof(arr); i++)
arr[i] = 1 + 2*i;
for (nmemb= 1; nmemb <= sizeof(arr); nmemb++) {
/* Non-existance keys: arr[i] < key < arr[i+1] */
for (i= 0; (size_t)i <= nmemb; i++) {
key = 2*i;
cmp_calls = 0;
if (bsearch (& key, arr, nmemb, 1, cmp) != 0)
exit (__LINE__);
if (cmp_calls > max_calls(nmemb))
exit (__LINE__);
}
/* All existance keys. */
for (i= 0; (size_t)i < nmemb; i++) {
key = arr[i];
cmp_calls = 0;
if (bsearch (& key, arr, nmemb, 1, cmp) != arr + i)
exit (__LINE__);
if (cmp_calls > max_calls(nmemb))
exit (__LINE__);
}
}
return 0;
}
|
