1/*
2 * Code adapted from uClibc-0.9.30.3
3 *
4 * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
5 * Version 2.1, February 1999
6 *
7 * Wolfgang Denk <wd@denx.de>
8 */
9
10/* This code is derived from a public domain shell sort routine by
11 * Ray Gardner and found in Bob Stout's snippets collection.  The
12 * original code is included below in an #if 0/#endif block.
13 *
14 * I modified it to avoid the possibility of overflow in the wgap
15 * calculation, as well as to reduce the generated code size with
16 * bcc and gcc. */
17
18#include <log.h>
19#include <linux/types.h>
20#include <exports.h>
21#include <sort.h>
22
23void qsort(void  *base,
24	   size_t nel,
25	   size_t width,
26	   int (*comp)(const void *, const void *))
27{
28	size_t wgap, i, j, k;
29	char tmp;
30
31	if ((nel > 1) && (width > 0)) {
32		assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
33		wgap = 0;
34		do {
35			wgap = 3 * wgap + 1;
36		} while (wgap < (nel-1)/3);
37		/* From the above, we know that either wgap == 1 < nel or */
38		/* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap <  nel. */
39		wgap *= width;			/* So this can not overflow if wnel doesn't. */
40		nel *= width;			/* Convert nel to 'wnel' */
41		do {
42			i = wgap;
43			do {
44				j = i;
45				do {
46					register char *a;
47					register char *b;
48
49					j -= wgap;
50					a = j + ((char *)base);
51					b = a + wgap;
52					if ((*comp)(a, b) <= 0) {
53						break;
54					}
55					k = width;
56					do {
57						tmp = *a;
58						*a++ = *b;
59						*b++ = tmp;
60					} while (--k);
61				} while (j >= wgap);
62				i += width;
63			} while (i < nel);
64			wgap = (wgap - width)/3;
65		} while (wgap);
66	}
67}
68
69int strcmp_compar(const void *p1, const void *p2)
70{
71	return strcmp(*(const char **)p1, *(const char **)p2);
72}
73