#include "malloc.h"

#include "../sys/brk.h"

/** DOC
 * @type typename
 * @name segment_t
 *
 * @member void      *ptr
 * @member u64       size
 * @member u8        free
 * @member segment_t *next
 *
 * @description
 * A segment is a meta block for an allocated area.
 * It contains the pointer `(void *ptr)` for the memory location
 * its size and if its free `(u8 free)`. 
 * The segment_t is a single linked list node because of that
 * it also holds a `(segment_t *next)` pointer to the next segment.
 */
typedef struct __segment_t {
	void                *ptr;
	u64                 size;
	u8                  free;
	struct __segment_t  *next;
} segment_t;


/** DOC
 * @type instance
 * @name mbrk
 *
 * @member u64       initial
 * @member u64       current
 * @member segment_t *first
 * @member segment_t *last
 *
 * @description
 * The mbrk instance holds the current brk `(see [man 2 brk])`
 * and the first and last element of the segement list.
 */
struct __break {
	u64        initial;
	u64        current;
	segment_t  *first;
	segment_t  *last;
} mbrk = {
	.initial = 0,
	.current = 0,
	.first = 0,
	.last = 0
};


void  __initialize_memory();
segment_t *__find_free_segment(u64 size);
segment_t *__allocate_new(u64 size);


/** DOC
 * @type function
 * @name malloc
 *
 * @param  u64 size
 * @return void*
 *
 * @description
 * Allocates memory. If there is no space left requests new space.
 */
void* malloc(u64 size)
{
	segment_t *seg;

	if (!mbrk.initial)
		__initialize_memory();
	
	seg = __find_free_segment(size);

	if (!seg)
		seg = __allocate_new(size);

	seg->free = 0;
	return seg->ptr;
}


/** DOC
 * @type function
 * @name free
 *
 * @param  void *ptr
 * @return void
 *
 * @description
 * Frees the memory allocated by `malloc`.
 *
 * ``IMPORTANT`` this function does not free the memory to be accessible
 * for the whole system. The freed memory is only accessible for the current
 * process and is released on exit.
 */
void free(void *ptr)
{
	segment_t * seg = mbrk.first;

	for (; seg; seg = seg->next) {
		if (ptr == seg->ptr) {
			seg->free = 1;
			break;
		}
	}
}


/** DOC
 * @type function
 * @name __initialize_memory
 *
 * @description
 * Initalizes `mbrk` by calling `brk(0)`.
 * Is only called if `mbrk.initial` is zero.
 */
void __initialize_memory()
{
	mbrk.initial = brk(0);
	mbrk.current = mbrk.initial;
}


/** DOC
 * @type function
 * @name __find_free_segment
 *
 * @param  u64 size
 * @return segment_t*
 *
 * @description
 * Searches a segment with the given `size` in
 * the segment linked-list.
 * If there is no such segment it returns `0`
 */
segment_t *__find_free_segment(u64 size)
{
	segment_t * seg = mbrk.first;

	for (; seg; seg = seg->next) {
		if (seg->free && size == seg->size)
			return seg;
	}

	return 0;
}

/** DOC
 * @type function
 * @name __allocate_new
 *
 * @param  u64 size
 * @return segment_t*
 *
 * @description
 * Allocates a new segement.
 * This function is only called if no free segment with
 * the given `size` was found. A new segment is allocated
 * by using the `brk` syscall and adding `size + sizeof(segment_t)`
 * new memory to the process.
 */
segment_t *__allocate_new(u64 size)
{
	u64 last = mbrk.current;
	mbrk.current += size + sizeof(segment_t);
	brk((void*)mbrk.current);

	segment_t *seg = (segment_t*)last;
	seg->ptr = (void*)(mbrk.current - size);
	seg->size = size;
	seg->free = 0;
	seg->next = 0;

	if (!mbrk.first)
		mbrk.first = seg;
	else
		mbrk.last->next = seg;
	
	mbrk.last = seg;

	return seg;
}