]> pd.if.org Git - pdclib/blob - functions/stdlib/bsearch.c
Improved header documentation.
[pdclib] / functions / stdlib / bsearch.c
1 /* $Id$ */
2
3 /* bsearch( const void *, const void *, size_t, size_t, int(*)( const void *, const void * ) )
4
5    This file is part of the Public Domain C Library (PDCLib).
6    Permission is granted to use, modify, and / or redistribute at will.
7 */
8
9 #include <stdlib.h>
10
11 #ifndef REGTEST
12
13 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
14 {
15     const void * pivot;
16     int rc;
17     int corr;
18     while ( nmemb )
19     {
20         /* algorithm needs -1 correction if remaining elements are an even number. */
21         corr = ( nmemb % 2 ) - 1;
22         nmemb /= 2;
23         pivot = (const char *)base + (nmemb * size);
24         rc = compar( key, pivot );
25         if ( rc > 0 )
26         {
27             base = (const char *)pivot + size;
28             nmemb += corr;
29         }
30         else if ( rc == 0 )
31         {
32             return (void *)pivot;
33         }
34     }
35     return NULL;
36 }
37
38 #endif
39
40 #ifdef TEST
41 #include <_PDCLIB_test.h>
42
43 static int compare( const void * left, const void * right )
44 {
45     return *( (unsigned char *)left ) - *( (unsigned char *)right );
46 }
47
48 int main( void )
49 {
50     TESTCASE( bsearch( "e", abcde, 4, 1, compare ) == NULL );
51     TESTCASE( bsearch( "e", abcde, 5, 1, compare ) == &abcde[4] );
52     TESTCASE( bsearch( "a", abcde + 1, 4, 1, compare ) == NULL );
53     TESTCASE( bsearch( "0", abcde, 1, 1, compare ) == NULL );
54     TESTCASE( bsearch( "a", abcde, 1, 1, compare ) == &abcde[0] );
55     TESTCASE( bsearch( "a", abcde, 0, 1, compare ) == NULL );
56     TESTCASE( bsearch( "e", abcde, 3, 2, compare ) == &abcde[4] );
57     TESTCASE( bsearch( "b", abcde, 3, 2, compare ) == NULL );
58     return TEST_RESULTS;
59 }
60
61 #endif