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
- 字符串哈希函数研究