1 /*
2 * Copyright (c) 2006-2018, RT-Thread Development Team
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 *
6 * Change Logs:
7 * Date Author Notes
8 */
9 #include <sys/types.h>
10 #include <stdlib.h>
11
exch(char * base,size_t size,size_t a,size_t b)12 static void exch(char* base,size_t size,size_t a,size_t b) {
13 char* x=base+a*size;
14 char* y=base+b*size;
15 while (size) {
16 char z=*x;
17 *x=*y;
18 *y=z;
19 --size; ++x; ++y;
20 }
21 }
22
23 /* Quicksort with 3-way partitioning, ala Sedgewick */
24 /* Blame him for the scary variable names */
25 /* http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf */
quicksort(char * base,size_t size,ssize_t l,ssize_t r,int (* compar)(const void *,const void *))26 static void quicksort(char* base,size_t size,ssize_t l,ssize_t r,
27 int (*compar)(const void*,const void*)) {
28 ssize_t i=l-1, j=r, p=l-1, q=r, k;
29 char* v=base+r*size;
30 if (r<=l) return;
31 for (;;) {
32 while (++i != r && compar(base+i*size,v)<0) ;
33 while (compar(v,base+(--j)*size)<0) if (j == l) break;
34 if (i >= j) break;
35 exch(base,size,i,j);
36 if (compar(base+i*size,v)==0) exch(base,size,++p,i);
37 if (compar(v,base+j*size)==0) exch(base,size,j,--q);
38 }
39 exch(base,size,i,r); j = i-1; ++i;
40 for (k=l; k<p; k++, j--) exch(base,size,k,j);
41 for (k=r-1; k>q; k--, i++) exch(base,size,i,k);
42 quicksort(base,size,l,j,compar);
43 quicksort(base,size,i,r,compar);
44 }
45
qsort(void * base,size_t nmemb,size_t size,int (* compar)(const void *,const void *))46 void qsort(void* base,size_t nmemb,size_t size,int (*compar)(const void*,const void*)) {
47 /* check for integer overflows */
48 if (nmemb >= (((size_t)-1)>>1) ||
49 size >= (((size_t)-1)>>1)) return;
50 if (nmemb>1)
51 quicksort(base,size,0,nmemb-1,compar);
52 }
53