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

📝缓存Cache

缓存是以键值对的形式进行数据的存储和检索，内部采用哈希表实现。当系统出现内存压力时则会释放掉部分缓存的键值对。 iOS系统提供了一套基于OC语言的高级缓存库NSCache，同时也提供一套基于C语言实现的缓存库libcache.dylib，其中NSCache是基于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;   //当值的引用计数从0变为1时对值内存进行非purgeable的处理函数。
    cache_value_make_purgeable_cb_t value_make_purgeable_cb;  //当值的引用计数变为0时对值进行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);

//将缓存中的值引用计数减1，当引用计数为0时则清理值分配的内存或者销毁值分配的内存。
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时则值分配的内存会设置为可清理(purgeable)或者被销毁掉。

3、cache_remove函数用于删除缓存中的键值对。当删除缓存中的键值对时，缓存对象会调用属性结构体中的key_release_cb函数进行键的内存销毁，以及如果值的引用计数变为0时则会调用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);
    ret = cache_release_value(cache, val);
    //获取键值对，使用后要释放。
    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);
}

三、缓存中键值对的清理策略和值的访问策略

缓存的作用是会对保存在里面的键值对进行丢弃，这取决于当前内存的使用情况以及其他一些场景。在调用cache_set_and_retain将键值对添加到缓存时还会指定一个cost值，值越大被丢弃的可能性就越低。在上面的介绍中有说明缓存会对键值对中的值进行引用计数管理。当调用cache_set_and_retain时值引用计数将设置为1，调用cache_get_and_retain函数获取值时如果键值对在缓存中则会增加值的引用计数。而不需要访问和操作值时我们需要调用cache_release_value函数来将引用计数减1。当值的引用计数变为0时就会立即或者以后发生如下的事情：

1、如果我们在缓存的属性结构体中设置了value_make_purgeable_cb函数则会调用这个函数表明此时值是可以被清理的。被清理的意思是说为值分配的物理内存随时有可能会被回收。因此当值被设置为可被清理状态时就不能继续去直接访问值所分配的内存了。
2、如果在此之前键值对因为函数cache_remove的调用而被从缓存中删除，则会调用属性结构体中的value_release_cb函数来执行值内存的销毁处理。
3、如果因为系统内存的压力导致需要丢弃缓存中的键值对时，就会把值引用计数为0的键值对丢弃掉！注意：只有值引用计数为0时才会缓存被丢弃。

每次对缓存中的值的访问都需要通过cache_get_and_retain函数来执行，当调用cache_get_and_retain函数时会发生如下事情：

1、判断当前键值对是否在缓存中，如果不再则值返回NULL。
2、如果键值对在缓存中。并且值的引用计数为0，就会判断缓存的结构体属性中是否存在value_make_nonpurgeable_cb函数，如果存在则会调用value_make_nonpurgeable_cb函数将值的内存设置为不可清理，如果设置为不可清理返回为false则表明此时值的内存已经被清理了，这时候键值对将会从缓存中丢弃，并且cache_get_and_retain函数将返回值为NULL。当然如果value_make_nonpurgeable_cb函数为空则不会发生这一步。
3、增加值的引用计数，并返回值。

链接：https://www.jianshu.com/p/2f58f165bf1a