/*
    The Merge Sort to use for Operating Systems Assignment 1 2019
    written by Robert Sheehan

    Modified by: put your name here
    UPI: put your login here

    By submitting a program you are claiming that you and only you have made
    adjustments and additions to this code.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/resource.h>
#include <stdbool.h>
#include <pthread.h>

#define SIZE    2

int THREAD_MAX=0;
pthread_mutex_t mutex;
long num_cpus;

struct block {
    int size;
    int *first;
};

// void print_block_data(struct block *blk) {
//     printf("size: %d address: %p\n", blk->size, blk->first);
// }

/* Combine the two halves back together. */
void merge(struct block *left, struct block *right) {
	int combined[left->size + right->size];
	int dest = 0, l = 0, r = 0;
	while (l < left->size && r < right->size) {
		if (left->first[l] < right->first[r])
			combined[dest++] = left->first[l++];
		else
			combined[dest++] = right->first[r++];
	}
	while (l < left->size)
		combined[dest++] = left->first[l++];
	while (r < right->size)
		combined[dest++] = right->first[r++];
    memmove(left->first, combined, (left->size + right->size) * sizeof(int));
}

/* Merge sort the data. */
void *merge_sort(void* args) {
    // print_block_data(my_data);
    struct block *my_data = (struct block *) args;

    if (my_data->size > 1) {
        struct block left_block;
        struct block right_block;
        left_block.size = my_data->size / 2;
        left_block.first = my_data->first;
        right_block.size = left_block.size + (my_data->size % 2);
        right_block.first = my_data->first + left_block.size;


        pthread_t thread1;
        if (THREAD_MAX<num_cpus){
            pthread_attr_t attr;
            pthread_attr_init(&attr);
            pthread_attr_setstacksize(&attr,900000000);

            pthread_mutex_lock(&mutex);
            //printf("%d\n",THREAD_MAX);
            THREAD_MAX++;
            pthread_mutex_unlock(&mutex);

            pthread_create(&thread1,&attr, merge_sort,&left_block);
            merge_sort(&right_block);
            pthread_join(thread1,NULL);
            pthread_mutex_lock(&mutex);
            THREAD_MAX--;
            pthread_mutex_unlock(&mutex);
        }else{
            merge_sort(&left_block);
            merge_sort(&right_block);
        }
        merge(&left_block, &right_block);
        pthread_mutex_destroy(&mutex);
    }
}

/* Check to see if the data is sorted. */
bool is_sorted(int data[], int size) {
    bool sorted = true;
    for (int i = 0; i < size - 1; i++) {
        if (data[i] > data[i + 1])
            sorted = false;
    }
    return sorted;
}

int main(int argc, char *argv[]) {
    struct rlimit limit;
    getrlimit(RLIMIT_STACK, &limit);
    limit.rlim_cur=900000000;
    limit.rlim_max=900000000;
    setrlimit(RLIMIT_STACK, &limit);
	long size;

    pthread_mutex_init(&mutex, NULL);
    num_cpus = sysconf( _SC_NPROCESSORS_ONLN);

	if (argc < 2) {
		size = SIZE;
	} else {
		size = atol(argv[1]);
	}
    struct block start_block;
    int data[size];
    start_block.size = size;
    start_block.first = data;
    for (int i = 0; i < size; i++) {
        data[i] = rand();
    }

    printf("starting---\n");
    merge_sort(&start_block);
    printf("---ending\n");
    printf(is_sorted(data, size) ? "sorted\n" : "not sorted\n");
    printf("\nStack Limit  = %ld and %ld max\n",limit.rlim_cur, limit.rlim_max);
    exit(EXIT_SUCCESS);
}