LRU算法 C语言简单实现_lru算法代码

背景

  LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

示例

  可以使用双向链表来将缓冲区页面串联起来，如上图所示，页面4，7，0被相继读入缓冲区，第四步页面需要访问页面7，然后就会去遍历该链表，发现找到了7号页面，而且此时页面没有全部用满，那么将页面7提到表头(通过更改双向链表的指针指向实现)，然后页面1被读到缓冲区，然后读取页面0，遍历链表找到了页面0并将页面0提到表头，其他步骤类似，再看看置换，比如最后一步，读取页面6，遍历链表后发现页面6没有找到，此时缓冲区已满，这时需要从缓冲区中置换掉链表最尾部(最近最少使用)的页面4进行淘汰，并且把页面6放在表头。PostgreSQL数据库中的SLRU算法思想也是基于此。

代码实现

struct HashNode {
    struct LRUNode *Node;
    struct HashNode *Next;
};

struct LRUNode {
    int Key;
    int Value;
    struct LRUNode *Next;
    struct LRUNode *Pre;
};

typedef struct {
    int Capacity;
    int Size;
    struct HashNode **Table;
    struct LRUNode *Head;
    struct LRUNode *Tail;
} LRUCache;

int Hash(int key, int capacity) {
    return key % capacity;
}

void Insert(struct HashNode *T, struct LRUNode *P) {
    //向哈希表某一排插,如果是正常哈希表，一般在这里面算哈希值
    //但对于这里因为插之前一定是算过哈希的，所以可以直接往那一排来插
    struct HashNode *NewNode = malloc(sizeof(struct HashNode));
    NewNode->Node = P;
    NewNode->Next = T->Next;
    T->Next = NewNode;
}

void Remove(LRUCache *obj, struct LRUNode *Target) {//满了，在双向链表和哈希中删去tail
    //在哈希表中删
    int index = Hash(Target->Key, obj->Capacity);
    struct HashNode *P = obj->Table[index]->Next;
    struct HashNode *Pre = obj->Table[index];
    while(P!=NULL) {
        if(P->Node->Key==Target->Key) {
            Pre->Next = P->Next;
            free(P);
            break;
        }
        P = P->Next;
        Pre = Pre->Next;
    }
    //在双向链表中删
    obj->Tail->Pre = Target->Pre;
    Target->Pre->Next = obj->Tail;
    //不释放Target，因为接下来可以继续用，只需修改下key,value
}

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache *obj = malloc(sizeof(LRUCache));
    obj->Capacity = capacity;
    obj->Size = 0;
    //创建哈希表
    obj->Table = malloc(sizeof(struct HashNode *) * capacity);
    for(int i=0; i<capacity; i++) {
        obj->Table[i] = malloc(sizeof(struct HashNode));
        obj->Table[i]->Node = malloc(sizeof(struct LRUNode));
        obj->Table[i]->Next = NULL;
    }
    //创建双向链表
    obj->Head = malloc(sizeof(struct LRUNode));
    obj->Tail = malloc(sizeof(struct LRUNode));
    obj->Head->Pre = NULL;
    obj->Head->Next = obj->Tail;
    obj->Tail->Pre = obj->Head;
    obj->Tail->Next = NULL;
    obj->Head->Key = -1;
    obj->Tail->Key = -1;
    obj->Head->Value = 0;
    obj->Tail->Value = 0;
    return obj;
}

void Update(struct LRUNode *H, struct LRUNode *Target) {
    if(!(Target->Pre==NULL&&Target->Next==NULL)) {//不是新加入的点，要调整一下之前的结构
        Target->Next->Pre = Target->Pre;
        Target->Pre->Next = Target->Next;
    }
    Target->Next = H->Next;
    Target->Next->Pre = Target;
    H->Next = Target;
    Target->Pre = H;
}

int lRUCacheGet(LRUCache* obj, int key) {
    int index = Hash(key, obj->Capacity);
    struct HashNode *P = obj->Table[index]->Next;
    while (P!=NULL)
    {
        if(P->Node->Key == key) {
            Update(obj->Head, P->Node);
            return P->Node->Value;
        }
        P = P->Next;
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    int index = Hash(key, obj->Capacity);
    int flag = 1;//记录哈希表中是否已存在，1不存在，0存在
    struct HashNode *P = obj->Table[index]->Next;
    while(P!=NULL) {
        if(P->Node->Key==key) {
            P->Node->Value = value;
            flag = 0;
            Update(obj->Head, P->Node);
            break;
        }
        P = P->Next;
    }
    if(flag) {//不存在，新建hashnode放进去
        struct HashNode *NewHashNode = malloc(sizeof(struct HashNode));
        if(obj->Size==obj->Capacity) {//满了，需要删
            struct LRUNode *Target = obj->Tail->Pre;
            Remove(obj, Target);
            (obj->Size)--;
            Target->Key = key;
            Target->Value = value;
            Target->Pre = NULL;
            Target->Next = NULL;
            NewHashNode->Node = Target;//直接拿来用，不用新分配了
        } else {
            NewHashNode->Node = malloc(sizeof(struct LRUNode));
            NewHashNode->Node->Key = key;
            NewHashNode->Node->Value = value;
            NewHashNode->Node->Next = NULL;
            NewHashNode->Node->Pre = NULL;
        }
        //在双向链表插
        Update(obj->Head, NewHashNode->Node);
        //在哈希表插
        int addIndex = Hash(key, obj->Capacity);
        Insert(obj->Table[addIndex], NewHashNode->Node);
        (obj->Size)++;
    }
    
}

void lRUCacheFree(LRUCache* obj) {
    free(obj->Table);
    free(obj->Head);
    free(obj->Tail);
    free(obj);
}
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

C++案例

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    /* 构造函数便于新定义节点时初始化对象 */
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> map;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;       // 缓冲区使用的大小
    int capacity;   // 缓冲区的容量

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        /* 使用伪头部和伪尾部节点 */
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    /* 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 */
    int get(int key) {
        if (!map.count(key)) return -1;
        /* 如果 key 存在，先通过哈希表定位，再移到头部 */
        DLinkedNode* node = map[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!map.count(key)) {
            /* 如果 key 不存在，创建一个新的节点 */
            DLinkedNode* node = new DLinkedNode(key, value);
            /* 添加进哈希表 */
            map[key] = node;
            /* 添加至双向链表的头部 */
            addToHead(node);
            /* 缓存大小+1 */
            size++;
            if (size > capacity) {
                DLinkedNode* removed = removeTail();// 如果超出容量，删除双向链表的尾部节点
                map.erase(removed->key);// 删除哈希表中对应的项
                delete removed;// 防止内存泄漏
                size--;// 缓存大小-1
            }
        }
        else {
            /* 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部 */
            DLinkedNode* node = map[key];
            node->value = value;
            moveToHead(node);
        }
    }

/****************定义双向链表需要用的API函数****************/
public:
    /* 在虚拟头节点后添加新的节点 node */
    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    /* 删除当前节点 node 这里也是为什么使用双向链表的原因方便删除节点 */
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    /* 把出现频率比较高的节点放入 头部 */
    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }
    /* 移除尾部节点 并返回尾部最后一个节点 */
    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};
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