gdk_qsort.c

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

				(C)))


#line 227 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define direct_chr_LMED3(a,b,c,buf)	chr_LMED3(direct(a),direct(b),direct(c),a,b,c)
#define direct_chr_LT(a,b)		chr_LT(direct(a),direct(b))
#define direct_chr_LE(a,b)		chr_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_chr(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_LE(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 = direct_chr_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = direct_chr_LMED3(pm - d, pm, pm + d, buf);
			pn = direct_chr_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = direct_chr_LMED3(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 && direct_chr_LE(pb, a)) {
			if (!direct_chr_LT(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 && direct_chr_LE(a, pc)) {
			if (!direct_chr_LT(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 && direct_chr_LE(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(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(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_LE(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_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = direct_chr_LMED3(pm - d, pm, pm + d, buf);
			pn = direct_chr_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = direct_chr_LMED3(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_LE(pb, a)) {
			if (!direct_chr_LT(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_LE(a, pc)) {
			if (!direct_chr_LT(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_LE(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(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_LMED3(a,b,c,buf)	chr_LMED3(offset(a),offset(b),offset(c),a,b,c)
#define offset_chr_LT(a,b)		chr_LT(offset(a),offset(b))
#define offset_chr_LE(a,b)		chr_LE(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(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_LE(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_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = offset_chr_LMED3(pm - d, pm, pm + d, buf);
			pn = offset_chr_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = offset_chr_LMED3(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_LE(pb, a)) {
			if (!offset_chr_LT(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_LE(a, pc)) {
			if (!offset_chr_LT(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_LE(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(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(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_LE(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_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = offset_chr_LMED3(pm - d, pm, pm + d, buf);
			pn = offset_chr_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = offset_chr_LMED3(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_LE(pb, a)) {
			if (!offset_chr_LT(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_LE(a, pc)) {
			if (!offset_chr_LT(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_LE(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(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 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 chr_GMED3(a,b,c,A,B,C)				\
	chr_GT(a,b) ?					\
		(chr_GT(b,c) ?				\
			(B):				\
			(chr_GT(a,c) ?			\
				(C):			\
				(A))):			\
		(chr_GT(c,b) ?				\
			(B):				\
			(chr_GT(a,c) ?			\
				(A):			\
				(C)))


#line 227 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define direct_chr_GMED3(a,b,c,buf)	chr_GMED3(direct(a),direct(b),direct(c),a,b,c)
#define direct_chr_GT(a,b)		chr_GT(direct(a),direct(b))
#define direct_chr_GE(a,b)		chr_GE(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_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)
				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 = 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);
	}
	register_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;
				register_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;
				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;