今天主要給大家分享下基于C語言實現(xiàn)的LRU緩存淘汰算法。

• 緩存，是一種提高數(shù)據(jù)讀取性能的技術，不論是在硬件，還是軟件設計中都會被廣泛的應用。

• 在軟件設計中，緩存的大小總是有限的。當緩存被使用完時，就需要對數(shù)據(jù)進行清理。在清理數(shù)據(jù)時，經(jīng)常會使用到緩存淘汰策略來決定清理哪些不需要的數(shù)據(jù)。

常見的策略有下面三種：

• 先進先出策略FIFO

• 最少使用策略LFU

• 最近最少使用策略LRU

一般采用鏈表實現(xiàn)LRU，基本的思路如下

首先需要在緩存中維護一個雙向鏈表，鏈表中的數(shù)據(jù)按照訪問的時間從新到舊排列。當有一個數(shù)據(jù)被訪問時，我們從鏈表頭開始順序遍歷。

如果該數(shù)據(jù)在此之前已經(jīng)被放入到了緩存中

• 我們需要將該數(shù)據(jù)的節(jié)點從原位置刪除，然后重新將其放入到鏈表的表頭。

如果該數(shù)據(jù)在這之前沒有被放入緩存中

• 如果此時緩存沒有滿，則將此數(shù)據(jù)放入到鏈表的表頭。

• 如果此時緩存已滿，則需要先將鏈表尾部的數(shù)據(jù)刪除，之后將該數(shù)據(jù)放入鏈表的表頭。

上述方法在我們需要從緩存中查找數(shù)據(jù)時，都需要遍歷一遍數(shù)據(jù)。因此，這種做法的時間復雜度為O(n)。

使用哈希表保證緩存的訪問速度

為了提高上述方法的時間復雜度，我們除了需要將數(shù)據(jù)維護在雙向鏈表中，還需要將數(shù)據(jù)維護在哈希表中。哈希表的數(shù)據(jù)訪問的時間復雜度為O(1)

LRU緩存內部數(shù)據(jù)結構

• LRU緩存包含了一個雙向鏈表和一個哈希表

/* 定義LRU緩存 */ typedef struct LRUCacheS{ sem_t cache_lock; int cacheCapacity; /*緩存的容量*/ int lruListSize; /*緩存的雙向鏈表節(jié)點個數(shù)*/ cacheEntryS **hashMap; /*緩存的哈希表*/ cacheEntryS *lruListHead; /*緩存的雙向鏈表表頭*/ cacheEntryS *lruListTail; /*緩存的雙向鏈表表尾*/ }LRUCacheS;

緩存中的數(shù)據(jù)單元

• 緩存中的數(shù)據(jù)單元，既是一個雙向鏈表的節(jié)點，也是哈希表中的一個節(jié)點。

typedef struct cacheEntryS{ char key[KEY_SIZE]; /* 數(shù)據(jù)的key */ char data[VALUE_SIZE]; /* 數(shù)據(jù)的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; //創(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"); //按照順序輸出緩存器當前的內容 LRUCachePrint(LruCache); //獲取緩存器內容 if (NULL == LRUCacheGet(LruCache, "key1")){ printf("key1 所對應的數(shù)據(jù)未被緩存\n");
 } else{ char data[VALUE_SIZE]; strncpy(data, LRUCacheGet(LruCache, "key1"), VALUE_SIZE); printf("key1所對應的數(shù)據(jù)為:%s", data);
 } char value4[VALUE_SIZE]; strncpy(value4, LRUCacheGet(LruCache, "key4"), VALUE_SIZE); printf("key4所對應的數(shù)據(jù):%s", value4);

 LRUCachePrint(LruCache); //銷毀緩存器 if (0 != LRUCacheDestory(LruCache)) printf("destory error");
}

• 結果

項目下載

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