pd.if.org Git - pdclib/blob - 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    Code taken from Paul Edward's PDPCLIB.
  11 */
  12
  13 #include <stdlib.h>
  14
  15 #ifndef REGTEST
  16
  17 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
  18 {
  19     const void * pivot;
  20     int rc;
  21     int corr;
  22     while ( nmemb )
  23     {
  24         /* algorithm needs -1 correction if remaining elements are an even number. */
  25         corr = ( nmemb % 2 ) - 1;
  26         nmemb /= 2;
  27         pivot = (const char *)base + (nmemb * size);
  28         rc = compar( key, pivot );
  29         if ( rc > 0 )
  30         {
  31             base = (const char *)pivot + size;
  32             nmemb += corr;
  33         }
  34         else if ( rc == 0 )
  35         {
  36             return (void *)pivot;
  37         }
  38     }
  39     return NULL;
  40 }
  41
  42 #endif
  43
  44 #ifdef TEST
  45 #include <_PDCLIB_test.h>
  46
  47 int compare( const void * left, const void * right )
  48 {
  49     return *( (unsigned char *)left ) - *( (unsigned char *)right );
  50 }
  51
  52 int main()
  53 {
  54     BEGIN_TESTS;
  55     TESTCASE( bsearch( "e", abcde, 4, 1, compare ) == NULL );
  56     TESTCASE( bsearch( "e", abcde, 5, 1, compare ) == &abcde[4] );
  57     TESTCASE( bsearch( "a", abcde + 1, 4, 1, compare ) == NULL );
  58     TESTCASE( bsearch( "0", abcde, 1, 1, compare ) == NULL );
  59     TESTCASE( bsearch( "a", abcde, 1, 1, compare ) == &abcde[0] );
  60     TESTCASE( bsearch( "a", abcde, 0, 1, compare ) == NULL );
  61     TESTCASE( bsearch( "e", abcde, 3, 2, compare ) == &abcde[4] );
  62     TESTCASE( bsearch( "b", abcde, 3, 2, compare ) == NULL );
  63     return TEST_RESULTS;
  64 }
  65
  66 #endif