算法-LRU缓存淘汰算法

Posted on | In |

我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

  2. 如果此数据没有在缓存链表中，又可以分为两种情况：

    如果此时缓存未满，则将此结点直接插入到链表的头部；

    如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//数据结构
typedef struct double_link_list_node
{
    struct double_link_list_node *prev;
    struct double_link_list_node *next;
    int data;
}DoubleLinkListNode;

typedef struct double_link_list_head
{
    int size;
    DoubleLinkListNode *head;//头指针
    DoubleLinkListNode *tail;//尾指针
}DoubleLinkListHead;

void LRU_list_test(void);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <stdlib.h>
#include <string.h>


/**
 创建双向链表

 @param list 双向链表
 */
void double_link_list_create(DoubleLinkListHead *list)
{
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
}

/**
 销毁双向链表

 @param list 双向链表
 */
void double_link_list_destory(DoubleLinkListHead *list)
{
    DoubleLinkListNode *temp = NULL;
    while (list->size > 0) {
        temp = list->head;
        list->head = temp->next;
        free(temp);
        list->size--;
    }
    
    memset(list, 0, sizeof(DoubleLinkListHead));
}


/**
 头部插入

 @param list 双向链表
 @param node 需插入的节点
 @param data 需插入的数据
 @return 是否插入成功
 */
int double_link_list_insert_head(DoubleLinkListHead *list, DoubleLinkListNode *node, int data)
{
    if (node == NULL) {
        node = (DoubleLinkListNode *)malloc(sizeof(DoubleLinkListNode));
        if (node == NULL) {
            return -1;
        }
    }
    
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    
    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    }
    else {
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    
    list->size++;
    
    return 0;
}

/**
 移除尾部节点

 @param list 双向链表
 @return 移除的尾部节点
 */
DoubleLinkListNode *double_link_list_remove_tail(DoubleLinkListHead *list)
{
    DoubleLinkListNode *node = NULL;
    if (list->size == 0) {
        return NULL;
    }
    
    node = list->tail;
    if (list->size > 1) {
        list->tail = list->tail->prev;
        list->tail->next = NULL;
    }
    else {
        list->head = NULL;
        list->tail = NULL;
    }
    list->size--;
    
    return node;
}

/**
 移除节点

 @param list 双向链表
 @param node 移除的节点
 */
void double_link_list_remove_node(DoubleLinkListHead *list, DoubleLinkListNode *node)
{
    if ((list == NULL) || (node == NULL)) {
        return;
    }
    
    if (list->head == node) {
        list->head = list->head->next;
    }
    else if (list->tail == node) {
        list->tail = node->prev;
        list->tail->next = NULL;
    }
    else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    list->size--;
    node->prev = NULL;
    node->next = NULL;
    
    if (list->size == 0) {
        memset(list, 0, sizeof(DoubleLinkListHead));
    }
}

/**
 查找节点

 @param list 双向链表
 @param data 查找的数据
 @return 查找到的节点
 */
DoubleLinkListNode *double_link_list_search(DoubleLinkListHead *list, int data)
{
    DoubleLinkListNode *node = list->head;
    while (node != NULL) {
        if (node->data == data) {
            return node;
        }
        node = node->next;
    }
    return NULL;
}

/**
 遍历双向链表

 @param list 双向链表
 */
void double_link_list_dump(DoubleLinkListHead *list)
{
    int count = 0;
    printf("打印链表\n");
    DoubleLinkListNode *node = list->head;
    while (node != NULL) {
        printf("[%d] = %d\n",count++, node->data);
        node = node->next;
    }
}

/**
 LRU缓存淘汰算法

 @param list 双向链表
 @param data 数据
 */
void LRU_list(DoubleLinkListHead *list, int data)
{
    DoubleLinkListNode *node = double_link_list_search(list, data);
    if (node != NULL) {
        double_link_list_remove_node(list, node);
    }
    else if (list->size >= 4) {
        node = double_link_list_remove_tail(list);
    }
    
    double_link_list_insert_head(list, node, data);
}

/**
 LRU缓存淘汰算法测试
 */
void LRU_list_test()
{
    DoubleLinkListHead list = {0};
    DoubleLinkListNode *node = NULL;
    
    double_link_list_create(&list);
    
    printf("插入 1 2 3\n");
    double_link_list_insert_head(&list, NULL, 1);
    double_link_list_insert_head(&list, NULL, 2);
    double_link_list_insert_head(&list, NULL, 3);
    
    double_link_list_dump(&list);
    
    node = double_link_list_remove_tail(&list);
    if (node != NULL) {
        printf("删除 %d\n",node->data);
    }
    double_link_list_insert_head(&list, node, 4);
    
    double_link_list_dump(&list);
    
    LRU_list(&list, 5);
    double_link_list_dump(&list);
    
    LRU_list(&list, 6);
    double_link_list_dump(&list);
    
    LRU_list(&list, 7);
    double_link_list_dump(&list);
    
    LRU_list(&list, 5);
    double_link_list_dump(&list);
    
    while (list.size > 0) {
        node = double_link_list_remove_tail(&list);
        if (node != NULL) {
            printf("删除 %d\n", node->data);
            free(node);
        }
    }
}