/******************************************************************************/
/**
@file "Pthreads/C/Primer 8 - pbs/pbs_thread.c"
@brief Parallel bucket sort primer.

Primer sortiranja liste jednako distribuiranih brojeva. Brojevi se
nasumično generisu izmedju 0 i 2*n. Koriste se Bucket sort i Sequential
sort algoritmi.

@author Miloš Gligorić
@author Andrija Bosnjaković
*/
/******************************************************************************/

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/******************************************************************************/

/**
@def ERROR_ALLOC
@brief greška u slucaju neuspele alokacije prostora.
*/
#define ERROR_ALLOC 2

/**
@def ERROR_NUM_OF_THREADS
@brief greška u slučaju nekorektnog boraj niti.
*/
#define ERROR_NUM_OF_THREADS 3

/**
@def NUM_OF_THREADS
@brief broj niti koji će biti pokrenut unutar programa.
*/
#define NUM_OF_THREADS 4

/******************************************************************************/

static void make_numbers(long int big_array[], int n, int n_bar, int p);

static void sequential_sort(void *);

static int  get_min_pos(long int array[] , int eff_size);

/******************************************************************************/

/**
@struct DATA
@brief Opis skupa podataka nad kojim se vrši obrada
*/
typedef struct {
    /**
    @property array
    @brief Pokazivač na niz koji se uredjuje.
    */
    int *array;

    /**
    @property n_bar
    @brief Broj elemenata koliko svaka nit treba da uredi.
    */
    int n_bar;
} DATA;

/******************************************************************************/

/**
@var data
@brief Promenljiva koja sadrži podatke za obradu
*/
DATA data;

/**
@var threads
@brief Niti koje vrše obradu podataka
*/
pthread_t threads[NUM_OF_THREADS];

/**
@var attr
@brief Atribut niti
*/
pthread_attr_t attr;

/******************************************************************************/

/**
@brief Glavni program
@param argc Broj argumenata komandne linije
@param argv Argumenti komandne linije
@return Vraca @b 0 ako je sve uspešno izvršeno
*/
int main(int argc, char* argv[]) {
	long int* big_array;

	/* Podrazumevano se sortira 80 elemenata */
	int n = 80;

    int status;

    /* pomocne promenljive */
	int i;

#ifdef WIN32
    pthread_win32_process_attach_np();
#endif

    if (argc == 2) {
	    /*
	    Prvi argument komandne linije predstavlja broj elemenata niza
	    koji treba sortirati
	    */
	    n = atoi(argv[1]);
    }

    /* Napravimo veliki niz */
	big_array = malloc(n * sizeof(long int));

    if (big_array == NULL) {
        fprintf(stderr, "Neuspela alokacija prostora za niz koji je potrebno sortirati\n");
        exit(ERROR_ALLOC);
    }

    if (n % NUM_OF_THREADS != 0) {
        fprintf(stderr, "Svaka nit treba da dobije isti broj elemenata na obradu.\n");
        exit(ERROR_NUM_OF_THREADS);
    }

    /* Generisemo elemente niza */
    srand(time(NULL));
    make_numbers(big_array, n, n / NUM_OF_THREADS, NUM_OF_THREADS);

    data.n_bar = n / NUM_OF_THREADS;
    data.array = big_array;

    /* kreiranje niti */
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

    for (i = 0; i < NUM_OF_THREADS; i++) {
        pthread_create(&threads[i], &attr, sequential_sort, (void*) i);
    }

    pthread_attr_destroy(&attr);

    for (i = 0; i < NUM_OF_THREADS; i++) {
        pthread_join(threads[i], (void **) &status);
    }

    /* ispisujem sortirani niz */
    for (i = 0; i < n; i++)
        printf("%ld ", data.array[i]);
    printf("\n");

    /* oslobadjanje zauzetog prostora */
	free(big_array);

	pthread_exit(NULL);

#ifdef WIN32
    pthread_win32_process_detach_np();
#endif
}

/******************************************************************************/

/**
@brief Metoda koja generiše elemente bafera.
@param big_array Bafer u koji se smeštaju generisani elementi.
@param n Veličina bafera.
@param n_bar Koeficijent koji koristimo za generisanje elemenata (= n / p).
@param p Koeficijent koji koristimo za generisanje elemenata.
*/
void make_numbers(long int	big_array[],
		  int		n,
		  int		n_bar,
		  int		p)
{
	/* Stavljamo brojeve u "kofe", mada ih mozemo tretirati i drugacije */ 
	int i, q;
	
	printf("Before sorting:\n");
	for (q = 0; q < p; q++)
	{
		printf("\nP%d: ", q); 
		for (i = 0; i < n_bar; i++)
		{
			big_array[q * n_bar + i] =
				rand() % (2 * n / p) + (q * 2 * n / p);
			printf("%7ld %s",
			 big_array[q * n_bar + i], i % 8 == 7 ? "\n\t" : " "); 
		}
		printf("\n"); 
	}
	printf("\n");
}

/******************************************************************************/

/**
@brief Sequential sort algoritam.
@param arg id niti.
*/
void sequential_sort(void *arg) {
    int eff_size, min_pos;
    long int temp;

    int id = (int) arg;
    long int *array = data.array + id * data.n_bar;
    int size = data.n_bar;

	for (eff_size = size; eff_size > 1; eff_size--)
	{
		min_pos = get_min_pos(array, eff_size);
		temp = array[min_pos];
		array[min_pos] = array[eff_size-1];
		array[eff_size-1] = temp;
	}
}

/******************************************************************************/

/**
@brief Vraća indeks najmanjeg od preostalih nesortiranih elemenata.
@param array Bafer čije elemente treba sortirati.
@param eff_size Broj preostalih elemenata.
@return Vraća indeks najmanjeg od preostalih nesortiranih elemenata.
*/
int get_min_pos(long int array[], int eff_size) {
	int i, min_pos = 0;
	
	for (i=0; i < eff_size; i++)
		min_pos = array[i] > array[min_pos] ? i: min_pos;
	return min_pos;
}

/******************************************************************************/