操作系统算法细嚼之：LRU算法简易实现

选用题目：leetcode 146. LRU缓存机制

146.LRU缓存机制

我的提交：

我的算法由于没有进行哈希优化，所以在最后一个测试点超时了。

实现思路：

设置一个链表，然后最近使用的插入到链表的尾部。那么最近最久未使用的内存页就是链表的第一个节点了，只需要把它移除就好！

我的代码：

头文件：

#pragma once
#ifndef _LRUCach_
#define _LRUCach_

typedef struct Link_Node {
	int _key, _val;
	struct Link_Node* Next;
} Link_Node;

typedef struct LRU_Cache {
	struct Link_List* LRU_List;
	int _capacity;
} LRU_Cache;

typedef struct Link_List {
	int _size;
	struct Link_Node* Head;
} Link_List;

#endif // !_LRUCach_

源文件：

#include "LRUCach.h"
#include <stdio.h>
#include <stdlib.h>

static struct Link_List* Link_List_Create() {
	struct Link_List* list;
	list = (struct Link_List*)malloc(sizeof(struct Link_List));
	list->Head = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	list->Head->Next = NULL;
	list->_size = 0;
	return list;
}

static struct LRU_Cache* lRUCacheCreate(int capacity) {
	if (capacity <= 0)
		return NULL;
	struct LRU_Cache* lru = (struct LRU_Cache*)malloc(sizeof(struct LRU_Cache));
	lru->_capacity = capacity;
	lru->LRU_List = Link_List_Create(capacity);
	return lru;
}

static void add_Node(struct Link_List* list, struct Link_Node* node) {
	struct Link_Node* pNode = list->Head;
	node->Next = NULL;
	while (pNode->Next)
		pNode = pNode->Next;
	pNode->Next = node;
	list->_size++;
}

static void del_Node(struct Link_List* list, struct Link_Node* node) {
	struct Link_Node* pNode = list->Head;
	struct Link_Node* pCur = pNode->Next;
	while (pCur->_key != node->_key) {
		pNode = pNode->Next;
		pCur = pCur->Next;
	}
	pNode->Next = pCur->Next;
	free(pCur);
	list->_size--;
}

static struct Link_Node* in_List(struct Link_List* list, int key) {
	struct Link_Node* pCur = list->Head->Next;
	struct Link_Node* isFind = NULL;
	while (pCur) {
		if (key == pCur->_key) {
			isFind = pCur;
			break;
		}
		pCur = pCur->Next;
	}
	return isFind;
}

static int lRUCacheGet(LRU_Cache* obj, int key) {
	struct Link_Node* Find = in_List(obj->LRU_List, key);
	struct Link_Node* Temp = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	Temp->Next = NULL;
	int value = -1;
	if (Find) {
		value = Find->_val;
		Temp->_key = Find->_key, Temp->_val = Find->_val;
		del_Node(obj->LRU_List, Find);
		add_Node(obj->LRU_List, Temp);
	}
	return value;
}

static void lRUCachePut(LRU_Cache* obj, int key, int value) {
	struct Link_Node* Find = in_List(obj->LRU_List, key);
	struct Link_Node* pCur = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	struct Link_Node* Temp = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	Temp->Next = NULL;
	if (Find) {
		del_Node(obj->LRU_List, Find);
		Temp->_key = key, Temp->_val = value;
		add_Node(obj->LRU_List, Temp);
	}
	else {
		if (obj->LRU_List->_size >= obj->_capacity)
			del_Node(obj->LRU_List, obj->LRU_List->Head->Next);
		pCur->_key = key;
		pCur->_val = value;
		pCur->Next = NULL;
		add_Node(obj->LRU_List, pCur);
	}
}

static void lRUCacheFree(LRU_Cache* obj) {
	struct Link_Node* pHead = obj->LRU_List->Head;
	struct Link_Node* pCur;
	while (pHead) {
		pCur = pHead->Next;
		free(pHead);
		pHead = NULL;
		pHead = pCur;
	}
	obj->LRU_List->_size = 0;
	free(obj->LRU_List);
	obj->LRU_List = NULL;
	obj->_capacity = 0;
	free(obj);
	obj = NULL;
}

/* 测试代码 */
int main() {
	struct LRU_Cache* My_LRU = lRUCacheCreate(2);
	lRUCachePut(My_LRU, 2, 1);
	lRUCachePut(My_LRU, 2, 2);
	printf("%d\n", lRUCacheGet(My_LRU, 2));
	lRUCachePut(My_LRU, 1, 1);
	lRUCachePut(My_LRU, 4, 1);
	printf("%d\n", lRUCacheGet(My_LRU, 2));
	lRUCacheFree(My_LRU);
	return 0;
}

写在后面：

有较好的优化方法还请告知，欢迎评论！感谢赐教！