svn commit: r318515 - head/lib/libc/stdlib

[Xin LI]

Author: delphij
Date: Fri May 19 04:59:12 2017
New Revision: 318515
URL: https://svnweb.freebsd.org/changeset/base/318515

Log:
  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

Modified:
  head/lib/libc/stdlib/qsort.c

Modified: head/lib/libc/stdlib/qsort.c
==============================================================================
--- head/lib/libc/stdlib/qsort.c	Fri May 19 04:44:14 2017	(r318514)
+++ head/lib/libc/stdlib/qsort.c	Fri May 19 04:59:12 2017	(r318515)
@@ -117,7 +117,7 @@ qsort(void *a, size_t n, size_t es, 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);*/
 }