Paralelni QSort

qsort.c

/* Neparalelní verze Quicksortu.
 * 
 * Určitě by to šlo udělat líp, už v tomhle stádiu. Ale
 */

#include <stdio.h>
#include <stdbool.h>
#include <pthread.h>
#include <unistd.h>   //sleep

#define barrier() __asm__ volatile ("mfence")

void *worker(void *work);

struct QSTask{
  int * from;
  int * to;
  };

void swap(int *a, int *b)
{
barrier();
  int c = *a;
  barrier();
  *a = *b;
  barrier();
  *b = c;
  barrier();
  return;
}

static const int * abs_from;
static const int * abs_to;

int main(void)
{
	volatile int a[] = {5,1,2,3,8,4,5,9};
	abs_from = a;
	abs_to =a+7;
	struct QSTask task = {.from = a, .to = a+7};
	pthread_t bla;
	pthread_create(&bla, NULL, worker, (void *) &task);
//	worker((void *) &task);
	pthread_join(bla, NULL);
	puts("vysledek");
	for(int i =0; i < 8; i++) {
	  printf("%d, ", a[i]);
	 }
	return 0;
}

/* Funkce, která bude provádět třídění. Protože právě tuhle funkci budeme
 * pozdějí spouštět ve vlánkech pomocí knihovny pthread, musí mít funkce
   knihovnou předepsaný typ void *fce(void *param). Kdyby bylo po mým,
   bude to void worker(struct QSTask task), ale i s tímhle se dá žít*/
void *worker(void *work)
{
  barrier();
  pthread_t chworker_l;
  pthread_t chworker_r;
  
  /* odvoidujeme a jsme více méně tam, kde jsme chtěli být. */
  struct QSTask * task = (struct QSTask *) work;
  
    printf("nove vlakno: abs_from: %d, abs_to: %d\n", task->from  - abs_from, task->to - abs_from);
  
  if ( task->from == task->to) {
//    pthread_exit(NULL);
    return;
  }
  
  /* jako pivot volím první prvek */
  int pivot = *task->from;
  
  /* třídit budeme pole bez prvního prvku - pivota. Ten tam vrazím až na
   * konec, takže budu přesně vědět, kde je. */
  int * left = task->from +1;
  int * right = task->to;
  
    for(int * i = task->from; i < task->to+1; i++) {
    printf("%d, ", *i);
  }
  
  
  printf("pivot: %d\n", pivot);
  
  /* zabodnu si ukazatele na začátek a na konec tříděného úseku. Dívám se na ukazované prvky a co se nehodí nalevo hodím napravo a naopak.
  Ukazately šoupu tak, abych při kažém průchodu zkrátil úsek mezi nimi nejméně o jeden prvek -- program zastaví, až se ukazatele překryjí.
  A platí podmínka, že za levým ukazatelem jsou prvky < pivot a za pravým >= pivotovi. */
  while(left < right) {
  printf("pivot: %d\n", pivot);
        printf("left: %d\n", *left);
            printf("right: %d\n", *right);
    if(*left >= pivot) {
      swap(left, right);
      right--;
      continue;
    } else {
      left++;
      continue;
    }
    if(*right < pivot) {
      swap(right, left);
      left++;
      continue;
    } else {
      right--;
      continue;
    }
    printf("pivot: %d\n", pivot);
        printf("left: %d\n", *left);
            printf("right: %d\n", *right);
  }
  /* zařadím pivota co nejvíce doprava to jde. nemůžu říct, jak to vypadá přímo s prvky, na které se ukazuje. proto tu blbnu s tím ifem*/
  if(*left<pivot) {
    ;
  } else {
    left -= 1;
  }
  swap(left, task->from);

  for(int * i = task->from; i < task->to+1; i++) {
    printf("%d, ", *i);
  }
  puts("");
  
  if ( task->from +1 == task->to) {
  puts("Tohle se muze objevit");
      pthread_exit(NULL);
	puts("Tohle by se nemelo objevit");
    return;
    puts("Tohle taky ne");
  }
  puts("a kdyz a tak ne b");

  /* Rekurzivně setřídíme levou a pravou část pole */  
  
  bool lw = false;
  bool rw = false;
  
  if(left < task->to) {
  	  rw=true;
	  struct QSTask task_r = {.from = left+1, .to = task->to};
	  //worker((void *) &task_r);
	   barrier();
	  pthread_create(&chworker_r, NULL, &worker, (void *) &task_r);
//	  pthread_join(chworker_r, NULL);
	//sleep(1);
	 barrier();
  }
  
  if(left > task->from) {
	  struct QSTask task_l = {.from = task->from, .to = left-1};
	  //worker((void *) &task_l);
	  lw=true;
	   barrier();
	  pthread_create(&chworker_l, NULL, &worker, (void *) &task_l);
//	  pthread_join(chworker_l, NULL);
	//sleep(1);
	 barrier();
	  }

  //sleep(1);
  if(lw) {
  	puts("joinuji levé");
	  pthread_join(chworker_l, NULL);
	  }
  if (rw) {
  	puts("joinuji pravé");
    pthread_join(chworker_r, NULL);
    }
    barrier();
  /* blbnutí s voidy kvůli předepsané hlavičce funkce */
      pthread_exit(NULL);
      return;
  
}