pd.if.org Git - pdclib/blob - 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