Changeset View
Changeset View
Standalone View
Standalone View
lib/libc/stdlib/qsort.c
Show All 31 Lines | |||||
#if defined(LIBC_SCCS) && !defined(lint) | #if defined(LIBC_SCCS) && !defined(lint) | ||||
static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; | static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; | ||||
#endif /* LIBC_SCCS and not lint */ | #endif /* LIBC_SCCS and not lint */ | ||||
#include <sys/cdefs.h> | #include <sys/cdefs.h> | ||||
__FBSDID("$FreeBSD$"); | __FBSDID("$FreeBSD$"); | ||||
#include <stdlib.h> | #include <stdlib.h> | ||||
#ifdef I_AM_QSORT_R | #if defined(I_AM_QSORT_R) | ||||
typedef int cmp_t(const void *, const void *, void *); | |||||
#elif defined(I_AM_QSORT_R_COMPAT) | |||||
typedef int cmp_t(void *, const void *, const void *); | typedef int cmp_t(void *, const void *, const 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 *); | ||||
#define MIN(a, b) ((a) < (b) ? a : b) | #define MIN(a, b) ((a) < (b) ? a : b) | ||||
Show All 11 Lines | do { | ||||
*a++ = *b; | *a++ = *b; | ||||
*b++ = t; | *b++ = t; | ||||
} while (--es > 0); | } while (--es > 0); | ||||
} | } | ||||
#define vecswap(a, b, n) \ | #define vecswap(a, b, n) \ | ||||
if ((n) > 0) swapfunc(a, b, n) | if ((n) > 0) swapfunc(a, b, n) | ||||
#ifdef I_AM_QSORT_R | #if defined(I_AM_QSORT_R) | ||||
#define CMP(t, x, y) (cmp((x), (y), (t))) | |||||
#elif defined(I_AM_QSORT_R_COMPAT) | |||||
#define CMP(t, x, y) (cmp((t), (x), (y))) | #define CMP(t, x, y) (cmp((t), (x), (y))) | ||||
#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 | #if !defined(I_AM_QSORT_R) && !defined(I_AM_QSORT_R_COMPAT) | ||||
__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 | #if defined(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) | ||||
#elif defined(I_AM_QSORT_R_COMPAT) | |||||
void | |||||
__qsort_r_compat(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) | |||||
#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 66 Lines • ▼ Show 20 Lines | loop: | ||||
d1 = MIN(pd - pc, pn - pd - es); | d1 = MIN(pd - pc, pn - pd - 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 | #if defined(I_AM_QSORT_R) | ||||
qsort_r(a, d1 / es, es, thunk, cmp); | qsort_r(a, d1 / es, es, cmp, thunk); | ||||
#elif defined(I_AM_QSORT_R_COMPAT) | |||||
__qsort_r_compat(a, d1 / es, es, thunk, cmp); | |||||
#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 | #if defined(I_AM_QSORT_R) | ||||
qsort_r(pn - d2, d2 / es, es, thunk, cmp); | qsort_r(pn - d2, d2 / es, es, cmp, thunk); | ||||
#elif defined(I_AM_QSORT_R_COMPAT) | |||||
__qsort_r_compat(pn - d2, d2 / es, es, thunk, cmp); | |||||
#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; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
kib: Why not put this into qsort_r_compat.c ? |
Why not put this into qsort_r_compat.c ?