[coreboot-gerrit] Change in coreboot[master]: payloads/libpayload/libc: uppgrade qsort.c to v1.15

[HAOUAS Elyes (Code Review)]

HAOUAS Elyes has uploaded this change for review. ( https://review.coreboot.org/c/coreboot/+/43717 )

Change subject: payloads/libpayload/libc: uppgrade qsort.c to v1.15
......................................................................

payloads/libpayload/libc: uppgrade qsort.c to v1.15

Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283
Signed-off-by: Elyes HAOUAS 
---
M payloads/libpayload/libc/qsort.c
1 file changed, 42 insertions(+), 37 deletions(-)

git pull ssh://review.coreboot.org:29418/coreboot refs/changes/17/43717/1

diff --git a/payloads/libpayload/libc/qsort.c b/payloads/libpayload/libc/qsort.c
index aad2aa3..51d67bc 100644
--- a/payloads/libpayload/libc/qsort.c
+++ b/payloads/libpayload/libc/qsort.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: qsort.c,v 1.11 2010/02/08 11:04:07 otto Exp $ */
+/*	$OpenBSD: qsort.c,v 1.15 2017/05/17 16:58:20 millert Exp $ */
 /*-
  * Copyright (c) 1992, 1993
  *	The Regents of the University of California.  All rights reserved.
@@ -39,11 +39,11 @@
 /*
  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  */
-#define swapcode(TYPE, parmi, parmj, n) { 		\
-	size_t i = (n) / sizeof (TYPE); 		\
-	TYPE *pi = (TYPE *) (parmi); 			\
-	TYPE *pj = (TYPE *) (parmj); 			\
-	do { 						\
+#define swapcode(TYPE, parmi, parmj, n) {		\
+	size_t i = (n) / sizeof(TYPE);			\
+	TYPE *pi = (TYPE *) (parmi);			\
+	TYPE *pj = (TYPE *) (parmj);			\
+	do {						\
    	TYPE	t = *pi;			\
    	*pi++ = *pj;				\
    	*pj++ = t;				\
@@ -70,7 +70,7 @@
    } else						\
    	swapfunc(a, b, es, swaptype)

-#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)

static __inline char *
 med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
@@ -84,23 +84,22 @@
 qsort(void *aa, size_t n, size_t es, int (*cmp)(const void *, const void *))
 {
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
-	int cmp_result, swaptype, swap_cnt;
-	size_t d, r;
+	int cmp_result, swaptype;
+	size_t d, r, s;
    char *a = aa;

loop:	SWAPINIT(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(pl - es, pl) > 0;
+		for (pm = a + es; pm < a + n * es; pm += es)
+			for (pl = pm; pl > a && cmp(pl - es, pl) > 0;
    		     pl -= es)
    			swap(pl, pl - es);
    	return;
    }
-	pm = (char *)a + (n / 2) * es;
+	pm = a + (n / 2) * es;
    if (n > 7) {
-		pl = (char *)a;
-		pn = (char *)a + (n - 1) * es;
+		pl = a;
+		pn = a + (n - 1) * es;
    	if (n > 40) {
    		d = (n / 8) * es;
    		pl = med3(pl, pl + d, pl + 2 * d, cmp);
@@ -110,13 +109,12 @@
    	pm = med3(pl, pm, pn, cmp);
    }
    swap(a, pm);
-	pa = pb = (char *)a + es;
+	pa = pb = a + es;

-	pc = pd = (char *)a + (n - 1) * es;
+	pc = pd = a + (n - 1) * es;
    for (;;) {
    	while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
    		if (cmp_result == 0) {
-				swap_cnt = 1;
    			swap(pa, pb);
    			pa += es;
    		}
@@ -124,7 +122,6 @@
    	}
    	while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
    		if (cmp_result == 0) {
-				swap_cnt = 1;
    			swap(pc, pd);
    			pd -= es;
    		}
@@ -133,30 +130,38 @@
    	if (pb > pc)
    		break;
    	swap(pb, pc);
-		swap_cnt = 1;
    	pb += es;
    	pc -= 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(pl - es, pl) > 0;
-			     pl -= es)
-				swap(pl, pl - es);
-		return;
-	}

-	pn = (char *)a + n * es;
-	r = min(pa - (char *)a, pb - pa);
+	pn = a + n * es;
+	r = min(pa - 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)
-		qsort(a, r / es, es, cmp);
-	if ((r = pd - pc) > es) {
-		/* Iterate rather than recurse to save stack space */
-		a = pn - r;
-		n = r / es;
-		goto loop;
+	/*
+	 * To save stack space we sort the smaller side of the partition first
+	 * using recursion and eliminate tail recursion for the larger side.
+	 */
+	r = pb - pa;
+	s = pd - pc;
+	if (r < s) {
+		/* Recurse for 1st side, iterate for 2nd side. */
+		if (s > es) {
+			if (r > es)
+				qsort(a, r / es, es, cmp);
+			a = pn - s;
+			n = s / es;
+			goto loop;
+		}
+	} else {
+		/* Recurse for 2nd side, iterate for 1st side. */
+		if (r > es) {
+			if (s > es)
+				qsort(pn - s, s / es, es, cmp);
+			n = r / es;
+			goto loop;
+		}
    }
-/*		qsort(pn - r, r / es, es, cmp);*/
 }
+DEF_STRONG(qsort);