/* * qsort -- simple quicksort */ typedefstruct{	int	(*cmp)(void*, void*);	void	(*swap)(char*, char*, long);	long	es;} Sort; static	voidswapb(char *i, char *j, long es){	char c; 	do {		c = *i;		*i++ = *j;		*j++ = c;		es--;	} while(es != 0); } static	voidswapi(char *ii, char *ij, long es){	long *i, *j, c; 	i = (long*)ii;	j = (long*)ij;	do {		c = *i;		*i++ = *j;		*j++ = c;		es -= sizeof(long);	} while(es != 0);} static	char*pivot(char *a, long n, Sort *p){	long j;	char *pi, *pj, *pk; 	j = n/6 * p->es;	pi = a + j;	/* 1/6 */	j += j;	pj = pi + j;	/* 1/2 */	pk = pj + j;	/* 5/6 */	if(p->cmp(pi, pj) < 0) {		if(p->cmp(pi, pk) < 0) {			if(p->cmp(pj, pk) < 0)				return pj;			return pk;		}		return pi;	}	if(p->cmp(pj, pk) < 0) {		if(p->cmp(pi, pk) < 0)			return pi;		return pk;	}	return pj;} static	voidqsorts(char *a, long n, Sort *p){	long j, es;	char *pi, *pj, *pn; 	es = p->es;	while(n > 1) {		if(n > 10) {			pi = pivot(a, n, p);		} else			pi = a + (n>>1)*es; 		p->swap(a, pi, es);		pi = a;		pn = a + n*es;		pj = pn;		for(;;) {			do				pi += es;			while(pi < pn && p->cmp(pi, a) < 0);			do				pj -= es;			while(pj > a && p->cmp(pj, a) > 0);			if(pj < pi)				break;			p->swap(pi, pj, es);		}		p->swap(a, pj, es);		j = (pj - a) / es; 		n = n-j-1;		if(j >= n) {			qsorts(a, j, p);			a += (j+1)*es;		} else {			qsorts(a + (j+1)*es, n, p);			n = j;		}	}} voidqsort(void *va, long n, long es, int (*cmp)(void*, void*)){	Sort s; 	s.cmp = cmp;	s.es = es;	s.swap = swapi;	if(((long)va | es) % sizeof(long))		s.swap = swapb;	qsorts((char*)va, n, &s);}