[APPS] Threads - Radek

// ***********************************************************************
//
// Demo program pro vyuku predmetu APPS (09/2011)
// Petr Olivka, katedra informatiky, FEI, VSB-TU Ostrava
// email:petr.olivka@vsb.cz
//
// Priklad pouzit vlaken v OS Windows
// Pro overeni paralelismu je nutno mit alespon dvoujadrovy procesor
//
// ***********************************************************************

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

#define TYP int

int DELKA = 20;
TYP *POLE, *LEFT, *RIGHT;
TYP MAX1 = 0, MAX2 = 0, MAX3 = 0;

// funkce rand() je pouze 16 bitova
// rand32 vraci 32 bitove nahodne cislo
int rand32()
{
    return rand() * RAND_MAX + rand();
}

void fillArray(int *array, int size) {
	for (int i = 0; i < size; i++)
	{
		array[i] = rand32() % DELKA;
		//array[i] = i;
	}
}

void fillArray2(TYP *array, TYP from, TYP to) {
	for (long i = from; i < to; i++)
	{
		array[i] = rand32()%100+1;
		//array[i] = i;
	}
}

void printArray(TYP *array, int size) {
	for (int i = 0; i < size; i++)
	{
		printf("%d\n", array[i]);
	}
}

// funkce pro nalezeni nejvetsiho cisla v useku pole
// od leveho (vcetne) az k pravemu prvku
TYP hledej_max( int levy, int pravy, TYP *pole )
{
	TYP nejvetsi = pole[ levy ];
	for ( int i = levy + 1; i < pravy; i++ )
		if ( nejvetsi < pole[ i ] )
			nejvetsi = pole[ i ];
	return nejvetsi;
}

// Pouziti globalnich promennych zjednodusuje ukazku pouziti vlaken.
// Neni ovsem programatorsky spravne!
// Globalni promenne: DELKA - pocet prvku na ktere odkazuje POLE


void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void bubbleSort(int *array, int size) {
	for (int i = 0; i < size - 1; i++)
	{
		for (int j = 0; j < size - i - 1; j++)
		{
			if (array[j] < array[j + 1])
			{
				swap(&array[j], &array[j + 1]);
			}
		}
	}
}

void bubbleSort2(int *array, int l, int r) {
	for (int i = l; i < r - 1; i++)
	{
		for (int j = l; j < r - i - 1; j++)
		{
			if (array[j] > array[j + 1])
			{
				swap(&array[j], &array[j + 1]);
			}
		}
	}
}

// vlakno A bude hledat maximalni prvek pole mezi prvkem 0 a DELKA/2
// vysledek ulozi do globalni promenne MAX1
DWORD WINAPI vlaknoA( LPVOID )
{
	printf( "Startuje vlakno A\n" );
    MAX1 = hledej_max( 0, DELKA / 3, POLE );
	return 0;
}

DWORD WINAPI vlaknoB( LPVOID )
{
	printf( "Startuje vlakno B\n" );
    MAX2 = hledej_max( DELKA / 3, 2*DELKA/3, POLE );
	return 0;
}

DWORD WINAPI vlaknoC(LPVOID)
{
	printf("Startuje vlakno C\n");
	MAX3 = hledej_max(2*DELKA/3, DELKA, POLE);
	return 0;
}

DWORD WINAPI vlaknoD(LPVOID)
{
	printf("Startuje vlakno D\n");
	MAX1 = hledej_max(0, DELKA/2, POLE);
	return 0;
}

DWORD WINAPI vlaknoE(LPVOID)
{
	printf("Startuje vlakno E\n");
	MAX2 = hledej_max(DELKA / 2, DELKA, POLE);
	return 0;
}

DWORD WINAPI vlaknoF(LPVOID)
{
	printf("Startuje vlakno F\n");
	MAX1 = hledej_max(0, DELKA, POLE);
	return 0;
}

DWORD WINAPI vlaknoNaplneni(LPVOID param)
{
	int *a = (int*)param;
	int l = a[0];
	int r = a[1];
	printf("Startuje vlakno F - %d - %d\n",l,r);
	fillArray2(POLE, l, r);
	return 0;
}

DWORD WINAPI vlaknoSetrizeni(LPVOID param)
{
	int *a = (int*)param;
	int l = a[0];
	int r = a[1];
	printf("Startuje vlakno SETRIZENI - %d - %d\n", l, r);
	return 0;
}

DWORD WINAPI vlaknoBubble(LPVOID param)
{
	int l = (int)param;
	printf("Startuje vlakno SETRIZENI - %d\n", l);
	if (l == 1)
	{
		bubbleSort(LEFT, DELKA / 2);
	}
	else {
		bubbleSort(RIGHT,DELKA - DELKA / 2);
	}
	return 0;
}

void split(int *l, int *p, int *arr, int size) {
	for (int i = 0; i < size / 2; i++)
	{
		l[i] = arr[i];
	}

	int pom = 0;
	for (int i = size / 2; i < size; i++)
	{
		p[pom++] = arr[i];
	}
}

void merge(int* l, int* p, int *arr, int lSize, int rSize) {
	int i, j, k;
	i = 0;
	j = 0;
	k = 0;

	while (i < lSize && j < rSize)
	{
		if (l[i] > p[j])
		{
			arr[k++] = l[i++];
		}
		else if (l[i] < p[j])
		{
			arr[k++] = p[j++];
		}
		else
		{
			arr[k++] = l[i++];
			arr[k++] = p[j++];
		}
	}

	while (i < lSize)
	{
		arr[k++] = l[i++];
	}

	while (j < rSize)
	{
		arr[k++] = p[j++];
	}

}


// vypocet casoveho intervalu v milisekundach
int kolik_ms( LPFILETIME pred, LPFILETIME po )
{
	hyper pred64b = pred->dwHighDateTime;
	pred64b = ( pred64b << 32 ) | pred->dwLowDateTime;
	hyper po64b = po->dwHighDateTime;
	po64b = ( po64b << 32 ) | po->dwLowDateTime;
	// konverze 100ns -> 1ms
	return ( int ) ( ( po64b - pred64b ) / 10000 );
}

int main( int na, char **arg )
{
	// pri zpusteni je nutno zadat argument udavajici delku pole 
	// nahodne vygenerovanych cisel
	/*if ( na != 2 ) 
	{ 
		printf( "Zadej pocet prvku, minimalne 1000000\n" ); 
		return 0; 
	}
	DELKA = atoi( arg[ 1 ] );
	if ( DELKA < 1000000 ) 
	{ 
		printf( "Pocet prvku musi byt minimalne 1000000\n" ); 
		return 0; 
	}*/

	// alokace pole
	

	// inicializace generatoru nahodnych cisel
	

	
	/*for ( int i = 0; i < DELKA; i++ )
	{
		POLE[ i ] = rand32() % ( DELKA * 10 );
		if ( !( i % 10000000 ) ) printf( "." ); 
	}*/

	/*printf( "\nHledani nejvetsiho prvku pomoci 2 vlaken...\n" );
	HANDLE p1, p2;
	FILETIME cas_pred, cas_po;

	// zaznamenani casu pred zapocetim hledani
	GetSystemTimeAsFileTime ( &cas_pred );

	// vytvoreni dvou vlaken
	p1 = CreateThread( 0, 0, vlaknoA, 0, 0, 0 );
	p2 = CreateThread( 0, 0, vlaknoB, 0, 0, 0 );

	// cekani na ukonceni vlaken
	WaitForSingleObject( p1, INFINITE );
	WaitForSingleObject( p2, INFINITE );

	// zaznam casu po ukonceni prace obou vlaken
	GetSystemTimeAsFileTime( &cas_po );

	printf( "Nalezene maximum je %d\n", max( MAX1, MAX2 ) );
	printf( "Cas hledani byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );

	printf( "Hledani nejvetsiho prvku pomoci 1 vlakna...\n" );
	GetSystemTimeAsFileTime( &cas_pred );

	// hledani jednim vlaknem
	TYP M = hledej_max( 0, DELKA, POLE );

	GetSystemTimeAsFileTime( &cas_po );

	printf( "Nalezene maximum je %d\n", M );
	printf( "Cas hledani byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );*/
	POLE = new TYP[DELKA];
	LEFT = new TYP[DELKA / 2];
	RIGHT = new TYP[DELKA - DELKA / 2];
	if (!POLE)
	{
		printf("Nelze alokovat pamet!\n");
		return 1;
	}


	srand((int)time(NULL));

	/*
	printf("Generuji nahodna cisla\n");
	fillArray(POLE, DELKA);

	HANDLE p1, p2, p3;
	FILETIME cas_pred, cas_po;

	GetSystemTimeAsFileTime(&cas_pred);

	p1 = CreateThread(0, 0, vlaknoA, 0, 0, 0);
	p2 = CreateThread(0, 0, vlaknoB, 0, 0, 0);
	p3 = CreateThread(0, 0, vlaknoC, 0, 0, 0);

	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);
	WaitForSingleObject(p3, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);

	printf("Nalezene maximum je %d\n", max(MAX1, max(MAX2,MAX3)));
	printf("Cas hledani byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));

	GetSystemTimeAsFileTime(&cas_pred);

	p1 = CreateThread(0, 0, vlaknoD, 0, 0, 0);
	p2 = CreateThread(0, 0, vlaknoE, 0, 0, 0);

	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);

	printf("Nalezene maximum je %d\n", max(MAX1, MAX2));
	printf("Cas hledani byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));

	GetSystemTimeAsFileTime(&cas_pred);

	p1 = CreateThread(0, 0, vlaknoF, 0, 0, 0);

	WaitForSingleObject(p1, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);

	printf("Nalezene maximum je %d\n", MAX1);
	printf("Cas hledani byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));
	*/

	/*printf("Generuji nahodna cisla\n");
	fillArray(POLE, DELKA);
	FILETIME cas_pred, cas_po;
	int casVms;

	GetSystemTimeAsFileTime(&cas_pred);

	printf("Tridim...\n");
	bubbleSort(POLE, DELKA);

	GetSystemTimeAsFileTime(&cas_po);

	casVms = kolik_ms(&cas_pred, &cas_po);
	printArray(POLE, 50);
	printf("Cas hledani byl %d [ms]\n", casVms);*/


	/*
	HANDLE p1, p2, p3, p4;
	FILETIME cas_pred, cas_po;

	GetSystemTimeAsFileTime(&cas_pred);

	int pom[2];
	int pom2[2];
	int pom3[2];
	int pom4[2];

	pom[0] = 0;
	pom[1] = DELKA/4;
	p1 = CreateThread(0, 0, vlaknoNaplneni, (LPVOID)pom, 0, 0);

	pom2[0] = DELKA / 4;
	pom2[1] = 2*(DELKA / 4);
	p2 = CreateThread(0, 0, vlaknoNaplneni, (LPVOID)pom2, 0, 0);

	pom3[0] = 2 * (DELKA / 4);
	pom3[1] = 3 * (DELKA / 4);
	p3 = CreateThread(0, 0, vlaknoNaplneni, (LPVOID)pom3, 0, 0);

	pom4[0] = 3 * (DELKA / 4);
	pom4[1] = DELKA;
	p4 = CreateThread(0, 0, vlaknoNaplneni, (LPVOID)pom4, 0, 0);

	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);
	WaitForSingleObject(p3, INFINITE);
	WaitForSingleObject(p4, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);

	printArray(POLE, 20);
	printf("Cas naplneni byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));

	GetSystemTimeAsFileTime(&cas_pred);

	fillArray2(POLE, 0, DELKA);

	GetSystemTimeAsFileTime(&cas_po);
	printf("1 vlakno - Cas naplneni byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));

	*/

	HANDLE p1, p2;
	FILETIME cas_pred, cas_po;

	fillArray(POLE, DELKA);
	//printArray(POLE, DELKA);
	split(LEFT, RIGHT, POLE, DELKA);

	p1 = CreateThread(0, 0, vlaknoBubble, (LPVOID)1, 0, 0);
	p2 = CreateThread(0, 0, vlaknoBubble, (LPVOID)0, 0, 0);

	GetSystemTimeAsFileTime(&cas_pred);
	
	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);

	
	merge(LEFT, RIGHT, POLE, DELKA / 2, DELKA - DELKA / 2);
	

	

	printf("SETRIZENO\n");
	printArray(POLE, DELKA);
	printf("Cas setrizeni byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));
	

}