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 ehaouas@noos.fr --- 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);
build bot (Jenkins) has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: uppgrade qsort.c to v1.15 ......................................................................
Patch Set 1:
(1 comment)
https://review.coreboot.org/c/coreboot/+/43717/1/payloads/libpayload/libc/qs... File payloads/libpayload/libc/qsort.c:
https://review.coreboot.org/c/coreboot/+/43717/1/payloads/libpayload/libc/qs... PS1, Line 73: #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) Macros starting with if should be enclosed by a do - while loop to avoid possible if/else logic defects
HAOUAS Elyes has uploaded a new patch set (#2). ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
payloads/libpayload/libc: upgrade "qsort.c" to v1.15
Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283 Signed-off-by: Elyes HAOUAS ehaouas@noos.fr --- 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/2
Hello build bot (Jenkins),
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/43717
to look at the new patch set (#3).
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
payloads/libpayload/libc: upgrade "qsort.c" to v1.15
Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283 Signed-off-by: Elyes HAOUAS ehaouas@noos.fr --- M payloads/libpayload/libc/qsort.c 1 file changed, 41 insertions(+), 37 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/17/43717/3
build bot (Jenkins) has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
Patch Set 3:
(1 comment)
https://review.coreboot.org/c/coreboot/+/43717/3/payloads/libpayload/libc/qs... File payloads/libpayload/libc/qsort.c:
https://review.coreboot.org/c/coreboot/+/43717/3/payloads/libpayload/libc/qs... PS3, Line 73: #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) Macros starting with if should be enclosed by a do - while loop to avoid possible if/else logic defects
Angel Pons has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
Patch Set 3: Code-Review+1
(1 comment)
https://review.coreboot.org/c/coreboot/+/43717/3//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/43717/3//COMMIT_MSG@8 PS3, Line 8: Any improvements?
HAOUAS Elyes has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
Patch Set 3:
(1 comment)
https://review.coreboot.org/c/coreboot/+/43717/3//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/43717/3//COMMIT_MSG@8 PS3, Line 8:
Any improvements?
maybe I need to upgrade to v1.18. it needs test.
https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/qsort.c
Hello build bot (Jenkins), Angel Pons,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/43717
to look at the new patch set (#4).
Change subject: payloads/libpayload/libc: uppgrade qsort.c to v1.18 ......................................................................
payloads/libpayload/libc: uppgrade qsort.c to v1.18
Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283 Signed-off-by: Elyes HAOUAS ehaouas@noos.fr --- M payloads/libpayload/libc/qsort.c 1 file changed, 132 insertions(+), 58 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/17/43717/4
build bot (Jenkins) has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: uppgrade qsort.c to v1.18 ......................................................................
Patch Set 4:
(5 comments)
https://review.coreboot.org/c/coreboot/+/43717/4/payloads/libpayload/libc/qs... File payloads/libpayload/libc/qsort.c:
https://review.coreboot.org/c/coreboot/+/43717/4/payloads/libpayload/libc/qs... PS4, Line 103: case SWAPTYPE_LONG: { \ Possible switch case/default not preceded by break or fallthrough comment
https://review.coreboot.org/c/coreboot/+/43717/4/payloads/libpayload/libc/qs... PS4, Line 109: default: \ Possible switch case/default not preceded by break or fallthrough comment
https://review.coreboot.org/c/coreboot/+/43717/4/payloads/libpayload/libc/qs... PS4, Line 114: #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) Macros starting with if should be enclosed by a do - while loop to avoid possible if/else logic defects
https://review.coreboot.org/c/coreboot/+/43717/4/payloads/libpayload/libc/qs... PS4, Line 126: int (*cmp)(const void *, const void *)) please, no spaces at the start of a line
https://review.coreboot.org/c/coreboot/+/43717/4/payloads/libpayload/libc/qs... PS4, Line 132: loop: if (n < 7) { suspect code indent for conditional statements (0, 16)
Hello build bot (Jenkins), Angel Pons,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/43717
to look at the new patch set (#5).
Change subject: payloads/libpayload/libc: uppgrade qsort.c to v1.18 ......................................................................
payloads/libpayload/libc: uppgrade qsort.c to v1.18
needs tests
Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283 Signed-off-by: Elyes HAOUAS ehaouas@noos.fr --- M payloads/libpayload/libc/qsort.c 1 file changed, 132 insertions(+), 58 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/17/43717/5
Hello build bot (Jenkins), Angel Pons,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/43717
to look at the new patch set (#6).
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
payloads/libpayload/libc: upgrade "qsort.c" to v1.15
Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283 Signed-off-by: Elyes HAOUAS ehaouas@noos.fr --- M payloads/libpayload/libc/qsort.c 1 file changed, 41 insertions(+), 37 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/17/43717/6
build bot (Jenkins) has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/43717/6/payloads/libpayload/libc/qs... File payloads/libpayload/libc/qsort.c:
https://review.coreboot.org/c/coreboot/+/43717/6/payloads/libpayload/libc/qs... PS6, Line 73: #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) Macros starting with if should be enclosed by a do - while loop to avoid possible if/else logic defects
Hello build bot (Jenkins), Angel Pons,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/43717
to look at the new patch set (#7).
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
payloads/libpayload/libc: upgrade "qsort.c" to v1.15
it needs test.
Change-Id: I3ab8d4b2c5ac782b949e244749ca285ed4700283 Signed-off-by: Elyes HAOUAS ehaouas@noos.fr --- M payloads/libpayload/libc/qsort.c 1 file changed, 41 insertions(+), 37 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/17/43717/7
HAOUAS Elyes has abandoned this change. ( https://review.coreboot.org/c/coreboot/+/43717 )
Change subject: payloads/libpayload/libc: upgrade "qsort.c" to v1.15 ......................................................................
Abandoned
-
Angel Pons (Code Review) -
build bot (Jenkins) (Code Review)
-
HAOUAS Elyes (Code Review)