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
|
/* bsearch( const void *, const void *, size_t, size_t, int(*)( const void *, const void * ) )
This file is part of the Public Domain C Library (PDCLib).
Permission is granted to use, modify, and / or redistribute at will.
*/
#include <stdlib.h>
#ifndef REGTEST
void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int ( *compar )( const void *, const void * ) )
{
const void * pivot;
int rc;
size_t corr;
while ( nmemb )
{
/* algorithm needs -1 correction if remaining elements are an even number. */
corr = nmemb % 2;
nmemb /= 2;
pivot = ( const char * )base + ( nmemb * size );
rc = compar( key, pivot );
if ( rc > 0 )
{
base = ( const char * )pivot + size;
/* applying correction */
nmemb -= ( 1 - corr );
}
else if ( rc == 0 )
{
return ( void * )pivot;
}
}
return NULL;
}
#endif
#ifdef TEST
#include "_PDCLIB_test.h"
static int compare( const void * left, const void * right )
{
return *( ( unsigned char * )left ) - *( ( unsigned char * )right );
}
int main( void )
{
TESTCASE( bsearch( "e", abcde, 4, 1, compare ) == NULL );
TESTCASE( bsearch( "e", abcde, 5, 1, compare ) == &abcde[4] );
TESTCASE( bsearch( "a", abcde + 1, 4, 1, compare ) == NULL );
TESTCASE( bsearch( "0", abcde, 1, 1, compare ) == NULL );
TESTCASE( bsearch( "a", abcde, 1, 1, compare ) == &abcde[0] );
TESTCASE( bsearch( "a", abcde, 0, 1, compare ) == NULL );
TESTCASE( bsearch( "e", abcde, 3, 2, compare ) == &abcde[4] );
TESTCASE( bsearch( "b", abcde, 3, 2, compare ) == NULL );
return TEST_RESULTS;
}
#endif
|
