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