//////////////////////////////////////////////////////////////////////
//mm.h////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
#ifndef _MM_H_
#define _MM_H_

#define HNODE_USED 1
#define HNODE_UNUSED 0

typedef struct _hnode
{
	u64 address;
	u32 used;
	u32 size;
	struct _hnode *prev;
	struct _hnode *next;
} __attribute__((packed)) hnode_t;

typedef struct _heap
{
	u64 start;
	u64 size;
	u32 usedmem;
	hnode_t *first;
} __attribute__((packed)) heap_t;

//Initialize rsx heap.
s32 rsxHeapInit();
//Allocate from rsx heap.
void *rsxAlloc(u32 size);
//Free allocated rsx memory.
void rsxFree(void *ptr)

#endif

//////////////////////////////////////////////////////////////////////
//mm.c////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
#include <malloc.h>

#include "rsx/reality.h"
#include "mm.h"

static u32 initialized = 0;
static gcmConfiguration config;
static u64 rsx_heap_ptr;
static heap_t *rsx_heap;

//Collect unused nodes and merge them to bigger ones.
static void _rsxHeapCollect()
{
	hnode_t *node = rsx_heap->first;

	//Iterate over all nodes.
	while(node != NULL)
	{
		//If we find an unused node ...
		if(node->used == HNODE_UNUSED)
			//... and if the previous node is also unused ...
			if(node->prev != NULL && node->prev->used == HNODE_UNUSED)
			{
				//... merge them.
				node->prev->size += node->size;
				node->prev->next = node->next;
				if(node->next != NULL)
					node->next->prev = node->prev;
				//Free node.
				free(node);
			}
		node = node->next;
	}
}

s32 rsxHeapInit()
{
	if(initialized == 0)
	{
		//Get config.
		gcmGetConfiguration(&config);
		//Setup heap.
		rsx_heap_ptr = (u64)config.localAddress;
		//Allocate base heap.
		if((rsx_heap = (heap_t *)malloc(sizeof(heap_t))) == NULL)
			return 0;
		//Start address and size.
		rsx_heap->start = rsx_heap_ptr;
		rsx_heap->size = config.localSize;
		//No memory used.
		rsx_heap->usedmem = 0;
		rsx_heap->first = NULL;
		//And done.
		initialized = 1;
	}

	return 1;
}

void *rsxAlloc(u32 size, u32 align)
{
	hnode_t *node, *new;
	u32 search = 1;

	if(initialized == 0)
		return NULL;

	//First node?
	if(rsx_heap->first == NULL)
	{
		if(size > heap->size)
			return NULL;
		//Allocate new node.
		if((node = (hnode_t *)malloc(sizeof(hnode_t))) == NULL)
			return NULL;

		node->address = rsx_heap->start;
		node->used = HNODE_USED;
		node->size = size;
		node->prev = NULL;
		node->next = NULL;
		rsx_heap->first = node;
		rsx_heap->usedmem = size;

		return (void *)node->address;
	}

	node = rsx_heap->first;
	while(search == 1)
	{
		//unused node?
		if(node->used == HNODE_UNUSED)
		{
			//20% bigger is acceptable.
			if(size <= node->size && node->size <= (size + node->size / 5))
			{
				node->used = HNODE_USED;
				rsx_heap->usedmem += node->size;
				return (void *)node->address;
			}
			else if(size < node->size) //Insert new node.
			{
				//Allocate new node.
				if((new = (hnode_t *)malloc(sizeof(hnode_t))) == NULL)
					return NULL;

				//The new node follwes the ucrrent one.
				new->size = node->size - size;
				new->used = HNODE_UNUSED;
				new->address = node->address + size;
				//Insert into list.
				new->next = node->next;
				new->priv = node;
				node->size = size;
				node->used = HNODE_UNSED;
				//The next one is the new node.
				node->next = new;

				rsx_heap->usemem += size;
				return (void *)node->address;
			}
		}
		if(node->next != NULL)
			node = node->next;
		else
			search = 0;
	}

	//Add new node at the end.
	//Enough memory available to create a new node?
	if(heap->usedmem + size > heap->size)
		return NULL;
	//Allocate new node.
	if((new = (hnode_t *)malloc(sizeof(hnode_t))) == NULL)
		return NULL;

	new->used = HNODE_USED;
	new->size = size;
	new->address = node->address + node->size;
	new->prev = node;
	new->next = NULL;
	node->next = new;

	rsx_heap->usedmem += size;
	return (void *)new->address;
}

void rsxFree(void *ptr)
{
	u64 addr = (u64)ptr;

	//Some basic error checking.
	if(initialized == 0)
		return;
	if(addr == 0 ||
		addr < (heap->start) ||
		addr > (heap->start + heap->size)
	)
		return;

	hnode_t *node = rsx_heap->first;

	//Find the correspondending node.
	while(node != NULL)
	{
		if(node->address == addr)
		{
			//Set it to unused.
			node->used = HNODE_UNUSED;
			//Update allocated size.
			rsx_heap->size -= node->size;
			return;
		}
		node = node->next;
	}

	//Collect nodes.
	_rsxHeapCollect();
}