Skip site navigation (1)Skip section navigation (2)
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>