154c6977eSWolfgang Denk /*
254c6977eSWolfgang Denk * Code adapted from uClibc-0.9.30.3
354c6977eSWolfgang Denk *
454c6977eSWolfgang Denk * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
554c6977eSWolfgang Denk * Version 2.1, February 1999
654c6977eSWolfgang Denk *
754c6977eSWolfgang Denk * Wolfgang Denk <wd@denx.de>
854c6977eSWolfgang Denk */
954c6977eSWolfgang Denk
1054c6977eSWolfgang Denk /* This code is derived from a public domain shell sort routine by
1154c6977eSWolfgang Denk * Ray Gardner and found in Bob Stout's snippets collection. The
1254c6977eSWolfgang Denk * original code is included below in an #if 0/#endif block.
1354c6977eSWolfgang Denk *
1454c6977eSWolfgang Denk * I modified it to avoid the possibility of overflow in the wgap
1554c6977eSWolfgang Denk * calculation, as well as to reduce the generated code size with
1654c6977eSWolfgang Denk * bcc and gcc. */
1754c6977eSWolfgang Denk
1854c6977eSWolfgang Denk #include <linux/types.h>
19*42c4a23aSSimon Glass #include <common.h>
20560d424bSMike Frysinger #include <exports.h>
2154c6977eSWolfgang Denk
qsort(void * base,size_t nel,size_t width,int (* comp)(const void *,const void *))2254c6977eSWolfgang Denk void qsort(void *base,
2354c6977eSWolfgang Denk size_t nel,
2454c6977eSWolfgang Denk size_t width,
2554c6977eSWolfgang Denk int (*comp)(const void *, const void *))
2654c6977eSWolfgang Denk {
2754c6977eSWolfgang Denk size_t wgap, i, j, k;
2854c6977eSWolfgang Denk char tmp;
2954c6977eSWolfgang Denk
3054c6977eSWolfgang Denk if ((nel > 1) && (width > 0)) {
3154c6977eSWolfgang Denk assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
3254c6977eSWolfgang Denk wgap = 0;
3354c6977eSWolfgang Denk do {
3454c6977eSWolfgang Denk wgap = 3 * wgap + 1;
3554c6977eSWolfgang Denk } while (wgap < (nel-1)/3);
3654c6977eSWolfgang Denk /* From the above, we know that either wgap == 1 < nel or */
3754c6977eSWolfgang Denk /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */
3854c6977eSWolfgang Denk wgap *= width; /* So this can not overflow if wnel doesn't. */
3954c6977eSWolfgang Denk nel *= width; /* Convert nel to 'wnel' */
4054c6977eSWolfgang Denk do {
4154c6977eSWolfgang Denk i = wgap;
4254c6977eSWolfgang Denk do {
4354c6977eSWolfgang Denk j = i;
4454c6977eSWolfgang Denk do {
4554c6977eSWolfgang Denk register char *a;
4654c6977eSWolfgang Denk register char *b;
4754c6977eSWolfgang Denk
4854c6977eSWolfgang Denk j -= wgap;
4954c6977eSWolfgang Denk a = j + ((char *)base);
5054c6977eSWolfgang Denk b = a + wgap;
5154c6977eSWolfgang Denk if ((*comp)(a, b) <= 0) {
5254c6977eSWolfgang Denk break;
5354c6977eSWolfgang Denk }
5454c6977eSWolfgang Denk k = width;
5554c6977eSWolfgang Denk do {
5654c6977eSWolfgang Denk tmp = *a;
5754c6977eSWolfgang Denk *a++ = *b;
5854c6977eSWolfgang Denk *b++ = tmp;
5954c6977eSWolfgang Denk } while (--k);
6054c6977eSWolfgang Denk } while (j >= wgap);
6154c6977eSWolfgang Denk i += width;
6254c6977eSWolfgang Denk } while (i < nel);
6354c6977eSWolfgang Denk wgap = (wgap - width)/3;
6454c6977eSWolfgang Denk } while (wgap);
6554c6977eSWolfgang Denk }
6654c6977eSWolfgang Denk }
67560d424bSMike Frysinger
strcmp_compar(const void * p1,const void * p2)68560d424bSMike Frysinger int strcmp_compar(const void *p1, const void *p2)
69560d424bSMike Frysinger {
70560d424bSMike Frysinger return strcmp(*(const char **)p1, *(const char **)p2);
71560d424bSMike Frysinger }
72