/* hacked version of the one from dlibs:
 *	removed size restriction by using alloca
 *	fixed alignment problems
 *	ints <-> longs fixed in accordance with ansi proto
 * note: changing longs to size_t in _[w,l,n]qsort for args/indices
 *	 breaks this code (not sure why!).
 *
 *	(duh, duh!)now i understand, its due to (hi > lo) condition.
 *	
 *	++jrb
 */

#ifdef minix
#include <sys/types.h>
#include "lib.h"
#else
#include <stddef.h>
#include <stdlib.h>
#endif
#include <string.h>


typedef unsigned short ushort;
typedef unsigned long  ulong;
typedef unsigned char  uchar;

uchar	*_qbuf;			/* pointer to storage for qsort() */

#define	PIVOT			((i+j)>>1)
#define moveitem(dst,src,size)	if(dst != src) bcopy(src, dst, size)
#ifdef __GNUC__
#ifdef minix
void *alloca(unsigned long);
#else
#define alloca __builtin_alloca
#endif
#endif

#if (defined(atarist) || defined(minix))
#define SHORT_ALIGN_DESIRABLE
	/* SHORT_ALIGN_DESIRABLE def'ed for machines on which short alignment
	   on a two word boundary is desirable */
#endif

#ifdef SHORT_ALIGN_DESIRABLE
static void _wqsort(base, lo, hi, cmp)
	register ushort *base;
	register long lo;
	register long hi;
	register int (*cmp)();
	{
	ushort k;
	register long i, j, t;
	register ushort *p = &k;

	while(hi > lo)
		{
		i = lo;
		j = hi;
		t = PIVOT;
		*p = base[t];
		base[t] = base[i];
		base[i] = *p;
		while(i < j)
			{
			while(((*cmp)((base+j), p)) > 0)
				--j;
			base[i] = base[j];
			while((i < j) && (((*cmp)((base+i), p)) <= 0))
				++i;
			base[j] = base[i];
			}
		base[i] = *p;
		if((i - lo) < (hi - i))
			{
			_wqsort(base, lo, (i - 1), cmp);
			lo = i + 1;
			}
		else
			{
			_wqsort(base, (i + 1), hi, cmp);
			hi = i - 1;
			}
		}
	}
#endif /* SHORT_ALIGN_DESIRABLE */

static void _lqsort(base, lo, hi, cmp)
	register ulong *base;
	register long lo;
	register long hi;
	register int (*cmp)();
	{
	ulong k;
	register long i, j, t;
	register ulong *p = &k;

	while(hi > lo)
		{
		i = lo;
		j = hi;
		t = PIVOT;
		*p = base[t];
		base[t] = base[i];
		base[i] = *p;
		while(i < j)
			{
			while(((*cmp)((base+j), p)) > 0)
				--j;
			base[i] = base[j];
			while((i < j) && (((*cmp)((base+i), p)) <= 0))
				++i;
			base[j] = base[i];
			}
		base[i] = *p;
		if((i - lo) < (hi - i))
			{
			_lqsort(base, lo, (i - 1), cmp);
			lo = i + 1;
			}
		else
			{
			_lqsort(base, (i + 1), hi, cmp);
			hi = i - 1;
			}
		}
	}

static void _nqsort(base, lo, hi, size, cmp)
	register uchar *base;
	register long lo;
	register long hi;
	register long size;
	register int (*cmp)();
	{
	register long i, j;
	register uchar *p = _qbuf;

	while(hi > lo)
		{
		i = lo;
		j = hi;
		p = (base+size*PIVOT);
		moveitem(_qbuf, p, size);
		moveitem(p, (base+size*i), size);
		moveitem((base+size*i), _qbuf, size);
		p = _qbuf;
		while(i < j)
			{
			while(((*cmp)((base+size*j), p)) > 0)
				--j;
			moveitem((base+size*i), (base+size*j), size);
			while((i < j) && (((*cmp)((base+size*i), p)) <= 0))
				++i;
			moveitem((base+size*j), (base+size*i), size);
			}
		moveitem((base+size*i), p, size);
		if((i - lo) < (hi - i))
			{
			_nqsort(base, lo, (i - 1), size, cmp);
			lo = i + 1;
			}
		else
			{
			_nqsort(base, (i + 1), hi, size, cmp);
			hi = i - 1;
			}
		}
	}

#define LONG_ALIGNED(X)	  ((((unsigned long)(X)) & 3) == 0)
#ifdef SHORT_ALIGN_DESIRABLE
#define SHORT_ALIGNED(X)  ((((unsigned long)(X)) & 1) == 0)
#endif

void qsort(base, num, size, cmp)
	void *base;
	size_t num;
	size_t size;
	int (*cmp)();
{
	if(num < 2)
	    return; /* nothing to do */
#if 0 /* later put in thresh stuff and kick in this code */
	else if(num == 2)  /* at some point replace if n < THRESH do insert sort */
	{	/* degenerate case */
	    if(((*cmp)( base, ((uchar *)base)+size )) > 0)
	    {
		if((_qbuf = alloca(size)) == (void *)0) return;
		bcopy(base, _qbuf, size);
		bcopy(((uchar *)base)+size, base, size);
		bcopy(_qbuf, ((uchar *)base)+size,  size);
	    }
	    return;
        }
#endif

#ifdef SHORT_ALIGN_DESIRABLE
	/* assumption: if short align desired, then its ok to
	   align a long at a short boundary too.
	 */
	if(SHORT_ALIGNED(base))
	{
	    if(size == 2)
		_wqsort((ushort *)base, 0L, num-1, cmp);
	    else if(size == 4)
		_lqsort((ulong *)base, 0L, num-1, cmp);
	}
#else
	if((size == 4) && LONG_ALIGNED(base))
	    _lqsort((ulong *)base, 0L, num-1, cmp);
#endif
	else
	{
#ifdef minix /* we have to check, otherwise ... */
		if((_qbuf = alloca(size)) == (void *)0) return;
#else
		_qbuf = alloca(size);	/* stack better be large enough */
#endif
		_nqsort((uchar *)base, 0L, num-1, size, cmp);
	}
}