c语言实现的LRU算法

使用c语言是实现的LRU算法，带测试用例，供大家学习参考使用

#include “lru.h“
#include 
#include 
/*
	initialization function	
	creates a single linked list of frame structures
*/
void init_it（） 
{
	scanf（“%d%d%d“ &ihash_size &MEMORY_SIZE &PAGE_TABLE_SIZE）;
	int i j;
	frame *pCurrent = NULL *pNew;
	for （i = 0; i < MEMORY_SIZE; i++） {
		// allocate memory for a structure
		if （（pNew = （frame *）malloc（sizeof（frame））） == NULL） {
			perror（“Error allocating memory“）;
			exit（1）;
		}
		//** Next -- initialize the fields in frame;.
		if （pCurrent == NULL）
			fm_free_list = pNew;
		else
			pCurrent->f_free_next = pNew;
		pNew->page_num = -1;
		pNew->f_hash_next = NULL;
		pNew->f_hash_prev = NULL;
		pNew->f_lru_next = NULL;
		pNew->f_lru_prev = NULL;
		pNew->f_free_next = NULL;
		//** set frame number 0 to M-1
		pNew->frame_num = i;
		pCurrent = pNew;
	}
	fm_lru_head = NULL;
	fm_lru_tail = NULL;
}
	/*
	If free frame list is not empty this function unlinks one frame packet from the free list and returns a pointer to the same. 
	If the free list is empty a null
	pointer is returned.
	*/
frame *get_frame_free（）
{
	frame *tmp = NULL;
	if （!fm_free_list）
		return NULL;
	for （frame *i = fm_free_list;i;i = i->f_free_next ）
	{
		if （i->page_num == -1）
			return i;
		if （i == fm_lru_tail） 
			tmp = i;
	}
	if（tmp）
	{
		fm_lru_tail = fm_lru_tail->f_lru_prev;
		fm_lru_tail->f_lru_next = NULL;
		return tmp;
	}
}

	/*
	Given a page number this function checks to see if the page is in hash table （memory）. 
	If the page is not in memorythis function frees （or gets a free frame packet） that is used to store the page number.
	*/
int check_page_table（long page_num frame **p_p_frame_pkt）
{
	for （frame *i = fm_free_list;i !=NULL && i->frame_num < MEMORY_SIZE; i = i->f_free_next）
	{
		if （i->page_num == page_num）
		{
			*p_p_frame_pkt = i;
			return 1;
		}
	}
	return 0;
}
	/*
	This function inserts
	the frame pointed to by p frame pkt in the hash table and the LRU list.
	*/
void put_pageframe_in_memory（long page_num frame *p_frame_pkt）
{
	p_frame_pkt->page_num = page_num;
	if （fm_lru_head） {
		fm_lru_head->f_lru_prev = p_frame_pkt;
		p_frame_pkt->f_lru_next = fm_lru_head;
		p_frame_pkt->f_lru_prev = NULL;
		fm_lru_head = p_frame_pkt;
	}
	else {
		fm_lru_head = p_frame_pkt;
		fm_lru_tail = p_frame_pkt;
		p_frame_pkt->f_lru_prev = NULL;
		p_frame_pkt->f_lru_next = NULL;
	}
	int i = hash（page_num）;
	frame *hashi = page_table[i];
	if （hashi）
	{
		for （; hashi->f_hash_next; hashi = hashi->f_hash_next）
		{
		}
		hashi->f_hash_next = p_frame_pkt;
		p_frame_pkt->f_hash_prev = hashi;
		p_frame_pkt->f_hash_next = NULL;
	}
	else
	{
		page_table[i] = p_frame_pkt;
		p_frame_pkt->f_hash_prev = NULL;
		p_frame_pkt->f_hash_next = NULL;
	}
}
	/*
	base the hash function on the page number.
	*/
int hash（long pageNumber）
{
	long iHashKey;
	iHashKey = pageNumber + 1;
	return（iHashKey % ihash_size）;
}

voi

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件         245  2018-11-19 00:44  hw7input1.txt
     文件          81  2018-11-19 00:44  hw7input2.txt
     文件       13144  2018-11-20 03:07  lru
     文件        3988  2018-11-20 03:11  lru.c
     文件         425  2018-11-19 00:44  lru.h
     文件          26  2018-11-20 03:06  makefile
     文件        1790  2018-11-20 09:02  out1.txt
     文件         229  2018-11-20 09:01  out2.txt
     文件         499  2018-11-20 06:05  readme.txt