#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <string.h>
#include <sys/types.h>
#include <memory.h>

const int INIT_SIZE = 64 * 1024;

#pragma pack(1)
struct bos_hdr {
    int magic; // must be set to 0xb055;
    union {
        char padding[16];
    } u;
};

struct bos_entry {
    int allocated:1; // will be non-zero if allocated
    int size; // includes the size of bos_entry
    union {
        char padding[8];
    } u;
};

#pragma pack()

int main(int argc, char **argv) {
    if (argc != 2) {
        printf("USAGE: %s bos_filename\n", argv[0]);
        exit(2);
    }
    int fd = open(argv[1], O_CREAT | O_RDWR, 0777);
    if (fd == -1) {
        perror(argv[1]);
        exit(3);
    }

    void *base = mmap(NULL, 1024*1024, PROT_WRITE | PROT_READ, MAP_SHARED, fd, 0);
    void *end;
    struct bos_hdr *hdr = base;
    struct bos_entry *first_entry = (struct bos_entry *)(hdr+1);

    struct stat stat;
    if (fstat(fd, &stat) == -1) {
        perror("fstat");
        exit(4);
    }
    if (stat.st_size == 0) {
        ftruncate(fd, INIT_SIZE);
        memset(hdr, 0, sizeof *hdr);
        hdr->magic = 0xb055;
        memset(first_entry, 0, sizeof *first_entry);
        first_entry->size = INIT_SIZE - sizeof *hdr;
        end = (char*)base + INIT_SIZE;
    } else {
        end = (char*)base + stat.st_size;
    }

    size_t n;
    char *line = NULL;
    while (getline(&line, &n, stdin) > 0) {
        // remove the newline
        size_t endi = strlen(line) - 1;
        if (line[endi] == '\n') {
            line[endi] = '\0';
        }
        switch(line[0]) {
            case 'l': {
                struct bos_entry *entry = first_entry;
                while ((void *) entry < end) {
                    if (entry->allocated) {
                        printf("%s\n", (char *) &entry[1]);
                    }
                    entry = (struct bos_entry *) ((char *) entry + entry->size);
                }
            }
                break; // break from the switch statement
            case 'a': {
                char *str = &line[2];
                struct bos_entry *bestFitEntry = NULL;
                struct bos_entry *entry = first_entry;
                int smallestLeftover = 99999;
                int needed_size = sizeof(*entry) + strlen(str) + 1;
                int left_over = 0;
                while ((void *) entry < end) {
                    //Checks for duplicates if allocated
                    printf("Checking %s against entry of value = %s\n", str,  (char *)&entry[1]);
                    if (entry->allocated) {
                        if (strcmp(str, (char *) &entry[1]) == 0) {
                            printf("Duplicate found\n");
                            break;
                        }
                    }
                        //If unallocated, check for best fit
                    else {
                        // split it (note this should be fixed so that it can grow if needed
                        left_over = entry->size - needed_size;
                        printf("Found space with %d leftover compared to %d best leftover\n", left_over, smallestLeftover);
                        if ((left_over >= 0) && (left_over < smallestLeftover)) {
                            printf("Found new best leftover = %p\n", (void *)entry);
                            smallestLeftover = left_over;
                            bestFitEntry = entry;
                        }
                    }
                    entry = (struct bos_entry *) ((char *) entry + entry->size);
                    /**
                    entry = (struct bos_entry *) ((char *) entry + entry->size);
                    if (!entry->allocated) {
                        // split it (note this should be fixed so that it can grow if needed
                        int needed_size = sizeof(*entry) + strlen(str) + 1;
                        int left_over = entry->size - needed_size;
                        if (left_over < sizeof(*entry) && smallestLeftover < left_over) {
                            // if we don't have enough left over for an entry struct, we just
                            // use it here and it will be internal fragmentation
                            needed_size = entry->size;
                            left_over = 0;
                        }
                        if (entry->size < needed_size) {
                            printf("hmmm, you need to grow!!!\n");
                            exit(6);
                        }
                        entry->size = needed_size;
                        entry->allocated = 1;
                        strcpy((char *) &entry[1], str);
                        if (left_over > 0) {
                            entry = (struct bos_entry *) ((char *) entry + entry->size);
                            memset(entry, 0, sizeof *entry);
                            entry->size = left_over;
                        }
                        break;
                        **/
                }
                if(bestFitEntry != NULL){
                    left_over = bestFitEntry->size - needed_size;
                    if (left_over < sizeof(*entry)) {
                        // if we don't have enough left over for an entry struct, we just
                        // use it here and it will be internal fragmentation
                        printf("Using all space of entry\n");
                        needed_size = bestFitEntry->size;
                        left_over = 0;
                    }
                    printf("bestfitEntry = %p\n", (void *)bestFitEntry);
                    bestFitEntry->size = needed_size;
                    bestFitEntry->allocated = 1;
                    strcpy((char *) &bestFitEntry[1], str);
                    if (left_over > 0) {
                        printf("Turning leftover into new unallocated entry\n");
                        entry = (struct bos_entry *) ((char *) bestFitEntry + bestFitEntry->size);
                        memset(entry, 0, sizeof *entry);
                        entry->size = left_over;
                    }
                }
            }
                break;
            case 'd': {
                char *str = &line[2];
                struct bos_entry *entry = first_entry;
                struct bos_entry *firstUnallocatedEntry = NULL;
                int foundTarget = 0;
                int lastRecordAllocated = 1;

                while ((void*)entry < end) {
                    //If entry is unallocated or target is found, unallocate and set flags
                    if((!entry->allocated) || (strcmp(str, (char *)&entry[1]) == 0)){
                        if(strcmp(str, (char *)&entry[1]) == 0){
                            foundTarget = 1;
                        }
                        entry->allocated = 0;
                        //sets pointer to first unallocated entry of segment
                        if(lastRecordAllocated){
                            firstUnallocatedEntry = entry;
                            lastRecordAllocated = 0;
                        }
                    }
                    else{   //is allocated
                        if(firstUnallocatedEntry != NULL){
                            //finds total unallocated space of segment and coalesces
                            printf("UnallocatedEntry size before: %d\n", firstUnallocatedEntry->size);
                            firstUnallocatedEntry->size = abs((entry - 1) - firstUnallocatedEntry);
                            printf("UnallocatedEntry size after: %d\n", firstUnallocatedEntry->size);
                            firstUnallocatedEntry = NULL;
                        }
                        lastRecordAllocated = 1;
                        if(foundTarget){
                            break;
                        }
                    }
                    entry = (struct bos_entry *) ((char *) entry + entry->size);
                }

                /**
                while ((void*)entry < end) {
                    printf("entry[1] = %s and str = %s\n", (char *)&entry[1], str);
                    if(entry->allocated && (strcmp(str, (char *)&entry[1]) == 0)){
                        entry->allocated = 0;
                        printf("Entered loop and turned off allocation");
                    }
                    entry = (struct bos_entry *) ((char *) entry + entry->size);
                }
                 **/


            }
                break;

            case 'L': {
                struct bos_entry *entry = first_entry;
                int i = 0;
                while ((void*)entry < end) {
                    char * allocated = "not allocated";
                    if(entry->allocated){
                        allocated = "allocated";
                    }

                    printf("Entry #%d of size %d and is %s\n", i, entry->size, allocated);
                    printf("%s\n", (char*)&entry[1]);
                    entry = (struct bos_entry *) ((char *) entry + entry->size);
                    i++;
                }
                printf("There were %d entries\n", i);
            }

                break; // break from the switch statement
        }
        free(line);
        n = 0;
        line = 0;
    }
    return 0;
}