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*, long); 12 long es; 13 } Sort; 14 15 static void 16 swapb(char *i, char *j, long 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, long 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, long n, Sort *p) 46 { 47 long 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, long n, Sort *p) 73 { 74 long 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, long n, long 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 } 125