Marcus Meissner : ntdll: Implement bsearch, lfind to use correct comparator functions.
Alexandre Julliard
julliard at winehq.org
Thu May 13 13:15:00 CDT 2010
Module: wine
Branch: master
Commit: 2ecd1dfaba9625935ed8b6fa04aff34e4d8703b1
URL: http://source.winehq.org/git/wine.git/?a=commit;h=2ecd1dfaba9625935ed8b6fa04aff34e4d8703b1
Author: Marcus Meissner <meissner at suse.de>
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();
}
More information about the wine-cvs
mailing list