Module: wine Branch: master Commit: d1cc31cebbdfc599907275cde9054d4fe8128756 URL: https://source.winehq.org/git/wine.git/?a=commit;h=d1cc31cebbdfc599907275cde...
Author: Alexandre Julliard julliard@winehq.org Date: Fri Jul 1 16:14:52 2022 +0200
ntdll: Add qsort_s.
Implementation copied from msvcrt.
Signed-off-by: Alexandre Julliard julliard@winehq.org
---
dlls/ntdll/misc.c | 154 +++++++++++++++++++++++++++++++++++++--------- dlls/ntdll/ntdll.spec | 1 + dlls/ntdll/tests/string.c | 2 - 3 files changed, 127 insertions(+), 30 deletions(-)
diff --git a/dlls/ntdll/misc.c b/dlls/ntdll/misc.c index bce8d7db54e..ab89ccb39d6 100644 --- a/dlls/ntdll/misc.c +++ b/dlls/ntdll/misc.c @@ -37,49 +37,147 @@ LPCSTR debugstr_us( const UNICODE_STRING *us ) return debugstr_wn(us->Buffer, us->Length / sizeof(WCHAR)); }
-static void -NTDLL_mergesort( void *arr, void *barr, size_t elemsize, int(__cdecl *compar)(const void *, const void *), - size_t left, size_t right ) -{ - if(right>left) { - size_t i, j, k, m; - m=left+(right-left)/2; - NTDLL_mergesort( arr, barr, elemsize, compar, left, m); - NTDLL_mergesort( arr, barr, elemsize, compar, m+1, right); - -#define X(a,i) ((char*)a+elemsize*(i)) - for (k=left, i=left, j=m+1; i<=m && j<=right; k++) { - if (compar(X(arr, i), X(arr,j)) <= 0) { - memcpy(X(barr,k), X(arr, i), elemsize); - i++; - } else { - memcpy(X(barr,k), X(arr, j), elemsize); - j++; +static int __cdecl compare_wrapper(void *ctx, const void *e1, const void *e2) +{ + int (__cdecl *compare)( const void *, const void * ) = ctx; + return compare( e1, e2 ); +} + +static inline void swap(char *l, char *r, size_t size) +{ + char tmp; + + while(size--) { + tmp = *l; + *l++ = *r; + *r++ = tmp; + } +} + +static void small_sort(void *base, size_t nmemb, size_t size, + int (CDECL *compar)(void *, const void *, const void *), void *context) +{ + 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, size_t nmemb, size_t size, + int (CDECL *compar)(void *, const void *, const void *), void *context) +{ + size_t stack_lo[8*sizeof(size_t)], stack_hi[8*sizeof(size_t)]; + size_t beg, end, lo, hi, med; + int stack_pos; + + 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 = lo + (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 (i<=m) - memcpy(X(barr,k), X(arr,i), (m-i+1)*elemsize); - else - memcpy(X(barr,k), X(arr,j), (right-j+1)*elemsize);
- memcpy(X(arr, left), X(barr, left), (right-left+1)*elemsize); + 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; + } } #undef X }
+ +/********************************************************************* + * qsort_s (NTDLL.@) + */ +void __cdecl qsort_s( void *base, size_t nmemb, size_t size, + int (__cdecl *compar)(void *, const void *, const void *), void *context ) +{ + const size_t total_size = nmemb * size; + + if (!base && nmemb) return; + if (!size) return; + if (!compar) return; + if (total_size / size != nmemb) return; + if (nmemb < 2) return; + quick_sort( base, nmemb, size, compar, context ); +} + + /********************************************************************* * qsort (NTDLL.@) */ void __cdecl qsort( void *base, size_t nmemb, size_t size, int (__cdecl *compar)(const void *, const void *) ) { - void *secondarr; - if (nmemb < 2 || size == 0) return; - secondarr = RtlAllocateHeap (GetProcessHeap(), 0, nmemb*size); - NTDLL_mergesort( base, secondarr, size, compar, 0, nmemb-1 ); - RtlFreeHeap (GetProcessHeap(),0, secondarr); + qsort_s( base, nmemb, size, compare_wrapper, compar ); }
+ /********************************************************************* * bsearch (NTDLL.@) */ diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index a4494f79452..c10ca903190 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -1603,6 +1603,7 @@ @ cdecl memset(ptr long long) @ cdecl pow(double double) @ cdecl qsort(ptr long long ptr) +@ cdecl qsort_s(ptr long long ptr ptr) @ cdecl sin(double) @ varargs sprintf(ptr str) NTDLL_sprintf @ varargs sprintf_s(ptr long str) diff --git a/dlls/ntdll/tests/string.c b/dlls/ntdll/tests/string.c index b9c6465dbee..d4ef5b0f54f 100644 --- a/dlls/ntdll/tests/string.c +++ b/dlls/ntdll/tests/string.c @@ -1452,11 +1452,9 @@ static void test_qsort(void) ok(!strcmp(strarr2[0], "!"), "badly sorted, strar2r[0] is %s\n", strarr2[0]); ok(!strcmp(strarr2[1], "Hello"), "badly sorted, strarr2[1] is %s\n", strarr2[1]); ok(!strcmp(strarr2[2], "Sorted"), "badly sorted, strarr2[2] is %s\n", strarr2[2]); -todo_wine { ok(!strcmp(strarr2[3], "wine"), "badly sorted, strarr2[3] is %s\n", strarr2[3]); ok(!strcmp(strarr2[4], "WINE"), "badly sorted, strarr2[4] is %s\n", strarr2[4]); ok(!strcmp(strarr2[5], "Wine"), "badly sorted, strarr2[5] is %s\n", strarr2[5]); -} ok(!strcmp(strarr2[6], "World"), "badly sorted, strarr2[6] is %s\n", strarr2[6]); }