Marcus Meissner : ntdll: Reimplement qsort() using generic mergesort.
Alexandre Julliard
julliard at winehq.org
Tue May 11 12:09:37 CDT 2010
Module: wine
Branch: master
Commit: 7642e03c6329868729254c4e3580a5037387734d
URL: http://source.winehq.org/git/wine.git/?a=commit;h=7642e03c6329868729254c4e3580a5037387734d
Author: Marcus Meissner <marcus at 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();
}
More information about the wine-cvs
mailing list