| 1 |
typedef __SIZE_TYPE__ size_t; |
| 2 |
typedef __UINT8_TYPE__ uint8_t; |
| 3 |
|
| 4 |
void swapfunc (char *a, char *b, int n) |
| 5 |
{ |
| 6 |
do |
| 7 |
{ |
| 8 |
char t = *a; |
| 9 |
*a++ = *b; |
| 10 |
*b++ = t; |
| 11 |
} while (--n > 0); |
| 12 |
} |
| 13 |
|
| 14 |
|
| 15 |
typedef int cmp_t (const void*, const void*); |
| 16 |
|
| 17 |
#define min(a, b) ((a) < (b) ? (a) : (b)) |
| 18 |
|
| 19 |
#define swap(a, b) \ |
| 20 |
swapfunc (a, b, es) |
| 21 |
|
| 22 |
#define vecswap(a, b, n) \ |
| 23 |
if ((n) > 0) swapfunc (a, b, n) |
| 24 |
|
| 25 |
static char* |
| 26 |
med3 (char *a, char *b, char *c, cmp_t *cmp) |
| 27 |
{ |
| 28 |
return cmp (a, b) < 0 |
| 29 |
? (cmp (b, c) < 0 ? b : (cmp (a, c) < 0 ? c : a )) |
| 30 |
: (cmp (b, c) > 0 ? b : (cmp (a, c) < 0 ? a : c )); |
| 31 |
} |
| 32 |
|
| 33 |
void |
| 34 |
qsort (void *a, size_t n, size_t es, cmp_t *cmp) |
| 35 |
{ |
| 36 |
char *pa, *pb, *pc, *pd, *pl, *pm, *pn; |
| 37 |
int d, r, swap_cnt; |
| 38 |
|
| 39 |
loop: |
| 40 |
swap_cnt = 0; |
| 41 |
if (n < 7) |
| 42 |
{ |
| 43 |
for (pm = (char*) a + es; pm < (char*) a + n * es; pm += es) |
| 44 |
for (pl = pm; pl > (char*) a && cmp (pl - es, pl) > 0; pl -= es) |
| 45 |
swap (pl, pl - es); |
| 46 |
return; |
| 47 |
} |
| 48 |
pm = (char*) a + (n / 2) * es; |
| 49 |
if (n > 7) |
| 50 |
{ |
| 51 |
pl = a; |
| 52 |
pn = (char*) a + (n - 1) * es; |
| 53 |
if (n > 40) |
| 54 |
{ |
| 55 |
d = (n / 8) * es; |
| 56 |
pl = med3 (pl, pl + d, pl + 2 * d, cmp); |
| 57 |
pm = med3 (pm - d, pm, pm + d, cmp); |
| 58 |
pn = med3 (pn - 2 * d, pn - d, pn, cmp); |
| 59 |
} |
| 60 |
pm = med3 (pl, pm, pn, cmp); |
| 61 |
} |
| 62 |
swap (a, pm); |
| 63 |
pa = pb = (char*) a + es; |
| 64 |
|
| 65 |
pc = pd = (char*) a + (n - 1) * es; |
| 66 |
for (;;) |
| 67 |
{ |
| 68 |
while (pb <= pc && (r = cmp (pb, a)) <= 0) |
| 69 |
{ |
| 70 |
if (r == 0) |
| 71 |
{ |
| 72 |
swap_cnt = 1; |
| 73 |
swap (pa, pb); |
| 74 |
pa += es; |
| 75 |
} |
| 76 |
pb += es; |
| 77 |
} |
| 78 |
while (pb <= pc && (r = cmp (pc, a)) >= 0) |
| 79 |
{ |
| 80 |
if (r == 0) |
| 81 |
{ |
| 82 |
swap_cnt = 1; |
| 83 |
swap (pc, pd); |
| 84 |
pd -= es; |
| 85 |
} |
| 86 |
pc -= es; |
| 87 |
} |
| 88 |
if (pb > pc) |
| 89 |
break; |
| 90 |
swap (pb, pc); |
| 91 |
swap_cnt = 1; |
| 92 |
pb += es; |
| 93 |
pc -= es; |
| 94 |
} |
| 95 |
if (swap_cnt == 0) |
| 96 |
{ |
| 97 |
for (pm = (char*) a + es; pm < (char*) a + n * es; pm += es) |
| 98 |
for (pl = pm; pl > (char*) a && cmp (pl - es, pl) > 0; pl -= es) |
| 99 |
swap (pl, pl - es); |
| 100 |
return; |
| 101 |
} |
| 102 |
|
| 103 |
pn = (char*) a + n * es; |
| 104 |
r = min (pa - (char*) a, pb - pa); |
| 105 |
vecswap (a, pb - r, r); |
| 106 |
r = min (pd - pc, (int) (pn - pd - es)); |
| 107 |
vecswap (pb, pn - r, r); |
| 108 |
if ((r = pb - pa) > (int) es) |
| 109 |
qsort(a, r / es, es, cmp); |
| 110 |
if ((r = pd - pc) > (int) es) |
| 111 |
{ |
| 112 |
/* Iterate rather than recurse to save stack space */ |
| 113 |
a = pn - r; |
| 114 |
n = r / es; |
| 115 |
goto loop; |
| 116 |
} |
| 117 |
} |