/*
 * Compile commad: gcc -O2 -s -o qsort_test.exe qsort_test.c
 * or              cl /O2 /Fe:qsort_test.exe qsort_test.c
 * Usage: qsort_test.exe [-d]
 *   -d - dump tables to stdout
 */

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

#define TABLESIZE 5

typedef struct {
	int f1;
	int f2;
	int f3;
} element_type;

static int
element_comparator (const void *el1, const void *el2)
{
	element_type *p1 = (element_type*) el1;
	element_type *p2 = (element_type*) el2;

	/* Only f1 and f2 are used as sort keys; f3 is irrelevant. */
	if (p1->f1 != p2->f1)
		return (p1->f1 > p2->f1) - (p1->f1 < p2->f1);

	if (p1->f2 != p2->f2)
		return (p1->f2 > p2->f2) - (p1->f2 < p2->f2);

	return 0;
}

static void
insertion_sort(void *base, size_t nmemb, size_t size,
				int (*compar)(const void *, const void *))
{
	unsigned char *a = base;
	unsigned char *tmp;
	size_t i, j;

	if (nmemb < 2 || size == 0)
		return;

	tmp = malloc(size);
	if (tmp == NULL)
		return;

	for (i = 1; i < nmemb; ++i) {
		memcpy(tmp, a + i * size, size);

		j = i;
		while (j > 0 && compar(tmp, a + (j - 1) * size) < 0) {
			memcpy(a + j * size, a + (j - 1) * size, size);
			--j;
		}

		memcpy(a + j * size, tmp, size);
	}

	free(tmp);
}

int main (int argc, char *argv[])
{
	element_type t0[TABLESIZE] = {
		{0, 0, 10}, {7, 7, 10}, {5, 5, 10}, {7, 7, 5}, {0, 0, 11}
	};
	element_type t1[TABLESIZE], t2[TABLESIZE];
	size_t i;

	memcpy(t1, t0, TABLESIZE*sizeof(element_type));
	memcpy(t2, t0, TABLESIZE*sizeof(element_type));

	insertion_sort(t1, TABLESIZE, sizeof(element_type), element_comparator);
	qsort(t2, TABLESIZE, sizeof(element_type), element_comparator);

	/* Dump tables to stdout */
	if (argc > 1 && argv[1][0] == '-' && argv[1][1] == 'd') {
		for (i = 0; i < TABLESIZE; ++i) {
			printf("t0[%zu]:\t%d\t%d\t%d\n", i, t0[i].f1, t0[i].f2, t0[i].f3);
			printf("t1[%zu]:\t%d\t%d\t%d\n", i, t1[i].f1, t1[i].f2, t1[i].f3);
			printf("t2[%zu]:\t%d\t%d\t%d\n\n", i, t2[i].f1, t2[i].f2, t2[i].f3);
		}
	}

	for (i = 0; i < TABLESIZE; ++i) {
		if ( memcmp(&t1[i], &t2[i], sizeof(element_type)) ) {
			printf("First fail at element %zu\n", i);
			printf("FAIL\n");
			return -1;
		}
	}
	printf("PASS\n");
	return 0;
}