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

3 files changed, 123 insertions, 66 deletions

diff --git a/kerberos5/lib/libroken/Makefile b/kerberos5/lib/libroken/Makefile
index 39e15a5..cf3d7b0 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 0881688..1ccc518 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 7a758d3..9c83f60 100644
--- a/sys/libkern/qsort.c
+++ b/sys/libkern/qsort.c
@@ -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);
-
-#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;
+		}
 	}
 }