The Design of a cache buffer 作者: 劉鵬 日期: 2008-11-26 在 GUI 系統中對資源進行高效管理是非常重要的問題。文本以圖檔管理為例，提出一個基于哈希表的 cache buffer。
背景
GUI 系統中往往會用到很多資源，如圖檔。若每次使用圖檔時都從磁盤裝入記憶體， 由于磁盤讀取速度很慢，效率會很低下。
我們可以設計一個 cache buffer，将讀進來的圖檔緩存到 cache 裡，當程式使 用圖檔時先去 cache 裡找，若 cache 沒有，再去磁盤讀取。這跟 Linux Kernel 針對磁盤塊的 cache buffer 是一樣的道理。
設計一個 cache ，需要考慮如下問題：
- cache 采用什麼樣的資料結構；
- 如何在 cache 中迅速找到需要的圖檔；
- cache 滿了之後如何處理，是否采用對換政策；若是，采用什麼樣的換出算 法。
針對上述問題，本文提出一個采用哈希表加雙向連結清單的 cache 設計政策。為了 簡化問題，暫時沒有考慮對換問題。
Buffer Cache 總體結構
使用哈希表組織和管理所有的資料，首先用哈希函數計算字元串在哪個連結清單，然 後根據 key 值順序比較連結清單元素，查找對應的字元。
哈希隊列結構示意圖如下所示:
 |
| 哈希隊列示意圖 |
哈希連結清單結點如下圖所示：
 |
| 連結清單結點結構圖 |
資料結構
資料結構代碼如下所示:
typedef struct _RESCACHENODE {
unsigned char key[LENTH];
IMAGE* *image;
int ref_count;
int is_preload;
_RESCACHNODE* pre;
_RESCACHNODE* next;
} RESCACHENODE;
#define NR_HASH_ENTRIES 20
typedef struct _RESCACHE {
RECACHENODE* res_hash_table [NR_HASH_ENTRIES];
} RESCACHE;
RESCACHE res_cache = {0};
哈希函數
哈希函數的選擇決定了查詢速度，哈希函數需要滿足以下要求：
- 計算非常快；
- 沖突均勻化。
下面是一個基于字元求和的哈希函數：
static int hash_string (const char* key)
{
int hval;
const char* ptr = (const char*) key;
char c;
int i;
hval = 0;
for (i = 1; (c = *ptr++); i++)
hval += c * i;
return (hval % NR_HASH_ENTRIES);
}
關于字元串哈希函數可見參考資源裡的“字元串哈希函數研究”。
Buffer Cache 程式設計接口
/*
* Read images files top dir.
**/
static BOOL set_res_top_dir (void);
/* Init cache: set top dir and initialize lock **/
void init_cache (void);
/*
* Load the file to IMAGE object , add a new node to the cache and
* set is_preload to FALSE.
* If the node already exists, then ref_count ++; Otherwise, load
* the Bitmap.
*
* hdc: dc
* file: key value
* Return: If succeed, return TRUE; Otherwise return FALSE.
*/
BOOL insert_into_cache_from_file (HDC hdc, const char *file);
/*
* Load the memory data to IMAGE object, create a new node to the cache
* and set is_preload to FALSE.
* If the node already exists, then ref_count ++; Otherwise, load the
* image object.
*
* hdc: dc
* file: key value
* Return: If succeed, return TRUE; Otherwise return FALSE.
**/
BOOL insert_into_cache_from_mem (HDC hdc, const char* key,
const unsigned char* data, size_t data_size);
/*
* Find an IMAGE object in cache with the key value "file".
*
* file: key value
* If found, then return the pointer of the image; Otherwise, return NULL;
*/
IMAGE* retrieve_in_cache (const char *file);
/*
* Remove the IMAGE object from cache buffer.
* If ref_count > 1, then refcount --; Otherwise, unload the IMAGE object
* and detach the node from the cache.
* If is_preload == TRUE, then do not unload IMAGE object.
*
* file: key value
* image: image object.
*/
void remove_from_cache (const char *file);
SeeAlso
- 字元串哈希函數研究