YYMemoryCache源码分析

YYCache 缓存框架

• YYMemoryCache 内存中的缓存
• YYDiskCache
• YYKVStorage

YYMemoryCache

内存缓存功能设计目标

• 对外接口是key，value进行缓存和获取
• 能够限制数量大小和总消耗cost
• 获取缓存时，支持LRU（最近最少使用），MRU（最近最多使用），Key-Value快速获取

实现基本思路

• 先用一个新的数据结构node对value数据进行封装，丰富携带信息，因为value需要很多个信息绑定在一起，包括时间，key，最近使用时间，开销等
• 使用CFMutableDictionaryRef存储<key，node>，非常方便通过key->node->value实现快速获取
• 同时又使用双向链表的设计，每一个node都有pre和next指针，根据使用情况将各个node进行排序。整个链表只需要头head指针，一个尾tail指针，就能同时实现MRU和LRU。

双向链表，节点的数据结构

/** 每一个数据节点的结构 */
@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;
    id _value;
    NSUInteger _cost;
    NSTimeInterval _time;
}
@end

/** 整个链表的结构 */
@interface _YYLinkedMap : NSObject {
    @package
    CFMutableDictionaryRef _dic; // do not set object directly
    NSUInteger _totalCost;
    NSUInteger _totalCount;
    _YYLinkedMapNode *_head; // MRU, do not change it directly
    _YYLinkedMapNode *_tail; // LRU, do not change it directly
    BOOL _releaseOnMainThread;
    BOOL _releaseAsynchronously;
}

双向链表的头插入

1. 先添加到dic，计算cost和count
2. 判断是否已存在head
   2.1 已存在，则把当前node添加到head的前面
   2.2 不存在，那就是第一个，head和tail都是node

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
    CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));
    _totalCost += node->_cost;
    _totalCount++;
    if (_head) {
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    } else {
        _head = _tail = node;
    }
}

双向链表把节点移动到第一位

1. 如果本来就是第一位，无需操作
2. 先把当前节点从链表中删除
   2.1 删除节点是最后一位？则尾部是上一位
   2.2 讲当前节点的下一位和上一位进行关联
3. 最后把当前节点替换成第一位

- (void)bringNodeToHead:(_YYLinkedMapNode *)node{
    if (_head == node) return;
    
    if (_tail == node) {
        _tail = node->_prev;
        _tail->_next = nil;
    } else {
        node->_next->_prev = node->_prev;
        node->_prev->_next = node->_next;
    }
    node->_next = _head;
    node->_prev = nil;
    _head->_prev = node;
    _head = node;
}

双向链表的删除

1. 从dic中删除key，计算cost，count
2. 处理next节点的prev
3. 处理prev节点的next
4. 是否删除的是head节点
5. 是否删除的是tail节点

- (void)removeNode:(_YYLinkedMapNode *)node {
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
    _totalCost -= node->_cost;
    _totalCount--;
    if (node->_next) node->_next->_prev = node->_prev;
    if (node->_prev) node->_prev->_next = node->_next;
    if (_head == node) _head = node->_next;
    if (_tail == node) _tail = node->_prev;
}

通过key获取缓存内容

1. 先通过key从dic中快速找出node
2. 找出来后，更新时间并且移动到链表的头部
3. 返回node->value即内容

- (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;
}

通过key添加缓存内容value

1. 没有key，啥也没法做
2. 没有object，表示删除key，
3. 如果当前key本身就有缓存，替换旧的数据，再次移动到链表头部
4. 如果当前key是新的，创建新的node，添加到链表头部
5. 超出cost/count，从tail开始清理缓存数据

- (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) {
        _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
            });
        } else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
            dispatch_async(dispatch_get_main_queue(), ^{
                [node class]; //hold and release in queue
            });
        }
    }
    pthread_mutex_unlock(&_lock);
}

iOS涉及知识点

• CFMutableDictionaryRef 的使用，与NSMutableDictionary的区别？
• MainThread和dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0)的区别
• pthread_mutex_t 线程锁的使用，
• 通过dispatch_async让一个已经没有用的对象在指定线程执行一个无用的代码进行释放