#include "stdafx.h"
#include "LRU.h"

LRU::LRU()
{
	for (int i = 0; i < DEFBUFSIZE; i++)
	{
		ftop[i] = -1;
		ptob[i] = NULL;
		memset(buf[i].field,'\0',FRAMESIZE);
	}
	lru = NULL;
	mru = lru;
	hit = 0;
	total = 0;
	flashreadcount = 0;
	flashwritecount = 0;
}

LRU::~LRU()
{
	//释放lru链表
	LRUElement * p = mru;
	while (p != NULL)
	{
		mru = mru->LessRecent;
		delete p;
		p = mru;
	}
	lru = mru = NULL;

	//释放控制块节点
	LRUBCB * pb= NULL;
	LRUBCB * head = NULL;;
	for (int i = 0; i<DEFBUFSIZE; i++)
	{
		head = ptob[i];
		pb = head;
		while (pb != NULL)
		{
			head = head->next;
			delete pb;
			pb = head;
		}
	}
	pb = head = NULL;
	maplist.clear();
}

void LRU::Init()
{
	//释放lru链表
	LRUElement * p = mru;
	while (p != NULL)
	{
		mru = mru->LessRecent;
		delete p;
		p = mru;
	}
	lru = mru = NULL;

	//释放控制块节点
	LRUBCB * pb= NULL;
	LRUBCB * head = NULL;;
	for (int i = 0; i<DEFBUFSIZE; i++)
	{
		head = ptob[i];
		pb = head;
		while (pb != NULL)
		{
			head = head->next;
			delete pb;
			pb = head;
		}
	}
	pb = head = NULL;
	
	/*初始化缓冲区*/
	for (int i = 0; i < DEFBUFSIZE; i++)
	{
		ftop[i] = -1;
		ptob[i] = NULL;
		memset(buf[i].field,'\0',FRAMESIZE);
	}
	hit = 0;
	total = 0;
	flashreadcount = 0;
	flashwritecount = 0;
}


int LRU::FixPage(int page_id)
{
	ASSERT(page_id >= 0);

	int frid = -1;
	int rv = -1;
	int hk = hash(page_id);
	LRUBCB* pb = NULL;
	pb = PageToLRUBCB(page_id);

	/*读计数加1*/
	total++;

	/*若该页在缓冲区中已存在*/
	if (pb != NULL)
	{
		frid = pb->frame_id;
		AdjustLRUList(frid);

		/*命中次数加1*/
		hit++;

		return frid;
	}
	else // 若该页不在缓冲区中
	{
		frid = SelectVictim();
		
		/*正常情形下，此时应该从二级存储器读入需要加载的数据*/
		rv = f_read_page(page_id,(BYTE *)(buf[frid].field),0,FRAMESIZE);
		if(rv == RV_ERROR_INVALID_PAGE_STATE)
		{
			printf("page readed is invalid\n");
		}
	    if (rv ==  RV_ERROR_FLASH_BLOCK_BROKEN)
		{
			printf("the block contained this page is broken \n");
		}
		
		flashreadcount++;

		ftop[frid] = page_id;
		pb = ptob[hk];
		/*将新的LRUBCB链接到桶的尾部*/
		if ( pb != NULL)
		{
			while( pb->next != NULL)
			{
				pb = pb->next;
			}
			pb->next = new LRUBCB();
			pb = pb->next;
		}
		else //桶为空
		{
			pb = new LRUBCB();
			ptob[hk] = pb;
		}
		pb->dirty = 0;
		pb->frame_id = frid;
		pb->page_id = page_id;
		pb->next = NULL;
		InsertLRUEle(frid);
		return frid;
	}
}


NewPage LRU::FixNewPage(LBA lba)
{
	NewPage np;
	np.frame_id = -1;
	np.page_id = -1;
	int pid = -1;
	int frid = -1;
	LRUBCB* pb = NULL;

	/* 申请分配新数据页 */
	f_alloc_page(1, &pid);
	if (pid == -1)
		printf("there is no free page in the flash memory");
     ASSERT(pid >= 0);

	 /*注册映射项*/
	 RegistEntry(lba,pid);

	/* 在缓冲区中寻找空闲块，用于存储新数据页中的数据*/
	frid = SelectVictim();
	ftop[frid] = pid;
	pb = ptob[hash(pid)];
	/*将新的LRUBCB链接到桶的尾部*/
	if ( pb != NULL)
	{
		while( pb->next != NULL)
		{
			pb = pb->next;
		}
		pb->next = new LRUBCB();
		pb = pb->next;
	}
	else //桶为空
	{
		pb = new LRUBCB();
		ptob[hash(pid)] = pb;
	}
	pb->dirty = 0;
	pb->frame_id = frid;
	pb->page_id = pid;
	pb->next = NULL;
	InsertLRUEle(frid);
	np.frame_id = frid;
	np.page_id = pid;
	return np;
}

int LRU::UnFixPage(int page_id)
{
	ASSERT(page_id >= 0);
	LRUBCB *pb = NULL;
	pb = PageToLRUBCB(page_id);
	int rv = -1;

	if(pb->dirty == 1)
	{
		pb->dirty = 0;
	}

	rv = f_release_page(page_id);
	if (rv == RV_ERROR_INVALID_LBA)
	{	
		printf("Invalid  LBA\n");
		return rv;
	}
	return 0;
}

void LRU::ReadFrame(int frame_id,char* buffer)
{
	ASSERT(frame_id >= 0 );
	ASSERT(buffer != NULL);

	memcpy(buffer,buf[frame_id].field,FRAMESIZE);
	return;
}

void LRU::WriteFrame(int frame_id,const char* buffer)
{
	ASSERT(frame_id >= 0);
	ASSERT(buffer != NULL);

	memcpy(buf[frame_id].field,buffer,FRAMESIZE);
	SetDirty(frame_id);
	return;
}

int LRU::WriteDirty()
{
	LRUBCB* pb = NULL;
	int rv = -1;
	for (int i = 0; i < DEFBUFSIZE; i++)
	{
		pb = ptob[i];
		while ( pb != NULL)
		{
			if (pb->dirty == 1)
			{		
				//程序结束时，我们应该将脏页写回二级存储器
				rv = f_write_page(pb->page_id,(BYTE *)(buf[pb->frame_id].field),0,FRAMESIZE);
				if (rv == RV_ERROR_FLASH_NO_MEMORY)
				{	
					printf("no more flash memory \n");
					return rv;
				}
			
				flashwritecount++;
			}
			pb = pb->next;
		}
	}
	return 0;
}

double LRU::HitRatio()
{
	return ((double)(hit)/(double)(total));
}

void LRU::RWInfo()
{
	printf("hit is: %d\n",hit);
	printf("total is: %d\n",total);
	printf("flash read count is: %d\n",flashreadcount);
	printf("flash write count is: %d\n",flashwritecount);
	return;
}

int LRU::IsLBAValid(LBA lba)
{
	ASSERT(lba >= 0);
	if(maplist.count(lba))
	{
		return LBA_IS_VALID;
	}
	else
	{
		return LBA_IS_INVALID;
	}
}

int LRU::LBAToPID(LBA lba)
{
	ASSERT(lba >= 0);
	return maplist[lba];
}

void LRU::SetDirty(int frame_id)
{
	ASSERT(frame_id >= 0);
	int pid = -1;
	LRUBCB* pb = NULL;
	pid = ftop[frame_id];
	pb = PageToLRUBCB(pid);
	if (pb->dirty == 0)
	{
		pb->dirty = 1;
	}
	return;
}



int LRU::hash(int page_id)
{
	ASSERT(page_id >= 0 );

	int hk = -1;
	hk = page_id % DEFBUFSIZE;
	return hk;
}

LRUBCB* LRU::PageToLRUBCB(int page_id)
{
	ASSERT(page_id >= 0);

	LRUBCB* pb = NULL;
	int hk = -1;
	hk = hash(page_id);
	pb = ptob[hk];
	while ( pb != NULL && pb->page_id != page_id)
	{	
		pb = pb->next;
	}
	return pb;
}


void LRU::RemoveLRUBCB(LRUBCB* pb)
{
	ASSERT(pb != NULL);

	LRUBCB* head = NULL;
	head = ptob[hash(pb->page_id)];

	/* 若该LRUBCB正好在桶的首部 */
	if (pb == head)
	{
		/* 如果桶的长度大于1，则需要维护桶的其它部分*/
		if ( head->next != NULL)
		{
			head = head->next;
			ptob[hash(pb->page_id)] = head;
			ftop[pb->frame_id] = -1;
			memset(&(buf[pb->frame_id].field),'\0',FRAMESIZE);
			delete pb;
			pb = NULL;
			head = NULL;
		}
		else //若桶中只有一个元素
		{
			ptob[hash(pb->page_id)] = NULL;
			ftop[pb->frame_id] = -1;
			memset(&(buf[pb->frame_id].field),'\0',FRAMESIZE);
			delete pb;
			pb = NULL;
		}
	}
	else //在桶内需找LRUBCB的正确位置
	{
		while ( head->next != pb)
		{
			head = head->next;
		}
		head->next = pb->next;
		ftop[pb->frame_id] = -1;
		memset(&(buf[pb->frame_id].field),'\0',FRAMESIZE);
		delete pb;
		pb = NULL;
		head = NULL;
	}
	return;
}

/* 在LRU置换策略中，每次只需删除lru指向的元素，这里做一般化处理*/
void LRU::RemoveLRUEle(int frame_id)
{
	ASSERT(frame_id >= 0);
	LRUElement* elem = NULL;
	elem = lru;
	if (elem == NULL)
	{
		return;
	}

	while( (elem != NULL)&&(elem->frame_id != frame_id))
	{
		elem = elem->MoreRecent;
	}

	if (elem == NULL)
	{
		return;  //找不到相应的元素
	}
	else
	{
		if ( elem == lru) //lru指向要删除的元素
		{
			if ( elem == mru) //mru也指向要删除的元素
			{
				lru = mru = NULL;
				delete elem;
			}
			else
			{
				lru = lru->MoreRecent;
				lru->LessRecent = NULL;
				delete elem;
			}
		}
		else //在lru策略中能删除除链尾以外的元素，只出现在多线程访问同一元素时（数据锁）
		{
			if ( elem == mru ) //mru指向要删除的元素
			{
				mru = mru->LessRecent;
				mru->MoreRecent = NULL;
				delete elem;
			}
			else //删除除链头和链尾的元素
			{
				elem->MoreRecent->LessRecent = elem->LessRecent;
				elem->LessRecent->MoreRecent = elem->MoreRecent;
				delete elem;
			}
		}//end elem == lru
		return;
	}//end elem == NULL
}



void LRU::InsertLRUEle(int frame_id)
{
	ASSERT(frame_id >= 0);

	LRUElement* elem = NULL;
	elem = new LRUElement();
	elem->frame_id = frame_id;
	elem->LessRecent = NULL;
	elem->MoreRecent = NULL;
	/* 若链表为空 */
	if ( mru == NULL)
	{
		mru = elem;
		lru = mru;
	}
	else
	{
		elem->LessRecent = mru;
		mru->MoreRecent = elem;
		mru = elem;
	}
	return;
}

void LRU::AdjustLRUList(int frame_id)
{
	ASSERT(frame_id >= 0);
	LRUElement* elem = NULL;
	elem = mru;

	/* 若链表为空*/
	if (elem == NULL)
	{
		return;
	}

	while ( (elem != NULL)&&(elem->frame_id != frame_id))
	{
		elem = elem->LessRecent;
	}

	/*若没找到*/
	if (elem == NULL)
	{
		return;
	}
	else
	{
		if (elem == mru) //访问的元素在链首，直接返回
		{
			return;
		}
		else //访问的元素在链尾，将其移到链首
		{
			if( elem == lru ) //若访问的元素为链尾元素
			{
				lru = lru->MoreRecent;
				lru->LessRecent = NULL;
			}
			else//访问除链首和链尾之外的元素
			{
				elem->LessRecent->MoreRecent = elem->MoreRecent;
				elem->MoreRecent->LessRecent = elem->LessRecent;
			}
			elem->LessRecent = mru;
			mru->MoreRecent = elem;
			elem->MoreRecent = NULL;
			mru = elem;
			return;
		} //end elem == mru
	} //end elem == NULL
}

int LRU::SelectVictim()
{	
	LRUBCB* pb = NULL;
	LRUElement* elem = NULL;
	int frid = -1;
	int rv = -1;

	/* 若干净页链表和脏页链表都为空，则选择缓冲区中的第一块 */
	if ( lru == NULL)
	{
		return 0;
	}

	/* 从缓冲区中找空闲块 */
	for ( int i = 0; i< DEFBUFSIZE; i++)
	{
		if ( ftop[i] == -1 )
		{
			return i;
		}
	}

	/* 若缓冲区已无空闲页，则从中选择置换页（执行置换策略）*/
	elem = lru;
	lru = lru->MoreRecent;
	lru->LessRecent = NULL;
	frid = elem->frame_id;
	pb = PageToLRUBCB(ftop[frid]);

	if ( pb->dirty == 1)
	{
		//正常情况下，应该将数据写回二级存储器，这里只计数
		rv = f_write_page(pb->page_id,(BYTE *)(buf[pb->frame_id].field),0,FRAMESIZE);
		if (rv == RV_ERROR_FLASH_NO_MEMORY)
		printf("no more flash memory \n");
		
		flashwritecount++;
	}

	/* 将置换帧的元信息和链表信息删除 */
	RemoveLRUEle(frid);
	RemoveLRUBCB(pb);
	return frid;
}



void LRU::RegistEntry(LBA lba, PID page_id)
{
	ASSERT(lba >= 0);
	ASSERT(page_id >= 0);
	maplist.insert(valType(lba,page_id));
}