123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124 |
- /*
- * qsort -- simple quicksort
- */
- #include <u.h>
- typedef
- struct
- {
- int (*cmp)(void*, void*);
- void (*swap)(char*, char*, long);
- long es;
- } Sort;
- static void
- swapb(char *i, char *j, long es)
- {
- char c;
- do {
- c = *i;
- *i++ = *j;
- *j++ = c;
- es--;
- } while(es != 0);
- }
- static void
- swapi(char *ii, char *ij, long es)
- {
- long *i, *j, c;
- i = (long*)ii;
- j = (long*)ij;
- do {
- c = *i;
- *i++ = *j;
- *j++ = c;
- es -= sizeof(long);
- } while(es != 0);
- }
- static char*
- pivot(char *a, long n, Sort *p)
- {
- long j;
- char *pi, *pj, *pk;
- j = n/6 * p->es;
- pi = a + j; /* 1/6 */
- j += j;
- pj = pi + j; /* 1/2 */
- pk = pj + j; /* 5/6 */
- if(p->cmp(pi, pj) < 0) {
- if(p->cmp(pi, pk) < 0) {
- if(p->cmp(pj, pk) < 0)
- return pj;
- return pk;
- }
- return pi;
- }
- if(p->cmp(pj, pk) < 0) {
- if(p->cmp(pi, pk) < 0)
- return pi;
- return pk;
- }
- return pj;
- }
- static void
- qsorts(char *a, long n, Sort *p)
- {
- long j, es;
- char *pi, *pj, *pn;
- es = p->es;
- while(n > 1) {
- if(n > 10) {
- pi = pivot(a, n, p);
- } else
- pi = a + (n>>1)*es;
- p->swap(a, pi, es);
- pi = a;
- pn = a + n*es;
- pj = pn;
- for(;;) {
- do
- pi += es;
- while(pi < pn && p->cmp(pi, a) < 0);
- do
- pj -= es;
- while(pj > a && p->cmp(pj, a) > 0);
- if(pj < pi)
- break;
- p->swap(pi, pj, es);
- }
- p->swap(a, pj, es);
- j = (pj - a) / es;
- n = n-j-1;
- if(j >= n) {
- qsorts(a, j, p);
- a += (j+1)*es;
- } else {
- qsorts(a + (j+1)*es, n, p);
- n = j;
- }
- }
- }
- void
- qsort(void *va, long n, long es, int (*cmp)(void*, void*))
- {
- Sort s;
- s.cmp = cmp;
- s.es = es;
- s.swap = swapi;
- if(((uintptr)va | es) % sizeof(long))
- s.swap = swapb;
- qsorts((char*)va, n, &s);
- }
|