X-Git-Url: https://pd.if.org/git/?a=blobdiff_plain;f=functions%2Fstdlib%2Fbsearch.c;h=e8e4f3125f53ef61677defaf38787103269c50b4;hb=b08f4b52b1cd1f7a9553c0f357a7c90859fa3e73;hp=056028623c209837ffbdd981e88567496b7fce04;hpb=34893ecc2200dc7017c36a54cb6c5f4c2378b5ec;p=pdclib

diff --git a/functions/stdlib/bsearch.c b/functions/stdlib/bsearch.c
index 0560286..e8e4f31 100644
--- a/functions/stdlib/bsearch.c
+++ b/functions/stdlib/bsearch.c
@@ -1,9 +1,61 @@
-// ----------------------------------------------------------------------------
-// $Id$
-// ----------------------------------------------------------------------------
-// Public Domain C Library - http://pdclib.sourceforge.net
-// This code is Public Domain. Use, modify, and redistribute at will.
-// ----------------------------------------------------------------------------
-
-// TODO: C/C++ linkage
-void * bsearch( const void * key, const void * base, size_t nelem, size_t size, int (*cmp) ( const void * ck, const void * ce) ) { /* TODO */ };
+/* $Id$ */
+
+/* bsearch( const void *, const void *, size_t, size_t, int(*)( const void *, const void * ) )
+
+   This file is part of the Public Domain C Library (PDCLib).
+   Permission is granted to use, modify, and / or redistribute at will.
+*/
+
+#include <stdlib.h>
+
+#ifndef REGTEST
+
+void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
+{
+    const void * pivot;
+    int rc;
+    int corr;
+    while ( nmemb )
+    {
+        /* algorithm needs -1 correction if remaining elements are an even number. */
+        corr = ( nmemb % 2 ) - 1;
+        nmemb /= 2;
+        pivot = (const char *)base + (nmemb * size);
+        rc = compar( key, pivot );
+        if ( rc > 0 )
+        {
+            base = (const char *)pivot + size;
+            nmemb += corr;
+        }
+        else if ( rc == 0 )
+        {
+            return (void *)pivot;
+        }
+    }
+    return NULL;
+}
+
+#endif
+
+#ifdef TEST
+#include <_PDCLIB_test.h>
+
+static int compare( const void * left, const void * right )
+{
+    return *( (unsigned char *)left ) - *( (unsigned char *)right );
+}
+
+int main( void )
+{
+    TESTCASE( bsearch( "e", abcde, 4, 1, compare ) == NULL );
+    TESTCASE( bsearch( "e", abcde, 5, 1, compare ) == &abcde[4] );
+    TESTCASE( bsearch( "a", abcde + 1, 4, 1, compare ) == NULL );
+    TESTCASE( bsearch( "0", abcde, 1, 1, compare ) == NULL );
+    TESTCASE( bsearch( "a", abcde, 1, 1, compare ) == &abcde[0] );
+    TESTCASE( bsearch( "a", abcde, 0, 1, compare ) == NULL );
+    TESTCASE( bsearch( "e", abcde, 3, 2, compare ) == &abcde[4] );
+    TESTCASE( bsearch( "b", abcde, 3, 2, compare ) == NULL );
+    return TEST_RESULTS;
+}
+
+#endif