背景

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

• 字符串哈希函数研究