#include "my_malloc.h"

/* You *MUST* use this macro when calling my_sbrk to allocate the
 * appropriate size. Failure to do so may result in an incorrect
 * grading!
 */
#define SBRK_SIZE 2048

/* If you want to use debugging printouts, it is HIGHLY recommended
 * to use this macro or something similar. If you produce output from
 * your code in your malloc library, then you will receive a grade
 * deduction. You have been warned!
 */
#ifdef DEBUG
#define DEBUG_PRINT(x) printf x
#else
#define DEBUG_PRINT(x)
#endif
static int firstTime = 1;
static metadata_t* offset = 0;
void split(metadata_t* block, int index);
int find_index(size_t);
void freeHelper(int index, metadata_t* ptr);
metadata_t* find_buddy(int temp, metadata_t* ptr);

int freelist_remove(metadata_t *block, int index );
/* Make sure this always points to the beginning of your current
 * heap space! If it does not, then the grader will not be able
 * to run correctly and you will probably get a 0. Remember that
 * only the _first_ call to my_malloc() returns the beginning of
 * the heap. Sequential calls will return a pointer to the newly
 * added space!
 * Technically this should be declared static because we do not
 * want any program outside of this file to be able to access it.
 * However, DO NOT CHANGE the way this variable is declared or
 * it will break the autograder.
 */
void* heap;

/* Our freelist structure. This is where the current freelist of
 * blocks will be maintained. Failure to maintain the list inside
 * of this structure will result in no credit, as the grader will
 * expect it to be maintained here.
 * Technically this should be declared static for the same reasons
 * as above, but DO NOT CHANGE the way this structure is declared
 * or it will break the autograder.
 */
metadata_t* freelist[8];
/* SIZES FOR THE FREE LIST:
 *   freelist[0] -> 16
 *   freelist[1] -> 32
 *   freelist[2] -> 64
 *   freelist[3] -> 128
 *   freelist[4] -> 256
 *   freelist[5] -> 512
 *   freelist[6] -> 1024
 *   freelist[7] -> 2048
 */

void* my_malloc(size_t size)
{
	int int_size = (int)size;
	size_t effective_size = int_size + sizeof(metadata_t);    //effective size = size requested plus metadata
	if(effective_size >2048)
	{
		ERRNO = SINGLE_REQUEST_TOO_LARGE;
		return NULL;
	}
	if(int_size < 0)
		return NULL;
	int index = find_index(effective_size);
	metadata_t* retBlock = NULL;
	if(freelist[index] !=NULL)				//if bock is present in freeListIndex
	{
		retBlock = freelist[index];
		freelist_remove(retBlock, index);
		retBlock->in_use = 1;
		char *address = (char*)retBlock;
		for(int i = 0; i< sizeof(metadata_t); i++)   //we want to point to address right after metadata
		{
			address++;
		}
		retBlock = (metadata_t*)(address);
		return retBlock;
	}
	else				//if block is not present in the index
	{
		metadata_t* splitBlock = NULL;
		int splitIndex = 0;
		for(int i = 8; i> index; i--)    	// look for block just above index. This is the block we want to split
		{
			if(freelist[i] != NULL)
			{
				splitBlock = freelist[i];
				splitIndex = i;
			}
		}

		if(splitBlock == NULL) 					//no block available to split
		{
			freelist[7] = my_sbrk(SBRK_SIZE);	//give size 2048 to freeList[7]
			if(firstTime)						// if this is happening the first time, initialize heap and point it to freeList[7] which now had size 2048
			{
				offset = freelist[7];
				heap = freelist[7];
				firstTime = 0;
			}

			if(freelist[7] == NULL)
			{
				ERRNO = OUT_OF_MEMORY;	 //all memory has been used up, we can't do anything
				return NULL;
			}
			else						//not the first time, so a block was made and has been completely used up. New block was made and now, set pointers right.
			{
				freelist[7] ->size = 2048;
				freelist[7] ->prev = NULL;
				freelist[7] ->next = NULL;
				freelist[7] ->in_use = 0;

			}
		}
		else					//found a block of memory somewhere up
		{
			split(splitBlock, splitIndex);
		}

		retBlock = my_malloc(size);
	}

	ERRNO = NO_ERROR;
	return retBlock;


}

void split(metadata_t* block, int index)
{
	int size = block ->size;					//size of the block to be split
	char* splitAddress = (char*)block;			//split address to updated in the next step
	for(int i=0; i<size/2; i++)
	{
		splitAddress++;							//find new splitAddress
	}

	metadata_t *temp1 = block;					//first block
	metadata_t *temp2 = (metadata_t*)(splitAddress);		//second block
	freelist[index] = block->next;				//remove block
	if(block->next !=NULL)
		block->next->prev = NULL;				//set pointers right

	temp1->next = temp2;						//set all ponters correctly
	temp1->prev = NULL;
	temp2->next = NULL;
	temp2->prev = temp1;
	temp1->in_use = 0;
	temp2->in_use = 0;
	temp1->size = size/2;
	temp2->size = size/2;

	freelist[index-1] = temp1;					//put them in an index lower.



}
int find_index(size_t effective_size)
{
	size_t minSize = 16;
	int index = 7;
	size_t current_size = 2048;
	int flag = 1;
	while(index >0 && flag)
	{
		if(effective_size<=current_size && effective_size> current_size/2)
			flag =0;
		else if(effective_size<minSize)
		{
			index = 0;
			flag = 0;
		}
		else
		{
			current_size = current_size/2;
			index--;
		}

	}
	return index;
}


int freelist_remove(metadata_t* block, int index)
{
    metadata_t *ptr = freelist[index];
    if(ptr == block)
    {
    	freelist[index] = block->next;
    	if(block->next !=NULL)
    	{
    		block->next->prev = NULL;
    	}
    	block->next = NULL;
    	block->prev = NULL;
    	return 1;
    }
    else
    {
    	while(ptr !=NULL)
    	{
    		if(ptr == block)
    		{
    			if(ptr->next == NULL)
    			{
    				ptr->prev->next = NULL;
    				block->prev = NULL;
    				block->next = NULL;
    				return 1;

    			}
    			else
    			{
    				ptr->next->prev = ptr->prev;
    				ptr->prev->next = ptr->next;
    				block->next= NULL;
    				block->prev= NULL;
    				return 1;
    			}
    		}
    		ptr = ptr->next;
    	}
    }
    return 0;

}

void* my_calloc(size_t num, size_t size)
{
	if(num*size > 8192)
	{
		ERRNO = SINGLE_REQUEST_TOO_LARGE;
		return NULL;
	}

	void *ptr = my_malloc(num*size);
	for(int i=0; i<num*size; i++)
	{
		((char*)ptr)[i] = 0;
	}

	ERRNO = NO_ERROR;
	return ptr;
}

void my_free(void* ptr)
{
 	metadata_t *block = (metadata_t*)((char*)ptr - sizeof(metadata_t));
 	if(block == NULL)
 		return NULL;

 	//if the pointer to begin with is already free
 	if(block->in_use == 0)
	{
		ERRNO = DOUBLE_FREE_DETECTED;
		return;
	}
	//set the block's in use to 0
	block->in_use = 0;
	block->next = NULL;
	block->prev = NULL;

	int index = find_index(block->size);

	freeHelper(index, block);
}


void freeHelper(int index, metadata_t* ptr)
{
	metadata_t* buddy = find_buddy(index, ptr);
	if(buddy == NULL || buddy->in_use == 1|| buddy->size != ptr->size || ptr->size>= SBRK_SIZE)  //if we don't have to coalesce, simply add to the freelist
	{
		ptr->next = freelist[index];
		if(ptr->next != NULL)
		{
			ptr->next->prev = ptr;
		}
		ptr->prev = NULL;
		freelist[index] = ptr;
		return;
	}

	if(buddy->prev !=NULL)
	{
		buddy->prev->next = buddy->next;
	}

	if(buddy->next !=NULL)
	{
		buddy->next->prev = buddy->prev;
	}

	if(freelist[index] == buddy)
	{
		freelist[index] = freelist[index]->next;
	}

	buddy->next = NULL;
	buddy->prev = NULL;
	if(buddy<ptr)
	{
		buddy->size = (buddy->size)*2;
		index++;
		freeHelper(index, buddy);
	}
	else
	{
		ptr->size = (ptr->size)*2;
		index++;
		freeHelper(index, ptr);
	}
}

metadata_t* find_buddy(int index, metadata_t* ptr)
{

	metadata_t* myPtr = (metadata_t*)((char*) ptr - (char*) heap);
	index = index +4;
	metadata_t* buddyPtr = (metadata_t*)((((size_t)myPtr)^(1 << index)) + (char*)heap);
	if(ptr->size == SBRK_SIZE)
		return NULL;
	else
		return buddyPtr;

}


void* my_memmove(void* dest, const void* src, size_t num_bytes)
{
	char* destination = (char*)dest;
	char* source = (char*)src;
	size_t size = (size_t)num_bytes;
	while(size!=0)
	{
		*destination++ = *source++;
		size--;
	}

	return dest;
}