#include <inttypes.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define K		  (29)
#define ALIGN	  (8)
#define N 		  (536870912) //2^K
#define MIN_ALLOC (32)
#define MIN_K	  (5) //2^5 = 32

const int K_EQUVALENT[K] = {2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,
							 16384,32768,65536,131072,262144,524288,1048576,
							 2097152, 4194304, 8388608, 16777216, 33554432,
							 67108864, 134217728, 268435456, 536870912};

typedef struct list_t	list_t;

struct list_t {
	unsigned int reserved;	/* one if reserved. */
	char		 kval;		/* current value of K. */
	list_t* 	 succ;		/* successor block in list. */
	list_t*	 	 pred;		/* predecessor block in list. */
};

static char pool[N]; // data pool
static list_t freelist[K];
static bool first = 1;
const void* START_ADDR = (void *)&pool;

static void init()
{
	int i;
	for (i = 0; i < K-1; ++i) {
		freelist[i].succ = NULL;
	}
	list_t* tmp = (list_t*) pool;
	tmp->succ = NULL;
	tmp->pred = &freelist[K-1];
	tmp->kval = K-1;
	tmp->reserved = 0;
	freelist[K-1].succ = tmp;
}

void* malloc(size_t size)
{
	size += sizeof(list_t);
	if(size == 0 || size > N/2)
		return NULL;

	if(first) {
		first = 0;
		init();
	}

	// Increase size to be the smallest power of two: size = 2^K
	int i;
	int pow = MIN_ALLOC;
	for(i = MIN_K; i < K; i++)
	{
		if( pow >= size)
			break;
		pow = pow*2;
	}
	size = pow;

	// Find the first list J with an available block; J >= K
	int block = -1;
	int j;
	for(j = i-1; j < K; j++)
	{
		if (freelist[j].succ != NULL) {
			block = j;
			break;
		}
	}

	// If no such J exists, then return NULL.
	if(block == -1) {
		printf("out of memory\n");
		fflush(stdout);
		return NULL;
	}

	// remove/fetch first item in freelist
	list_t *mem, *tmp;
	mem = freelist[j].succ;
	freelist[j].succ = mem->succ;
	if(mem->succ != NULL)
		mem->succ->pred = &freelist[j];
	if (block != i-1) {
		while (block != i-1) {
			// split mem in two equal parts and insert the one to
			// the right in freelist[block-1]
			block--;
			tmp = (list_t*)((char*)mem + K_EQUVALENT[block]);
			tmp->succ = freelist[block].succ;
			tmp->pred = &freelist[block];
			tmp->kval = block;
			tmp->reserved = 0;
			freelist[block].succ = tmp;
			if(tmp->succ != NULL)
				tmp->succ->pred = tmp;
		}
		mem->kval = i-1;
	}
	mem->reserved = 1;
	return (void*)((char*)mem + sizeof(list_t));
}

void* calloc(size_t n, size_t size)
{
	void*	p;
	p = malloc(n * size);
	memset(p, 0, n * size);

	return p;
}

void free(void* ptr)
{
	if(ptr == NULL)
		return;
	list_t* mem = (list_t*)((char*)ptr - sizeof(list_t));
	while(mem->kval < K-1){
		list_t* tmp = (list_t*)(START_ADDR +
					  (((void*)mem - START_ADDR) ^ (1 << mem->kval+1)));
		if (tmp > mem && tmp->kval == mem->kval && !tmp->reserved) {
			mem->kval++;
			tmp->pred->succ = tmp->succ;
			if(tmp->succ != NULL)
				tmp->succ->pred = tmp->pred;
		} else if (tmp->kval == mem->kval && !tmp->reserved) {
			tmp->kval++;
			mem = tmp;
			tmp = mem->pred;
			tmp->succ = mem->succ;
			if(tmp->succ != NULL)
				tmp->succ->pred = tmp;
		} else
			break;
	}
	mem->succ = freelist[mem->kval].succ;
	mem->pred = &freelist[mem->kval];
	freelist[mem->kval].succ = mem;
	if(mem->succ != NULL)
		mem->succ->pred = mem;
	mem->reserved = 0;
}

void* realloc(void* ptr, size_t size)
{
	if(ptr == NULL)
		return;
	list_t* mem = (list_t*)((char*)ptr - sizeof(list_t));
	if(mem == NULL)
		return;
	void* new_mem = malloc(size);
	if(size < K_EQUVALENT[mem->kval] - sizeof(list_t) )
		memcpy(new_mem, ptr, size);
	else
		memcpy(new_mem, ptr, K_EQUVALENT[mem->kval] - sizeof(list_t));
	free(ptr);
	return new_mem;
}

void malloc_stats()
{

}