gdk_qsort.mx

这个是内存数据库中的一个管理工具

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f gdk_qsort
@a Peter Boncz et al
@* Qsort
There were two problems with the OS provided qsort() library routine:
@table @samp
@item unreliable
on certain OSs (e.g. SunOS), the qsort somehow degenerates
if there are a very small number of different values (on 
132K elements with 7 values, I never saw it return). 
This is a serious bug.
@item atom format
 when comparing GDK atoms (e.g. in BATs) it was not
possible to use qsort on varsized atoms (as monet stores them 
as integer offsets from a global base pointer that qsort does 
not know about), nor if the values were not placed at the start 
of the record (e.g.  if the column is the tail column of a BAT).
@end table

Both these problems are fixed in the new GDKqsort function, that
is based on the standard Berkeley qsort (see copyright notice below).

The routine was "monet"-ified with macro code expansions for the specific
data types to obtain extra speed (we know more about our data than the stdlib 
qsort() ever can).
@{
@c
#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.
 */

@-
Record containing all data-specific info.
Introduced to reduce number of qsort parameters 
@c
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)
@}
@-
qsort is macro expanded in four dimensions:
@table @samp
@item direction:2
	L: from lesser to greater is standard.
	G: from greater to lesser is the _rev version of quicksort.
@item type:7
	in order to factor out a type-specific check, or a function call for each 
	value comparison, we separate different qsort implementations by the comparison 
	type, of which each has the comparison hard-coded. We factor out the types 
	@{chr,bte,sht,int,wrd,flt,lng,dbl,any@} (the latter uses an adt function call).
@item storage:2
	denoted @{direct,offset@}, means whether the array to be sorted contains the 
	(fixed-width) values itself, or whether it contains integer byte-offsets, that point 
	into some heap. Note that we support byte-offset qsort also on fixed-size types, 
	as this is handy in many cases.
@item swapmethod:2
	qsort sorts an array by continually swapping entries. To do this, two
	implementations of the swap action are supported: @{iterate,register@}. 
	The default implementation takes the comparison type and does the swapping by 
	iterating a number of times per entry, copying one comparison value per iteration. 
	One often-occurring special case is when the entry width is 8 (two integers). These 
	can be copied by one long integer load and store; without the loop overhead.
@end table
Thus, there are 2 * 7 * 2 * 2 = 56 GDKqsort implementation routines.
@{
@c
#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;
@:qsort_L_or_G_direction(any)@

#ifndef NOEXPAND_CHR
@:qsort_cmpdef(chr)@
#endif
#ifndef NOEXPAND_BTE
@:qsort_cmpdef(bte)@
#endif
#ifndef NOEXPAND_SHT
@:qsort_cmpdef(sht)@
#endif
#ifndef NOEXPAND_INT
@:qsort_cmpdef(int)@
#endif
#ifndef NOEXPAND_FLT
@:qsort_cmpdef(flt)@
#endif
#ifndef NOEXPAND_DBL
@:qsort_cmpdef(dbl)@
#endif
#ifndef NOEXPAND_LNG
@:qsort_cmpdef(lng)@
#endif

@= qsort_cmpdef
#define @1_LE(a,b) (*(@1*) (a) <= *(@1*) (b))
#define @1_LT(a,b) (*(@1*) (a) <  *(@1*) (b))
#define @1_GE(a,b) (*(@1*) (a) >= *(@1*) (b))
#define @1_GT(a,b) (*(@1*) (a) >  *(@1*) (b))

@:qsort_L_or_G_direction(@1)@

@= qsort_L_or_G_direction
@:qsort_direct_or_offset_storage(@1,L)@
@:qsort_direct_or_offset_storage(@1,G,_rev)@

@= qsort_direct_or_offset_storage
#define @1_@2MED3(a,b,c,A,B,C)				\
	@1_@2T(a,b) ?					\
		(@1_@2T(b,c) ?				\
			(B):				\
			(@1_@2T(a,c) ?			\
				(C):			\
				(A))):			\
		(@1_@2T(c,b) ?				\
			(B):				\
			(@1_@2T(a,c) ?			\
				(A):			\
				(C)))

@:qsort_register_or_iterate_swapmethod(direct,@1,@2,@3)@
@:qsort_register_or_iterate_swapmethod(offset,@1,@2,@3)@

@= qsort_register_or_iterate_swapmethod
#define @1_@2_@3MED3(a,b,c,buf)	@2_@3MED3(@1(a),@1(b),@1(c),a,b,c)
#define @1_@2_@3T(a,b)		@2_@3T(@1(a),@1(b))
#define @1_@2_@3E(a,b)		@2_@3E(@1(a),@1(b))

@:qsort_algo(register,@1,@2,@3,@4)@
@:qsort_algo(iterate,@1,@2,@3,@4)@

@= qsort_algo
static void
GDKqsort_@1_@2_@3@5(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 && @2_@3_@4E(pl, pl - buf->width);
			     pl -= buf->width)
				@1_SWAP(@3, 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 = @2_@3_@4MED3(pl, pl + d, pl + 2 * d, buf);
			pm = @2_@3_@4MED3(pm - d, pm, pm + d, buf);
			pn = @2_@3_@4MED3(pn - 2 * d, pn - d, pn, buf);
		}
		pm = @2_@3_@4MED3(pl, pm, pn, buf);
	}
	@1_SWAP(@3, a, pm);
	pa = pb = (char *) a + buf->width;
	pc = pd = (char *) a + MULT_WIDTH(n - 1);

	for (;;) {
		while (pb <= pc && @2_@3_@4E(pb, a)) {
			if (!@2_@3_@4T(pb, a)) { /* pb (<|>)= a && !(pb (<|>) a)  =>  pb == a */
				swap_cnt = 1;
				@1_SWAP(@3, pa, pb);
				pa += buf->width;
			}
			pb += buf->width;
		}
		while (pb <= pc && @2_@3_@4E(a, pc)) {
			if (!@2_@3_@4T(a, pc)) { /* a (<|>)= pc && !(a (<|>) pc)  =>  a == pc */
				swap_cnt = 1;
				@1_SWAP(@3, pc, pd);
				pd -= buf->width;
			}
			pc -= buf->width;
		}
		if (pb > pc) {
			break;
		}
		@1_SWAP(@3, 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 && @2_@3_@4E(pl, pl - buf->width); 
			     pl -= buf->width)
				@1_SWAP(@3, pl, pl - buf->width);
		return;
	}

	pn = (char *) a + MULT_WIDTH(n);
	r = MIN(pa - (char *)a, pb - pa);
	multi_SWAP(@3, a, pb - r, r);
	r = MIN(pd - pc, (ptrdiff_t) (pn - pd - buf->width));
	multi_SWAP(@3, pb, pn - r, r);
	if ((r = pb - pa) > buf->width)
		GDKqsort_@1_@2_@3@5(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;
	}
}

@= call_offset_or_direct_storage
	/* factorization by storage mode */
	if (base) {
		GDKqsort_@3_offset_@2@1(((char*) a)+loc, n, &buf); /* array of var_t, that are byte-offsets from some base */
	} else {
		GDKqsort_@3_direct_@2@1(((char*) a)+loc, n, &buf); /* array of fixed-size values */
	} 

@= call_iterate_or_register_swapmethod
	/* factorization by array swap implementation */
	if ((((size_t) a)&7) || width != 8) {
		/* array is non-aligned or entries are not one 64-bit integer wide */
		@:call_offset_or_direct_storage(@1,@2,iterate)@
	} else {
		/* we can swap array entries by one 64-bit integer swap */
		@:call_offset_or_direct_storage(@1,@2,register)@
	}
	break;

@= qsort
void
GDKqsort@1(void *a, void* base, size_t n, int width, int tpe, int loc)
{
	int i = 0;
	buf_t buf;

	assert(tpe != TYPE_void);

	/* init the qsort record */
	buf.cmp = BATatoms[tpe].atomCmp;
	buf.offst = base;
	buf.width = (unsigned) width;
	buf.loc = loc;
	buf.shift = -1;
	do {
		int mask = 1 << i; 
		if ((width&mask) && (width & ~mask) == 0) {
			buf.shift = i;
			break;
		}
	} while (++i < 32);

	/* factorization by comparsion type */
	switch (ATOMstorage(tpe)) {
#ifndef NOEXPAND_CHR
	case TYPE_chr:
		@:call_iterate_or_register_swapmethod(@1,chr)@
#endif
#ifndef NOEXPAND_BTE
	case TYPE_bte:
		@:call_iterate_or_register_swapmethod(@1,bte)@
#endif
#ifndef NOEXPAND_SHT
	case TYPE_sht:
		@:call_iterate_or_register_swapmethod(@1,sht)@
#endif
#ifndef NOEXPAND_INT
	case TYPE_int:
		@:call_iterate_or_register_swapmethod(@1,int)@
#endif
#ifndef NOEXPAND_FLT
	case TYPE_flt:
		@:call_iterate_or_register_swapmethod(@1,flt)@
#endif
#ifndef NOEXPAND_LNG
	case TYPE_lng:
		@:call_iterate_or_register_swapmethod(@1,lng)@
#endif
#ifndef NOEXPAND_DBL
	case TYPE_dbl:
		@:call_iterate_or_register_swapmethod(@1,dbl)@
#endif
	default:
		@:call_iterate_or_register_swapmethod(@1,any)@
	}
}
@c
@:qsort()@
@:qsort(_rev)@

@ test
main(int argc, char** argv)
{
	int i, n = atoi(argv[1]), m = atoi(argv[2]);
	float d = 0.0, f = d, *buf = (float*) malloc(2*n*sizeof(float));

	for (i=0; i < n; i++) {
		buf[i+i] = f++;
		buf[i+i+1] = d++;
		if (d > m)
			d = 0.0;
	}
	printf("start sort\n");
	GDKqsort(buf, NULL, n, 8, TYPE_flt, 4);
	printf("end sort\n");
	for(i=0; i < n; i++) {
		printf("% 9i [% 9d,% 9d]\n",
		       i, (int) buf[i+i], (int) buf[i+i+1]);
	}
}
@}