#include <string.h>
#include <stdlib.h>
#include <sys/mman.h>

#include "config.h"

struct heap_node
{
	size_t size;
	union
	{
		struct
		{
			struct heap_node *prev;
			struct heap_node *next;
		};
		struct
		{
			char block;
		};
	};
};

struct heap_head
{
	size_t allocated_size;
	size_t maximum_size;
	size_t minimum_alloc;
	struct heap_node *root;
};

struct heap_head *heap;

void *allocate_superblock(void)
{
	return mmap(nullptr, HEAP_SEGMENT_SIZE, 0, 0, -1, 0);
}

static struct heap_node *try_create_heap()
{
	if (heap != nullptr) return heap->root;

	char *superblock = allocate_superblock();

	heap = (struct heap_head *)superblock;
	heap->root = (struct heap_node *)(superblock + sizeof(struct heap_head));

	heap->allocated_size = HEAP_SEGMENT_SIZE;
	heap->maximum_size = HEAP_MAX_SIZE;
	heap->minimum_alloc = sizeof(heap->root);

	heap->root->next = nullptr;
	heap->root->prev = nullptr;
	heap->root->size = HEAP_SEGMENT_SIZE - sizeof(superblock) - sizeof(heap->root->size);

	return heap->root;
}

static struct heap_node *try_grow_heap(struct heap_node *prev)
{
	if (heap->allocated_size >= heap->maximum_size)
	{
		return nullptr;
	}

	struct heap_node *node = allocate_superblock();

	if (node == nullptr)
	{
		return nullptr;
	}

	node->size = HEAP_SEGMENT_SIZE - sizeof(node->size);
	node->prev = prev;
	prev->next = node;

	return node;
}

static inline size_t get_node_size(size_t size)
{
	return size + sizeof(size);
}

static inline bool can_divide_node(struct heap_node *parent)
{
	return parent->size <= heap->minimum_alloc + sizeof(struct heap_node);
}

static inline void *new_node_address(struct heap_node *parent, size_t size)
{
	return &parent->block + parent->size - get_node_size(size);
}

static inline struct heap_node *divide_node(struct heap_node *parent, size_t size)
{
	struct heap_node *child = new_node_address(parent, size);

	parent->size -= get_node_size(size);
	child->size = size;

	return child;
}

static inline struct heap_node *try_divide_node(struct heap_node *node, size_t size)
{
	return can_divide_node(node) ? divide_node(node, size) : node;
}

static inline struct heap_node *allocate_node(size_t size)
{
	struct heap_node *node = try_create_heap();

	while(node != nullptr)
	{
		if (node->size > size)
		{
			break;
		}

		node = node->next
			? node->next
			: try_grow_heap(node);
	}

	return node;
}

void *malloc(size_t size)
{
	// TODO: min(heap->minimum_alloc, size);
	size = size >= heap->minimum_alloc 
		? size 
		: heap->minimum_alloc;

	struct heap_node *node = try_divide_node(allocate_node(size), size);

	return node != nullptr
		? &node->block
		: nullptr;
}

void *calloc(size_t count, size_t size)
{
	void *block = malloc(count * size);

	if (block != nullptr)
	{
		memset(block, 0, count * size);
	}

	return block;
}

static inline struct heap_node *block_to_node(char *block)
{
	return (struct heap_node *)(block - sizeof(size_t));
}

void free(void *block)
{
	// TODO: insertion sort by address of node
	// TODO: coalesce adjacent nodes
	if (block == nullptr)
	{
		return;
	}

	struct heap_node *node = block_to_node(block);
	node->prev = nullptr;
	node->next = heap->root;
	heap->root = node;
	
	if (node->next != nullptr)
	{
		node->next->prev = node;
	}
}