X-Git-Url: https://pd.if.org/git/?p=pdclib;a=blobdiff_plain;f=functions%2Fstdlib%2Fbsearch.c;h=835407f5ee8e2314100cee595a1e25d44346d5a3;hp=c03cd45716e435b884a01f5b8e4ac20ea12decc4;hb=da0f3f353d417fed71f358a48d5d5394145e460d;hpb=0a5395faab237ba9008352b0f4bee9659bbd3d5f

diff --git a/functions/stdlib/bsearch.c b/functions/stdlib/bsearch.c
index c03cd45..835407f 100644
--- a/functions/stdlib/bsearch.c
+++ b/functions/stdlib/bsearch.c
@@ -1,38 +1,60 @@
-// ----------------------------------------------------------------------------
-// $Id$
-// ----------------------------------------------------------------------------
-// Public Domain C Library - http://pdclib.sourceforge.net
-// This code is Public Domain. Use, modify, and redistribute at will.
-// ----------------------------------------------------------------------------
+/* bsearch( const void *, const void *, size_t, size_t, int(*)( const void *, const void * ) )
 
-// 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 */ };
+   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>
 
-/* PDPC code - unreviewed
+#ifndef REGTEST
+
+void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) )
 {
-    size_t try;
-    int res;
-    const void *ptr;
-    
-    while (nmemb > 0)
+    const void * pivot;
+    int rc;
+    size_t corr;
+    while ( nmemb )
     {
-        try = nmemb / 2;    
-        ptr = (void *)((char *)base + try * size);
-        res = compar(ptr, key);
-        if (res == 0)
-        {
-            return ((void *)ptr);
-        }
-        else if (res < 0)
+        /* algorithm needs -1 correction if remaining elements are an even number. */
+        corr = nmemb % 2;
+        nmemb /= 2;
+        pivot = (const char *)base + (nmemb * size);
+        rc = compar( key, pivot );
+        if ( rc > 0 )
         {
-            nmemb = nmemb - try - 1;
-            base = (const void *)((const char *)ptr + size);
+            base = (const char *)pivot + size;
+            /* applying correction */
+            nmemb -= ( 1 - corr );
         }
-        else
+        else if ( rc == 0 )
         {
-            nmemb = try;
+            return (void *)pivot;
         }
     }
-    return (NULL);
+    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