/*
 * This program demonstrates a possible gcc optimization bug. On my system,
 * when compiled with -O2 -finline-functions, or -O3, the data is not sorted.
 * With -O2 or with uncommenting the debugging printout at the end
 * of qsort_data() (thus disabling the tail-call), it works.
 * My gcc is gcc version 4.1.2 20070925 (Red Hat 4.1.2-33) fron Fedora 8,
 * AMD64.
 */
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

typedef struct bucket_entry {
        u_int32_t key, value;
} bucket_entry_t;

static void qsort_data(bucket_entry_t *list, int size);
static void swap_entry(bucket_entry_t *e1, bucket_entry_t *e2);

#define DATASIZE 300000

int main(int argc, char **argv)
{
	bucket_entry_t data[DATASIZE], *p;
	u_int32_t key;
	int i;

	for (i=0; i < DATASIZE; i++) {
		data[i].key = (u_int32_t) lrand48();
		data[i].value = (u_int32_t) lrand48();
	}

	qsort_data(data, DATASIZE);

	for (p = data, key = p->key; p < data + DATASIZE; key = p->key, p++) {
		if (key > p->key) {
			fprintf(stderr, "unsorted at %ld: %x > %x\n", p - data,
				key, p->key);
			exit(1);
		}
	}
	printf("OK sorted.\n");
	return 0;
}

/* Note, this works on 64-bit systems only! */
static inline void swap_entry(bucket_entry_t *e1, bucket_entry_t *e2)
{
	unsigned long d;

	d = *(unsigned long *)e1;
	*(unsigned long *)e1 = *(unsigned long *)e2;
	*(unsigned long *)e2 = d;
}

static void qsort_data(bucket_entry_t *list, int size)
{
	bucket_entry_t *pivot = list;
	u_int32_t pv = pivot->key;
	int lo, hi;
	if (size <= 1)
		return;

	lo = 1;
	hi = size - 1;
	while (lo < hi) {
		while (lo < hi && list[lo].key <= pv)
			lo++;
		while (lo < hi && list[hi].key > pv)
			hi--;
		if (lo < hi) {
			swap_entry(list+lo, list+hi);
		}
	}
	if (list[lo].key < pv)
		swap_entry(pivot, list+lo);

	qsort_data(list, lo);
	qsort_data(list+lo, size - lo);

/* *** uncomment me 
	{ int i;
	for (i = 0; i < size-1; i++) {
		if (list[i].key > list[i+1].key) {
			fprintf(stderr, "Error in sort: size=%d, lo=%d, i=%d, pv=%x\n",
				size, lo, i, pv);
			for (i = 0; i < size; i++) {
				fprintf(stderr, "%d %x\n", i, list[i].key);
			}
			exit(1);
		}
	}
	}
 */
}