Piotr Caban : msvcrt: Rewrite qsort function.
Alexandre Julliard
julliard at winehq.org
Wed May 21 13:39:23 CDT 2014
Module: wine
Branch: master
Commit: b703afda86ef962c617ff33f7b8a552ea550d1e5
URL: http://source.winehq.org/git/wine.git/?a=commit;h=b703afda86ef962c617ff33f7b8a552ea550d1e5
Author: Piotr Caban <piotr at codeweavers.com>
Date: Wed May 21 11:57:13 2014 +0200
msvcrt: Rewrite qsort function.
---
dlls/msvcrt/misc.c | 145 +++++++++++++++++++++++++++++++++++++---------------
1 file changed, 104 insertions(+), 41 deletions(-)
diff --git a/dlls/msvcrt/misc.c b/dlls/msvcrt/misc.c
index 7bb84c8..36d0608 100644
--- a/dlls/msvcrt/misc.c
+++ b/dlls/msvcrt/misc.c
@@ -229,41 +229,108 @@ void CDECL _chkesp(void)
#endif /* __i386__ */
-/*********************************************************************
- * Helper function for MSVCRT_qsort_s.
- *
- * Based on NTDLL_qsort in dlls/ntdll/misc.c
- */
-static void MSVCRT_mergesort( void *arr, void *barr, size_t elemsize,
- int (CDECL *compar)(void *, const void *, const void *),
- size_t left, size_t right, void *context )
+static inline void swap(char *l, char *r, MSVCRT_size_t size)
+{
+ char tmp;
+
+ while(size--) {
+ tmp = *l;
+ *l++ = *r;
+ *r++ = tmp;
+ }
+}
+
+static void small_sort(void *base, MSVCRT_size_t nmemb, MSVCRT_size_t size,
+ int (CDECL *compar)(void *, const void *, const void *), void *context)
+{
+ MSVCRT_size_t e, i;
+ char *max, *p;
+
+ for(e=nmemb; e>1; e--) {
+ max = base;
+ for(i=1; i<e; i++) {
+ p = (char*)base + i*size;
+ if(compar(context, p, max) > 0)
+ max = p;
+ }
+
+ if(p != max)
+ swap(p, max, size);
+ }
+}
+
+static void quick_sort(void *base, MSVCRT_size_t nmemb, MSVCRT_size_t size,
+ int (CDECL *compar)(void *, const void *, const void *), void *context)
{
- if (right>left) {
- size_t i, j, k, m;
- m=left+(right-left)/2;
- MSVCRT_mergesort(arr, barr, elemsize, compar, left, m, context);
- MSVCRT_mergesort(arr, barr, elemsize, compar, m+1, right, context);
-
-#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);
-
- /* i=left; j=right; */
- for (k=left; i<=m && j>m; k++) {
- if (i==j || compar(context, 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--;
+ int stack_lo[8*sizeof(MSVCRT_size_t)], stack_hi[8*sizeof(MSVCRT_size_t)], stack_pos;
+ int beg, end, lo, hi, med;
+
+ stack_pos = 0;
+ stack_lo[stack_pos] = 0;
+ stack_hi[stack_pos] = nmemb-1;
+
+#define X(i) ((char*)base+size*(i))
+ while(stack_pos >= 0) {
+ beg = stack_lo[stack_pos];
+ end = stack_hi[stack_pos--];
+
+ if(end-beg < 8) {
+ small_sort(X(beg), end-beg+1, size, compar, context);
+ continue;
+ }
+
+ lo = beg;
+ hi = end;
+ med = (hi+lo+1)/2;
+ if(compar(context, X(lo), X(med)) > 0)
+ swap(X(lo), X(med), size);
+ if(compar(context, X(lo), X(hi)) > 0)
+ swap(X(lo), X(hi), size);
+ if(compar(context, X(med), X(hi)) > 0)
+ swap(X(med), X(hi), size);
+
+ lo++;
+ hi--;
+ while(1) {
+ while(lo <= hi) {
+ if(lo!=med && compar(context, X(lo), X(med))>0)
+ break;
+ lo++;
+ }
+
+ while(med != hi) {
+ if(compar(context, X(hi), X(med)) <= 0)
+ break;
+ hi--;
}
+
+ if(hi < lo)
+ break;
+
+ swap(X(lo), X(hi), size);
+ if(hi == med)
+ med = lo;
+ lo++;
+ hi--;
+ }
+
+ while(hi > beg) {
+ if(hi!=med && compar(context, X(hi), X(med))!=0)
+ break;
+ hi--;
+ }
+
+ if(hi-beg >= end-lo) {
+ stack_lo[++stack_pos] = beg;
+ stack_hi[stack_pos] = hi;
+ stack_lo[++stack_pos] = lo;
+ stack_hi[stack_pos] = end;
+ }else {
+ stack_lo[++stack_pos] = lo;
+ stack_hi[stack_pos] = end;
+ stack_lo[++stack_pos] = beg;
+ stack_hi[stack_pos] = hi;
}
- for (; i<=m; i++, k++)
- memcpy(X(arr,k),X(barr,i),elemsize);
- for (; j>m; j--, k++)
- memcpy(X(arr,k),X(barr,j),elemsize);
}
#undef X
}
@@ -271,13 +338,13 @@ static void MSVCRT_mergesort( void *arr, void *barr, size_t elemsize,
/*********************************************************************
* qsort_s (MSVCRT.@)
*
- * Based on NTDLL_qsort in dlls/ntdll/misc.c
+ * This function is trying to sort data doing identical comparisons
+ * as native does. There are still cases where it behaves differently.
*/
void CDECL MSVCRT_qsort_s(void *base, MSVCRT_size_t nmemb, MSVCRT_size_t size,
int (CDECL *compar)(void *, const void *, const void *), void *context)
{
- void *secondarr;
- const size_t total_size = nmemb*size;
+ const MSVCRT_size_t total_size = nmemb*size;
if (!MSVCRT_CHECK_PMT(base != NULL || (base == NULL && nmemb == 0))) return;
if (!MSVCRT_CHECK_PMT(size > 0)) return;
@@ -286,11 +353,7 @@ void CDECL MSVCRT_qsort_s(void *base, MSVCRT_size_t nmemb, MSVCRT_size_t size,
if (nmemb < 2) return;
- secondarr = MSVCRT_malloc(total_size);
- if (!secondarr)
- return;
- MSVCRT_mergesort(base, secondarr, size, compar, 0, nmemb-1, context);
- MSVCRT_free(secondarr);
+ quick_sort(base, nmemb, size, compar, context);
}
/*********************************************************************
@@ -299,7 +362,7 @@ void CDECL MSVCRT_qsort_s(void *base, MSVCRT_size_t nmemb, MSVCRT_size_t size,
void CDECL MSVCRT_qsort(void *base, MSVCRT_size_t nmemb, MSVCRT_size_t size,
int (CDECL *compar)(const void*, const void*))
{
- return MSVCRT_qsort_s(base, nmemb, size, compare_wrapper, compar);
+ MSVCRT_qsort_s(base, nmemb, size, compare_wrapper, compar);
}
/*********************************************************************
More information about the wine-cvs
mailing list