iOS标准库中常用数据结构和算法之cache

缓存是以键值对的形式进行数据的存储和检索，内部采用哈希表实现。当系统出现内存压力时则会释放掉部分缓存的键值对。 iOS系统提供了一套基于OC语言的高级缓存库NSCache，同时也提供一套基于 C语言 实现的缓存库libcache.dylib，本文主要介绍基于C语言的缓存库的各种API函数。

头文件： #include <cache.h>, #include <cache_callbacks.h>

平台： iOS系统

一、缓存对象的创建和关闭

功能：创建或者销毁一个缓存对象。

函数签名：

int cache_create(const char *name, cache_attributes_t *attrs, cache_t **cache_out);
int cache_destroy(cache_t *cache);
复制代码

参数：

name:[in] 创建缓存时用来指定缓存的字符串名称，不能为空。

attrs: [in] 设置缓存的属性。不能为空。

cache_out: [out] 返回创建的缓存对象。

return: [out] 成功操作返回0，否则返回非0

描述:

缓存对象是一个容器对象，其缓存的内容是一个个键值对，至于这些键值对是什么类型的数据，如何控制键值对的数据的生命周期，如何判断两个键是否是相同的键等等这些信息缓存对象本身是无法得知，因此需要我们明确的告诉缓存对象如何去操作这些键值信息。这也就是为什么在创建缓存对象时需要指定属性这个参数了。属性的参数类型是一个cache_attributes_t结构体。这个结构体的大部分数据成员都是函数指针，这些函数指针就是用来实现对键值进行操作的各种策略。

struct cache_attributes_s {
    uint32_t version;  //缓存对象的版本信息
    cache_key_hash_cb_t key_hash_cb;  //对键执行hash计算的函数，不能为空                         
    cache_key_is_equal_cb_t key_is_equal_cb;  //判断两个键是否相等的函数，不能为空                      
    
    cache_key_retain_cb_t  key_retain_cb;   //键加入缓存时调用，用于增加键的引用计数或者进行内存拷贝。
    cache_release_cb_t key_release_cb;  //键的释放处理函数，用于对键的内存管理使用。
    cache_release_cb_t value_release_cb;  //值的释放处理函数，用于对值的内存管理使用。                         
    
    cache_value_make_nonpurgeable_cb_t value_make_nonpurgeable_cb;   //对值内存的非purgeable处理函数。
    cache_value_make_purgeable_cb_t value_make_purgeable_cb;  //对值的purgeable的处理函数。       
    
    void *user_data;  //附加数据，这个附加数据会在所有的这些回调函数中出现。

	// Added in CACHE_ATTRIBUTES_VERSION_2
	cache_value_retain_cb_t value_retain_cb;   //值增加引用计数的函数，用于对值的内存管理使用。
};
typedef struct cache_attributes_s cache_attributes_t;

复制代码

上述的各种回调函数的格式都在cache.h中有明确的定义，因此这里就不再展开介绍了。一般情况下我们通常都会将字符串或者整数来作为键使用，因此当你采用字符串或者整数作为键时，系统预置了一系列缓存对象属性的默认实现函数。这些函数的声明在cache_callbacks.h文件中

/*
 * Pre-defined callback functions.
 */

//用于键进行哈希计算的预置函数
CACHE_PUBLIC_API uintptr_t cache_key_hash_cb_cstring(void *key, void *unused);
CACHE_PUBLIC_API uintptr_t cache_key_hash_cb_integer(void *key, void *unused);
//用于键进行相等比较的预置函数
CACHE_PUBLIC_API bool cache_key_is_equal_cb_cstring(void *key1, void *key2, void *unused);
CACHE_PUBLIC_API bool cache_key_is_equal_cb_integer(void *key1, void *key2, void *unused);

//键值进行释放的函数，这函数默认实现就是调用free函数，因此如果采用这个函数进行释放处理则键值需要从堆中进行内存分配。
CACHE_PUBLIC_API void cache_release_cb_free(void *key_or_value, void *unused);

 //对值进行purgeable处理的预置函数。
CACHE_PUBLIC_API void cache_value_make_purgeable_cb(void *value, void *unused);
CACHE_PUBLIC_API bool cache_value_make_nonpurgeable_cb(void *value, void *unused);

复制代码

示例代码：

//下面代码用于创建一个以字符串为键的缓存对象，其中的缓存对象的属性中的各个成员函数采用的是系统默认预定的函数。
 #include <cache.h>
 #include <cache_callbcaks.h>

 cache_t *im_cache;
 cache_attributes_t attrs = {
         .version = CACHE_ATTRIBUTES_VERSION_2,
         .key_hash_cb = cache_key_hash_cb_cstring,
         .key_is_equal_cb = cache_key_is_equal_cb_cstring,
         .key_retain_cb = my_copy_string,
         .key_release_cb = cache_release_cb_free,
         .value_release_cb = cache_release_cb_free,
  };
  cache_create("com.acme.im_cache", &attrs, &im_cache);
复制代码

二、缓存对象中键值对的设置和获取以及删除

功能：用于处理键值对在缓存中的添加、获取和删除操作。

函数签名:

//将键值对添加到缓存，或者替换掉原有的键值对。
 int cache_set_and_retain(cache_t *cache, void *key, void *value, size_t cost);

//从缓存中根据键获取值
int cache_get_and_retain(cache_t *cache, void *key, void **value_out);

//释放缓存中的值
int cache_release_value(cache_t *cache, void *value);

//从缓存中删除键值。
int cache_remove(cache_t *cache, void *key);

复制代码

参数：

cache:[in] 缓存对象。

key:[in] 添加或者获取或者删除时的键。

cost:[in] 添加缓存时的成本代价，值越大键值在缓存中保留的时间就越长久。

value:[in] 添加时的值。

value_out: [out] 用于值获取时的输出。

描述：

1. cache_set_and_retain 函数用于将键值对放入缓存中，并指定cost值。当将一个键添加到缓存时，系统内部分别会调用缓存属性cache_attributes_t结构体中的key_retain_cb来实现对键的内存的管理，如果这个函数设置为NULL的话那就表明我们需要自己负责键的生命周期的管理。因为缓存对象内部是通过哈希表来进行数据的存储和检索的，所以在将键值对加入缓存时，还需要提供对键进哈希计算和比较的属性函数key_hash_cb，key_is_equal_cb。 而对于值来说，当值加入缓存时系统会将值的引用计数设置为1，如果我们想自定义值的引用计数时则需要指定缓存属性中的value_retain_cb来实现，加入缓存中的值是可以为NULL的。最后的cost参数用于指定这个键值对的成本值，值越小在缓存中保留的时间就越少，反之亦然。

2. cache_get_and_retain函数用来根据键获取对应的值，如果缓存中没有保存对应的键值对，则value_out返回NULL，并且函数返回特殊的值ENOENT。每调用一次值的获取，缓存对象都会增加值的引用计数。因此当我们不再需要访问返回的值时则需要调用手动调用cache_release_value函数来减少缓存对象中值的引用计数。而当值的引用计数变为0时则缓存对象会调用属性结构中的value_release_cb函数来实现值的销毁和释放处理。

3. cache_remove函数用于删除缓存中的键值对。当删除缓存中的键值对时，缓存对象会调用属性结构体中的key_release_cb和value_release_cb函数来进行引用计数管理，从而删除对应的键值对。

示例代码:

#include <cache.h>
#include <cache_callbacks.h>

void main()
{
    cache_attributes_t attr;
    attr.key_hash_cb = cache_key_hash_cb_cstring;
    attr.key_is_equal_cb = cache_key_is_equal_cb_cstring;
    attr.key_retain_cb =  NULL;
    attr.key_release_cb = cache_release_cb_free;
    attr.version = CACHE_ATTRIBUTES_VERSION_2;
    attr.user_data = NULL;
    attr.value_retain_cb = NULL;
    attr.value_release_cb = cache_release_cb_free;
    attr.value_make_purgeable_cb = cache_value_make_purgeable_cb;
    attr.value_make_nonpurgeable_cb = cache_value_make_nonpurgeable_cb;
    
    //创建缓存
    cache_t *cache = NULL;
    int ret = cache_create("com.test", &attr, &cache);
    
    //将键值对放入缓存
    char *key = malloc(4);
    strcpy(key, "key");
    char *val = malloc(4);
    strcpy(val, "val");
    ret = cache_set_and_retain(cache, key, val, 0);
    
    //获取键值对，使用后要释放。
    char *val2 = NULL;
    ret = cache_get_and_retain(cache, key, (void**)&val2);
    ret = cache_release_value(cache, val2);
    
    //删除键值
    cache_remove(cache, key);
    
    //销毁缓存。
    cache_destroy(cache);
}
复制代码

欢迎大家访问欧阳大哥2013的 github地址 和 简书地址