WebSVN – Kolibri OS – Blame – /programs/develop/open watcom/trunk/clib/search/qsortrtn.c

Rev	Author	Line No.	Line
553	serge	1	/****************************************************************************
		2	*
		3	* Open Watcom Project
		4	*
		5	* Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
		6	*
		7	* ========================================================================
		8	*
		9	* This file contains Original Code and/or Modifications of Original
		10	* Code as defined in and that are subject to the Sybase Open Watcom
		11	* Public License version 1.0 (the 'License'). You may not use this file
		12	* except in compliance with the License. BY USING THIS FILE YOU AGREE TO
		13	* ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
		14	* provided with the Original Code and Modifications, and is also
		15	* available at www.sybase.com/developer/opensource.
		16	*
		17	* The Original Code and all software distributed under the License are
		18	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
		19	* EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
		20	* ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
		21	* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
		22	* NON-INFRINGEMENT. Please see the License for the specific language
		23	* governing rights and limitations under the License.
		24	*
		25	* ========================================================================
		26	*
		27	* Description: WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
		28	* DESCRIBE IT HERE!
		29	*
		30	****************************************************************************/
		31
		32
		33	/*
		34	* This file is #included by qsort.c.
		35	*/
		36
		37
		38	/* Support OS/2 16-bit protected mode - will never get stack overflow */
		39	#define MAXDEPTH (sizeof(long) * 8)
		40
		41	#define SHELL 3 /* Shell constant used in shell sort */
		42
		43	typedef int WORD;
		44	#define W sizeof( WORD )
		45
		46	/*
		47	swap() is a macro that chooses between an in_line function call and
		48	an exchange macro.
		49	*/
		50	#define exch( a, b, t) ( t = a, a = b, b = t )
		51	#define swap( a, b ) \
		52	swaptype != 0 ? BYTESWAP( a, b, size ) : \
		53	( void ) exch( ( WORD )( a ), ( WORD )( b ), t )
		54
		55	/*
		56	Note: The following assembly was timed against several other methods
		57	of doing the same thing. The pragmas here were either fastest on all
		58	machines tested, or fastest on most machines tested. (including an 8088,
		59	386 16mhz, 386 33mhz, and 486 25mhz).
		60	*/
		61
		62	#if defined( __386__ )
		63	/* this is intended for 386 only... */
		64	void inline_swap( char p, char q, size_t size );
		65	#pragma aux inline_swap = \
		66	0x06 /* push es */ \
		67	0x1e /* push ds */ \
		68	0x07 /* pop es */ \
		69	0x0f 0xb6 0xd1 /* movzx edx,cl */ \
		70	0xc1 0xe9 0x02 /* shr ecx,02H */ \
		71	0x74 0x0b /* je L1 */ \
		72	0x8b 0x07 /L2 mov eax,[edi] / \
		73	0x87 0x06 /* xchg eax,[esi] */ \
		74	0xab /* stosd */ \
		75	0x83 0xc6 0x04 /* add esi,0004H */ \
		76	0x49 /* dec ecx */ \
		77	0x75 0xf5 /* jne L2 */ \
		78	0x80 0xe2 0x03 /L1 and dl,03H / \
		79	0x74 0x09 /* je L3 */ \
		80	0x8a 0x07 /L4 mov al,[edi] / \
		81	0x86 0x06 /* xchg al,[esi] */ \
		82	0xaa /* stosb */ \
		83	0x46 /* inc esi */ \
		84	0x4a /* dec edx */ \
		85	0x75 0xf7 /* jne L4 */ \
		86	/L3 / \
		87	0x07 /* pop es */ \
		88	parm caller [esi] [edi] [ecx] \
		89	value \
		90	modify exact [esi edi ecx eax edx];
		91	#pragma aux byteswap parm [esi] [edi] [ecx] \
		92	modify exact [esi edi ecx eax edx];
		93	static void _WCNEAR byteswap( char p, char q, size_t size ) {
		94	inline_swap( p, q, size );
		95	}
		96
		97	#elif defined( M_I86 ) && defined( __BIG_DATA__ )
		98	void inline_swap( char _WCFAR p, char _WCFAR q, size_t size );
		99	#pragma aux inline_swap = \
		100	0x1e /* push ds */ \
		101	0x8e 0xda /* mov ds,dx */ \
		102	0xd1 0xe9 /* shr cx,1 */ \
		103	0x74 0x0b /* je L1 */ \
		104	0x26 0x8b 0x05 /L2 mov ax,es:[di] / \
		105	0x87 0x04 /* xchg ax,[si] */ \
		106	0xab /* stosw */ \
		107	0x46 /* inc si */ \
		108	0x46 /* inc si */ \
		109	0x49 /* dec cx */ \
		110	0x75 0xf5 /* jne L2 */ \
		111	0x73 0x07 /L1 jnc L3 / \
		112	0x8a 0x04 /* mov al,[si] */ \
		113	0x26 0x86 0x05 /* xchg al,es:[di] */ \
		114	0x88 0x04 /* mov [si],al */ \
		115	0x1f /L3 pop ds / \
		116	parm caller [dx si] [es di] [cx] \
		117	value \
		118	modify exact [si di cx ax];
		119	#pragma aux byteswap parm [dx si] [es di] [cx] modify exact [si di cx ax];
		120	static void _WCNEAR byteswap( char _WCFAR p, char _WCFAR q, size_t size ) {
		121	inline_swap( p, q, size );
		122	}
		123
		124	#elif defined( M_I86 ) && defined( __SMALL_DATA__ )
		125	/* we'll ask for char __far q to save us writing code to load es /
		126	void inline_swap( char p, char _WCFAR q, size_t size );
		127	#pragma aux inline_swap = \
		128	0xd1 0xe9 /* shr cx,1 */ \
		129	0x74 0x0b /* je L1 */ \
		130	0x26 0x8b 0x05 /L2 mov ax,es:[di] / \
		131	0x87 0x04 /* xchg ax,[si] */ \
		132	0xab /* stosw */ \
		133	0x46 /* inc si */ \
		134	0x46 /* inc si */ \
		135	0x49 /* dec cx */ \
		136	0x75 0xf5 /* jne L2 */ \
		137	0x73 0x07 /L1 jnc L3 / \
		138	0x8a 0x04 /* mov al,[si] */ \
		139	0x26 0x86 0x05 /* xchg al,es:[di] */ \
		140	0x88 0x04 /* mov [si],al */ \
		141	/L3 / \
		142	parm caller [si] [es di] [cx] \
		143	value \
		144	modify exact [si di cx ax];
		145	#pragma aux byteswap parm [si] [es di] [cx] modify exact [si di cx ax];
		146	static void _WCNEAR byteswap( char p, char _WCFAR q, size_t size ) {
		147	inline_swap( p, q, size );
		148	}
		149
		150	#else
		151	/* this is an optimized version of a simple byteswap */
		152	#define inline_swap BYTESWAP
		153	static void _WCNEAR BYTESWAP( PTRATTR char p, PTRATTR char q, size_t size ) {
		154	long dword;
		155	short word;
		156	char byte;
		157
		158	#if 1 /* this is for 32 bit machines */
		159	while( size > 3 ) {
		160	dword = (PTRATTR long )p;
		161	(PTRATTR long )p = (PTRATTR long )q;
		162	(PTRATTR long )q = dword;
		163	p += 4;
		164	q += 4;
		165	size -= 4;
		166	}
		167	if( size > 1 ) {
		168	word = (PTRATTR short )p;
		169	(PTRATTR short )p = (PTRATTR short )q;
		170	(PTRATTR short )q = word;
		171	p += 2;
		172	q += 2;
		173	size -= 2;
		174	}
		175	#else /* this is for 16 bit machines */
		176	while( size > 1 ) {
		177	word = (PTRATTR short )p;
		178	(PTRATTR short )p = (PTRATTR short )q;
		179	(PTRATTR short )q = word;
		180	p += 2;
		181	q += 2;
		182	size -= 2;
		183	}
		184	#endif
		185	if( size ) {
		186	byte = *p;
		187	p = q;
		188	*q = byte;
		189	}
		190	}
		191	#endif
		192
		193
		194	FUNCTION_LINKAGE void FUNCTION_NAME(
		195	PTRATTR void *in_base, size_t n,
		196	size_t size,
		197	int (compar)(const void , const void *)
		198	)
		199	/**********************************************************************/
		200	{
		201	PTRATTR char * base = (PTRATTR char*) in_base;
		202	PTRATTR char * p1;
		203	PTRATTR char * p2;
		204	PTRATTR char * pa;
		205	PTRATTR char * pb;
		206	PTRATTR char * pc;
		207	PTRATTR char * pd;
		208	PTRATTR char * pn;
		209	PTRATTR char * pv;
		210	PTRATTR char * mid;
		211	WORD v; /* used in pivot initialization */
		212	WORD t; /* used in exch() macro */
		213	int comparison, swaptype, shell;
		214	size_t count, r, s;
		215	unsigned int sp;
		216	auto char * base_stack[MAXDEPTH];
		217	auto unsigned int n_stack[MAXDEPTH];
		218	qcomp * cmp = (qcomp*) compar;
		219
		220	/*
		221	Initialization of the swaptype variable, which determines which
		222	type of swapping should be performed when swap() is called.
		223
		224	2 for swapping by bytes. W (it's a macro) = sizeof(WORD).
		225	*/
		226	swaptype = ( ( base - (char *)0 ) \| size ) % W ? 2 : size > W ? 1 : 0;
		227	sp = 0;
		228	for(;;) {
		229	while( n > 1 ) {
		230	if( n < 16 ) { /* 2-shell sort on smallest arrays */
		231	for( shell = (size * SHELL) ;
		232	shell > 0 ;
		233	shell -= ((SHELL-1) * size) ) {
		234	p1 = base + shell;
		235	for( ; p1 < base + n * size; p1 += shell ) {
		236	for( p2 = p1;
		237	p2 > base && cmp( p2 - shell, p2 ) > 0;
		238	p2 -= shell ) {
		239	swap( p2, p2 - shell );
		240	}
		241	}
		242	}
		243	break;
		244	} else { /* n >= 16 */
		245	/* Small array (15 < n < 30), mid element */
		246	mid = base + (n >> 1) * size;
		247	if( n > 29 ) {
		248	p1 = base;
		249	p2 = base + ( n - 1 ) * size;
		250	if( n > 42 ) { /* Big array, pseudomedian of 9 */
		251	s = (n >> 3) * size;
		252	p1 = MED3( p1, p1 + s, p1 + (s << 1), cmp );
		253	mid = MED3( mid - s, mid, mid + s, cmp );
		254	p2 = MED3( p2 - (s << 1), p2 - s, p2, cmp );
		255	}
		256	/* Mid-size (29 < n < 43), med of 3 */
		257	mid = MED3( p1, mid, p2, cmp );
		258	}
		259	/*
		260	The following sets up the pivot (pv) for partitioning.
		261	It's better to store the pivot value out of line
		262	instead of swapping it to base. However, it's
		263	inconvenient in C unless the element size is fixed.
		264	So, only the important special case of word-size
		265	objects has utilized it.
		266	*/
		267	if( swaptype != 0 ) { /* Not word-size objects */
		268	pv = base;
		269	swap( pv, mid );
		270	} else { /* Storing the pivot out of line (at v) */
		271	pv = ( char* )&v;
		272	v = ( WORD )mid;
		273	}
		274
		275	pa = pb = base;
		276	pc = pd = base + ( n - 1 ) * size;
		277	count = n;
		278	/*
		279	count keeps track of how many entries we have
		280	examined. Once we have looked at all the entries
		281	then we know that the partitioning is complete.
		282	We use count to terminate the looping, rather than
		283	a pointer comparison, to handle 16bit pointer
		284	limitations that may lead pb or pc to wrap.
		285	i.e. pc = 0x0000;
		286	pc -= 0x0004;
		287	pc == 0xfffc;
		288	pc is no longer less that 0x0000;
		289	*/
		290	for(;;) {
		291	while(count && (comparison = cmp(pb, pv)) <= 0) {
		292	if( comparison == 0 ) {
		293	swap( pa, pb );
		294	pa += size;
		295	}
		296	pb += size;
		297	count--;
		298	}
		299	while(count && (comparison = cmp(pc, pv)) >= 0) {
		300	if( comparison == 0 ) {
		301	swap( pc, pd );
		302	pd -= size;
		303	}
		304	pc -= size;
		305	count--;
		306	}
		307	if( !count ) break;
		308	swap( pb, pc );
		309	pb += size;
		310	count--;
		311	if( !count ) break;
		312	pc -= size;
		313	count--;
		314	}
		315	pn = base + n * size;
		316	s = min( pa - base, pb - pa );
		317	if( s > 0 ) {
		318	inline_swap( base, pb - s, s );
		319	}
		320	s = min( pd - pc, pn - pd - size);
		321	if( s > 0 ) {
		322	inline_swap( pb, pn - s, s );
		323	}
		324	/* Now, base to (pb-pa) needs to be sorted */
		325	/* Also, pn-(pd-pc) needs to be sorted */
		326	/* The middle 'chunk' contains all elements=pivot value*/
		327	r = pb - pa;
		328	s = pd - pc;
		329	if( s >= r ) { /* Stack up the larger chunk */
		330	base_stack[sp] = pn - s;/* Stack up base */
		331	n_stack[sp] = s / size; /* Stack up n */
		332	n = r / size; /* Set up n for next 'call'*/
		333	/* next base is still base */
		334	} else {
		335	if( r <= size ) break;
		336	base_stack[sp] = base; /* Stack up base */
		337	n_stack[sp] = r / size; /* Stack up n */
		338	base = pn - s; /* Set up base and n for */
		339	n = s / size; /* next 'call' */
		340	}
		341	++sp;
		342	}
		343	}
		344	if( sp == 0 ) break;
		345	--sp;
		346	base = base_stack[sp];
		347	n = n_stack[sp];
		348	}
		349	}

Subversion Repositories Kolibri OS

(root)/programs/develop/open watcom/trunk/clib/search/qsortrtn.c – Rev 553