pd.if.org Git - pdclib/blob - functions/stdlib/bsearch.c

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