qsort.c.bak

来自「An complete pmp solution for mattel juic」· BAK 代码 · 共 114 行

#include "qsort.h"

//static inline char	*med3 __P((char *, char *, char *, cmp_t *));
//static inline void	 swapfunc __P((char *, char *, int, int));
#define min(a, b)	(a) < (b) ? a : b

/*
 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
 */
#define swapcode(parmi, parmj, n) { 		\
	long i = (n); 			\
	register long *pi = (long *) (parmi); 		\
	register long *pj = (long *) (parmj); 		\
	do { 						\
		register long	t = *pi;		\
		*pi++ = *pj;				\
		*pj++ = t;				\
        } while (--i > 0);				\
}


#define swap(a, b)					\
	{               				\
		long t = *(long *)(a);			\
		*(long *)(a) = *(long *)(b);		\
		*(long *)(b) = t;			\
	} 

#define vecswap(a, b, n) 	if ((n) > 0) swapcode(a, b, n)

static inline u32 med3 (void *a, void *b, void *c, i16 (*cmp)(void*, void*))
	
{
	return (u32)(cmp(a, b) < 0 ?
	            (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )));
}
//-------------------------------------------------------------------------
void wQSort(void *a, u32 n, i16 (*cmp)(void *, void*))

{
	u32 *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	int d, r, swaptype, swap_cnt;

loop:	
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (u32 *)a + 1; pm < (u32 *)a + n * 1; pm ++)
			for (pl = pm; pl > (u32 *)a && cmp(pl - 1, pl) > 0; pl --)
				swap(pl, pl - 1);
		return;
	}
	pm = (u32 *)a + (n / 2);
	if (n > 7) {
		pl = a;
		pn = (u32 *)a + (n - 1);
		if (n > 40) {
			d = (n / 8);
			pl = (u32*)med3(pl, pl + d, pl + 2 * d, cmp);
			pm = (u32*)med3(pm - d, pm, pm + d, cmp);
			pn = (u32*)med3(pn - 2 * d, pn - d, pn, cmp);
		}
		pm = (u32*)med3(pl, pm, pn, cmp);
	}
	swap(a, pm);
	pa = pb = (u32 *)a;

	pc = pd = (u32 *)a + (n - 1);
	for (;;) {
		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
			if (r == 0) {
				swap_cnt = 1;
				swap(pa, pb);
				pa ++;
			}
			pb ++;
		}
		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
			if (r == 0) {
				swap_cnt = 1;
				swap(pc, pd);
				pd --;
			}
			pc --;
		}
		if (pb > pc)
			break;
		swap(pb, pc);
		swap_cnt = 1;
		pb ++;
		pc --;
	}
	if (swap_cnt == 0) {  /* Switch to insertion sort */
		for (pm = (u32 *)a + 1; pm < (u32 *)a + n; pm ++)
			for (pl = pm; pl > (u32 *)a && cmp(pl - 1, pl) > 0; pl --)
				swap(pl, pl - 1);
		return;
	}

	pn = (u32 *)a + n;
	r = min(pa - (u32 *)a, pb - pa);
	vecswap(a, pb - r, r);
	r = min(pd - pc, pn - pd - 1);
	vecswap(pb, pn - r, r);
	if ((r = pb - pa) > 1)
		wQSort(a, r, cmp);
	if ((r = pd - pc) > 1) {
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = r;
		goto loop;
	}
/*		wQSort(pn - r, r / 4, cmp);*/
}