#include <stdlib.h>
#include <string.h>
#include "cpen212alloc.h"

typedef struct {
    void *end;   // end of heap
    void *free;  // next free address on heap
} alloc_state_t;

void *cpen212_init(void *heap_start, void *heap_end) {
    alloc_state_t *s = (alloc_state_t *) malloc(sizeof(alloc_state_t));
    s->end = heap_end;
    s->free = heap_start;
    return s;
}

void cpen212_deinit(void *s) {
    free(s);
}

void *cpen212_alloc(void *alloc_state, size_t nbytes) {
    alloc_state_t *s = (alloc_state_t *) alloc_state;
    size_t aligned_sz = (nbytes + 7) & ~7;

    void* p = s->free;

    if ((p >= s->end) || (p + aligned_sz > s->end)) {
        void* temp = s->free;
        while(temp < s->end) {
            size_t check_hdr = (size_t)(temp); 
            if (check_hdr % 2 == 0){  //sanity check
                check_hdr = aligned_sz++;
                return (void*) check_hdr + 8;
            }
        temp++;
        }
        return NULL;
    }

    size_t hdr = (size_t)s->free;
    s->free += aligned_sz;
    hdr = aligned_sz++;
    return p + 8;
}

void cpen212_free(void *alloc_state, void *p) {
    alloc_state_t *s = (alloc_state_t *) alloc_state;

    void *prev = p - 8;
    void *next = p + *(size_t *)p;

    void* start = s->free;
    void* end = s->end;

    if (p == NULL) {
        return;
    }

    // previous
    if (prev >= start && *(size_t *)prev % 2 == 0) {
        *(size_t *)prev += *(size_t *)p;
        p = prev;
    }
    
    // next
    if (next + 8 < end && *(size_t *)next % 2 == 0) {
        *(size_t *)p += *(size_t *)next;
    }

    if (p + *(size_t *)p == s->end) {
        s->free = p;
    }

    *(size_t *)p = *(size_t *)p | 1;

}

void *cpen212_realloc(void *alloc_state, void *prev, size_t nbytes) {
    alloc_state_t *s = (alloc_state_t *) alloc_state;
    
    if(prev == NULL){
        return cpen212_alloc(s, nbytes);
    }

    if(nbytes == 0){
        cpen212_free(s, prev);
        return NULL;
    }
    
    void *p = cpen212_alloc(s, nbytes);
    if (p != NULL && ((size_t)p % 2 == 0) && (!(p >= s->end) && !(p + ((nbytes + 7) & ~7) > s->end)) ) {
        memmove(p, prev, nbytes);
        cpen212_free(s, prev);
    }

    return p;
}

// WARNING: we don't know the prev block's size, so memmove just copies nbytes here.
//          this is safe only because in this dumb allocator we know that prev < p,
//          and p has at least nbytes usable. in your implementation,
//          you probably need to use the original allocation size.

bool cpen212_check_consistency(void *alloc_state) {
    alloc_state_t *s = (alloc_state_t *) alloc_state;
    return s->end > s->free;
}