#include <stdlib.h>
#include <iostream>
#include <ctime>
#include <stddef.h>
#include <stdint.h>
#include <algorithm>
#include <vector>

#define PTRS_TO_MAKE_IN_MB 1024
#define ITERATIONS_TO_RUN 1000

//typedef unsigned long long ptr_t;
typedef intptr_t ptr_t;

void *dereference(ptr_t what, int num)
{
	ptr_t our_ptr = what;
	ptr_t *ptr = (ptr_t *)what;
 
	for (int i = 0; i < num; i++) {
        // Grab the contents of the memory at our_ptr
		our_ptr = *ptr;
        // Set ptr to contents of memory at our_ptr
		ptr = (ptr_t *)our_ptr;

	}
	return (void *)ptr;
}

void *dereference_itself(void *what, int num)
{
	// Let's try to keep the compiler honest
	int *foo = (int *)what;
	void *mine = what;
	for (int i = 0; i < num; i++) {
		mine = mine;
	}
	return mine;
}

int main()
{
	// Let's get our variable we're pointing to!
	int a = 4;
	
	// Now let's figure out how many structs to allocate
	const int num_elements = (PTRS_TO_MAKE_IN_MB*1024*256); // this is *2 in mb if you're targeting 64-bit
	ptr_t *pstr = (ptr_t *)malloc(num_elements * sizeof(ptr_t));
	if (pstr == NULL) { std::cout << "Failed to allocate the memory, y'all!"; return -1; }

	// Let's do a loopdy-doop
	void *base_ptr = (void *)&a;
	ptr_t last_ptr = (ptr_t)base_ptr;

	pstr[0] = (ptr_t)base_ptr;
	last_ptr = (ptr_t)&pstr[0];
	for (int i = 1; i < num_elements; i++) {
		pstr[i] = last_ptr;
		last_ptr = (ptr_t)&pstr[i];
	}

	int *e = (int *)dereference(pstr[200],200);
	std::cout << "Should be 4: " << *e << std::endl;


	std::cout << "Our number of pointers is: " << num_elements << std::endl;

	// Dereference all the way from the top to the bottom
	ptr_t top_ptr = pstr[num_elements-1];
	int *aptr = (int *)dereference(top_ptr,num_elements-1);
	std::cout << "Should be 4: " << *aptr << std::endl;



	std::cout << "Shuffling internal pointers to mess with the cache" << std::endl;
/*	ptr_t *pstart = &pstr[1];
	ptr_t *pend = &pstr[num_elements];
	ptr_t pfind = pstr[num_elements-1];
	std::random_shuffle (pstart, pend);
	for (int i = 0; i < num_elements; i++) {
		ptr_t a = pstr[i];
		if (a == pfind) {
			std::cout << i;
			ptr_t tmp = pstr[i];
			pstr[i] = pstr[num_elements - 1];
			pstr[num_elements - 1] = tmp;
			std::cout << "YAY!" << std::endl;
			break;
		}
	}*/

	// 


	std::cout << "Starting benchmark of " << ITERATIONS_TO_RUN << " dereferences:" << std::endl;
	clock_t timer = clock();
	for (int i = 0; i < ITERATIONS_TO_RUN; i++) {
		int *hey = (int *)dereference(top_ptr,num_elements-1);
		*hey = *hey + 1;
	}
	clock_t end = clock() - timer;
	float time_in_seconds = ((float)end / (float)CLOCKS_PER_SEC);
	std::cout << "Time: " << time_in_seconds << "s" << std::endl;
	std::cout << "Should be " << (ITERATIONS_TO_RUN + 4) << ": " << *aptr << std::endl << std::endl;

	std::cout << "Trivial function replication benchmark commencing..." << std::endl;
	timer = clock();
	void *trivial_ptr = (void *)&a;
	for (int i = 0; i < ITERATIONS_TO_RUN; i++) {
		int *hey = (int *)dereference_itself(trivial_ptr,num_elements-1);
		*hey = *hey + 1;
	}
	end = clock() - timer;
	time_in_seconds = ((float)end / (float)CLOCKS_PER_SEC);
	std::cout << "That took: " << time_in_seconds << "s" << std::endl;

endit:
	if (pstr) free(pstr);
	char foo[50];
	gets(foo);
}