/******************************************************************************/
/**
@file "Pthreads/C/Ispitni zadaci/si4mps_k1_20112012_z5.c"
@brief Trazenje k pojavljivanja zadatog elementa u nizu.

@author Marko Misic
*/
/******************************************************************************/

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

// Global variables
pthread_mutex_t start_mutex;
pthread_cond_t start_cond;
int start_flag = 0;

pthread_mutex_t k_matches_mutex;
int k_mathces_count = 0;
int* k_matches_indices;
int next_match_index = 0;

// Arguments structure for every thread
typedef struct {
  int* array;
  int my_start;
  int my_end;
  int k;
  int number;
} Arguments;

// Thread function
void* find_k_matches (void* arg) {
  
  Arguments* args = (Arguments*)arg;
  int count =  0;
  int i;

  pthread_mutex_lock(&start_mutex);
  if (!start_flag) {
    pthread_cond_wait(&start_cond, &start_mutex);
  }
  pthread_mutex_unlock(&start_mutex);
  
  for (i = args->my_start; i < args->my_end; i++) {
    if (args->array[i] == args->number) {
      pthread_mutex_lock(&k_matches_mutex);
      if (k_mathces_count == args->k) {
        pthread_mutex_unlock(&k_matches_mutex);
        break;
      }
      k_mathces_count++;
      k_matches_indices[next_match_index++] = i;
      
      pthread_mutex_unlock(&k_matches_mutex);
    }
  }

  free(args);

  pthread_exit(NULL);
  return 0;
}

// Main program
void main () {
   
  pthread_attr_t attributes;
  pthread_t* threads;
  int num_threads;
    
  int arr_len;
  int* array;

  int chunk;
  int i;
  int number;
  int k;

  // Init 
  pthread_attr_init(&attributes);
	pthread_attr_setdetachstate(&attributes, PTHREAD_CREATE_JOINABLE);

  pthread_mutex_init(&start_mutex, NULL);
  pthread_mutex_init(&k_matches_mutex, NULL);
  pthread_cond_init (&start_cond, NULL);
  
  // Input
  printf("Enter number of threads: ");
  scanf("%d", &num_threads);

  threads = (pthread_t*) malloc(num_threads * sizeof(pthread_t));
  if (threads == NULL) {
    printf("Memory allocation failed!");
    exit(2);
  }

  printf("Enter number of elements: ");
  scanf("%d", &arr_len);

  chunk = arr_len / num_threads;
  if (arr_len % num_threads) {
    printf("Array length not divisible by number of threads!");
    exit(1);
  }

  array = (int*) malloc(arr_len * sizeof(int));
  if (array == NULL) {
    printf("Memory allocation failed!");
    exit(2);
  }

  srand(time(NULL));
  printf("Array elements: \n");
  for(i=0; i < arr_len; i++) {
    //scanf("%d", &array[i]);
    array[i] = (rand() / (RAND_MAX + 0.0)) * 100;
  }
  
  printf("Element to find: \n");
  scanf("%d", &number);

  printf("Enter k: \n");
  scanf("%d", &k);
  
  k_matches_indices = malloc(k*sizeof(int));
  if (k_matches_indices == NULL) {
    printf("Memory allocation failed!");
    exit(2);
  }

  // Thread creation
  for (i=0; i < num_threads; i++) {
    int rc;
    Arguments* arg = malloc(sizeof(Arguments));
    if (arg == NULL) {
      printf("Memory allocation failed!");
      exit(2);
    }

    arg->array = array;
    arg->my_start = i*chunk;
    arg->my_end = arg->my_start + chunk;
    arg->k = k;
    arg->number = number;

    rc = pthread_create(&threads[i], NULL, find_k_matches,(void*)arg);
		if (rc) {
			printf("Pthread_create failed! Error: %d\n", rc);
			exit(3);
		}
  }

  // Release threads
  pthread_mutex_lock(&start_mutex);
  start_flag = 1;
  pthread_cond_broadcast(&start_cond);
  pthread_mutex_unlock(&start_mutex);
  
  for (i=0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
  }

  // Print the results
  if (k_mathces_count == k) {
    printf("\nK = %d matches of number %d found in the array at following positions: \n", k, number);
    for(i=0; i < k; i++) printf("%d ", k_matches_indices[i]);
  } else {
    printf("\nK = %d matches of number %d not found in the array!", k, number);
  }

  // Free resources
  free(threads);
  free(array);
  free(k_matches_indices);

  pthread_mutex_destroy(&k_matches_mutex);
  pthread_mutex_destroy(&start_mutex);
  pthread_cond_destroy(&start_cond);

  pthread_attr_destroy(&attributes);

}