source: trunk/sys/dietlibc/qsort.c @ 191

Last change on this file since 191 was 1, checked in by alain, 8 years ago

First import

File size: 1.5 KB
Line 
1#include <stdlib.h>
2
3static void exch(char* base,size_t size,size_t a,size_t b) {
4  char* x=base+a*size;
5  char* y=base+b*size;
6  while (size) {
7    char z=*x;
8    *x=*y;
9    *y=z;
10    --size; ++x; ++y;
11  }
12}
13
14/* Quicksort with 3-way partitioning, ala Sedgewick */
15/* Blame him for the scary variable names */
16/* http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf */
17static void quicksort(char* base,size_t size,ssize_t l,ssize_t r,
18                      int (*compar)(const void*,const void*)) {
19  ssize_t i=l-1, j=r, p=l-1, q=r, k;
20  char* v=base+r*size;
21  if (r<=l) return;
22  for (;;) {
23    while (++i != r && compar(base+i*size,v)<0) ;
24    while (compar(v,base+(--j)*size)<0) if (j == l) break;
25    if (i >= j) break;
26    exch(base,size,i,j);
27    if (compar(base+i*size,v)==0) exch(base,size,++p,i);
28    if (compar(v,base+j*size)==0) exch(base,size,j,--q);
29  }
30  exch(base,size,i,r); j = i-1; ++i;
31  for (k=l; k<p; k++, j--) exch(base,size,k,j);
32  for (k=r-1; k>q; k--, i++) exch(base,size,i,k);
33  quicksort(base,size,l,j,compar);
34  quicksort(base,size,i,r,compar);
35}
36
37void qsort(void* base,size_t nmemb,size_t size,int (*compar)(const void*,const void*)) {
38  /* check for integer overflows */
39  if (nmemb >= (((size_t)-1)>>1) ||
40      size >= (((size_t)-1)>>1)) return;
41#if 0
42  if (sizeof(size_t) < sizeof(unsigned long long)) {
43    if ((unsigned long long)size * nmemb > (size_t)-1) return;
44  } else {
45    if (size*nmemb/nmemb != size) return;
46  }
47#endif
48  if (nmemb>1)
49    quicksort(base,size,0,nmemb-1,compar);
50}
Note: See TracBrowser for help on using the repository browser.