iOS YYMemoryCache

YYMemoryCache

YYCache是由ibireme 开发的组件库 YYKit 中的一款独立的高性能 iOS 缓存框架。
YYMemoryCache则是YYCache 中的一种存储键值对的快速内存缓存框架。与 NSDictionary 相比，键被保留而不被复制。API 和性能类似于NSCache，使用互斥锁保证所有方法都是线程安全的。另外，缓存内部用双向链表和 NSDictionary 实现了 LRU 淘汰算法
YYMemoryCache 和 NSCache 的不同点:

YYMemoryCache使用 LRU（最近最少使用）来删除对象； NSCache 的eviction方法是非确定性的。
YYMemoryCache可以通过成本、数量和年龄来控制； NSCache 的限制是不精确的。
YYMemoryCache可以配置为在收到内存警告或应用程序进入后台时自动驱逐对象。

#pragma mark - Access Methods
///=============================================================================
/// @name Access Methods
///=============================================================================

/**
 返回一个布尔值，指示给定键是否在缓存中。
 */
- (BOOL)containsObjectForKey:(id)key;
/**
 返回与给定键关联的值。
 */
- (nullable id)objectForKey:(id)key;
/**
 设置缓存中指定键的值（0 成本）。
 */
- (void)setObject:(nullable id)object forKey:(id)key;
/**
 设置缓存中指定key的值，并关联key-value
 与指定的成本配对。
 */
- (void)setObject:(nullable id)object forKey:(id)key withCost:(NSUInteger)cost;

- (void)removeObjectForKey:(id)key;

- (void)removeAllObjects;

containsObjectForKey的实现

- (BOOL)containsObjectForKey:(id)key {
    if (!key) return NO;
    pthread_mutex_lock(&_lock);//使用互斥锁保证read线程安全
    BOOL contains = CFDictionaryContainsKey(_lru->_dic, (__bridge const void *)(key));
    pthread_mutex_unlock(&_lock);
    return contains;
}

objectForKey的实现

- (id)objectForKey:(id)key {
    if (!key) return nil;//非空判断
    pthread_mutex_lock(&_lock);//线程安全
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        node->_time = CACurrentMediaTime();
        [_lru bringNodeToHead:node];//将使用后的节点置为头节点
    }
    pthread_mutex_unlock(&_lock);
    return node ? node->_value : nil;
}

setObject:forKey:withCost:的实现

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    if (!key) return;
    if (!object) {
        [self removeObjectForKey:key];
        return;
    }
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    NSTimeInterval now = CACurrentMediaTime();
    if (node) {//调整cost , 若存在队列中
        _lru->_totalCost -= node->_cost;
        _lru->_totalCost += cost;
        node->_cost = cost;
        node->_time = now;
        node->_value = object;
        [_lru bringNodeToHead:node];
    } else {
        node = [_YYLinkedMapNode new];
        node->_cost = cost;
        node->_time = now;
        node->_key = key;
        node->_value = object;
        [_lru insertNodeAtHead:node];
    }
    if (_lru->_totalCost > _costLimit) {
        dispatch_async(_queue, ^{
            [self trimToCost:_costLimit];
        });
    }
    if (_lru->_totalCount > _countLimit) {
        _YYLinkedMapNode *node = [_lru removeTailNode];//进行淘汰
        if (_lru->_releaseAsynchronously) {
            dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();//
            dispatch_async(queue, ^{
                [node class]; //hold and release in queue  在特定的queue里释放
/*
应该是node在执行完这个方法后就出了作用域了，reference会减1，
但是此时node不会被dealloc，因为block 中retain了node，
使得node的reference count为1，当执完block后，node的reference count又-1，
此时node就会在block对应的queue上release了。
*/
            });
        } else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
            dispatch_async(dispatch_get_main_queue(), ^{
                [node class]; //hold and release in queue
            });
        }
    }
    pthread_mutex_unlock(&_lock);
}

在 _YYLinkedMap 类中使用双链表+哈希表实现LRU算法

插入：当Cache未满时，新的数据项只需插到双链表头部即可
替换：当Cache已满时，将新的数据项插到双链表头部，并删除双链表的尾结点即可
查找：每次数据项被查询到时，都将此数据项移动到链表头部

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
   //使用字典保存链表节点node
    CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));
    //叠加该缓存开销到内存总开销
    _totalCost += node->_cost;
    //总缓存数+1
    _totalCount++;
    if (_head) { //如果存在头部节点,则将node 置为 头节点
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    } else {//如果不存在,则将node置为当前唯一节点
        _head = _tail = node;
    }
}

- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
    if (_head == node) return;//如果当前节点是表头

    if (_tail == node) {//如果当前节点是尾节点
        _tail = node->_prev;//将node的前驱结点指向尾节点
        _tail->_next = nil;//将尾节点的后继节点置空
    } else {
        node->_next->_prev = node->_prev;//将node指向的下一个节点的前驱节点,指向node的前驱节点
        node->_prev->_next = node->_next;//将node指向的上一个节点的后继节点,指向node的后继节点,从链表中剥离出node
    }
    node->_next = _head;//将node的后继节点指向当前头节点
    node->_prev = nil;//将node的前驱节点置空
    _head->_prev = node;//此时的头节点的前驱指向node
    _head = node;//将此时的node置为头节点
}

- (void)removeNode:(_YYLinkedMapNode *)node {//前提是node为链表中的一个节点
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
    _totalCost -= node->_cost;//调整总开销
    _totalCount--;//调整总缓存数
    if (node->_next) node->_next->_prev = node->_prev;//如果node 存在后继节点,则将node的后继节点的前驱指向node的前驱结点
    if (node->_prev) node->_prev->_next = node->_next;//如果node 存在前驱节点,则将node的前驱节点的后继指向node的后继节点
    if (_head == node) _head = node->_next;//如果node是头节点,则将node的后继节点置为头节点
    if (_tail == node) _tail = node->_prev;//如果node是尾节点, 则将node的前驱结点置为尾节点
}

Kerwin

iOS YYMemoryCache