Author: delphij
Date: Wed May 31 06:26:37 2017
New Revision: 319291
URL: https://svnweb.freebsd.org/changeset/base/319291
Log:
MFC r318514-r318515, r318517, r318917
r318514:
Use size_t.
Inspired by: OpenBSD src/lib/libc/stdlib/qsort.c,v 1.11
r318515:
The current qsort(3) implementation ignores the sizes of partitions, and
always perform recursion on the left partition, then use a tail call to
handle the right partition. In the worst case this could require O(N)
levels of recursions.
Reduce the possible recursion level to log2(N) by always recursing on the
smaller partition instead.
Obtained from: PostgreSQL 9d6077abf9d6efd992a59f05ef5aba981ea32096
r318517:
Sync qsort.c with userland r318515.
(Note that MIN macro is removed in favor of sys/param.h's version).
PR: 213922
r318917:
Disconnect heimdal version of qsort.c from build because we are already
using libc's version of qsort.
PR: bin/213922
Modified:
stable/10/kerberos5/lib/libroken/Makefile
stable/10/lib/libc/stdlib/qsort.c
stable/10/sys/libkern/qsort.c
Directory Properties:
stable/10/ (props changed)
Modified: stable/10/kerberos5/lib/libroken/Makefile
==============================================================================
--- stable/10/kerberos5/lib/libroken/Makefile Wed May 31 06:19:12 2017
(r319290)
+++ stable/10/kerberos5/lib/libroken/Makefile Wed May 31 06:26:37 2017
(r319291)
@@ -53,7 +53,6 @@ SRCS= base64.c \
parse_bytes.c \
parse_time.c \
parse_units.c \
- qsort.c \
rand.c \
realloc.c \
resolve.c \
Modified: stable/10/lib/libc/stdlib/qsort.c
==============================================================================
--- stable/10/lib/libc/stdlib/qsort.c Wed May 31 06:19:12 2017
(r319290)
+++ stable/10/lib/libc/stdlib/qsort.c Wed May 31 06:26:37 2017
(r319291)
@@ -41,7 +41,7 @@ typedef int cmp_t(void *, const void *, const void
*
typedef int cmp_t(const void *, const void *);
#endif
static inline char *med3(char *, char *, char *, cmp_t *, void *);
-static inline void swapfunc(char *, char *, int, int, int);
+static inline void swapfunc(char *, char *, size_t, int, int);
#define MIN(a, b) ((a) < (b) ? a : b)
@@ -49,7 +49,7 @@ static inline void swapfunc(char *, char *, int, int,
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
*/
#define swapcode(TYPE, parmi, parmj, n) { \
- long i = (n) / sizeof (TYPE); \
+ size_t i = (n) / sizeof (TYPE); \
TYPE *pi = (TYPE *) (parmi); \
TYPE *pj = (TYPE *) (parmj); \
do { \
@@ -64,7 +64,7 @@ static inline void swapfunc(char *, char *, int, int,
es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1;
static inline void
-swapfunc( char *a, char *b, int n, int swaptype_long, int swaptype_int)
+swapfunc(char *a, char *b, size_t n, int swaptype_long, int swaptype_int)
{
if (swaptype_long <= 1)
swapcode(long, a, b, n)
@@ -117,7 +117,7 @@ qsort(void *a, size_t n, size_t es, cmp_t *cmp)
#endif
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
- size_t d, r;
+ size_t d1, d2;
int cmp_result;
int swaptype_long, swaptype_int, swap_cnt;
@@ -137,7 +137,8 @@ loop: SWAPINIT(long, a, es);
pl = a;
pn = (char *)a + (n - 1) * es;
if (n > 40) {
- d = (n / 8) * es;
+ size_t d = (n / 8) * es;
+
pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
pm = med3(pm - d, pm, pm + d, cmp, thunk);
pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
@@ -182,21 +183,43 @@ loop: SWAPINIT(long, a, es);
}
pn = (char *)a + n * es;
- r = MIN(pa - (char *)a, pb - pa);
- vecswap(a, pb - r, r);
- r = MIN(pd - pc, pn - pd - es);
- vecswap(pb, pn - r, r);
- if ((r = pb - pa) > es)
+ d1 = MIN(pa - (char *)a, pb - pa);
+ vecswap(a, pb - d1, d1);
+ d1 = MIN(pd - pc, pn - pd - es);
+ vecswap(pb, pn - d1, d1);
+
+ d1 = pb - pa;
+ d2 = pd - pc;
+ if (d1 <= d2) {
+ /* Recurse on left partition, then iterate on right partition */
+ if (d1 > es) {
#ifdef I_AM_QSORT_R
- qsort_r(a, r / es, es, thunk, cmp);
+ qsort_r(a, d1 / es, es, thunk, cmp);
#else
- qsort(a, r / es, es, cmp);
+ qsort(a, d1 / es, es, cmp);
#endif
- if ((r = pd - pc) > es) {
- /* Iterate rather than recurse to save stack space */
- a = pn - r;
- n = r / es;
- goto loop;
+ }
+ if (d2 > es) {
+ /* Iterate rather than recurse to save stack space */
+ /* qsort(pn - d2, d2 / es, es, cmp); */
+ a = pn - d2;
+ n = d2 / es;
+ goto loop;
+ }
+ } else {
+ /* Recurse on right partition, then iterate on left partition */
+ if (d2 > es) {
+#ifdef I_AM_QSORT_R
+ qsort_r(pn - d2, d2 / es, es, thunk, cmp);
+#else
+ qsort(pn - d2, d2 / es, es, cmp);
+#endif
+ }
+ if (d1 > es) {
+ /* Iterate rather than recurse to save stack space */
+ /* qsort(a, d1 / es, es, cmp); */
+ n = d1 / es;
+ goto loop;
+ }
}
-/* qsort(pn - r, r / es, es, cmp);*/
}
Modified: stable/10/sys/libkern/qsort.c
==============================================================================
--- stable/10/sys/libkern/qsort.c Wed May 31 06:19:12 2017
(r319290)
+++ stable/10/sys/libkern/qsort.c Wed May 31 06:26:37 2017
(r319291)
@@ -33,51 +33,57 @@ __FBSDID("$FreeBSD$");
#include <sys/param.h>
#include <sys/libkern.h>
-#ifdef I_AM_QSORT_R
-typedef int cmp_t(void *, const void *, const void *);
+#ifdef I_AM_QSORT_R
+typedef int cmp_t(void *, const void *, const void *);
#else
-typedef int cmp_t(const void *, const void *);
+typedef int cmp_t(const void *, const void *);
#endif
-static __inline char *med3(char *, char *, char *, cmp_t *, void *);
-static __inline void swapfunc(char *, char *, int, int);
+static inline char *med3(char *, char *, char *, cmp_t *, void *);
+static inline void swapfunc(char *, char *, size_t, int, int);
-#define min(a, b) (a) < (b) ? (a) : (b)
-
/*
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
*/
-#define swapcode(TYPE, parmi, parmj, n) { \
- long i = (n) / sizeof (TYPE); \
- TYPE *pi = (TYPE *) (parmi); \
- TYPE *pj = (TYPE *) (parmj); \
+#define swapcode(TYPE, parmi, parmj, n) { \
+ size_t i = (n) / sizeof (TYPE); \
+ TYPE *pi = (TYPE *) (parmi); \
+ TYPE *pj = (TYPE *) (parmj); \
do { \
- TYPE t = *pi; \
+ TYPE t = *pi; \
*pi++ = *pj; \
*pj++ = t; \
- } while (--i > 0); \
+ } while (--i > 0); \
}
-#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
- es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+#define SWAPINIT(TYPE, a, es) swaptype_ ## TYPE = \
+ ((char *)a - (char *)0) % sizeof(TYPE) || \
+ es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1;
-static __inline void
-swapfunc(char *a, char *b, int n, int swaptype)
+static inline void
+swapfunc(char *a, char *b, size_t n, int swaptype_long, int swaptype_int)
{
- if(swaptype <= 1)
+ if (swaptype_long <= 1)
swapcode(long, a, b, n)
+ else if (swaptype_int <= 1)
+ swapcode(int, a, b, n)
else
swapcode(char, a, b, n)
}
-#define swap(a, b) \
- if (swaptype == 0) { \
+#define swap(a, b) \
+ if (swaptype_long == 0) { \
long t = *(long *)(a); \
*(long *)(a) = *(long *)(b); \
*(long *)(b) = t; \
+ } else if (swaptype_int == 0) { \
+ int t = *(int *)(a); \
+ *(int *)(a) = *(int *)(b); \
+ *(int *)(b) = t; \
} else \
- swapfunc(a, b, es, swaptype)
+ swapfunc(a, b, es, swaptype_long, swaptype_int)
-#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
+#define vecswap(a, b, n) \
+ if ((n) > 0) swapfunc(a, b, n, swaptype_long, swaptype_int)
#ifdef I_AM_QSORT_R
#define CMP(t, x, y) (cmp((t), (x), (y)))
@@ -85,16 +91,16 @@ swapfunc(char *a, char *b, int n, int swaptype)
#define CMP(t, x, y) (cmp((x), (y)))
#endif
-static __inline char *
+static inline char *
med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk
-#ifndef I_AM_QSORT_R
+#ifndef I_AM_QSORT_R
__unused
#endif
)
{
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 ? a : c ));
+ :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
}
#ifdef I_AM_QSORT_R
@@ -107,13 +113,17 @@ qsort(void *a, size_t n, size_t es, cmp_t *cmp)
#endif
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
- int d, r, swaptype, swap_cnt;
+ size_t d1, d2;
+ int cmp_result;
+ int swaptype_long, swaptype_int, swap_cnt;
-loop: SWAPINIT(a, es);
+loop: SWAPINIT(long, a, es);
+ SWAPINIT(int, a, es);
swap_cnt = 0;
if (n < 7) {
for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
- for (pl = pm; pl > (char *)a && CMP(thunk, pl - es, pl)
> 0;
+ for (pl = pm;
+ pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
@@ -123,7 +133,8 @@ loop: SWAPINIT(a, es);
pl = a;
pn = (char *)a + (n - 1) * es;
if (n > 40) {
- d = (n / 8) * es;
+ size_t d = (n / 8) * es;
+
pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
pm = med3(pm - d, pm, pm + d, cmp, thunk);
pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
@@ -135,16 +146,16 @@ loop: SWAPINIT(a, es);
pc = pd = (char *)a + (n - 1) * es;
for (;;) {
- while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
- if (r == 0) {
+ while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
+ if (cmp_result == 0) {
swap_cnt = 1;
swap(pa, pb);
pa += es;
}
pb += es;
}
- while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
- if (r == 0) {
+ while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
+ if (cmp_result == 0) {
swap_cnt = 1;
swap(pc, pd);
pd -= es;
@@ -160,27 +171,51 @@ loop: SWAPINIT(a, es);
}
if (swap_cnt == 0) { /* Switch to insertion sort */
for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
- for (pl = pm; pl > (char *)a && CMP(thunk, pl - es, pl)
> 0;
+ for (pl = pm;
+ pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
pn = (char *)a + n * es;
- r = min(pa - (char *)a, pb - pa);
- vecswap(a, pb - r, r);
- r = min(pd - pc, pn - pd - es);
- vecswap(pb, pn - r, r);
- if ((r = pb - pa) > es)
-#ifdef I_AM_QSORT_R
- qsort_r(a, r / es, es, thunk, cmp);
+ d1 = MIN(pa - (char *)a, pb - pa);
+ vecswap(a, pb - d1, d1);
+ d1 = MIN(pd - pc, pn - pd - es);
+ vecswap(pb, pn - d1, d1);
+
+ d1 = pb - pa;
+ d2 = pd - pc;
+ if (d1 <= d2) {
+ /* Recurse on left partition, then iterate on right partition */
+ if (d1 > es) {
+#ifdef I_AM_QSORT_R
+ qsort_r(a, d1 / es, es, thunk, cmp);
#else
- qsort(a, r / es, es, cmp);
+ qsort(a, d1 / es, es, cmp);
#endif
- if ((r = pd - pc) > es) {
- /* Iterate rather than recurse to save stack space */
- a = pn - r;
- n = r / es;
- goto loop;
+ }
+ if (d2 > es) {
+ /* Iterate rather than recurse to save stack space */
+ /* qsort(pn - d2, d2 / es, es, cmp); */
+ a = pn - d2;
+ n = d2 / es;
+ goto loop;
+ }
+ } else {
+ /* Recurse on right partition, then iterate on left partition */
+ if (d2 > es) {
+#ifdef I_AM_QSORT_R
+ qsort_r(pn - d2, d2 / es, es, thunk, cmp);
+#else
+ qsort(pn - d2, d2 / es, es, cmp);
+#endif
+ }
+ if (d1 > es) {
+ /* Iterate rather than recurse to save stack space */
+ /* qsort(a, d1 / es, es, cmp); */
+ n = d1 / es;
+ goto loop;
+ }
}
}
_______________________________________________
svn-src-stable-10@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-stable-10
To unsubscribe, send any mail to "svn-src-stable-10-unsubscr...@freebsd.org"
