//+----------------------------------------------------------------------+
//|								    DAPsim								 |
//| Dean Morrison												11/30/06 |
//| University of Florida												 |
//| Department of Electrical and Computer Engineering					 |
//+----------------------------------------------------------------------+
//| Description: DAPsim is a trace-driven simulator developed in C++ for |
//| the purpose of designing, testing, and evaluating demand prepaging 	 |
//| policies.  It currently implements my proposed concept of Dynamically|
//| Adaptive Prepaging, but may be modified to evaluate many other 		 |
//| policies.															 |
//|																		 |
//| Reuse Policy: Use of this software for personal or instructional	 |
//| purposes is granted without fee provided that the source bears a	 |
//| clear and complete citation.										 |
//+----------------------------------------------------------------------+

#include "main.h"
#include "PrepagedPageQ.h"

int debugModePrepaged = DEBUG_MODE;

PrepagedPageQ::PrepagedPageQ()
{
	// Set Prepaged Target Allocation 
	targetAlloc = DEFAULT_PREPAGED_TARGET_ALLOC;
	ResidentQ.setMaxSize(targetAlloc);

	// Set Prepaged Consumed Allocation
	consumedAlloc = 0;

	clearHistogram();

	DegreeQ.setMaxSize(DEFAULT_MAX_DEGREE+2);
}

PrepagedPageQ::PrepagedPageQ(int newTargetAlloc)
{
	// Set Prepaged Target Allocation 
	targetAlloc = newTargetAlloc;
	ResidentQ.setMaxSize(targetAlloc);

	// Set Prepaged Consumed Allocation
	consumedAlloc = 0;

	clearHistogram();

	DegreeQ.setMaxSize(DEFAULT_MAX_DEGREE+2);
}

void PrepagedPageQ::setTargetAlloc(int newTargetAlloc)
{
	int oldConsumedAlloc = getConsumedAlloc();

	if (newTargetAlloc > DEFAULT_MAX_PREPAGED_TARGET_ALLOC) targetAlloc = DEFAULT_MAX_PREPAGED_TARGET_ALLOC;
	else if (newTargetAlloc < DEFAULT_MIN_PREPAGED_TARGET_ALLOC) targetAlloc = DEFAULT_MIN_PREPAGED_TARGET_ALLOC;
	else targetAlloc = newTargetAlloc;
	ResidentQ.setMaxSize(targetAlloc);

	// If New Target Allocation is less than old consumed allocation, place extra pages into non-resident queue
	int elementNum;
	int numOfPagesToRemove = 0;
	if (newTargetAlloc < oldConsumedAlloc) {
		numOfPagesToRemove = oldConsumedAlloc - newTargetAlloc;
		for (elementNum = 0; elementNum < numOfPagesToRemove; ++elementNum) {
			NonResidentQ.pushMRU(ResidentQ.popLRU().getPageNumber());
		}
	}

	// Reset Consumed Allocation
	consumedAlloc = ResidentQ.getSize();
}

int PrepagedPageQ::getConsumedAlloc(void)
{
	// Refresh Consumed Allocation
	consumedAlloc = ResidentQ.getSize();

	return consumedAlloc;
}

int PrepagedPageQ::getTargetAlloc(void)
{
	return targetAlloc;
}

LRU_pageQ_entry PrepagedPageQ::referencePage(unsigned long int pageNumber)
{
	LRU_pageQ_entry referencedPage;
	bool pageHit = false;

	// Check Resident Queue
	int elementNum = 0;
	list<LRU_pageQ_entry>::iterator position;
	for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
		if ((*position).getPageNumber() == pageNumber) {
			pageHit = true;
			incHistogram(elementNum);
			referencedPage = *position;
			removeResidentPage(pageNumber);
			return referencedPage;
		}
		else elementNum++;
    }
	
	// Check Non-Resident Queue (for purposes of updating histogram)
	elementNum = targetAlloc;
	for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
		if (elementNum >= DEFAULT_MAX_MEM_SIZE) break;
		if ((*position).getPageNumber() == pageNumber) {
			//cout << "Incrementing Prepage Histogram at " << elementNum << " for Non-Resident Page " << (*position).getPageNumber() << endl;
			incHistogram(elementNum);
			break;
		}
		else elementNum++;
    }

	// No page hit
	referencedPage.setPageNumber(NULL);

	return referencedPage;
}

void PrepagedPageQ::addPage(unsigned long int newPage)
{
	// Check if already present in prepage queue
	if (pagePresentInQ(newPage)) {
		removeResidentPage(newPage);
	}
	
	// Check if Eviction is necessary
	if ((ResidentQ.getSize() + 1) > targetAlloc) {	//Evict LRU Page
		evictPage();
	}
	ResidentQ.pushMRU(newPage);
	// Update Consumed Allocation
	consumedAlloc = ResidentQ.getSize();
}

void PrepagedPageQ::evictPage(void)
{
	// Evict Page
	// Add Evicted Page to NonResident Queue
	NonResidentQ.pushMRU(ResidentQ.popLRU().getPageNumber());

	// Update Consumed Allocation
	consumedAlloc = ResidentQ.getSize();
}

void PrepagedPageQ::removeResidentPage(unsigned long int pageNumber)
{
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			// Remove Page
			ResidentQ.getQueue()->erase(position);
			// Update Consumed Alloc
			consumedAlloc = ResidentQ.getSize();
			return;
		}
    }
}

void PrepagedPageQ::removeNonResidentPage(unsigned long int pageNumber)
{
	list<LRU_pageQ_entry>::iterator position;
    for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			// Remove Page
			NonResidentQ.getQueue()->erase(position);
			return;
		}
    }
}

void PrepagedPageQ::printQueueEntries(void)
{
	cout << "Prepaged Page Queue:\n";
	cout << "Resident Queue:\n";
	cout << "Entry\tPage #\tHist Value\n";
	cout << "-----\t------\t----------\n";
	
	// Resident Queue Entries
	int elementNum = 0;
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
		if (elementNum == 0) cout << elementNum + 1 << " MRU\t";
		else if (elementNum == (ResidentQ.getSize()-1)) cout << elementNum + 1 << " LRU\t";
		else cout << elementNum + 1 << "\t";
		cout << (*position).getPageNumber() << "\t";
		//cout << (*position).getHistValue() << "\n";
		cout << histogram[elementNum] << "\n";
		elementNum++;
	}

	// NonResident Queue Entries
	elementNum = targetAlloc;
	cout << "Non-Resident Queue:\n";
	cout << "Entry\tPage #\tHist Value\n";
	cout << "-----\t------\t----------\n";
	for (position = NonResidentQ.getQueue()->begin(); position != NonResidentQ.getQueue()->end(); ++position) {
		if (elementNum == targetAlloc) cout << elementNum + 1 << " MRU\t";
		else if (elementNum == (targetAlloc + NonResidentQ.getSize() - 1)) cout << elementNum + 1 << " LRU\t";
		else cout << elementNum + 1 << "\t";
		cout << (*position).getPageNumber() << "\t";
		//cout << (*position).getHistValue() << "\n";
		if (elementNum < DEFAULT_MAX_MEM_SIZE) cout << histogram[elementNum] << "\n";
		else break;
		elementNum++;
	}
}

void PrepagedPageQ::printResidentQueueEntries(void)
{
	cout << "Prepaged Page Queue:\n";
	cout << "Resident Queue:\n";
	cout << "Entry\tPage #\tHist Value\n";
	cout << "-----\t------\t----------\n";
	
	int elementNum = 0;
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
		if (elementNum == 0) cout << elementNum + 1 << " MRU\t";
		else if (elementNum == (ResidentQ.getSize()-1)) cout << elementNum + 1 << " LRU\t";
		else cout << elementNum + 1 << "\t";
		cout << (*position).getPageNumber() << "\t";
		//cout << (*position).getHistValue() << "\n";
		cout << histogram[elementNum] << "\n";
		elementNum++;
	}
}

void PrepagedPageQ::clearHistogram(void)
{
	int index;
	for (index = 0; index < DEFAULT_MAX_MEM_SIZE; index++) {
		histogram[index] = 0;
	}
}

void PrepagedPageQ::clearDegreeHistogram(void)
{
	int index;
	for (index = 0; index < (DEFAULT_MAX_DEGREE + 2); index++) {
		degreeHistogram[index] = 0;
	}
}

void PrepagedPageQ::incHistogram(int index)
{
	if (index >= DEFAULT_MAX_MEM_SIZE) {
		if (debugModePrepaged == DEBUG_2) cout << "ERROR: Histogram index out of bounds!\n";
		return;
	}

	histogram[index] += 1;
}

void PrepagedPageQ::incDegreeHistogram(int index)
{
	if (index > (DEFAULT_MAX_DEGREE + 1)) {
		if (debugModePrepaged == DEBUG_2) cout << "ERROR: Degree histogram index out of bounds!\n";
		return;
	}

	degreeHistogram[index] += 1;
}

int PrepagedPageQ::getHistogramEntry(int index)
{
	if (index >= DEFAULT_MAX_MEM_SIZE) {
		if (debugModePrepaged == DEBUG_2) cout << "ERROR: Histogram index out of bounds!\n";
		return -1;
	}

	return histogram[index];
}

bool PrepagedPageQ::pagePresentInQ(unsigned long int pageNumber)
{
	bool pagePresent = false;
	list<LRU_pageQ_entry>::iterator position;
    for (position = ResidentQ.getQueue()->begin(); position != ResidentQ.getQueue()->end(); ++position) {
        if ((*position).getPageNumber() == pageNumber) {
			pagePresent = true;
			break;
		}
    }
	
	return pagePresent;
}

void PrepagedPageQ::decayHistogram(double decayValue)
{
	int index;
	for (index = 0; index < DEFAULT_MAX_MEM_SIZE; index++) {
		histogram[index] = (double)histogram[index] * decayValue;	//Truncation allowed
	}
}

void PrepagedPageQ::printHistogram(void)
{
	cout << "Prepaged Page Queue Histogram:\n";
	int index;
	for (index = 0; index < targetAlloc; index++) {
		cout << histogram[index] << endl;
	}
}

void PrepagedPageQ::printDegreeQueue(int currentDegree)
{
	cout << "Prepaged Degree Queue:\n";
	cout << "\tEntry\tHist\n";
	cout << "\t-----\t----\n";

	int index = 0;
	list<LRU_pageQ_entry>::iterator position;
    for (position = DegreeQ.getQueue()->begin(); position != DegreeQ.getQueue()->end(); ++position) {
		if (index > (currentDegree + 1)) break;
		if (index == 0) cout << "MRU\t";
		else cout << "\t";
		cout << (*position).getPageNumber() << "\t" << degreeHistogram[index] << endl;
		index++;
	}
}

void PrepagedPageQ::updateDegreeHistogram(unsigned long int pageNumber, int currentDegree)
{
	// Check Degree Queue
	int elementNum = 0;
	list<LRU_pageQ_entry>::iterator position;
	for (position = DegreeQ.getQueue()->begin(); position != DegreeQ.getQueue()->end(); ++position) {
		if (elementNum > (currentDegree + 1)) break;
		else if ((*position).getPageNumber() == pageNumber) {
			incDegreeHistogram(elementNum);
		}
		elementNum++;
    }
}

void PrepagedPageQ::addDegreePage(unsigned long int newPage)
{
	if ((DegreeQ.getSize() + 1) > DegreeQ.getMaxSize()) {	//Evict LRU Page
		DegreeQ.evictPage();
	}
	
	DegreeQ.pushMRU(newPage);
}

int PrepagedPageQ::getDegreeHistogramEntry(int index)
{
	if (index > (DEFAULT_MAX_DEGREE + 1)) {
		if (debugModePrepaged == DEBUG_2) cout << "ERROR: Degree histogram index out of bounds!\n";
		return 0;
	}

	return degreeHistogram[index];
}

int PrepagedPageQ::getDegreeQueueSize(void)
{
	return DegreeQ.getSize();
}