#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

struct boundary_tag {
	unsigned int magic;	   
	unsigned int size; 	   
	unsigned int real_size;
	int index;

	struct boundary_tag *split_left;
	struct boundary_tag *split_right;
	
	struct boundary_tag *next;
	struct boundary_tag *prev;
};

#define ALLOC_MAGIC     0xc001c0de
#define MAXCOMPLETE     5
#define MAXEXP          32
#define MINEXP          8    

#define MODE_BEST       0
#define MODE_INSTANT    1

#define MODE    MODE_BEST

struct boundary_tag *l_freePages[MAXEXP];
int                  l_completePages[MAXEXP];

static int l_initialized = 0;
static int l_pageSize  = 4096;
static int l_pageCount = 16;

static inline int getexp(unsigned int size) {
    if (size < (1<<MINEXP)) {
        return -1;
    }
        
    int shift = MINEXP;

    while (shift < MAXEXP) {
        if ((unsigned)(1<<shift) > size) break;
        shift += 1;
    }

    return shift - 1;    
}

static inline void insert_tag(struct boundary_tag *tag, int index) {
    int realIndex;
    
    if (index < 0)  {
        realIndex = getexp(tag->real_size - sizeof(struct boundary_tag));
        if (realIndex < MINEXP) realIndex = MINEXP;
    } else {
        realIndex = index;
    }
    
    tag->index = realIndex;
    
    if (l_freePages[ realIndex ] != NULL) {
        l_freePages[ realIndex ]->prev = tag;
        tag->next = l_freePages[ realIndex ];
    }

    l_freePages[ realIndex ] = tag;
}

static inline void remove_tag(struct boundary_tag *tag) {
    if (l_freePages[ tag->index ] == tag) l_freePages[ tag->index ] = tag->next;

    if (tag->prev != NULL) tag->prev->next = tag->next;
    if (tag->next != NULL) tag->next->prev = tag->prev;

    tag->next = NULL;
    tag->prev = NULL;
    tag->index = -1;
}

static inline struct boundary_tag *melt_left(struct boundary_tag *tag) {
    struct boundary_tag *left = tag->split_left;
                            
    left->real_size   += tag->real_size;
    left->split_right  = tag->split_right;
    
    if (tag->split_right != NULL) tag->split_right->split_left = left;

    return left;
}


static inline struct boundary_tag *absorb_right(struct boundary_tag *tag) {
    struct boundary_tag *right = tag->split_right;

    remove_tag(right);
    
    tag->real_size += right->real_size;
    
    tag->split_right  = right->split_right;
    if (right->split_right != NULL)
                right->split_right->split_left = tag;

    return tag;
}

static inline struct boundary_tag *split_tag(struct boundary_tag *tag) {
    unsigned int remainder = tag->real_size - sizeof(struct boundary_tag) - tag->size;

    struct boundary_tag *new_tag = 
        (struct boundary_tag*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag) + tag->size);    
    
    new_tag->magic = ALLOC_MAGIC;
    new_tag->real_size = remainder;    

    new_tag->next = NULL;
    new_tag->prev = NULL;
    
    new_tag->split_left = tag;
    new_tag->split_right = tag->split_right;
    
    if (new_tag->split_right != NULL) new_tag->split_right->split_left = new_tag;
    tag->split_right = new_tag;
    
    tag->real_size -= new_tag->real_size;
    
    insert_tag(new_tag, -1);
    
    return new_tag;
}

static struct boundary_tag *allocate_new_tag(unsigned int size) {
    unsigned int pages;
    unsigned int usage;
    struct boundary_tag *tag;

    usage  = size + sizeof(struct boundary_tag);

    pages = usage / l_pageSize;
    if ((usage % l_pageSize) != 0) pages += 1;

    if (pages < (unsigned) l_pageCount) pages = l_pageCount;

    tag = (struct boundary_tag*)memory_alloc_page(pages);

    if (tag == NULL) return NULL;
    
    tag->magic         = ALLOC_MAGIC;
    tag->size         = size;
    tag->real_size     = pages * l_pageSize;
    tag->index         = -1;

    tag->next        = NULL;
    tag->prev        = NULL;
    tag->split_left     = NULL;
    tag->split_right     = NULL;

    return tag;
}



void *malloc(size_t size) {
    int index;
    void *ptr;
    struct boundary_tag *tag = NULL;

    memory_lock();

    if (l_initialized == 0) {
        for (index = 0; index < MAXEXP; index++) {
            l_freePages[index] = NULL;
            l_completePages[index] = 0;
        }
        l_initialized = 1;
    }

    index = getexp(size) + MODE;
    if (index < MINEXP) index = MINEXP;
    
    tag = l_freePages[index];
    while (tag != NULL) {
        if (
            (tag->real_size - sizeof(struct boundary_tag)) 
            >= (size + sizeof(struct boundary_tag))
       ) {
            break;
        }
        tag = tag->next;
    }
    
    if (tag == NULL) {    
        if ((tag = allocate_new_tag(size)) == NULL) {
            memory_unlock();
            return NULL;
        }
        index = getexp(tag->real_size - sizeof(struct boundary_tag));
    } else {
        remove_tag(tag);

        if ((tag->split_left == NULL) && (tag->split_right == NULL))
            l_completePages[ index ] -= 1;
    }
    
    tag->size = size;

    unsigned int remainder = tag->real_size - size - sizeof(struct boundary_tag) * 2;

    if (((int)(remainder) > 0)) {
        int childIndex = getexp(remainder);

        if (childIndex >= 0) {
            struct boundary_tag *new_tag = split_tag(tag); 
            tag = new_tag;
        }
    }

    ptr = (void*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag));
    memory_unlock();
    return ptr;
}

void free(void *ptr) {
    int index;
    struct boundary_tag *tag;

    if (ptr == NULL) return;

    memory_lock();
    
    tag = (struct boundary_tag*)((uintptr_t)(void *)ptr - sizeof(struct boundary_tag));
    
    if (tag->magic != ALLOC_MAGIC) {
        memory_unlock();
        return;
    }

    while ((tag->split_left != NULL) && (tag->split_left->index >= 0)) {
        tag = melt_left(tag);
        remove_tag(tag);
    }

    while ((tag->split_right != NULL) && (tag->split_right->index >= 0)) {
        tag = absorb_right(tag);
    }

    index = getexp(tag->real_size - sizeof(struct boundary_tag));
    if (index < MINEXP) index = MINEXP;
    
    if ((tag->split_left == NULL) && (tag->split_right == NULL)) {
        if (l_completePages[index] == MAXCOMPLETE) {
            unsigned int pages = tag->real_size / l_pageSize;

            if ((tag->real_size % l_pageSize) != 0) pages += 1;
            if (pages < (unsigned) l_pageCount) pages = l_pageCount;

            memory_free_page(tag, pages);
            memory_unlock();
            return;
        }

        l_completePages[ index ] += 1;
    }

    insert_tag(tag, index);

    memory_unlock();
}

void *calloc(size_t nobj, size_t size) {
    int real_size;
    void *p;

    real_size = nobj * size;
       
    p = malloc(real_size);

    memset(p, 0, real_size);

    return p;
}

void *realloc(void *p, size_t size) {
    void *ptr;
    struct boundary_tag *tag;
    size_t real_size;
    
    if (size == 0) {
        free(p);
        return NULL;
    }

    if (p == NULL) {
        return malloc(size);
    }

    memory_lock();
    tag = (struct boundary_tag*)((uintptr_t)(void *)p - sizeof(struct boundary_tag));
    real_size = tag->size;
    memory_unlock();

    if (real_size > size) real_size = size;

    ptr = malloc(size);
    memcpy(ptr, p, real_size);
    free(p);

    return ptr;
}