学步园

背景

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

• 字符串哈希函数研究