nativelibc/qsort.c

/*	A part of the Native C Library for Windows NT
	Copyright 2007-2015 PC GO Ld.

	This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

	This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
*/

#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define MAX_THRESH 8
#define STACK_SIZE (8 * sizeof(size_t))

#define swap(a, b, size) \
	do {					\
		char *_a = (a), *_b = (b);	\
		size_t _size = (size);		\
		if(_a == _b) break;		\
		while(_size--) {		\
			char _t = *_a;		\
			*_a++ = *_b;		\
			*_b++ = _t;		\
		}				\
	} while(0)


static void ssort(char *low, char *high, size_t size, int (*compar)(const void *, const void *)) {
	while(high > low) {
		char *max = low;
		char *p;
		for(p = low + size; p <= high; p += size) {
			if(compar(p, max) > 0) max = p;
		}
		swap(max, high, size);
		high -= size;
	}
}

void qsort(void *base, size_t count, size_t size, int (*compar)(const void *, const void *)) {
	//if(!count) return;
	if(count < 2) return;
	if(!size) return;
	char *low_stack[STACK_SIZE], *high_stack[STACK_SIZE];
	int index = 0;
	//char *low = (char *)base;
	//char *high = (char *)base + (count - 1) * size;
	char *low, *high;
	*low_stack = base;
	*high_stack = (char *)base + (count - 1) * size;
	do {
		low = low_stack[index];
		high = high_stack[index];
		size_t len = (high - low) / size + 1;

		if(len < MAX_THRESH) ssort(low, high, size, compar);
		else {
			char *mid = low + (len / 2) * size;
			//if(compar(low, mid) > 0) swap(low, mid, size);
			//if(compar(low, high) > 0) swap(low, high, size);
			//if(compar(mid, high) > 0) swap(mid, high, size);
			swap(mid, low, size);
#if 0
			char *left_ptr = low + size;
			char *right_ptr = high - size;
#else
			char *left_ptr = low;
			char *right_ptr = high + size;
#endif

#if 0
			/// NEED TEST!
			do {
				while(compar(left_ptr, mid) < 0) left_ptr += size;
				while(compar(mid, right_ptr) < 0) right_ptr -= size;
				if(left_ptr < right_ptr) {
					swap(left_ptr, right_ptr, size);
					if(mid == left_ptr) mid = right_ptr;
					else if(mid == right_ptr) mid = left_ptr;
					left_ptr += size;
					right_ptr -= size;
				} else if(left_ptr == right_ptr) {
					left_ptr += size;
					right_ptr -= size;
					break;
				}
			} while(left_ptr <= right_ptr);
#else
			while(1) {
				do {
					left_ptr += size;
				} while(left_ptr <= high && compar(left_ptr, low) <= 0);
				do {
					right_ptr -= size;
				} while(right_ptr > low && compar(right_ptr, low) >= 0);
				if(right_ptr < left_ptr) break;
				swap(left_ptr, right_ptr, size);
			}
#endif

			//right_ptr += size;
			//while(mid < right_ptr && compar(right_ptr, mid) == 0) right_ptr -= size;
			//while(low < right_ptr && compar(right_ptr, mid) == 0) right_ptr -= size;
			swap(low, right_ptr, size);
			if(right_ptr - 1 - low >= high - left_ptr) {
				if(low + size < right_ptr) {
					low_stack[index] = low;
					high_stack[index] = right_ptr - size;
					index++;
				}
				if(left_ptr < high) {
					//low = left_ptr;
					//low_stack[index] = low;
					low_stack[index] = left_ptr;
					high_stack[index] = high;
					continue;
				}
			} else {
				if(left_ptr < high) {
					low_stack[index] = left_ptr;
					high_stack[index] = high;
					index++;
				}
				if(low + size < right_ptr) {
					low_stack[index] = low;
					high_stack[index] = right_ptr - size;
					continue;
				}
			}
		}
		index--;
	} while(index >= 0);
}