Page MenuHomeFreeBSD
Differential D23174 Diff 67041 head/lib/libc/stdlib/qsort.c

Changeset View

Standalone View

View Options

head/lib/libc/stdlib/qsort.c

Show All 29 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 <errno.h>
#include <stdint.h>
#include <stdlib.h> #include <stdlib.h>
#include <string.h>
#include "libc_private.h"
#ifdef I_AM_QSORT_R #if defined(I_AM_QSORT_R)
typedef int cmp_t(void *, const void *, const void *); typedef int cmp_t(void *, const void *, const void *);
#elif defined(I_AM_QSORT_S)
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 *);
#define MIN(a, b) ((a) < (b) ? a : b) #define MIN(a, b) ((a) < (b) ? a : b)
/* /*
Show All 10 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((t), (x), (y))) #define CMP(t, x, y) (cmp((t), (x), (y)))
#elif defined(I_AM_QSORT_S)
#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 #if !defined(I_AM_QSORT_R) && !defined(I_AM_QSORT_S)
__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, void *thunk, cmp_t *cmp)
#elif defined(I_AM_QSORT_S)
errno_t
qsort_s(void *a, rsize_t n, rsize_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;
int cmp_result; int cmp_result;
int swap_cnt; int swap_cnt;
#ifdef I_AM_QSORT_S
if (n > RSIZE_MAX) {
__throw_constraint_handler_s("qsort_s : n > RSIZE_MAX", EINVAL);
return (EINVAL);
} else if (es > RSIZE_MAX) {
__throw_constraint_handler_s("qsort_s : es > RSIZE_MAX", EINVAL);
return (EINVAL);
} else if (n != 0) {
if (a == NULL) {
__throw_constraint_handler_s("qsort_s : a == NULL", EINVAL);
return (EINVAL);
} else if (cmp == NULL) {
__throw_constraint_handler_s("qsort_s : cmp == NULL", EINVAL);
return (EINVAL);
}
}
#endif
loop: loop:
swap_cnt = 0; swap_cnt = 0;
if (n < 7) { if (n < 7) {
for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
for (pl = pm; for (pl = pm;
pl > (char *)a && CMP(thunk, pl - es, pl) > 0; pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
pl -= es) pl -= es)
swapfunc(pl, pl - es, es); swapfunc(pl, pl - es, es);
#ifdef I_AM_QSORT_S
return (0);
#else
return; return;
#endif
} }
pm = (char *)a + (n / 2) * es; pm = (char *)a + (n / 2) * es;
if (n > 7) { if (n > 7) {
pl = a; pl = a;
pn = (char *)a + (n - 1) * es; pn = (char *)a + (n - 1) * es;
if (n > 40) { if (n > 40) {
size_t d = (n / 8) * es; size_t d = (n / 8) * es;
Show All 32 Lines for (;;) {
pc -= es; pc -= es;
} }
if (swap_cnt == 0) { /* Switch to insertion sort */ if (swap_cnt == 0) { /* Switch to insertion sort */
for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
for (pl = pm; for (pl = pm;
pl > (char *)a && CMP(thunk, pl - es, pl) > 0; pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
pl -= es) pl -= es)
swapfunc(pl, pl - es, es); swapfunc(pl, pl - es, es);
#ifdef I_AM_QSORT_S
return (0);
#else
return; return;
#endif
} }
pn = (char *)a + n * es; pn = (char *)a + n * es;
d1 = MIN(pa - (char *)a, pb - pa); d1 = MIN(pa - (char *)a, pb - pa);
vecswap(a, pb - d1, d1); vecswap(a, pb - d1, d1);
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, thunk, cmp);
#elif defined(I_AM_QSORT_S)
qsort_s(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 #if defined(I_AM_QSORT_R)
qsort_r(pn - d2, d2 / es, es, thunk, cmp); qsort_r(pn - d2, d2 / es, es, thunk, cmp);
#elif defined(I_AM_QSORT_S)
qsort_s(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;
} }
} }
#ifdef I_AM_QSORT_S
return (0);
#endif
} }