Marcus Meissner : ntdll: Reimplement qsort() using generic mergesort.
Module: wine Branch: master Commit: 7642e03c6329868729254c4e3580a5037387734d URL: http://source.winehq.org/git/wine.git/?a=commit;h=7642e03c6329868729254c4e35... Author: Marcus Meissner <marcus(a)jet.franken.de> Date: Sun May 9 13:09:47 2010 +0200 ntdll: Reimplement qsort() using generic mergesort. --- dlls/ntdll/misc.c | 43 ++++++++++++++++++++++++++++++++ dlls/ntdll/string.c | 10 ------- dlls/ntdll/tests/string.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 102 insertions(+), 10 deletions(-) diff --git a/dlls/ntdll/misc.c b/dlls/ntdll/misc.c index f4cef42..d09ceef 100644 --- a/dlls/ntdll/misc.c +++ b/dlls/ntdll/misc.c @@ -2,6 +2,7 @@ * Helper functions for ntdll * * Copyright 2000 Juergen Schmied + * Copyright 2010 Marcus Meissner * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -250,3 +251,45 @@ double CDECL NTDLL_tan( double d ) { return tan( d ); } + + +/* Merge Sort. Algorithm taken from http://www.linux-related.de/index.html?/coding/sort/sort_merge.htm */ +static void mergesort( void *arr, void *barr, int elemsize, int(__cdecl *compar)(const void *, const void *), + int left, int right ) +{ + if(right>left) { + int i, j, k, m; + m=(right+left)/2; + mergesort( arr, barr, elemsize, compar, left, m); + mergesort( arr, barr, elemsize, compar, m+1, right); + +#define X(a,i) ((char*)a+elemsize*(i)) + for (i=m+1; i>left; i--) + memcpy (X(barr,(i-1)),X(arr,(i-1)),elemsize); + for (j=m; j<right; j++) + memcpy (X(barr,(right+m-j)),X(arr,(j+1)),elemsize); + + for (k=left; k<=right; k++) { + /*arr[k]=(barr[i]<barr[j])?barr[i++]:barr[j--];*/ + if (compar(X(barr,i),X(barr,j))<0) { + memcpy(X(arr,k),X(barr,i),elemsize); + i++; + } else { + memcpy(X(arr,k),X(barr,j),elemsize); + j--; + } + } + } +#undef X +} + +/********************************************************************* + * qsort (NTDLL.@) + */ +void __cdecl NTDLL_qsort( void *base, size_t nmemb, size_t size, + int(__cdecl *compar)(const void *, const void *) ) +{ + void *secondarr = RtlAllocateHeap (GetProcessHeap(), 0, nmemb*size); + mergesort( base, secondarr, size, compar, 0, nmemb-1 ); + RtlFreeHeap (GetProcessHeap(),0, secondarr); +} diff --git a/dlls/ntdll/string.c b/dlls/ntdll/string.c index c9ca3ce..d1178a7 100644 --- a/dlls/ntdll/string.c +++ b/dlls/ntdll/string.c @@ -93,16 +93,6 @@ void * __cdecl NTDLL_bsearch( const void *key, const void *base, size_t nmemb, /********************************************************************* - * qsort (NTDLL.@) - */ -void __cdecl NTDLL_qsort( void *base, size_t nmemb, size_t size, - int(*compar)(const void *, const void *) ) -{ - qsort( base, nmemb, size, compar ); -} - - -/********************************************************************* * _lfind (NTDLL.@) */ void * __cdecl _lfind( const void *key, const void *base, unsigned int *nmemb, diff --git a/dlls/ntdll/tests/string.c b/dlls/ntdll/tests/string.c index c1632f7..556db8e 100644 --- a/dlls/ntdll/tests/string.c +++ b/dlls/ntdll/tests/string.c @@ -57,6 +57,9 @@ static ULONG (WINAPIV *pwcstoul)(LPCWSTR, LPWSTR *, INT); 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 InitFunctionPtrs(void) { hntdll = LoadLibraryA("ntdll.dll"); @@ -90,6 +93,7 @@ static void InitFunctionPtrs(void) p_wcschr= (void *)GetProcAddress(hntdll, "wcschr"); p_wcsrchr= (void *)GetProcAddress(hntdll, "wcsrchr"); + p_qsort= (void *)GetProcAddress(hntdll, "qsort"); } /* if */ } @@ -1137,6 +1141,59 @@ static void test_wcsrchr(void) "wcsrchr should have returned NULL\n"); } +static __cdecl int intcomparefunc(const void *a, const void*b) +{ + return (*(int*)a) - (*(int*)b); +} + +static __cdecl int charcomparefunc(const void *a, const void*b) +{ + return (*(char*)a) - (*(char*)b); +} + +static __cdecl int strcomparefunc(const void *a, const void*b) +{ + return lstrcmpA(*(char**)a,*(char**)b); +} + +static void test_qsort(void) +{ + int arr[5] = { 23, 42, 8, 4, 16 }; + char carr[5] = { 42, 23, 4, 8, 16 }; + const char *strarr[7] = { + "Hello", + "Wine", + "World", + "!", + "Hopefully", + "Sorted", + "." + }; + + p_qsort ((void*)arr, 5, sizeof(int), intcomparefunc); + ok(arr[0] == 4, "badly sorted, arr[0] is %d\n", arr[0]); + ok(arr[1] == 8, "badly sorted, arr[1] is %d\n", arr[1]); + ok(arr[2] == 16, "badly sorted, arr[2] is %d\n", arr[2]); + ok(arr[3] == 23, "badly sorted, arr[3] is %d\n", arr[3]); + ok(arr[4] == 42, "badly sorted, arr[4] is %d\n", arr[4]); + + p_qsort ((void*)carr, 5, sizeof(char), charcomparefunc); + ok(carr[0] == 4, "badly sorted, carr[0] is %d\n", carr[0]); + ok(carr[1] == 8, "badly sorted, carr[1] is %d\n", carr[1]); + ok(carr[2] == 16, "badly sorted, carr[2] is %d\n", carr[2]); + ok(carr[3] == 23, "badly sorted, carr[3] is %d\n", carr[3]); + ok(carr[4] == 42, "badly sorted, carr[4] is %d\n", carr[4]); + + p_qsort ((void*)strarr, 7, sizeof(char*), strcomparefunc); + ok(!strcmp(strarr[0],"!"), "badly sorted, strarr[0] is %s\n", strarr[0]); + ok(!strcmp(strarr[1],"."), "badly sorted, strarr[1] is %s\n", strarr[1]); + ok(!strcmp(strarr[2],"Hello"), "badly sorted, strarr[2] is %s\n", strarr[2]); + ok(!strcmp(strarr[3],"Hopefully"), "badly sorted, strarr[3] is %s\n", strarr[3]); + ok(!strcmp(strarr[4],"Sorted"), "badly sorted, strarr[4] is %s\n", strarr[4]); + ok(!strcmp(strarr[5],"Wine"), "badly sorted, strarr[5] is %s\n", strarr[5]); + ok(!strcmp(strarr[6],"World"), "badly sorted, strarr[6] is %s\n", strarr[6]); +} + START_TEST(string) { InitFunctionPtrs(); @@ -1165,4 +1222,6 @@ START_TEST(string) test_atoi(); if (patol) test_atol(); + if (p_qsort) + test_qsort(); }
participants (1)
-
Alexandre Julliard