Changeset View
Changeset View
Standalone View
Standalone View
sys/libkern/qsort.c
Show All 30 Lines | |||||
#include <sys/cdefs.h> | #include <sys/cdefs.h> | ||||
__FBSDID("$FreeBSD$"); | __FBSDID("$FreeBSD$"); | ||||
#include <sys/param.h> | #include <sys/param.h> | ||||
#include <sys/libkern.h> | #include <sys/libkern.h> | ||||
#ifdef I_AM_QSORT_R | #ifdef I_AM_QSORT_R | ||||
typedef int cmp_t(void *, const void *, const void *); | typedef int cmp_t(const void *, const void *, void *); | ||||
#else | #else | ||||
typedef int cmp_t(const void *, const void *); | typedef int cmp_t(const void *, const void *); | ||||
#endif | #endif | ||||
static inline char *med3(char *, char *, char *, cmp_t *, void *); | static inline char *med3(char *, char *, char *, cmp_t *, void *); | ||||
static inline void swapfunc(char *, char *, size_t, int, int); | static inline void swapfunc(char *, char *, size_t, int, int); | ||||
/* | /* | ||||
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". | ||||
Show All 35 Lines | if (swaptype_long == 0) { \ | ||||
*(int *)(b) = t; \ | *(int *)(b) = t; \ | ||||
} else \ | } else \ | ||||
swapfunc(a, b, es, swaptype_long, swaptype_int) | swapfunc(a, b, es, swaptype_long, swaptype_int) | ||||
#define vecswap(a, b, n) \ | #define vecswap(a, b, n) \ | ||||
if ((n) > 0) swapfunc(a, b, n, swaptype_long, swaptype_int) | if ((n) > 0) swapfunc(a, b, n, swaptype_long, swaptype_int) | ||||
#ifdef I_AM_QSORT_R | #ifdef I_AM_QSORT_R | ||||
#define CMP(t, x, y) (cmp((t), (x), (y))) | #define CMP(t, x, y) (cmp((x), (y), (t))) | ||||
#else | #else | ||||
#define CMP(t, x, y) (cmp((x), (y))) | #define CMP(t, x, y) (cmp((x), (y))) | ||||
#endif | #endif | ||||
static inline char * | static inline char * | ||||
med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk | med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk | ||||
#ifndef I_AM_QSORT_R | #ifndef I_AM_QSORT_R | ||||
__unused | __unused | ||||
#endif | #endif | ||||
) | ) | ||||
{ | { | ||||
return CMP(thunk, a, b) < 0 ? | return CMP(thunk, a, b) < 0 ? | ||||
(CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) | (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) | ||||
:(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); | :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); | ||||
} | } | ||||
#ifdef I_AM_QSORT_R | #ifdef I_AM_QSORT_R | ||||
void | void | ||||
qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) | (qsort_r)(void *a, size_t n, size_t es, cmp_t *cmp, void *thunk) | ||||
#else | #else | ||||
#define thunk NULL | #define thunk NULL | ||||
void | void | ||||
qsort(void *a, size_t n, size_t es, cmp_t *cmp) | qsort(void *a, size_t n, size_t es, cmp_t *cmp) | ||||
#endif | #endif | ||||
{ | { | ||||
char *pa, *pb, *pc, *pd, *pl, *pm, *pn; | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; | ||||
size_t d1, d2; | size_t d1, d2; | ||||
▲ Show 20 Lines • Show All 68 Lines • ▼ Show 20 Lines | loop: SWAPINIT(long, a, es); | ||||
vecswap(pb, pn - d1, d1); | vecswap(pb, pn - d1, d1); | ||||
d1 = pb - pa; | d1 = pb - pa; | ||||
d2 = pd - pc; | d2 = pd - pc; | ||||
if (d1 <= d2) { | if (d1 <= d2) { | ||||
/* Recurse on left partition, then iterate on right partition */ | /* Recurse on left partition, then iterate on right partition */ | ||||
if (d1 > es) { | if (d1 > es) { | ||||
#ifdef I_AM_QSORT_R | #ifdef I_AM_QSORT_R | ||||
qsort_r(a, d1 / es, es, thunk, cmp); | qsort_r(a, d1 / es, es, cmp, thunk); | ||||
#else | #else | ||||
qsort(a, d1 / es, es, cmp); | qsort(a, d1 / es, es, cmp); | ||||
#endif | #endif | ||||
} | } | ||||
if (d2 > es) { | if (d2 > es) { | ||||
/* Iterate rather than recurse to save stack space */ | /* Iterate rather than recurse to save stack space */ | ||||
/* qsort(pn - d2, d2 / es, es, cmp); */ | /* qsort(pn - d2, d2 / es, es, cmp); */ | ||||
a = pn - d2; | a = pn - d2; | ||||
n = d2 / es; | n = d2 / es; | ||||
goto loop; | goto loop; | ||||
} | } | ||||
} else { | } else { | ||||
/* Recurse on right partition, then iterate on left partition */ | /* Recurse on right partition, then iterate on left partition */ | ||||
if (d2 > es) { | if (d2 > es) { | ||||
#ifdef I_AM_QSORT_R | #ifdef I_AM_QSORT_R | ||||
qsort_r(pn - d2, d2 / es, es, thunk, cmp); | qsort_r(pn - d2, d2 / es, es, cmp, thunk); | ||||
#else | #else | ||||
qsort(pn - d2, d2 / es, es, cmp); | qsort(pn - d2, d2 / es, es, cmp); | ||||
#endif | #endif | ||||
} | } | ||||
if (d1 > es) { | if (d1 > es) { | ||||
/* Iterate rather than recurse to save stack space */ | /* Iterate rather than recurse to save stack space */ | ||||
/* qsort(a, d1 / es, es, cmp); */ | /* qsort(a, d1 / es, es, cmp); */ | ||||
n = d1 / es; | n = d1 / es; | ||||
goto loop; | goto loop; | ||||
} | } | ||||
} | } | ||||
} | } |