#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/types.h>

#define SENTINEL -1

struct node {
    int             element;
    struct node     *next;
};

struct linkedlist {
    struct node     *head;
    int             length;
    pthread_mutex_t lock;
};

void init(struct linkedlist *list){
    list->length = 0;
    list->head = NULL;
    pthread_mutex_init(&list->lock, NULL);
}

void clear(struct linkedlist *list){
    pthread_mutex_destroy(&list->lock);
    for(int i = 0; i < list->length; i++)
        remove(0);
}

void push(struct linkedlist *list, int element){
    struct node *node = malloc(sizeof(struct node));
    node->element = element;
    node->next = NULL;
    if(list->head == NULL){
        list->head = node;
    } else {
        struct node *last = list->head;
        while(last->next != NULL){
            last = last->next;
        }
        last->next = node;
    }
    ++list->length;
}

int remove_at(struct linkedlist *list, int index){
    int retval;
    if(index == 0){
        retval = list->head->element;
        struct node* n = list->head->next;
        free(list->head);
        list->head = n;
    } else {
        struct node* n = list->head;
        for(int i = 0; i < index-1; i++)
            n = n->next;
        struct node *to_be_removed = n->next;
        retval = to_be_removed->element;
        n->next = to_be_removed->next;
        free(to_be_removed);
    }
    --list->length;
    return retval;
}

void *erstellen(void *arg){
    struct linkedlist *list = (struct linkedlist *)arg;
    for(int aufgabe = 0; aufgabe < 1000; aufgabe++){
        // Schläft eine zufällige Zeit im Bereich [0,1000) us. Simuliert die zum Erstellen einer Aufgabe notwendige Zeit.
        usleep(rand()%1000);
        printf("Thread #%d erstellt Aufgabe #%d\n", (int)pthread_self(), aufgabe);
        pthread_mutex_lock(&list->lock);
        push(list, aufgabe);
        pthread_mutex_unlock(&list->lock);
    }
    // Signalisiert, dass alle Aufgaben erstellt worden sind.
    push(list, SENTINEL);
    return NULL;
}

void *verifizieren(void *arg){
    struct linkedlist *list = (struct linkedlist *)arg;
    while(1){
        pthread_mutex_lock(&list->lock);
        if(list->length > 0){
            int aufgabe = remove_at(list, 0);
            pthread_mutex_unlock(&list->lock);
            // SENTINEL bedeutet, dass wir ans Ende der Aufgabenliste angekommen sind und, dass alle Aufgaben verifiziert worden sind.
            if(aufgabe == SENTINEL){
                // Pusht den SENTINEL Wert zurück in die Liste.
                push(list, SENTINEL);
                return NULL;
            }
            // Schläft eine zufällige Zeit im Bereich [0,1000) us. Simuliert die zum Verifizieren einer Aufgabe notwendige Zeit.
            usleep(rand()%1000);
            printf("Thread #%d verifiziert Aufgabe #%d\n", (int)pthread_self(), aufgabe);
        }
        else{
            pthread_mutex_unlock(&list->lock);
        }
    }
}


int main(){
    struct linkedlist list;
    init(&list);

    pthread_mutex_init(&list.lock, NULL);

    pthread_t dawid, hiwi1, hiwi2;
    pthread_create(&hiwi1, NULL, verifizieren, &list);
    pthread_create(&hiwi2, NULL, verifizieren, &list);
    pthread_create(&dawid, NULL, erstellen, &list);

    pthread_join(dawid, NULL);
    pthread_join(hiwi1, NULL);
    pthread_join(hiwi2, NULL);

    // Das Programm funktioniert korrekt, falls am Ende nur der SENTINEL Wert in der Liste zu finden ist.
    printf("List length: %d\n", list.length);
    printf("Last element == SENTINEL: %s\n", remove_at(&list, 0) == SENTINEL ? "yes" : "no");
    clear(&list);

}