#ifndef STACK_PROFILE_H_
#define STACK_PROFILE_H_

#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>

#include <list>
#include <vector>

#include <iostream>
#include <ostream>

struct StackProfile
{
	// associativity of the cache to consider
	int associativity;

	// the profile for different stack distances itself
	std::vector<int> counts;

	// stack of accessed addresses used to calculate the profile
	std::list<uintptr_t> stack;

	StackProfile(int _associativity) : associativity(_associativity), counts(_associativity + 1), stack(_associativity)
	{};

	/*
	 * Simulate an access on the stack, optionally count the distance in the profile
	 *
	 * Return the stack distance of the access, -1 if not present on the stack (miss).
	 */
	int access(uintptr_t addr, bool count) {
		std::list<uintptr_t>::iterator it = stack.begin();
		int position = 0;
		while (it != stack.end()) {
			if (*it == addr) {
				// push to front
				stack.erase(it);
				stack.push_front(addr);
				if (count) {
					counts[position]++;
				}
				return position;
			}
			it++;
			position++;
		}

		// not found, push to front and remove the last
		stack.pop_back();
		stack.push_front(addr);
		if (count) {
			counts[associativity]++;
		}
		return -1;
	};

	void printCounts() {
		for (std::vector<int>::iterator it = counts.begin(); it != counts.end(); it++) {
			std::cout << *it << " ";
		}
		std::cout << std::endl;
	};

	void printCountsR(std::ostream & o) {
		for (std::vector<int>::iterator it = counts.begin(); it != counts.end(); ) {
			o << "\t" << *it;
			it++;
		}
	};
};

class StackProfiler
{
private:
	// number of sets in the cache
	size_t cacheSets;

	// vector of stack profiles of individual cache sets
	std::vector<StackProfile> setProfiles;

	// cache line size in bytes
	size_t cacheLineSize;

	// size of the range of addresses after which the mapping to sets wraps
	// calculated as cacheSize / associativity
	size_t cacheWrapSize;

	int associativity;

public:
	StackProfiler(size_t cacheSize, size_t cacheLineSize, int associativity);

	// simulate access to one address
	int access(uintptr_t addr, bool count) {
		const size_t cacheSet = (addr % cacheWrapSize) / cacheLineSize;
		//std::cout << "access to addr " << (void *) addr << " goes to set " << cacheSet << std::endl;
		return setProfiles[cacheSet].access(addr, count);
	}

	// follow a NULL-terminated pointer chain, optionally count
	void followPointers(void * start, bool count);

	void test();

	void printCounts();

	void printCountsR(std::ostream & o);
};

#endif /* STACK_PROFILE_H_ */