]> pd.if.org Git - pdclib/blob - functions/stdlib/bsearch.c
ab93b94782284e7a1414aa9b5176a50203965a3c
[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     size_t corr;
18     while ( nmemb )
19     {
20         /* algorithm needs -1 correction if remaining elements are an even number. */
21         corr = nmemb % 2;
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             /* applying correction */
29             nmemb -= ( 1 - corr );
30         }
31         else if ( rc == 0 )
32         {
33             return (void *)pivot;
34         }
35     }
36     return NULL;
37 }
38
39 #endif
40
41 #ifdef TEST
42 #include <_PDCLIB_test.h>
43
44 static int compare( const void * left, const void * right )
45 {
46     return *( (unsigned char *)left ) - *( (unsigned char *)right );
47 }
48
49 int main( void )
50 {
51     TESTCASE( bsearch( "e", abcde, 4, 1, compare ) == NULL );
52     TESTCASE( bsearch( "e", abcde, 5, 1, compare ) == &abcde[4] );
53     TESTCASE( bsearch( "a", abcde + 1, 4, 1, compare ) == NULL );
54     TESTCASE( bsearch( "0", abcde, 1, 1, compare ) == NULL );
55     TESTCASE( bsearch( "a", abcde, 1, 1, compare ) == &abcde[0] );
56     TESTCASE( bsearch( "a", abcde, 0, 1, compare ) == NULL );
57     TESTCASE( bsearch( "e", abcde, 3, 2, compare ) == &abcde[4] );
58     TESTCASE( bsearch( "b", abcde, 3, 2, compare ) == NULL );
59     return TEST_RESULTS;
60 }
61
62 #endif