C語言實(shí)現(xiàn)LRU緩存策略
掃描二維碼
隨時(shí)隨地手機(jī)看文章
今天主要給大家分享下基于C語言實(shí)現(xiàn)的LRU緩存淘汰算法。
-
緩存，是一種提高數(shù)據(jù)讀取性能的技術(shù)，不論是在硬件，還是軟件設(shè)計(jì)中都會(huì)被廣泛的應(yīng)用。
-
在軟件設(shè)計(jì)中，緩存的大小總是有限的。當(dāng)緩存被使用完時(shí)，就需要對(duì)數(shù)據(jù)進(jìn)行清理。在清理數(shù)據(jù)時(shí)，經(jīng)常會(huì)使用到緩存淘汰策略來決定清理哪些不需要的數(shù)據(jù)。
常見的策略有下面三種：
-
先進(jìn)先出策略FIFO
-
最少使用策略LFU
-
最近最少使用策略LRU
一般采用鏈表實(shí)現(xiàn)LRU，基本的思路如下
首先需要在緩存中維護(hù)一個(gè)雙向鏈表，鏈表中的數(shù)據(jù)按照訪問的時(shí)間從新到舊排列。當(dāng)有一個(gè)數(shù)據(jù)被訪問時(shí)，我們從鏈表頭開始順序遍歷。
如果該數(shù)據(jù)在此之前已經(jīng)被放入到了緩存中
-
我們需要將該數(shù)據(jù)的節(jié)點(diǎn)從原位置刪除，然后重新將其放入到鏈表的表頭。
如果該數(shù)據(jù)在這之前沒有被放入緩存中
-
如果此時(shí)緩存沒有滿，則將此數(shù)據(jù)放入到鏈表的表頭。
-
如果此時(shí)緩存已滿，則需要先將鏈表尾部的數(shù)據(jù)刪除，之后將該數(shù)據(jù)放入鏈表的表頭。
上述方法在我們需要從緩存中查找數(shù)據(jù)時(shí)，都需要遍歷一遍數(shù)據(jù)。因此，這種做法的時(shí)間復(fù)雜度為O(n)。
使用哈希表保證緩存的訪問速度
為了提高上述方法的時(shí)間復(fù)雜度，我們除了需要將數(shù)據(jù)維護(hù)在雙向鏈表中，還需要將數(shù)據(jù)維護(hù)在哈希表中。哈希表的數(shù)據(jù)訪問的時(shí)間復(fù)雜度為O(1)
LRU緩存內(nèi)部數(shù)據(jù)結(jié)構(gòu)
-
LRU緩存包含了一個(gè)雙向鏈表和一個(gè)哈希表
/* 定義LRU緩存 */ typedef struct LRUCacheS{ sem_t cache_lock; int cacheCapacity; /*緩存的容量*/ int lruListSize; /*緩存的雙向鏈表節(jié)點(diǎn)個(gè)數(shù)*/ cacheEntryS **hashMap; /*緩存的哈希表*/ cacheEntryS *lruListHead; /*緩存的雙向鏈表表頭*/ cacheEntryS *lruListTail; /*緩存的雙向鏈表表尾*/ }LRUCacheS;
緩存中的數(shù)據(jù)單元
-
緩存中的數(shù)據(jù)單元，既是一個(gè)雙向鏈表的節(jié)點(diǎn)，也是哈希表中的一個(gè)節(jié)點(diǎn)。
typedef struct cacheEntryS{ char key[KEY_SIZE]; /* 數(shù)據(jù)的key */ char data[VALUE_SIZE]; /* 數(shù)據(jù)的data */ sem_t entry_lock; struct cacheEntryS *hashListPrev; /* 緩存哈希表指針， 指向哈希鏈表的前一個(gè)元素 */ struct cacheEntryS *hashListNext; /* 緩存哈希表指針， 指向哈希鏈表的后一個(gè)元素 */ struct cacheEntryS *lruListPrev; /* 緩存雙向鏈表指針， 指向鏈表的前一個(gè)元素 */ struct cacheEntryS *lruListNext; /* 緩存雙向鏈表指針， 指向鏈表后一個(gè)元素 */ }cacheEntryS;
測(cè)試
int main(int argc, char **argv){ void *LruCache; //創(chuàng)建緩存器 if (0 == LRUCacheCreate(3, &LruCache)) printf("緩存器創(chuàng)建成功，容量為3\n"); //向緩存器中添加數(shù)據(jù) 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"); //按照順序輸出緩存器當(dāng)前的內(nèi)容 LRUCachePrint(LruCache); //獲取緩存器內(nèi)容 if (NULL == LRUCacheGet(LruCache, "key1")){ printf("key1 所對(duì)應(yīng)的數(shù)據(jù)未被緩存\n"); } else{ char data[VALUE_SIZE]; strncpy(data, LRUCacheGet(LruCache, "key1"), VALUE_SIZE); printf("key1所對(duì)應(yīng)的數(shù)據(jù)為:%s", data); } char value4[VALUE_SIZE]; strncpy(value4, LRUCacheGet(LruCache, "key4"), VALUE_SIZE); printf("key4所對(duì)應(yīng)的數(shù)據(jù):%s", value4); LRUCachePrint(LruCache); //銷毀緩存器 if (0 != LRUCacheDestory(LruCache)) printf("destory error"); }
-
結(jié)果
項(xiàng)目下載
https://github.com/Lighter-z/c_demo
下載文檔
