[PATCH] ntdll: Reimplement qsort() using generic mergesort
Marcus Meissner
marcus at jet.franken.de
Sun May 9 06:09:47 CDT 2010
Hi,
As __cdecl (for the compare function) is not the UNIX cdecl in Win64
anymore, we need to reimplement sort to call the right comparator
functions.
Ciao, Marcus
---
dlls/ntdll/Makefile.in | 1 +
dlls/ntdll/sort.c | 75 +++++++++++++++++++++++++++++++++++++++++++++
dlls/ntdll/string.c | 10 ------
dlls/ntdll/tests/string.c | 59 +++++++++++++++++++++++++++++++++++
4 files changed, 135 insertions(+), 10 deletions(-)
create mode 100644 dlls/ntdll/sort.c
diff --git a/dlls/ntdll/Makefile.in b/dlls/ntdll/Makefile.in
index c51776b..f9ef4f7 100644
--- a/dlls/ntdll/Makefile.in
+++ b/dlls/ntdll/Makefile.in
@@ -44,6 +44,7 @@ C_SRCS = \
signal_powerpc.c \
signal_sparc.c \
signal_x86_64.c \
+ sort.c \
string.c \
sync.c \
tape.c \
diff --git a/dlls/ntdll/sort.c b/dlls/ntdll/sort.c
new file mode 100644
index 0000000..399c857
--- /dev/null
+++ b/dlls/ntdll/sort.c
@@ -0,0 +1,75 @@
+/*
+ * NTDLL sort functions
+ *
+ * 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
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+/* Merge Sort. Algorithm taken from http://www.linux-related.de/index.html?/coding/sort/sort_merge.htm */
+#include "config.h"
+#include "wine/port.h"
+
+#include <ctype.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "windef.h"
+#include "winternl.h"
+#include "ntdll_misc.h"
+
+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();
}
--
1.5.6
More information about the wine-patches
mailing list