From 1e9d313b895c6630c6dbf532a07cb5712ff0d960 Mon Sep 17 00:00:00 2001 From: delphij Date: Wed, 31 May 2017 06:26:37 +0000 Subject: [PATCH] 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 git-svn-id: svn://svn.freebsd.org/base/stable/10@319291 ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f --- kerberos5/lib/libroken/Makefile | 1 - lib/libc/stdlib/qsort.c | 59 ++++++++++----- sys/libkern/qsort.c | 129 ++++++++++++++++++++------------ 3 files changed, 123 insertions(+), 66 deletions(-) diff --git a/kerberos5/lib/libroken/Makefile b/kerberos5/lib/libroken/Makefile index 39e15a549..cf3d7b014 100644 --- a/kerberos5/lib/libroken/Makefile +++ b/kerberos5/lib/libroken/Makefile @@ -53,7 +53,6 @@ SRCS= base64.c \ parse_bytes.c \ parse_time.c \ parse_units.c \ - qsort.c \ rand.c \ realloc.c \ resolve.c \ diff --git a/lib/libc/stdlib/qsort.c b/lib/libc/stdlib/qsort.c index 08816887c..1ccc518d3 100644 --- a/lib/libc/stdlib/qsort.c +++ b/lib/libc/stdlib/qsort.c @@ -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, 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, 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);*/ } diff --git a/sys/libkern/qsort.c b/sys/libkern/qsort.c index 7a758d3a8..9c83f608d 100644 --- a/sys/libkern/qsort.c +++ b/sys/libkern/qsort.c @@ -33,51 +33,57 @@ __FBSDID("$FreeBSD$"); #include #include -#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); - -#define min(a, b) (a) < (b) ? (a) : (b) +static inline char *med3(char *, char *, char *, cmp_t *, void *); +static inline void swapfunc(char *, char *, size_t, int, int); /* * 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, d1 / es, es, cmp); +#endif + } + 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(a, r / es, es, cmp); + qsort(pn - d2, d2 / 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 (d1 > es) { + /* Iterate rather than recurse to save stack space */ + /* qsort(a, d1 / es, es, cmp); */ + n = d1 / es; + goto loop; + } } } -- 2.45.0