/*
 * Code adapted from uClibc-0.9.30.3
 *
 * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
 * Version 2.1, February 1999
 *
 * Wolfgang Denk <wd@denx.de>
 */

/* This code is derived from a public domain shell sort routine by
 * Ray Gardner and found in Bob Stout's snippets collection.  The
 * original code is included below in an #if 0/#endif block.
 *
 * I modified it to avoid the possibility of overflow in the wgap
 * calculation, as well as to reduce the generated code size with
 * bcc and gcc. */

#include <linux/types.h>
#include <common.h>
#include <qsort.h>

void qsort(void  *base,
	   size_t nel,
	   size_t width,
	   int (*comp)(const void *, const void *))
{
	size_t wgap, i, j, k;
	char tmp;

	if (nel < 2 || width == 0)
		return;

	/* check for overflow */
	if (nel > ((size_t)(-1)) / width)
		return;

	wgap = 0;
	do {
		wgap = 3 * wgap + 1;
	} while (wgap < (nel - 1) / 3);

	/*
	 * From the above, we know that either wgap == 1 < nel or
	 * ((wgap-1) / 3 < (int) ((nel - 1) / 3) <= (nel - 1) / 3 ==> wgap <  nel.
	 */
	wgap *= width;	/* So this can not overflow if wnel doesn't. */
	nel *= width;	/* Convert nel to 'wnel' */
	do {
		i = wgap;
		do {
			j = i;
			do {
				char *a;
				char *b;

				j -= wgap;
				a = j + ((char *)base);
				b = a + wgap;

				if (comp(a, b) <= 0)
					break;

				k = width;
				do {
					tmp = *a;
					*a++ = *b;
					*b++ = tmp;
				} while (--k);
			} while (j >= wgap);
			i += width;
		} while (i < nel);
		wgap = (wgap - width) / 3;
	} while (wgap);
}

int strcmp_compar(const void *p1, const void *p2)
{
	return strcmp((const char *)p1, (const char *)p2);
}