#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <string.h>

/* a linked list node */
struct node_t {
    int data;
    struct node_t* next;
};

/* add an element at front of list */
void list_insert(struct node_t** head, int data) {
    struct node_t* new = malloc(sizeof(struct node_t));
    new->data = data;
    new->next = *head;
    *head = new;
}

/* print a linked list to the screen */
void list_print(struct node_t* head) {
    struct node_t* current = head;
    while (current) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}


struct node_t* string_search(char* data, char* target, int data_length) {
    int targ_length = strlen(target);

    /* the list of locations we found it at */
    struct node_t* head = NULL;

    // for each starting index
#pragma omp parallel for num_threads(8)
    for (int start = 0; start < (data_length - targ_length); start++) {

        // for each one past this
        int found = 1;
        for (int letter = 0; letter < targ_length; letter++) {
            
            if (data[start + letter] != target[letter]) {
                // this start is not right
                found = 0;
                break;
            }
        }

        // check if it was found
        if (found) {
#pragma omp critical
            list_insert(&head, start);
        }
    }

    return head;
}

unsigned long ms_diff(struct timeval a, struct timeval b) {
    unsigned long msa = (a.tv_sec * 1000) + (a.tv_usec / 1000);
    unsigned long msb = (b.tv_sec * 1000) + (b.tv_usec / 1000);
    return msb - msa;
}

int main(int argc, char** argv) {
    unsigned int length;
    char* data;
    char target[256];
    struct timeval a, b;

    /* get start time */
    gettimeofday(&a, NULL);

    /* open the file */
    if (argc < 2) {
        printf("Please pass an input file.\n");
        return 0;
    }
    FILE* filetest = fopen(argv[1], "r");
    if (!filetest) {
        printf("Could not open %s for reading.\n", argv[1]);
        return 0;
    }

    /* find the length of the file */
    fseek(filetest, 0L, SEEK_END);
    length = ftell(filetest);
    fseek(filetest, 0L, SEEK_SET);
    fclose(filetest);

    /* read the file into memory */
    data = malloc(length * sizeof(char) + 1);
    memset(data, 0, length + 1);
   
    int num_threads = 8;
    
    #pragma omp parallel for num_threads(num_threads)
    for (int i = 0; i < num_threads; i++) {
        int start = (length / num_threads) * i;
        int size = length / num_threads;
   
        if (i == (num_threads - 1)) {
            size += length % num_threads;
        }
    
        FILE* file = fopen(argv[1], "r");
        fseek(file, start, SEEK_SET);
        fread(data + start, sizeof(char), size, file);
        fclose(file);
    }
    
    gettimeofday(&b, NULL);

    unsigned long read = ms_diff(a, b);
    printf("Reading took %lu ms.\n", read);

    /* ask what should be searched for */
    printf("Enter search term: ");
    scanf("%s", target);

    gettimeofday(&a, NULL);
    
    /* now do the searching */
    struct node_t* list = string_search(data, target, length);
    gettimeofday(&b, NULL);
    unsigned long search = ms_diff(a, b);
    
    if (list == NULL) {
        printf("There were no occurences.");
    } else {
        printf("Occurences:\n");
        list_print(list);
    }

    printf("Searching took %lu ms.\n", search);
    return 0;
}