gdk_qsort.c

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

#line 43 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#include "monetdb_config.h"
#include "gdk.h"

/*-
 * Copyright (c) 1992, 1993
 *      The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */



#line 83 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
typedef struct {
	int (*cmp) (ptr, ptr);	/* routine that compares two atoms */
	char *offst;		/* NULL or start of varsized heap */
	int loc;		/* byte-offset of sort atom in record */
	int shift;		/* log2 if width is a power of two, else -1 */
	unsigned width;		/* byte-width of record */
} buf_t;

/* fast arithmetic on the record width */
#define MULT_WIDTH(d)					\
	((buf->shift == -1)?				\
		((d) * buf->width):			\
		((d) << buf->shift))

#define DIV_WIDTH(d)					\
	((buf->shift == -1)?				\
		((d) / buf->width):			\
		((d) >> buf->shift))


/* fast record swapping */
#define register_SWAP(TYPE, a, b) {			\
	lng *_pa = (lng *) (((char*) (a)) - buf->loc);	\
	lng *_pb = (lng *) (((char*) (b)) - buf->loc);	\
	lng _tmp = *_pa;				\
	*_pa = *_pb;					\
	*_pb = _tmp;					\
}

#define tpe_SWAP(TYPE, a, b, n) {			\
	size_t _i = (n)/sizeof(TYPE);			\
	TYPE *_pa = (TYPE*) (((char*) (a)) - buf->loc);	\
	TYPE *_pb = (TYPE*) (((char*) (b)) - buf->loc);	\
	do {						\
		TYPE _tmp = *_pa;			\
		*_pa++ = *_pb;				\
		*_pb++ = _tmp;				\
	} while (--_i > 0);				\
}

#define iterate_SWAP(TYPE, a, b)			\
	tpe_SWAP(TYPE, a, b, buf->width)

#define multi_SWAP(TYPE, a, b, n)			\
	if ((n) > 0) tpe_SWAP(TYPE, a, b, n)


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


#line 156 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#ifndef HAVE_PTRDIFF_T
#if SIZEOF_SIZE_T == SIZEOF_INT
typedef int ptrdiff_t;
#else
typedef lng ptrdiff_t;
#endif
#endif

#define offset(p)		(buf->offst + *(var_t*) (p))
#define direct(p)		(p)

#define any_LE(a,b)		((buf->cmp)(a,b) <= 0)
#define any_LT(a,b)		((buf->cmp)(a,b) <  0)
#define any_GE(a,b)		((buf->cmp)(a,b) >= 0)
#define any_GT(a,b)		((buf->cmp)(a,b) >  0)

typedef chr any;

#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 any_LMED3(a,b,c,A,B,C)				\
	any_LT(a,b) ?					\
		(any_LT(b,c) ?				\
			(B):				\
			(any_LT(a,c) ?			\
				(C):			\
				(A))):			\
		(any_LT(c,b) ?				\
			(B):				\
			(any_LT(a,c) ?			\
				(A):			\
				(C)))


#line 227 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_qsort.mx"
#define direct_any_LMED3(a,b,c,buf)	any_LMED3(direct(a),direct(b),direct(c),a,b,c)
#define direct_any_LT(a,b)		any_LT(direct(a),direct(b))
#define direct_any_LE(a,b)		any_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_any(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_any_LE(pl, pl - buf->width);
			     pl -= buf->width)
				register_SWAP(any, 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_any_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = direct_any_LMED3(pm - d, pm, pm + d, buf);
			pn = direct_any_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = direct_any_LMED3(pl, pm, pn, buf);
	}
	register_SWAP(any, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && direct_any_LE(pb, a)) {
			if (!direct_any_LT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				register_SWAP(any, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && direct_any_LE(a, pc)) {
			if (!direct_any_LT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				register_SWAP(any, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		register_SWAP(any, 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_any_LE(pl, pl - buf->width); 
			     pl -= buf->width)
				register_SWAP(any, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(any, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(any, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_register_direct_any(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_any(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_any_LE(pl, pl - buf->width);
			     pl -= buf->width)
				iterate_SWAP(any, 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_any_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = direct_any_LMED3(pm - d, pm, pm + d, buf);
			pn = direct_any_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = direct_any_LMED3(pl, pm, pn, buf);
	}
	iterate_SWAP(any, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && direct_any_LE(pb, a)) {
			if (!direct_any_LT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				iterate_SWAP(any, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && direct_any_LE(a, pc)) {
			if (!direct_any_LT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				iterate_SWAP(any, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		iterate_SWAP(any, 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_any_LE(pl, pl - buf->width); 
			     pl -= buf->width)
				iterate_SWAP(any, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(any, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(any, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_iterate_direct_any(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_any_LMED3(a,b,c,buf)	any_LMED3(offset(a),offset(b),offset(c),a,b,c)
#define offset_any_LT(a,b)		any_LT(offset(a),offset(b))
#define offset_any_LE(a,b)		any_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_any(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_any_LE(pl, pl - buf->width);
			     pl -= buf->width)
				register_SWAP(any, 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_any_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = offset_any_LMED3(pm - d, pm, pm + d, buf);
			pn = offset_any_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = offset_any_LMED3(pl, pm, pn, buf);
	}
	register_SWAP(any, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && offset_any_LE(pb, a)) {
			if (!offset_any_LT(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				register_SWAP(any, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && offset_any_LE(a, pc)) {
			if (!offset_any_LT(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				register_SWAP(any, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		register_SWAP(any, 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_any_LE(pl, pl - buf->width); 
			     pl -= buf->width)
				register_SWAP(any, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(any, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(any, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_register_offset_any(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_any(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_any_LE(pl, pl - buf->width);
			     pl -= buf->width)
				iterate_SWAP(any, 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_any_LMED3(pl, pl + d, pl + 2 * d, buf);
			pm = offset_any_LMED3(pm - d, pm, pm + d, buf);
			pn = offset_any_LMED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = offset_any_LMED3(pl, pm, pn, buf);
	}
	iterate_SWAP(any, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

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