WebSVN – Kolibri OS – Blame – /contrib/media/stb_vorbis/qsort.c

Rev	Author	Line No.	Line
8039	hidnplayr	1	/*******************************************************************************
		2	*
		3	* Author: Remi Dufour - remi.dufour@gmail.com
		4	* Date: July 23rd, 2012
		5	*
		6	* Name: Quicksort
		7	*
		8	* Description: This is a well-known sorting algorithm developed by C. A. R.
		9	* Hoare. It is a comparison sort and in this implementation,
		10	* is not a stable sort.
		11	*
		12	* Note: This is public-domain C implementation written from
		13	* scratch. Use it at your own risk.
		14	*
		15	*******************************************************************************/
		16
		17	#include
		18	#include
		19
		20	/* Insertion sort threshold shift
		21	*
		22	* This macro defines the threshold shift (power of 2) at which the insertion
		23	* sort algorithm replaces the Quicksort. A zero threshold shift disables the
		24	* insertion sort completely.
		25	*
		26	* The value is optimized for Linux and MacOS on the Intel x86 platform.
		27	*/
		28	#ifndef INSERTION_SORT_THRESHOLD_SHIFT
		29	# ifdef __APPLE__ & __MACH__
		30	# define INSERTION_SORT_THRESHOLD_SHIFT 0
		31	# else
		32	# define INSERTION_SORT_THRESHOLD_SHIFT 2
		33	# endif
		34	#endif
		35
		36	/* Macro SWAP
		37	*
		38	* Swaps the elements of two arrays.
		39	*
		40	* The length of the swap is determined by the value of "SIZE". While both
		41	* arrays can't overlap, the case in which both pointers are the same works.
		42	*/
		43	#define SWAP(A,B,SIZE) \
		44	{ \
		45	register char *a_byte = A; \
		46	register char *b_byte = B; \
		47	register const char *a_end = a_byte + SIZE; \
		48	\
		49	while (a_byte < a_end) \
		50	{ \
		51	register const char swap_byte = *b_byte; \
		52	b_byte++ = a_byte; \
		53	*a_byte++ = swap_byte; \
		54	} \
		55	}
		56
		57	/* Macro SWAP_NEXT
		58	*
		59	* Swaps the elements of an array with its next value.
		60	*
		61	* The length of the swap is determined by the value of "SIZE". This macro
		62	* must be used at the beginning of a scope and "A" shouldn't be an expression.
		63	*/
		64	#define SWAP_NEXT(A,SIZE) \
		65	register char *a_byte = A; \
		66	register const char *a_end = A + SIZE; \
		67	\
		68	while (a_byte < a_end) \
		69	{ \
		70	register const char swap_byte = *(a_byte + SIZE); \
		71	(a_byte + SIZE) = a_byte; \
		72	*a_byte++ = swap_byte; \
		73	}
		74
		75	/* Function Quicksort
		76	*
		77	* This function performs a basic Quicksort. This implementation is the
		78	* in-place version of the algorithm and is done in he following way:
		79	*
		80	* 1. In the middle of the array, we determine a pivot that we temporarily swap
		81	* to the end.
		82	* 2. From the beginning to the end of the array, we swap any elements smaller
		83	* than this pivot to the start, adjacent to other elements that were
		84	* already moved.
		85	* 3. We swap the pivot next to these smaller elements.
		86	* 4. For both sub-arrays on sides of the pivot, we repeat this process
		87	* recursively.
		88	* 5. For a sub-array smaller than a certain threshold, the insertion sort
		89	* algorithm takes over.
		90	*
		91	* As an optimization, rather than performing a real recursion, we keep a
		92	* global stack to track boundaries for each recursion level.
		93	*
		94	* To ensure that at most O(log2 N) space is used, we recurse into the smaller
		95	* partition first. The log2 of the highest unsigned value of an integer type
		96	* is the number of bits needed to store that integer.
		97	*/
		98	void qsort(void *array,
		99	size_t length,
		100	size_t size,
		101	int(compare)(const void , const void *))
		102	{
		103	/* Recursive stacks for array boundaries (both inclusive) */
		104	struct stackframe
		105	{
		106	void *left;
		107	void *right;
		108	} stack[CHAR_BIT * sizeof(void *)];
		109
		110	/* Recursion level */
		111	struct stackframe *recursion = stack;
		112
		113	#if INSERTION_SORT_THRESHOLD_SHIFT != 0
		114	/* Insertion sort threshold */
		115	const int threshold = size << INSERTION_SORT_THRESHOLD_SHIFT;
		116	#endif
		117
		118	/* Assign the first recursion level of the sorting */
		119	recursion->left = array;
		120	recursion->right = (char )array + size (length - 1);
		121
		122	do
		123	{
		124	/* Partition the array */
		125	register char *index = recursion->left;
		126	register char *right = recursion->right;
		127	char *left = index;
		128
		129	/* Assigning store to the left */
		130	register char *store = index;
		131
		132	/* Pop the stack */
		133	--recursion;
		134
		135	/* Determine a pivot (in the middle) and move it to the end */
		136	const size_t middle = (right - left) >> 1;
		137	SWAP(left + middle - middle % size,right,size)
		138
		139	/* From left to right */
		140	while (index < right)
		141	{
		142	/* If item is smaller than pivot */
		143	if (compare(right, index) > 0)
		144	{
		145	/* Swap item and store */
		146	SWAP(index,store,size)
		147
		148	/* We increment store */
		149	store += size;
		150	}
		151
		152	index += size;
		153	}
		154
		155	/* Move the pivot to its final place */
		156	SWAP(right,store,size)
		157
		158	/* Performs a recursion to the left */
		159	#define RECURSE_LEFT \
		160	if (left < store - size) \
		161	{ \
		162	(++recursion)->left = left; \
		163	recursion->right = store - size; \
		164	}
		165
		166	/* Performs a recursion to the right */
		167	#define RECURSE_RIGHT \
		168	if (store + size < right) \
		169	{ \
		170	(++recursion)->left = store + size; \
		171	recursion->right = right; \
		172	}
		173
		174	/* Insertion sort inner-loop */
		175	#define INSERTION_SORT_LOOP(LEFT) \
		176	{ \
		177	register char *trail = index - size; \
		178	while (trail >= LEFT && compare(trail, trail + size) > 0) \
		179	{ \
		180	SWAP_NEXT(trail,size) \
		181	trail -= size; \
		182	} \
		183	}
		184
		185	/* Performs insertion sort left of the pivot */
		186	#define INSERTION_SORT_LEFT \
		187	for (index = left + size; index < store; index +=size) \
		188	INSERTION_SORT_LOOP(left)
		189
		190	/* Performs insertion sort right of the pivot */
		191	#define INSERTION_SORT_RIGHT \
		192	for (index = store + (size << 1); index <= right; index +=size) \
		193	INSERTION_SORT_LOOP(store + size)
		194
		195	/* Sorts to the left */
		196	#if INSERTION_SORT_THRESHOLD_SHIFT == 0
		197	# define SORT_LEFT RECURSE_LEFT
		198	#else
		199	# define SORT_LEFT \
		200	if (store - left <= threshold) \
		201	{ \
		202	INSERTION_SORT_LEFT \
		203	} \
		204	else \
		205	{ \
		206	RECURSE_LEFT \
		207	}
		208	#endif
		209
		210	/* Sorts to the right */
		211	#if INSERTION_SORT_THRESHOLD_SHIFT == 0
		212	# define SORT_RIGHT RECURSE_RIGHT
		213	#else
		214	# define SORT_RIGHT \
		215	if (right - store <= threshold) \
		216	{ \
		217	INSERTION_SORT_RIGHT \
		218	} \
		219	else \
		220	{ \
		221	RECURSE_RIGHT \
		222	}
		223	#endif
		224
		225	/* Recurse into the smaller partition first */
		226	if (store - left < right - store)
		227	{
		228	/* Left side is smaller */
		229	SORT_RIGHT
		230	SORT_LEFT
		231
		232	continue;
		233	}
		234
		235	/* Right side is smaller */
		236	SORT_LEFT
		237	SORT_RIGHT
		238
		239	#undef RECURSE_LEFT
		240	#undef RECURSE_RIGHT
		241	#undef INSERTION_SORT_LOOP
		242	#undef INSERTION_SORT_LEFT
		243	#undef INSERTION_SORT_RIGHT
		244	#undef SORT_LEFT
		245	#undef SORT_RIGHT
		246	}
		247	while (recursion >= stack);
		248	}
		249
		250	#undef INSERTION_SORT_THRESHOLD_SHIFT
		251	#undef SWAP
		252	#undef SWAP_NEXT

Subversion Repositories Kolibri OS

(root)/contrib/media/stb_vorbis/qsort.c – Rev 8065