36#include <sys/libkern.h>
39typedef int cmp_t(
void *,
const void *,
const void *);
41typedef int cmp_t(
const void *,
const void *);
43static inline char *
med3(
char *,
char *,
char *,
cmp_t *,
void *);
44static inline void swapfunc(
char *,
char *,
size_t,
int,
int);
49#define swapcode(TYPE, parmi, parmj, n) { \
50 size_t i = (n) / sizeof (TYPE); \
51 TYPE *pi = (TYPE *) (parmi); \
52 TYPE *pj = (TYPE *) (parmj); \
60#define SWAPINIT(TYPE, a, es) swaptype_ ## TYPE = \
61 ((char *)a - (char *)0) % sizeof(TYPE) || \
62 es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1;
65swapfunc(
char *a,
char *b,
size_t n,
int swaptype_long,
int swaptype_int)
67 if (swaptype_long <= 1)
69 else if (swaptype_int <= 1)
76 if (swaptype_long == 0) { \
77 long t = *(long *)(a); \
78 *(long *)(a) = *(long *)(b); \
80 } else if (swaptype_int == 0) { \
81 int t = *(int *)(a); \
82 *(int *)(a) = *(int *)(b); \
85 swapfunc(a, b, es, swaptype_long, swaptype_int)
87#define vecswap(a, b, n) \
88 if ((n) > 0) swapfunc(a, b, n, swaptype_long, swaptype_int)
91#define CMP(t, x, y) (cmp((t), (x), (y)))
93#define CMP(t, x, y) (cmp((x), (y)))
110qsort_r(
void *a,
size_t n,
size_t es,
void *
thunk,
cmp_t *cmp)
117 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
120 int swaptype_long, swaptype_int, swap_cnt;
126 for (pm = (
char *)a + es; pm < (
char *)a + n * es; pm += es)
128 pl > (
char *)a &&
CMP(
thunk, pl - es, pl) > 0;
133 pm = (
char *)a + (n / 2) * es;
136 pn = (
char *)a + (n - 1) * es;
138 size_t d = (n / 8) * es;
140 pl =
med3(pl, pl + d, pl + 2 * d, cmp,
thunk);
141 pm =
med3(pm - d, pm, pm + d, cmp,
thunk);
142 pn =
med3(pn - 2 * d, pn - d, pn, cmp,
thunk);
147 pa = pb = (
char *)a + es;
149 pc = pd = (
char *)a + (n - 1) * es;
151 while (pb <= pc && (cmp_result =
CMP(
thunk, pb, a)) <= 0) {
152 if (cmp_result == 0) {
159 while (pb <= pc && (cmp_result =
CMP(
thunk, pc, a)) >= 0) {
160 if (cmp_result == 0) {
175 for (pm = (
char *)a + es; pm < (
char *)a + n * es; pm += es)
177 pl > (
char *)a &&
CMP(
thunk, pl - es, pl) > 0;
183 pn = (
char *)a + n * es;
184 d1 = MIN(pa - (
char *)a, pb - pa);
186 d1 = MIN(pd - pc, pn - pd - es);
195 qsort_r(a, d1 / es, es,
thunk, cmp);
197 qsort(a, d1 / es, es, cmp);
211 qsort_r(pn - d2, d2 / es, es,
thunk, cmp);
213 qsort(pn - d2, d2 / es, es, cmp);
void qsort(void *a, size_t n, size_t es, cmp_t *cmp)
static char * med3(char *, char *, char *, cmp_t *, void *)
#define SWAPINIT(TYPE, a, es)
#define swapcode(TYPE, parmi, parmj, n)
int cmp_t(const void *, const void *)
static void swapfunc(char *, char *, size_t, int, int)