#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>
#include <math.h>
#include "mymalloc.h"

//malloc() 1 byte and immediately free it - do this 150 times
int memgrindA() {
    	void* pointerArray[150];
	int i = 0;
	while(i < 150){
		pointerArray[i] = (void *)(uintptr_t)malloc(1);
		free(pointerArray[i]);
		i++;
	}
	return 0;
}

//malloc() 1 byte, store the pointer in an array - do this 150 times.
//Once you've malloc()ed 150 byte chunks, then free() the 150 1 byte pointers one by one.
int memgrindB() {
	void *pointerArray[150];
	int i = 0;
	while(i < 150){
		pointerArray[i] = (void *)(uintptr_t)malloc(1);
		i++;
	}
	i = 0;
	while(i < 150){
		free(pointerArray[i]);
		i++;
	}
	return 0;
}

//Randomly choose between a 1 byte malloc() or free()ing a 1 byte pointer - do this 150 times
//Keep track of each operation so that you eventually malloc() 150 bytes, in total
//Keep track of each operation so that you eventually free() all pointers
//(don't allow a free() if you have no pointers to free())
int memgrindC() {
	void* pointerArray[150];
	int malcount = 0;
	int freecount = 0;

	while(malcount < 150){
		if(rand() % 2 == 0 && malcount < 150){
			pointerArray[malcount] = (void *)(uintptr_t)malloc(1);
			if(pointerArray[malcount] != NULL){
				malcount++;
			}
		}
		else{
			if(freecount < malcount){
				free(pointerArray[freecount]);
				freecount++;
			}
		}
	}
	while(freecount < malcount){
		free(pointerArray[freecount]);
		freecount++;
	}
	return 0;
}

//Randomly choose between a randomly-sized malloc() or free()ing a pointer  do this many times
//Keep track of each malloc so that all mallocs do not exceed your total memory capacity
//Keep track of each operation so that you eventually malloc() 150 times
//Keep track of each operation so that you eventually free() all pointers
//Choose a random allocation size between 1 and 64 bytes
int memgrindD() {
	void* pointerArray[150];
	int malSizeArray[150];
	int malcount = 0;
	int freecount = 0;
	int malsize = 0;

	while(malcount < 150){
		if(rand() % 2 == 0 && malcount < 150 && malsize < memoryBlockSize){
			int randomSize = (rand() % 64) + 1;
			pointerArray[malcount] = (void *)(uintptr_t)malloc(randomSize);
			if(pointerArray[malcount] != NULL){
				malSizeArray[malcount] = randomSize + blockSize;
				malsize += randomSize + blockSize;
				malcount++;
			}
		}
		else{
			if(freecount < malcount){
				malsize -= malSizeArray[freecount];
				free(pointerArray[freecount]);
				freecount++;
			}
		}
	}
	while(freecount < malcount){
		free(pointerArray[freecount]);
		malsize -= malSizeArray[freecount];
		freecount++;
	}
}

//malloc until full
//free every other block
//remalloc freed blocks
//free all the blocks
//test how malloc how efficient it handles empty space
int memgrindE() {
	int numBlocks = 1;
	int malcount = 0;
	int freecount = 0;
	void* pointerArray[150];
	while((pointerArray[malcount] = (void *)(uintptr_t)malloc(2)) != NULL){
		numBlocks++;
		malcount++;
	}
	for(freecount = 0; freecount < malcount; freecount += 2){
		free(pointerArray[freecount]);
		pointerArray[freecount] = NULL;
	}
	for(malcount = 0; malcount < numBlocks - 1; malcount +=2){
		pointerArray[malcount] = (void *)(uintptr_t)malloc(1);
	}
	for(freecount = 0; freecount < numBlocks - 1; freecount++){
		free(pointerArray[freecount]);
		pointerArray[freecount] = NULL;
	}

	return 0;
}

//malloc blocks with bytes that increase in powers of two
//test to see if it can malloc bytes efficiently when it is doubling in size
//test to see if it can free bytes efficiently when it is doubling in size
int memgrindF() {
	void* pointerArray[150];
	int i = 0;
	int numBytes = 1;

	while(i < 150){
		pointerArray[i] = (void *)(uintptr_t)malloc(numBytes);
		if(pointerArray[i] == NULL){
			break;
		}
		else{
			numBytes = numBytes * 2;
			i++;
		}
	}
	i = 0;
	while(i < 150){
		free(pointerArray[i]);
		i++;
	}
	return 0;
}

void averageRunTime(int(memgrind)()){
	struct timeval t0;
	struct timeval t1;
	long int averageTime = 0;
	int t = 0;
	while(t < 100){
		gettimeofday(&t0,0);
		memgrind();
		gettimeofday(&t1,0);
		averageTime += (t1.tv_sec - t0.tv_sec) * 1000000 + (t1.tv_usec - t0.tv_usec);
	}
	averageTime /= 100;
	int grind = 1;
	for(grind = 1; grind < 7; grind++){
		print("The average running time of memgrind %d was %ld ms.\n", grind, averageTime);
	}
}

int main() {
    	averageRunTime(memgrindA);
	averageRunTime(memgrindB);
	averageRunTime(memgrindC);
	averageRunTime(memgrindD);
	averageRunTime(memgrindE);
	averageRunTime(memgrindF);
	return 0;
}