scc

commit a7be835f62ea88b05cfd3ee3a31e702133d7cbd2
parent a15a20fdd53e15e9250237d2c7c9d112d5e3cd01
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Wed, 21 Aug 2019 10:31:42 +0100

[libc] Avoid too deep recursion in qsort()

Recursing over the smaller part of the array before than
over the bigger part limits the recursion depth to
log2(n).

Diffstat:
M
src/libc/stdlib/qsort.c
 | 
22
++++++++++++++++++----

1 file changed, 18 insertions(+), 4 deletions(-)
diff --git a/src/libc/stdlib/qsort.c b/src/libc/stdlib/qsort.c
@@ -23,10 +23,15 @@ swap(char *i, char *j, size_t n)
 	} while (--n > 0);
 }
 
+/*
+ * This function recurses as much as log2(n) because
+ * it always recurses in the smaller part of the
+ * array.
+ */
 static void
 xqsort(char *a, size_t n, struct qsort *qs)
 {
-	size_t j, es = qs->es;
+	size_t nj, ni, es = qs->es;
 	char *pi, *pj, *pn;
 
 	if (n <= 1)
@@ -51,9 +56,18 @@ xqsort(char *a, size_t n, struct qsort *qs)
 	}
 	swap(a, pj, es);
 
-	j = (pj - a) / es;
-	xqsort(a, j, qs);
-	xqsort(a + (j+1)*es, n-j-1, qs);
+	pi = a;
+	ni = (pj - a) / es;
+	pj += es;
+	nj = n-nj-1;
+
+	if (ni < nj) {
+		xqsort(pi, ni, qs);
+		xqsort(pj, nj, qs);
+	} else {
+		xqsort(pj, nj, qs);
+		xqsort(pi, ni, qs);
+	}
 }
 
 void