sys/src/libc/port/qsort.c

   1 /*
   2  * qsort -- simple quicksort
   3  */
   4
   5 #include <u.h>
   6
   7 typedef
   8 struct
   9 {
  10         int     (*cmp)(void*, void*);
  11         void    (*swap)(char*, char*, usize);
  12         usize   es;
  13 } Sort;
  14
  15 static  void
  16 swapb(char *i, char *j, usize es)
  17 {
  18         char c;
  19
  20         do {
  21                 c = *i;
  22                 *i++ = *j;
  23                 *j++ = c;
  24                 es--;
  25         } while(es != 0);
  26
  27 }
  28
  29 static  void
  30 swapi(char *ii, char *ij, usize es)
  31 {
  32         long *i, *j, c;
  33
  34         i = (long*)ii;
  35         j = (long*)ij;
  36         do {
  37                 c = *i;
  38                 *i++ = *j;
  39                 *j++ = c;
  40                 es -= sizeof(long);
  41         } while(es != 0);
  42 }
  43
  44 static  char*
  45 pivot(char *a, usize n, Sort *p)
  46 {
  47         usize j;
  48         char *pi, *pj, *pk;
  49
  50         j = n/6 * p->es;
  51         pi = a + j;     /* 1/6 */
  52         j += j;
  53         pj = pi + j;    /* 1/2 */
  54         pk = pj + j;    /* 5/6 */
  55         if(p->cmp(pi, pj) < 0) {
  56                 if(p->cmp(pi, pk) < 0) {
  57                         if(p->cmp(pj, pk) < 0)
  58                                 return pj;
  59                         return pk;
  60                 }
  61                 return pi;
  62         }
  63         if(p->cmp(pj, pk) < 0) {
  64                 if(p->cmp(pi, pk) < 0)
  65                         return pi;
  66                 return pk;
  67         }
  68         return pj;
  69 }
  70
  71 static  void
  72 qsorts(char *a, usize n, Sort *p)
  73 {
  74         usize j, es;
  75         char *pi, *pj, *pn;
  76
  77         es = p->es;
  78         while(n > 1) {
  79                 if(n > 10) {
  80                         pi = pivot(a, n, p);
  81                 } else
  82                         pi = a + (n>>1)*es;
  83
  84                 p->swap(a, pi, es);
  85                 pi = a;
  86                 pn = a + n*es;
  87                 pj = pn;
  88                 for(;;) {
  89                         do
  90                                 pi += es;
  91                         while(pi < pn && p->cmp(pi, a) < 0);
  92                         do
  93                                 pj -= es;
  94                         while(pj > a && p->cmp(pj, a) > 0);
  95                         if(pj < pi)
  96                                 break;
  97                         p->swap(pi, pj, es);
  98                 }
  99                 p->swap(a, pj, es);
 100                 j = (pj - a) / es;
 101
 102                 n = n-j-1;
 103                 if(j < n) {
 104                         qsorts(a, j, p);
 105                         a += (j+1)*es;
 106                 } else {
 107                         qsorts(a + (j+1)*es, n, p);
 108                         n = j;
 109                 }
 110         }
 111 }
 112
 113 void
 114 qsort(void *va, usize n, usize es, int (*cmp)(void*, void*))
 115 {
 116         Sort s;
 117
 118         s.cmp = cmp;
 119         s.es = es;
 120         s.swap = swapi;
 121         if(((uintptr)va | es) % sizeof(long))
 122                 s.swap = swapb;
 123         qsorts((char*)va, n, &s);
 124 }