Marcus Meissner : ntdll: Implement bsearch, lfind to use correct comparator functions.

[Alexandre Julliard]

Module: wine
Branch: master
Commit: 2ecd1dfaba9625935ed8b6fa04aff34e4d8703b1
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=2ecd1dfaba9625935ed8b6fa04...

Author: Marcus Meissner 
Date:   Wed May 12 17:26:33 2010 +0200

ntdll: Implement bsearch, lfind to use correct comparator functions.

---

dlls/ntdll/misc.c         |   46 +++++++++++++++++++++++++++++++++++++++++++++
 dlls/ntdll/string.c       |   21 --------------------
 dlls/ntdll/tests/string.c |   22 +++++++++++++++++++++
 3 files changed, 68 insertions(+), 21 deletions(-)

diff --git a/dlls/ntdll/misc.c b/dlls/ntdll/misc.c
index 01e9ab6..eedef65 100644
--- a/dlls/ntdll/misc.c
+++ b/dlls/ntdll/misc.c
@@ -294,3 +294,49 @@ void __cdecl NTDLL_qsort( void *base, size_t nmemb, size_t size,
     NTDLL_mergesort( base, secondarr, size, compar, 0, nmemb-1 );
     RtlFreeHeap (GetProcessHeap(),0, secondarr);
 }
+
+/*********************************************************************
+ *                  bsearch   (NTDLL.@)
+ */
+void * __cdecl
+NTDLL_bsearch( const void *key, const void *base, size_t nmemb,
+               size_t size, int (__cdecl *compar)(const void *, const void *) )
+{
+    int begin, end, cursor;
+
+    begin = 0;
+    end = nmemb-1;
+    while (1) {
+	int ret;
+        cursor = (end-begin)/2+begin;
+        ret = compar(key,(char*)base+(cursor*size));
+        if (!ret)
+            return (char*)base+(cursor*size);
+        if (ret < 0)
+            end = cursor;
+        else
+            begin = cursor;
+        if ((end-begin)<=1)
+            break;
+    }
+    if (!compar(key,(char*)base+(begin*size)))
+        return (char*)base+(begin*size);
+    if (!compar(key,(char*)base+(end*size)))
+        return (char*)base+(end*size);
+    return NULL;
+}
+
+
+/*********************************************************************
+ *                  _lfind   (NTDLL.@)
+ */
+void * __cdecl _lfind( const void *key, const void *base, unsigned int *nmemb,
+                       size_t size, int(__cdecl *compar)(const void *, const void *) )
+{
+    size_t i, n = *nmemb;
+
+    for (i=0;i<n;i++)
+        if (!compar(key,(char*)base+(size*i)))
+            return (char*)base+(size*i);
+    return NULL;
+}
diff --git a/dlls/ntdll/string.c b/dlls/ntdll/string.c
index d1178a7..716dbdf 100644
--- a/dlls/ntdll/string.c
+++ b/dlls/ntdll/string.c
@@ -83,27 +83,6 @@ void * __cdecl NTDLL_memset( void *dst, int c, size_t n )

/*********************************************************************
- *                  bsearch   (NTDLL.@)
- */
-void * __cdecl NTDLL_bsearch( const void *key, const void *base, size_t nmemb,
-                              size_t size, int (*compar)(const void *, const void *) )
-{
-    return bsearch( key, base, nmemb, size, compar );
-}
-
-
-/*********************************************************************
- *                  _lfind   (NTDLL.@)
- */
-void * __cdecl _lfind( const void *key, const void *base, unsigned int *nmemb,
-                       size_t size, int(*compar)(const void *, const void *) )
-{
-    size_t n = *nmemb;
-    return lfind( key, base, &n, size, compar );
-}
-
-
-/*********************************************************************
  *                  strcat   (NTDLL.@)
  */
 char * __cdecl NTDLL_strcat( char *dst, const char *src )
diff --git a/dlls/ntdll/tests/string.c b/dlls/ntdll/tests/string.c
index 556db8e..cd362ed 100644
--- a/dlls/ntdll/tests/string.c
+++ b/dlls/ntdll/tests/string.c
@@ -58,6 +58,7 @@ static LPWSTR   (WINAPIV *p_wcschr)(LPCWSTR, WCHAR);
 static LPWSTR   (WINAPIV *p_wcsrchr)(LPCWSTR, WCHAR);

static void     (__cdecl *p_qsort)(void *,size_t,size_t, int(__cdecl *compar)(const void *, const void *) );
+static void*    (__cdecl *p_bsearch)(void *,void*,size_t,size_t, int(__cdecl *compar)(const void *, const void *) );

static void InitFunctionPtrs(void)
@@ -94,6 +95,7 @@ static void InitFunctionPtrs(void)
    p_wcschr= (void *)GetProcAddress(hntdll, "wcschr");
    p_wcsrchr= (void *)GetProcAddress(hntdll, "wcsrchr");
    p_qsort= (void *)GetProcAddress(hntdll, "qsort");
+	p_bsearch= (void *)GetProcAddress(hntdll, "bsearch");
     } /* if */
 }

@@ -1194,6 +1196,24 @@ static void test_qsort(void)
     ok(!strcmp(strarr[6],"World"),  "badly sorted, strarr[6] is %s\n", strarr[6]);
 }

+static void test_bsearch(void)
+{
+    int arr[7] = { 1, 3, 4, 8, 16, 23, 42 };
+    int *x, l, i,j ;
+
+    /* just try all all sizes */
+    for (j=1;j<sizeof(arr)/sizeof(arr[0]);j++) {
+        for (i=0;i<j;i++) {
+            l = arr[i];
+            x = p_bsearch (&l, arr, j, sizeof(arr[0]), intcomparefunc);
+            ok (x == &arr[i], "bsearch did not find %d entry in loopsize %d.\n", i, j);
+        }
+        l = 4242;
+        x = p_bsearch (&l, arr, j, sizeof(arr[0]), intcomparefunc);
+        ok (x == NULL, "bsearch did find 4242 entry in loopsize %d.\n", j);
+    }
+}
+
 START_TEST(string)
 {
     InitFunctionPtrs();
@@ -1224,4 +1244,6 @@ START_TEST(string)
         test_atol();
     if (p_qsort)
         test_qsort();
+    if (p_bsearch)
+        test_bsearch();
 }