#include "fixed_alloc.h"
#include "object.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE+1];

void fixed_alloc_init()
{
	int i;
	for(i = 0; i < ((MAX_SIZE-MIN_SIZE)/STRIDE+1); ++i)
		max_free[i] = (BLOCK_SIZE - sizeof(mem_block)+1)*8/((i*STRIDE+MIN_SIZE)*8+1);
}

mem_manager * new_mem_manager()
{
	int i;
	mem_manager * ret = malloc(sizeof(mem_manager));
	memset(ret, 0, sizeof(mem_manager));
	return ret;
}

void print_mem_info(mem_manager * manager)
{
	int i,count,freeobjs;
	mem_block * cur;
	//printf("Free blocks: %d\n", manager->freecount);
	if (manager->fullcount)
		printf("Full Blocks: %d\n", manager->fullcount);
	for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++)
	{
		count = 0;
		freeobjs = 0;
		cur = manager->inuse[i];
		while(cur)
		{
			count++;
			freeobjs += ((int)cur->numfree);
			cur = cur->next;
		}
		if (freeobjs)
			printf("Bucket %d(size: %d) has %d blocks in use with %d free slots out of %d\n", i, i*STRIDE+MIN_SIZE,count, freeobjs, max_free[i]*count);
	}
	fflush(stdout);
}

void find_live_objects_oftype(mem_manager * manager, int32_t type_id, void ** output)
{
	object * obj;
	mem_block * cur;
	int32_t i,j,bitslots,bit,outpos=0;
	for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++)
	{
		cur = manager->inuse[i];
		while(cur)
		{
			bitslots = max_free[i]/8;
			if(max_free[i]&7)
				++bitslots;
			for(j = 0; j < bitslots; ++j)
				if(cur->bitmap[j] != 0xFF)
				{
					for (bit = 0; bit < 8; ++bit)
					{
						if (!(cur->bitmap[j] & (1 << bit)))
						{
							obj = (object *)(((char *)cur)+BLOCK_SIZE-(((j*8+bit)+1)*(i*STRIDE+MIN_SIZE)));
							if(obj->bprint->type_id == type_id)
								output[outpos++] = obj;
						}
					}
				}
			cur = cur->next;
		}
	}
}

void get_live_object_counts(mem_manager * manager, int32_t * counts)
{
	object * obj;
	mem_block * cur;
	int32_t i,j,bitslots,bit;
	memset(counts, 0, sizeof(int32_t)*max_registered_type);
	for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++)
	{
		cur = manager->inuse[i];
		while(cur)
		{
			bitslots = max_free[i]/8;
			if(max_free[i]&7)
				++bitslots;
			for(j = 0; j < bitslots; ++j)
				if(cur->bitmap[j] != 0xFF)
				{
					for (bit = 0; bit < 8; ++bit)
					{
						if (!(cur->bitmap[j] & (1 << bit)))
						{
							obj = (object *)(((char *)cur)+BLOCK_SIZE-(((j*8+bit)+1)*(i*STRIDE+MIN_SIZE)));
							counts[obj->bprint->type_id]++;
						}
					}
				}
			cur = cur->next;
		}
	}
}

void print_live_object_types(mem_manager * manager)
{
	int32_t i,*counts = malloc(sizeof(int32_t)*max_registered_type);
	get_live_object_counts(manager, counts);
	for (i = 0; i < max_registered_type; ++i)
		if(counts[i])
			printf("%d live objects of type %d\n", counts[i], i);
	fflush(stdout);
}

void * falloc(size_t size, mem_manager * manager)
{
	uint16_t i,bit;
	uint16_t bucket;
	mem_block * block,*temp;
	if(size > MAX_SIZE)
		return malloc(size);
	//puts("falloc");
	size = ADJUST_SIZE(size);
	bucket = (size-MIN_SIZE)/STRIDE;
	block = manager->inuse[bucket];
	if(!block)
	{
		block = manager->freelist;
		if(block)
		{
			--manager->freecount;
			manager->freelist = block->next;
			//memset(block, 0xCD, BLOCK_SIZE);
		}
		else
		{
			block = block_alloc(BLOCK_SIZE);
			//memset(block, 0xAB, BLOCK_SIZE);
		}
		manager->inuse[bucket] = block;
		block->next = NULL;
		block->last = NULL;
		block->numfree = max_free[bucket];
		block->firstfree = 0;
		memset(block->bitmap, 0xFF, max_free[bucket]/8+1);
	}
	//printf("block: %X,numfree: %d, firstfree: %d, maxfree: %d\n", block, block->numfree, block->firstfree, max_free[bucket]);
	/*if(block->numfree > max_free[bucket])
	{
		puts("uh oh!");
		exit(1);
	}*/
	//find first free 
	i = block->firstfree;
	while(!block->bitmap[i])
		++i;
	//printf("i:%d,bitmap:%X\n", i, block->bitmap[i]);
	bit = 0;
	while(!((1 << bit) & block->bitmap[i]))
		++bit;
	//update free bitmask
	block->bitmap[i] ^= 1 << bit;
	//If current bitmap has no more free elements, set firstfree to the next bitmap
	if(!block->bitmap[i])
		block->firstfree = i+1;
	else
		block->firstfree = i;
	--block->numfree;
	if(!block->numfree)
	{
		//Remove from linked list if there are no more free elements
		manager->inuse[bucket] = block->next;
		manager->fullcount++;
		if(block->next)
			block->next->last = block->last;
	}
	i = i*8+bit;
	return (void *)(((char *)block)+BLOCK_SIZE-((i+1)*size));
}

void ffree(void * ptr, size_t size, mem_manager * manager)
{
	mem_block * block,*temp;
	uint16_t i,bit,bucket;
	if(size > MAX_SIZE)
	{
		free(ptr);
		return;
	}
	//puts("ffree");
	size = ADJUST_SIZE(size);
	//memset(ptr, 0xEF, size);
	block = GET_BLOCK(ptr);
	i = (((((char *)block) + BLOCK_SIZE) - ((char *)ptr))/size)-1;
	bit = i & 0x7;
	i = (i&0xFFFFFFF8) >> 3;
	//printf("ptr:%X,block:%X,i:%d,bit:%d\n", ptr,block,bit,i);
	block->bitmap[i] |= 1 << bit;
	if(i < block->firstfree)
		block->firstfree = i;
	++block->numfree;
	bucket = (size-MIN_SIZE)/STRIDE;
	//printf("numfree:%d,max_free:%d,last:%X,next:%X\n", block->numfree, max_free[bucket], block->last, block->next);
	/*if(block->numfree > max_free[bucket])
	{
		puts("uh oh!");
		exit(1);
	}*/
	if(block->numfree == max_free[bucket])
	{
		//Block is now unused, remove it from the inuse list
		if(block->last)
			block->last->next = block->next;
		else
			manager->inuse[bucket] = block->next;
		if(block->next)
			block->next->last = block->last;
		if(manager->freecount == MAX_FREE)
		{
			block_free(block, BLOCK_SIZE);
		}
		else
		{
			block->next = manager->freelist;
			manager->freelist = block;
			++manager->freecount;
		}
	} else if(block->numfree == 1) {
		//Block was previously full, add it to the inuse list
		block->next = manager->inuse[bucket];
		block->last = NULL;
		manager->inuse[bucket] = block;
		manager->fullcount--;
		if(block->next)
			block->next->last = block;
	} else if(block->next && block->next->numfree < block->numfree) {
		//We want to use more filled blockes before less filled ones
		//so we can return empty ones to the OS more often
		//so if we now have more free nodes in this block than the 
		//next one swap them
		temp = block->next;
		block->next = temp->next;
		temp->last = block->last;
		block->last = temp;
		temp->next = block;
		if(block->next)
			block->next->last = block;
		if(temp->last)
			temp->last->next = temp;
		else
			manager->inuse[bucket] = temp;
	}
}