/*http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29*/
/*http://en.wikipedia.org/wiki/Free_list*/

#define NULE 0
#define MULE 8888

typedef struct NOiD_memory
{
	int id;
	int size;
	struct NOiD_memory * last;
	struct NOiD_memory * next;
} NOiD_memory;

typedef struct NOiD_yromem
{
	NOiD_memory * space;
	int id;
} NOiD_yromem;

/*after reading in wikipedia , i found similarity with Garbage Collection by John McCarthy*/
/*so i've invented nothing*/

NOiD_memory * NOiD_seg (void * noid_array, int noid_size)
{

	NOiD_memory * noid_header = (NOiD_memory*)noid_array;
	NOiD_memory * noid_new = (NOiD_memory*)(noid_array + sizeof(NOiD_memory));
	NOiD_yromem * noid_ender = (NOiD_yromem*)(noid_array + noid_size - sizeof(NOiD_yromem));
	noid_header->id = MULE;
	noid_header->size = noid_size;
	noid_header->last = noid_new;
	noid_header->next = noid_new;
	noid_new->id = MULE;
	noid_new->size = noid_size - sizeof(NOiD_memory);
	noid_new->last = noid_header;
	noid_new->next = noid_header;
	noid_ender->space = noid_header;
	noid_ender->id = MULE;
	return noid_header;
}

void * NOiD_alloc (NOiD_memory * noid_segment, int noid_size)
{
	if (noid_size < sizeof(NOiD_memory)+sizeof(NOiD_yromem))
	{
		noid_size = sizeof(NOiD_memory)+sizeof(NOiD_yromem);
	}
	NOiD_memory * noid_pivot = noid_segment->next;
	NOiD_memory * noid_enogh;
	while (noid_pivot != noid_segment)
	{
		if (noid_pivot->size - sizeof(NOiD_memory) > noid_size + sizeof(int))
		{
			noid_enogh = noid_pivot;
			noid_pivot = noid_segment->last;
		}
		noid_pivot = noid_pivot->next;
	}

	if (noid_enogh != 0)
	{
		NOiD_memory * noid_mov = (NOiD_memory*)((void*)noid_enogh + noid_size + sizeof(int));
		NOiD_yromem * noid_set = (NOiD_yromem*)((void*)noid_enogh + noid_enogh->size - sizeof(NOiD_yromem));
		void * noid_new = (void*) noid_enogh;

		noid_mov->id = noid_enogh->id;
		noid_mov->size = noid_enogh->size - noid_size - sizeof(int);
		noid_mov->last = noid_enogh->last;
		noid_mov->next = noid_enogh->next;
		noid_mov->last->next = noid_mov;
		noid_mov->next->last = noid_mov;

		noid_set->space = noid_mov;
		*(int*)noid_new = noid_size;
		noid_new = noid_new +sizeof(int);

		//debug debug debug debug debug debug
		*(int*)noid_new = 0;
		*(int*)(noid_new + sizeof(int)) = 0;
		*(int*)(noid_new + (sizeof(int) * 2)) = 0;
		//debug debug debug debug debug debug

		return noid_new;
	}
	return NULE;
}

void NOiD_free (NOiD_memory * noid_segment, void * noid_offset)
{
	int noid_size = *(int*)(noid_offset - sizeof(int));
	NOiD_memory * noid_new = (NOiD_memory*) (noid_offset - sizeof(int));
	NOiD_yromem * noid_end = (NOiD_yromem*) (noid_offset + noid_size - sizeof(NOiD_yromem));
	noid_new->id = MULE;
	noid_new->size = noid_size + sizeof(int);
	noid_new->last = noid_segment;
	noid_new->next = noid_segment->next;
	noid_new->last->next = noid_new;
	noid_new->next->last = noid_new;
	noid_end->id = MULE;
	noid_end->space = noid_new;
	if ((*(int*)(noid_offset + noid_size)) == MULE )
	{

		NOiD_memory * noid_forward = (NOiD_memory*)(noid_offset + noid_size);
		NOiD_yromem * noid_foreend = (NOiD_yromem*)((void*)noid_forward + noid_forward->size - sizeof(NOiD_yromem));
		noid_new->size = noid_new->size + noid_forward->size;
		noid_forward->next->last = noid_forward->last;
		noid_forward->last->next = noid_forward->next;
		noid_foreend->space = noid_new;
		//debug
		noid_end->id = 0;
		noid_end->space = 0;
		noid_forward->id = 0;
		noid_forward->size = 0;
		noid_forward->last = 0;
		noid_forward->next = 0;
		//debug
		noid_end = noid_foreend;
	}
	if ((*(int*)(noid_offset - (sizeof(int)*2))) == MULE )
	{
		NOiD_yromem * noid_backend = (NOiD_yromem*)(noid_offset - (sizeof(int)*2) - sizeof(void*));
		NOiD_memory * noid_bacward = noid_backend->space;

		noid_bacward->size = noid_bacward->size + noid_new->size;
		noid_new->next->last = noid_new->last;
		noid_new->last->next = noid_new->next;
		noid_end->space = noid_bacward;
		//debug
		noid_backend->id = 0;
		noid_backend->space = 0;
		noid_new->id = 0;
		noid_new->size = 0;
		noid_new->last = 0;
		noid_new->next = 0;
		//debug
		noid_new = noid_bacward;
	}
}

//================================================================================
//================================================================================
//================================================================================

/*http://en.wikipedia.org/wiki/Linked_list*/


typedef struct NOiD_node
{
	void * pack;
	struct NOiD_node * last;
	struct NOiD_node * next;
} NOiD_node;

NOiD_node * NOiD_create (NOiD_node * noid_src, void * noid_pack, void * noid_ptr)
{
	if (noid_ptr == 0)
	{	return 0;	}

	NOiD_node * noid_nud = (NOiD_node*) noid_ptr;
	noid_nud->pack = noid_pack;

	if (noid_src != 0)
	{
		noid_nud->last = noid_src;
		noid_nud->next = noid_src->next;
		noid_nud->last->next = noid_nud;
		noid_nud->next->last = noid_nud;
	}
	else
	{
		noid_nud->last = noid_nud;
		noid_nud->next = noid_nud;
	}

	return noid_nud;
}

void * NOiD_destroy (NOiD_node * noid_src, NOiD_node * noid_nud)
{
	if ((noid_src == 0)||(noid_nud == 0))
	{	return;		}

	if (noid_src == noid_nud)
	{
		//you shouldnt destroy sentinel if array is not empty
			if (noid_src != noid_src->next)
			{
				return;
			}
	}

	noid_nud->last->next = noid_nud->next;
	noid_nud->next->last = noid_nud->last;

	noid_nud->pack = 0;
	noid_nud->last = 0;
	noid_nud->next = 0;

	return (void*) noid_nud;	//return ptr in case of alloc/free
}

void * NOiD_loop (NOiD_node * noid_src)
/* all node will move around noid_src */
/* so its sure that youll get them all */
{
	NOiD_node * noid_nud = noid_src->next;

	noid_src->last->next = noid_src->next;
	noid_src->next->last = noid_src->last;

	noid_nud->next->last = noid_src;
	noid_src->next = noid_nud->next;

	noid_nud->next = noid_src;
	noid_src->last = noid_nud;


	return noid_nud->pack;
}


//================================================================================
//================================================================================
//================================================================================



typedef struct NOiD_agenda
{
	signed long int wait;		//interval between call
	void (*func)(void);		//function to call
	signed long int till;		//wait till to execute
	signed long int idle;		//time left before execute
	signed long int loop;		//value that end loop
	NOiD_node * node;		//the node that list it
} NOiD_agenda;


NOiD_node * NOiD_schedule (NOiD_node * noid_sentinel, void (*noid_func)(void), signed long int noid_wait ,void * noid_ptr)
{
	NOiD_agenda * noid_now = (NOiD_agenda*) noid_ptr;
	NOiD_node * noid_node_now = NOiD_create(noid_sentinel,noid_now,noid_ptr + sizeof(NOiD_agenda));
	noid_now->node = noid_node_now;
	noid_now->func = noid_func;
	noid_now->wait = noid_wait;

	return noid_node_now;
}

void * NOiD_cancel (NOiD_node * noid_node_today, NOiD_node * noid_node_now)
{
	NOiD_agenda * noid_now = noid_node_now->pack;
	noid_now->wait = 0;
	noid_now->func = 0;
	noid_now->idle = 0;
	noid_now->till = 0;
	noid_now->loop = 0;
	noid_now->node = 0;
	noid_node_now = NOiD_destroy (noid_node_today, noid_node_now);
	return ((void*)noid_now);
}

signed long int NOiD_do (NOiD_node * noid_sentinel, signed long int noid_time)
{
		NOiD_agenda * noid_today = (NOiD_agenda*)noid_sentinel->pack;
		NOiD_agenda * noid_now;
		noid_today->loop += 1;
		noid_today->idle = noid_today->wait;
		int noid_yet = 0;
		while (noid_yet != 1)
		{

			noid_now = NOiD_loop(noid_sentinel);
			if (noid_now->loop == noid_today->loop)
			{
				noid_yet = 1;
			}
			

			if (noid_now->till == 0)
			{
				noid_now->till = noid_time + noid_now->wait;
			}
			if (noid_now->till <= noid_time)
			{
				noid_now->till = noid_time + noid_now->wait;
				noid_now->idle = 0;
				noid_now->func();
				noid_yet = 1;
			}
			else
			{
				noid_now->idle = noid_now->till - noid_time;
				noid_now->loop = noid_today->loop;
			}
			if (noid_now->idle < noid_today->idle)
			{
				noid_today->idle = noid_now->idle;
			}
		}
	return noid_today->idle;
}