Module: wine Branch: master Commit: 2ecd1dfaba9625935ed8b6fa04aff34e4d8703b1 URL: http://source.winehq.org/git/wine.git/?a=commit;h=2ecd1dfaba9625935ed8b6fa04...
Author: Marcus Meissner meissner@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(); }
-
Alexandre Julliard