gdk_qsort.c

来自「这个是内存数据库中的一个管理工具」· C语言 代码 · 共 2,358 行 · 第 1/5 页

	}
	if (swap_cnt == 0) {  /* Switch to insertion sort */
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && direct_chr_GE(pl, pl - buf->width); 
			     pl -= buf->width)
				register_SWAP(chr, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(chr, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(chr, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_register_direct_chr_rev(a, DIV_WIDTH(r), buf);
	if ((r = pd - pc) > buf->width) { 
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = DIV_WIDTH(r);
		goto loop;
	}
}



#line 231 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"


#line 235 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
static void
GDKqsort_iterate_direct_chr_rev(char *a, size_t n, buf_t *buf)
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t r;
	int swap_cnt;

	/* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".  */
loop:
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && direct_chr_GE(pl, pl - buf->width);
			     pl -= buf->width)
				iterate_SWAP(chr, pl, pl - buf->width);
		return;
	}
	pm = (char *) a + MULT_WIDTH(n >> 1);
	if (n > 7) {
		pl = a;
		pn = (char *) a + MULT_WIDTH(n - 1);
		if (n > 40) {
			size_t d;

			d = MULT_WIDTH(n >> 3);
			pl = direct_chr_GMED3(pl, pl + d, pl + 2 * d, buf);
			pm = direct_chr_GMED3(pm - d, pm, pm + d, buf);
			pn = direct_chr_GMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = direct_chr_GMED3(pl, pm, pn, buf);
	}
	iterate_SWAP(chr, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && direct_chr_GE(pb, a)) {
			if (!direct_chr_GT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				iterate_SWAP(chr, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && direct_chr_GE(a, pc)) {
			if (!direct_chr_GT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				iterate_SWAP(chr, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		iterate_SWAP(chr, pb, pc);
		swap_cnt = 1;
		pb += buf->width;
		pc -= buf->width;

	}
	if (swap_cnt == 0) {  /* Switch to insertion sort */
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && direct_chr_GE(pl, pl - buf->width); 
			     pl -= buf->width)
				iterate_SWAP(chr, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(chr, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(chr, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_iterate_direct_chr_rev(a, DIV_WIDTH(r), buf);
	if ((r = pd - pc) > buf->width) { 
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = DIV_WIDTH(r);
		goto loop;
	}
}



#line 232 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"




#line 223 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"


#line 227 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define offset_chr_GMED3(a,b,c,buf)	chr_GMED3(offset(a),offset(b),offset(c),a,b,c)
#define offset_chr_GT(a,b)		chr_GT(offset(a),offset(b))
#define offset_chr_GE(a,b)		chr_GE(offset(a),offset(b))


#line 235 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
static void
GDKqsort_register_offset_chr_rev(char *a, size_t n, buf_t *buf)
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t r;
	int swap_cnt;

	/* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".  */
loop:
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && offset_chr_GE(pl, pl - buf->width);
			     pl -= buf->width)
				register_SWAP(chr, pl, pl - buf->width);
		return;
	}
	pm = (char *) a + MULT_WIDTH(n >> 1);
	if (n > 7) {
		pl = a;
		pn = (char *) a + MULT_WIDTH(n - 1);
		if (n > 40) {
			size_t d;

			d = MULT_WIDTH(n >> 3);
			pl = offset_chr_GMED3(pl, pl + d, pl + 2 * d, buf);
			pm = offset_chr_GMED3(pm - d, pm, pm + d, buf);
			pn = offset_chr_GMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = offset_chr_GMED3(pl, pm, pn, buf);
	}
	register_SWAP(chr, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && offset_chr_GE(pb, a)) {
			if (!offset_chr_GT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				register_SWAP(chr, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && offset_chr_GE(a, pc)) {
			if (!offset_chr_GT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				register_SWAP(chr, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		register_SWAP(chr, pb, pc);
		swap_cnt = 1;
		pb += buf->width;
		pc -= buf->width;

	}
	if (swap_cnt == 0) {  /* Switch to insertion sort */
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && offset_chr_GE(pl, pl - buf->width); 
			     pl -= buf->width)
				register_SWAP(chr, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(chr, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(chr, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_register_offset_chr_rev(a, DIV_WIDTH(r), buf);
	if ((r = pd - pc) > buf->width) { 
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = DIV_WIDTH(r);
		goto loop;
	}
}



#line 231 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"


#line 235 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
static void
GDKqsort_iterate_offset_chr_rev(char *a, size_t n, buf_t *buf)
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t r;
	int swap_cnt;

	/* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".  */
loop:
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && offset_chr_GE(pl, pl - buf->width);
			     pl -= buf->width)
				iterate_SWAP(chr, pl, pl - buf->width);
		return;
	}
	pm = (char *) a + MULT_WIDTH(n >> 1);
	if (n > 7) {
		pl = a;
		pn = (char *) a + MULT_WIDTH(n - 1);
		if (n > 40) {
			size_t d;

			d = MULT_WIDTH(n >> 3);
			pl = offset_chr_GMED3(pl, pl + d, pl + 2 * d, buf);
			pm = offset_chr_GMED3(pm - d, pm, pm + d, buf);
			pn = offset_chr_GMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = offset_chr_GMED3(pl, pm, pn, buf);
	}
	iterate_SWAP(chr, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && offset_chr_GE(pb, a)) {
			if (!offset_chr_GT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				iterate_SWAP(chr, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && offset_chr_GE(a, pc)) {
			if (!offset_chr_GT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				iterate_SWAP(chr, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		iterate_SWAP(chr, pb, pc);
		swap_cnt = 1;
		pb += buf->width;
		pc -= buf->width;

	}
	if (swap_cnt == 0) {  /* Switch to insertion sort */
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && offset_chr_GE(pl, pl - buf->width); 
			     pl -= buf->width)
				iterate_SWAP(chr, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(chr, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(chr, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_iterate_offset_chr_rev(a, DIV_WIDTH(r), buf);
	if ((r = pd - pc) > buf->width) { 
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = DIV_WIDTH(r);
		goto loop;
	}
}



#line 232 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"




#line 224 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"




#line 207 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"




#line 203 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"




#line 176 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"

#endif
#ifndef NOEXPAND_BTE

#line 198 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define bte_LE(a,b) (*(bte*) (a) <= *(bte*) (b))
#define bte_LT(a,b) (*(bte*) (a) <  *(bte*) (b))
#define bte_GE(a,b) (*(bte*) (a) >= *(bte*) (b))
#define bte_GT(a,b) (*(bte*) (a) >  *(bte*) (b))


#line 206 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"

#line 210 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define bte_LMED3(a,b,c,A,B,C)				\
	bte_LT(a,b) ?					\
		(bte_LT(b,c) ?				\
			(B):				\
			(bte_LT(a,c) ?			\
				(C):			\
				(A))):			\
		(bte_LT(c,b) ?				\
			(B):				\
			(bte_LT(a,c) ?			\
				(A):			\
				(C)))


#line 227 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define direct_bte_LMED3(a,b,c,buf)	bte_LMED3(direct(a),direct(b),direct(c),a,b,c)
#define direct_bte_LT(a,b)		bte_LT(direct(a),direct(b))
#define direct_bte_LE(a,b)		bte_LE(direct(a),direct(b))


#line 235 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
static void
GDKqsort_register_direct_bte(char *a, size_t n, buf_t *buf)
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t r;
	int swap_cnt;

	/* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".  */
loop:
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && direct_bte_LE(pl, pl - buf->width);
			     pl -= buf->width)
				register_SWAP(bte, pl, pl - buf->width);
		return;
	}
	pm = (char *) a + MULT_WIDTH(n >> 1);
	if (n > 7) {
		pl = a;
		pn = (char *) a + MULT_WIDTH(n - 1);
		if (n > 40) {
			size_t d;

			d = MULT_WIDTH(n >> 3);
			pl = direct_bte_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = direct_bte_LMED3(pm - d, pm, pm + d, buf);
			pn = direct_bte_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = direct_bte_LMED3(pl, pm, pn, buf);
	}
	register_SWAP(bte, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && direct_bte_LE(pb, a)) {
			if (!direct_bte_LT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				register_SWAP(bte, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && direct_bte_LE(a, pc)) {
			if (!direct_bte_LT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				register_SWAP(bte, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		register_SWAP(bte, pb, pc);
		swap_cnt = 1;
		pb += buf->width;
		pc -= buf->width;

	}
	if (swap_cnt == 0) {  /* Switch to insertion sort */
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && direct_bte_LE(pl, pl - buf->width); 
			     pl -= buf->width)
				register_SWAP(bte, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(bte, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(bte, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_register_direct_bte(a, DIV_WIDTH(r), buf);
	if ((r = pd - pc) > buf->width) { 
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = DIV_WIDTH(r);
		goto loop;
	}
}



#line 231 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"


#line 235 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
static void
GDKqsort_iterate_direct_bte(char *a, size_t n, buf_t *buf)
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t r;
	int swap_cnt;

	/* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".  */
loop:
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (char *) a + buf->width; pm < (char *) a + MULT_WIDTH(n); pm += buf->width)
			for (pl = pm; pl > (char *) a && direct_bte_LE(pl, pl - buf->width);
			     pl -= buf->width)
				iterate_SWAP(bte, pl, pl - buf->width);
		return;
	}
	pm = (char *) a + MULT_WIDTH(n >> 1);
	if (n > 7) {