/*
	QuickSort for Solaris, OpenMP
	WindyHana's Solanara: OpenMP http://www.solanara.net/solanara/openmp
	cc -O3 -xopenmp=parallel -o openmpquick openmp_quick.c
*/
#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#include <omp.h>
#include <sys/time.h>

#define MAX_ELEMENTS 500000
#define MEMALLOCSIZE MAX_ELEMENTS * sizeof(int)

void quicksort(unsigned int * data, int lo, int hi);
void quicksort_openmp(unsigned int * data, int lo, int hi);
void printdata(unsigned int * data, int size);
unsigned long long gettimestamp();

int main(int argc, char *argv[]){
	unsigned int * data;
	unsigned int * data2;
	unsigned long long e1, e2, t1, t2;
	unsigned int seed = (unsigned int)gettimestamp();
	printf("Seed is %d\n", seed);
	srand(seed);
	
	printf("Alloc Memory: %d * 2 bytes\n", MEMALLOCSIZE);
	data = (unsigned int *) malloc(MEMALLOCSIZE);
	data2 = (unsigned int *) malloc(MEMALLOCSIZE);

	printf("Initializing Data [%d]\n", MAX_ELEMENTS);
	for (int i = 0; i < MAX_ELEMENTS; i++) { 
		int r1 = rand() & 0x0000FFFF;
		int r2 = rand() & 0x0000FFFF;
		unsigned int t = (r1 << 16) | r2;
		data[i] = t;
	}
	memcpy((void *)data2, (void *)data, MEMALLOCSIZE);

    #if defined (_OPENMP)
		printf("Max OpenMP Threads: %d\n", omp_get_max_threads());
    #endif

	t1 = gettimestamp();
	quicksort(data, 0, MAX_ELEMENTS - 1);
	t2 = gettimestamp();
	printf("QuickSort\n");
	printdata(data, MAX_ELEMENTS);
	e1 = t2 - t1;

	t1 = gettimestamp();
	quicksort_openmp(data2, 0, MAX_ELEMENTS - 1);
	t2 = gettimestamp();
	printf("QuickSort(OpenMP)\n");
	printdata(data2, MAX_ELEMENTS);
	e2 = t2 - t1;

	printf("       Elapsed: %lld\n", e1);
	printf("OpenMP Elapsed: %lld\n", e2);
	free(data);
	free(data2);
	return 0;
}

void quicksort_openmp(unsigned int * data, int lo, int hi) {
	int i = lo, j = hi, temp;
	int x = data[(lo + hi) / 2];
	do { 
		while (data[i] < x) i++; 
		while (data[j] > x) j--;
		if (i <= j) {
			temp = data[i]; data[i] = data[j]; data[j] = temp; // SWAP
			i++; j--;
		}
	} while (i <= j);
	#pragma omp parallel sections
	{
		#pragma omp section
		if (lo < j) quicksort(data, lo, j);
		#pragma omp section
		if (i < hi) quicksort(data, i, hi);
	}
}

// Just remove openmp progma from quicksort_openmp()
void quicksort(unsigned int * data, int lo, int hi) {
	int i = lo, j = hi, temp;
	int x = data[(lo + hi) / 2];
	do { 
		while (data[i] < x) i++; 
		while (data[j] > x) j--;
		if (i <= j) {
			temp = data[i]; data[i] = data[j]; data[j] = temp; // SWAP
			i++; j--;
		}
	} while (i <= j);
	if (lo < j) quicksort(data, lo, j);
	if (i < hi) quicksort(data, i, hi);
}

// print integer array (for debug)
void printdata(unsigned int * data, int size) {
	if (size > 100) {
		for (int i = 0; i < 2; i ++) {
			printf("data[%d] = %d\n", i, data[i]);
		}
		printf("...\n");
		for (int i = size - 3; i < size; i ++) {
			printf("data[%d] = %d\n", i, data[i]);
		}
	} else {
		for (int i = 0; i < size; i ++) {
			printf("data[%d] = %d\n", i, data[i]);
		}
	}
}

// get current timestamp (micro seconds)
unsigned long long gettimestamp() {
	struct timeval t;
	gettimeofday(&t, NULL);
	return t.tv_sec * 1000000 + t.tv_usec;
}