vlambda博客
学习文章列表

今天主要给大家分享下基于C语言实现的LRU缓存淘汰算法。

• 缓存，是一种提高数据读取性能的技术，不论是在硬件，还是软件设计中都会被广泛的应用。

• 在软件设计中，缓存的大小总是有限的。当缓存被使用完时，就需要对数据进行清理。在清理数据时，经常会使用到缓存淘汰策略来决定清理哪些不需要的数据。

常见的策略有下面三种：

• 先进先出策略FIFO

• 最少使用策略LFU

• 最近最少使用策略LRU

一般采用链表实现LRU，基本的思路如下

首先需要在缓存中维护一个双向链表，链表中的数据按照访问的时间从新到旧排列。当有一个数据被访问时，我们从链表头开始顺序遍历。

如果该数据在此之前已经被放入到了缓存中

• 我们需要将该数据的节点从原位置删除，然后重新将其放入到链表的表头。

如果该数据在这之前没有被放入缓存中

• 如果此时缓存没有满，则将此数据放入到链表的表头。

• 如果此时缓存已满，则需要先将链表尾部的数据删除，之后将该数据放入链表的表头。

上述方法在我们需要从缓存中查找数据时，都需要遍历一遍数据。因此，这种做法的时间复杂度为O(n)。

使用哈希表保证缓存的访问速度

为了提高上述方法的时间复杂度，我们除了需要将数据维护在双向链表中，还需要将数据维护在哈希表中。哈希表的数据访问的时间复杂度为O(1)

LRU缓存内部数据结构

• LRU缓存包含了一个双向链表和一个哈希表

/* 定义LRU缓存 */
typedef struct LRUCacheS{
    sem_t cache_lock;
    int cacheCapacity;  /*缓存的容量*/
    int lruListSize;    /*缓存的双向链表节点个数*/

    cacheEntryS **hashMap;  /*缓存的哈希表*/

    cacheEntryS *lruListHead;   /*缓存的双向链表表头*/
    cacheEntryS *lruListTail;   /*缓存的双向链表表尾*/
}LRUCacheS;

缓存中的数据单元

• 缓存中的数据单元，既是一个双向链表的节点，也是哈希表中的一个节点。

typedef struct cacheEntryS{
    char key[KEY_SIZE];   /* 数据的key */
    char data[VALUE_SIZE];  /* 数据的data */

    sem_t entry_lock;

    struct cacheEntryS *hashListPrev;   /* 缓存哈希表指针， 指向哈希链表的前一个元素 */
    struct cacheEntryS *hashListNext;   /* 缓存哈希表指针， 指向哈希链表的后一个元素 */

    struct cacheEntryS *lruListPrev;    /* 缓存双向链表指针， 指向链表的前一个元素 */
    struct cacheEntryS *lruListNext;    /* 缓存双向链表指针， 指向链表后一个元素 */
}cacheEntryS;

测试

int main(int argc, char **argv){
    void *LruCache;

    //创建缓存器
    if (0 == LRUCacheCreate(3, &LruCache))
        printf("缓存器创建成功，容量为3\n");

    //向缓存器中添加数据
    if (0 != LRUCacheSet(LruCache, "key1", "value1"))
        printf("put (key1, value1) failed!\n");

    if (0 != LRUCacheSet(LruCache, "key2", "value2"))
        printf("put (key2, value2) failed!\n");

    if (0 != LRUCacheSet(LruCache, "key3", "value3"))
        printf("put (key3, value3) failed!\n");

    if (0 != LRUCacheSet(LruCache, "key4", "value4"))
        printf("put (key4, value4) failed!\n");

    if (0 != LRUCacheSet(LruCache, "key5", "value5"))
        printf("put (key5, value5) failed!\n");

    //按照顺序输出缓存器当前的内容
    LRUCachePrint(LruCache);

    //获取缓存器内容
    if (NULL == LRUCacheGet(LruCache, "key1")){
        printf("key1 所对应的数据未被缓存\n");
    }
    else{
        char data[VALUE_SIZE];
        strncpy(data, LRUCacheGet(LruCache, "key1"), VALUE_SIZE);
        printf("key1所对应的数据为:%s", data);
    }

    char value4[VALUE_SIZE];
    strncpy(value4, LRUCacheGet(LruCache, "key4"), VALUE_SIZE);
    printf("key4所对应的数据:%s", value4);

    LRUCachePrint(LruCache);

    //销毁缓存器
    if (0 != LRUCacheDestory(LruCache))
        printf("destory error");
}

• 结果

项目下载

https://github.com/Lighter-z/c_demo