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