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