#include <types.h>
#include <lib.h>
#include <thread.h>
#include <test.h>
#include <synch.h>

#define N_LORD_FLOWERKILLER 8
#define NROPES 16
static int ropes_left = NROPES;
#define FREED_INDEX -27

/* Data structures for rope mappings */

volatile int rope_list[NROPES];
volatile int rope_count;
volatile int stake_list[NROPES];
volatile int hook_list[NROPES];

// false until each character has completed their tasks
struct characters_complete {
    volatile bool dandelion_status;
    volatile bool marigold_status;
    volatile bool balloon_status;

    volatile int flowerkiller_clones;
    volatile bool flowerkiller_status;
};

static struct characters_complete *characters_complete;

/* Synchronization primitives */

struct semaphore *sem;
struct lock *lk_dandelion;
struct lock *lk_marigold;
struct lock *lk_flowerkiller;
struct lock *lk_balloon;

/*
 * Describe your design and any invariants or locking protocols
 * that must be maintained. Explain the exit conditions. How
 * do all threads know when they are done?

	Each character is provided their own locking, to ensure concurrent threads working.
	Semaphores are used when each character checks for uncut ropes/stakes, randomly selects one
	and attempts to cut it if it hasn't already been cut. An additional lock, made for the character,
	is called when it should be marked as done its work. It is done when there are no more ropes/stakes
	that are fully connected that can be severed by the character.

	The flowerkiller and its clones use a semaphore as well. They randomly look for a rope
	and if its not currently freed, will attempt to find another distinct rope to switch with.
	If that is found, they will be switched and message is posted. The flowerkiller's work is done when
	there is no ropes for switching.

	All threads know they are done by tracking through a character_complete structure that holds booleans
	for when each thread has completed the work it can do, including the balloon which is done when all
	ropes are correctly severed.
 */


static
void
dandelion(void *p, unsigned long arg)
{
    (void)p;
    (void)arg;

    kprintf("Dandelion thread starting\n");
    int index = random() % NROPES;
    P(sem);
    while (rope_count > 0) {

        while ((rope_list[hook_list[index]] == 0)
			|| (hook_list[index] == FREED_INDEX)) {
            index = random() % NROPES;
        }

        rope_list[hook_list[index]] = 0;
        kprintf("Dandelion severed rope %d\n", hook_list[index]);
        rope_count--;
        hook_list[index] = FREED_INDEX;

        V(sem);
        thread_yield();
        P(sem);
    }
    kprintf("Dandelion thread done\n");
    V(sem);

    lock_acquire(lk_dandelion);
    characters_complete->dandelion_status = true;
    lock_release(lk_dandelion);
}

static
void
marigold(void *p, unsigned long arg)
{
    (void)p;
    (void)arg;

    kprintf("Marigold thread starting\n");
    int index = random() % NROPES;
    P(sem);
    while (rope_count > 0) {

        while ((rope_list[stake_list[index]] == 0)
			|| (stake_list[index] == FREED_INDEX)) {
            index = random() % NROPES;
        }

        rope_list[stake_list[index]] = 0;
        kprintf("Marigold severed rope %d\n", stake_list[index]);
        rope_count--;
        stake_list[index] = FREED_INDEX;

        V(sem);
        thread_yield();
        P(sem);
    }
    kprintf("Marigold thread done\n");
    V(sem);

    lock_acquire(lk_marigold);
    characters_complete->marigold_status = true;
    lock_release(lk_marigold);
}

static void flowerkiller(void *p, unsigned long arg) {
    (void)p;
    (void)arg;

    kprintf("Lord FlowerKiller thread starting\n");

    int index1, index2;
    int rope1, rope2;

	P(sem);
    while (ropes_left > 0) {
        do {
            index1 = random() % NROPES;
        } while (stake_list[index1] == FREED_INDEX
			|| rope_list[stake_list[index1]] == 0);

        do {
            index2 = random() % NROPES;
        } while (index2 == index1
			|| stake_list[index2] == FREED_INDEX
			|| rope_list[stake_list[index2]] == 0);

		/* stake switching */
        rope1 = stake_list[index1];
        rope2 = stake_list[index2];
        stake_list[index1] = rope2;
        stake_list[index2] = rope1;

        V(sem);
        thread_yield();
        kprintf("Lord FlowerKiller switched rope %d from stake %d to stake %d\n",
                rope1, index1, index2);

        kprintf("Lord FlowerKiller switched rope %d from stake %d to stake %d\n",
                rope2, index2, index1);

        /* Check if all ropes have been severed and break */
        if (rope_count == 0) break;
		P(sem);
    }
	V(sem);

    kprintf("Lord FlowerKiller thread done\n");

    lock_acquire(lk_flowerkiller);
    characters_complete->flowerkiller_clones--;
    
    // If all clones are done, set the status to true
    if (characters_complete->flowerkiller_clones == 0) {
        characters_complete->flowerkiller_status = true;
    }

    lock_release(lk_flowerkiller);
}


static
void
balloon(void *p, unsigned long arg)
{
    (void)p;
    (void)arg;

    kprintf("Balloon thread starting\n");

    P(sem);
    while (rope_count > 0) {
        V(sem);
        thread_yield();
        P(sem);
    }
    kprintf("Balloon freed and Prince Dandelion escapes!\n");
    V(sem);

    lock_acquire(lk_balloon);
    characters_complete->balloon_status = true;
    lock_release(lk_balloon);

    kprintf("Balloon thread done\n");
    return;
}

int
airballoon(int nargs, char **args)
{
    int err = 0, i;

    (void)nargs;
    (void)args;
    (void)ropes_left;

    rope_count = NROPES;
    for (int i = 0; i < NROPES; i++) {
        rope_list[i] = 1;
		hook_list[i] = i;
        stake_list[i] = i;
    }

    characters_complete = kmalloc(sizeof(*characters_complete));
    characters_complete->dandelion_status = false;
    characters_complete->marigold_status = false;
    characters_complete->balloon_status = false;

    characters_complete->flowerkiller_clones = N_LORD_FLOWERKILLER;
    characters_complete->flowerkiller_status = false;

    sem = sem_create("sem", 1);
    if (sem == NULL) {
        panic("sem_create failed\n");
    }
    lk_dandelion = lock_create("lk_dandelion");
    if (lk_dandelion == NULL) {
        panic("lock_create failed\n");
    }
    lk_marigold = lock_create("lk_marigold");
    if (lk_marigold == NULL) {
        panic("lock_create failed\n");
    }
    lk_flowerkiller = lock_create("lk_flowerkiller");
    if (lk_flowerkiller == NULL) {
        panic("lock_create failed\n");
    }
    lk_balloon = lock_create("lk_balloon");
    if (lk_balloon == NULL) {
        panic("lock_create failed\n");
    }

    err = thread_fork("Marigold Thread",
        NULL, marigold, NULL, 0);
    if (err)
        goto panic;

    err = thread_fork("Dandelion Thread",
        NULL, dandelion, NULL, 0);
    if (err)
        goto panic;

    for (i = 0; i < N_LORD_FLOWERKILLER; i++) {
        err = thread_fork("Lord FlowerKiller Thread",
            NULL, flowerkiller, NULL, 0);
        if (err)
            goto panic;
    }

    err = thread_fork("Air Balloon",
        NULL, balloon, NULL, 0);
    if (err)
        goto panic;

    lock_acquire(lk_dandelion);
	while (!characters_complete->dandelion_status) {
    	lock_release(lk_dandelion);
    	thread_yield();
    	lock_acquire(lk_dandelion);
	}

	lock_acquire(lk_marigold);
	while (!characters_complete->marigold_status) {
		lock_release(lk_marigold);
		thread_yield();
		lock_acquire(lk_marigold);
	}

	lock_acquire(lk_balloon);
	while (!characters_complete->balloon_status) {
		lock_release(lk_balloon);
		thread_yield();
		lock_acquire(lk_balloon);
	}

	lock_acquire(lk_flowerkiller);
	while (!characters_complete->flowerkiller_status) {
		lock_release(lk_flowerkiller);
		thread_yield();
		lock_acquire(lk_flowerkiller);
	}

	lock_release(lk_dandelion);
	lock_release(lk_marigold);
	lock_release(lk_balloon);
	lock_release(lk_flowerkiller);

	kfree(characters_complete);
    sem_destroy(sem);
    lock_destroy(lk_dandelion);
    lock_destroy(lk_marigold);
    lock_destroy(lk_flowerkiller);
    lock_destroy(lk_balloon);

    kprintf("Main thread done\n");
    goto done;
panic:
    panic("airballoon: thread_fork failed: %s)\n",
        strerror(err));

done:
    return 0;
}