Date: Wed, 31 May 2017 06:26:37 +0000 (UTC) From: Xin LI <delphij@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-10@freebsd.org Subject: svn commit: r319291 - in stable/10: kerberos5/lib/libroken lib/libc/stdlib sys/libkern Message-ID: <201705310626.v4V6Qbxn064699@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
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; + } } }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201705310626.v4V6Qbxn064699>