关注v-x-公-众-号：【嵌入式基地】
后-台-回-复：【电赛】 即可获资料
回复【编程】即可获取
包括有：C、C++、C#、JAVA、Python、JavaScript、PHP、数据库、微信小程序、人工智能、嵌入式、Linux、Unix、QT、物联网、算法导论、大数据等资料
原文链接 点击查看
5个G的计算机，电子专业书籍分享。
链接：/s/1y8BnUlGmiJMujLlTyrhznA
提取码：j9na
今天主要给大家分享下基于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");}
结果
