YYCache源码分析(二)

原文链接：http://www.jianshu.com/p/492c3c3a0485

本文分析YYMemoryCache实现原理：

Mou icon

YYMemoryCache是内存缓存，所以存取速度非常快，主要用到两种数据结构的LRU(Least Recently Used 近期最少使用算法)淘汰算法

1.LRU

Cache的容量是有限的，当Cache的空间都被占满后，如果再次发生缓存失效，就必须选择一个缓存块来替换掉.LRU法是依据各块使用的情况， 总是选择那个最长时间未被使用的块替换。这种方法比较好地反映了程序局部性规律

2.LRU主要采用两种数据结构实现

• 双向链表（Doubly Linked List）
• 哈希表（Dictionary）

3.对一个Cache的操作无非三种：插入、替换、查找

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

4.分析图(分析源码时可以对照该图)

Mou icon

5.YYMemoryCache.m里的两个分类

链表节点_YYLinkedMapNode：

@interface _YYLinkedMapNode : NSObject {
    @package
    // 指向前一个节点
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    // 指向后一个节点
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    // 缓存key
    id _key;
    // 缓存对象
    id _value;
    // 当前缓存内存开销
    NSUInteger _cost;
    // 缓存时间
    NSTimeInterval _time;
}
@end

链表_YYLinkedMap

@interface _YYLinkedMap : NSObject {
    @package
    // 用字典保存所有节点_YYLinkedMapNode (为什么不用oc字典?因为用CFMutableDictionaryRef效率高，毕竟基于c)
    CFMutableDictionaryRef _dic;
    // 总缓存开销
    NSUInteger _totalCost;
    // 总缓存数量
    NSUInteger _totalCount;
    // 链表头节点
    _YYLinkedMapNode *_head;
    // 链表尾节点
    _YYLinkedMapNode *_tail;
    // 是否在主线程上，异步释放 _YYLinkedMapNode对象
    BOOL _releaseOnMainThread;
    // 是否异步释放 _YYLinkedMapNode对象
    BOOL _releaseAsynchronously;
}
// 添加节点到链表头节点
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
// 移动当前节点到链表头节点
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
// 移除链表节点
- (void)removeNode:(_YYLinkedMapNode *)node;
// 移除链表尾节点(如果存在)
- (_YYLinkedMapNode *)removeTailNode;
// 移除所有缓存
- (void)removeAll;
@end

方法插入、替换、查找方法实现：

// 添加节点到链表头节点
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
    // 字典保存链表节点node
    CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));
    // 叠加该缓存开销到总内存开销
    _totalCost += node->_cost;
    // 总缓存数+1
    _totalCount++;
    if (_head) {
        // 存在链表头，取代当前表头
        node->_next = _head;
        _head->_prev = node;
        // 重新赋值链表表头临时变量_head
        _head = node;
    } else {
        // 不存在链表头
        _head = _tail = node;
    }
}

存在表头情况图形分析(其他情况不用图分析,自己想象吧，呵呵)

Mou icon

// 移动当前节点到链表头节点
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
    // 当前节点已是链表头节点
    if (_head == node) return;

    if (_tail == node) {
        //**如果node是链表尾节点**

        // 把node指向的上一个节点赋值给链表尾节点
        _tail = node->_prev;
        // 把链表尾节点指向的下一个节点赋值nil
        _tail->_next = nil;
    } else {
        //**如果node是非链表尾节点和链表头节点**

        // 把node指向的上一个节点赋值給node指向的下一个节点node指向的上一个节点
        node->_next->_prev = node->_prev;
        // 把node指向的下一个节点赋值给node指向的上一个节点node指向的下一个节点
        node->_prev->_next = node->_next;
    }
    // 把链表头节点赋值给node指向的下一个节点
    node->_next = _head;
    // 把node指向的上一个节点赋值nil
    node->_prev = nil;
    // 把节点赋值给链表头节点的指向的上一个节点
    _head->_prev = node;
    _head = node;
}

如果node是非链表尾节点和链表头节点情况图形分析(其他情况不用图分析,自己想象吧，呵呵)

Mou icon

// 移除节点
- (void)removeNode:(_YYLinkedMapNode *)node {
    // 从字典中移除node
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
    // 减掉总内存消耗
    _totalCost -= node->_cost;
    // // 总缓存数-1
    _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;
}

// 移除尾节点(如果存在)
- (_YYLinkedMapNode *)removeTailNode {
    if (!_tail) return nil;
    // 拷贝一份要删除的尾节点指针
    _YYLinkedMapNode *tail = _tail;
    // 移除链表尾节点
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
    // 减掉总内存消耗
    _totalCost -= _tail->_cost;
    // 总缓存数-1
    _totalCount--;
    if (_head == _tail) {
        // 清除节点，链表上已无节点了
        _head = _tail = nil;
    } else {
        // 设倒数第二个节点为链表尾节点
        _tail = _tail->_prev;
        _tail->_next = nil;
    }
    // 返回完tail后_tail将会释放
    return tail;
}

// 移除所有缓存
- (void)removeAll {
    // 清空内存开销与缓存数量
    _totalCost = 0;
    _totalCount = 0;
    // 清空头尾节点
    _head = nil;
    _tail = nil;

    if (CFDictionaryGetCount(_dic) > 0) {
        // 拷贝一份字典
        CFMutableDictionaryRef holder = _dic;
        // 重新分配新的空间
        _dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);

        if (_releaseAsynchronously) {
            // 异步释放缓存
            dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
            dispatch_async(queue, ^{
                CFRelease(holder); // hold and release in specified queue
            });
        } else if (_releaseOnMainThread && !pthread_main_np()) {
            // 主线程上释放缓存
            dispatch_async(dispatch_get_main_queue(), ^{
                CFRelease(holder); // hold and release in specified queue
            });
        } else {
            // 同步释放缓存
            CFRelease(holder);
        }
    }
}

YYMemoryCache.m实现分析(如果上面弄清楚，接下来就简单多了)，增删改都是调用上面的方法，下面分析查找与添加缓存方法实现

// 查找缓存
- (id)objectForKey:(id)key {
    if (!key) return nil;
    // 加锁，防止资源竞争
    // OSSpinLock 自旋锁，性能最高的锁。原理很简单，就是一直 do while 忙等。它的缺点是当等待时会消耗大量 CPU 资源，所以它不适用于较长时间的任务。对于内存缓存的存取来说，它非常合适。
    pthread_mutex_lock(&_lock);
    // _lru为链表_YYLinkedMap，全部节点存在_lru->_dic中
    // 获取节点
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        //** 有对应缓存 **

        // 重新更新缓存时间
        node->_time = CACurrentMediaTime();
        // 把当前node移到链表表头(为什么移到表头？根据LRU淘汰算法:Cache的容量是有限的，当Cache的空间都被占满后，如果再次发生缓存失效，就必须选择一个缓存块来替换掉.LRU法是依据各块使用的情况， 总是选择那个最长时间未被使用的块替换。这种方法比较好地反映了程序局部性规律)
        [_lru bringNodeToHead:node];
    }
    // 解锁
    pthread_mutex_unlock(&_lock);
    // 有缓存则返回缓存值
    return node ? node->_value : nil;
}

// 添加缓存
- (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]; //  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);
}

4.YYMemoryCache.m tips

// 用字典保存所有节点_YYLinkedMapNode (为什么不用oc字典?因为用CFMutableDictionaryRef效率高，毕竟基于c)
CFMutableDictionaryRef _dic;

_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);

CFMutableDictionaryRef 用法mark。

http://everettjf.github.io/2016/03/17/yycache-learn

YYMemoryCache 是内存缓存。
Key是retained，而不是copied。
使用了LRU（最近最少使用）算法。

if __has_include("YYDispatchQueuePool.h")

可以这么判断是否包含了某个头文件。

@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

双向链表的节点。 cost以及time（最后使用时间）。 _prev 和 _next 是__unsafe_unretained 修饰，被外层的 CFMutableDictionaryRef retained。
@package 修饰符，在framework内部可访问，framework外部不可访问。

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

双向链表 定义。头、尾。dic用于存储元素，同时retain元素。

- (void)_trimRecursively {
    __weak typeof(self) _self = self;
    dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(_autoTrimInterval * NSEC_PER_SEC)), dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
        __strong typeof(_self) self = _self;
        if (!self) return;
        [self _trimInBackground];
        [self _trimRecursively];
    });
}

简单的定时器。 dispatch_after实现，因为它递归调用，所以它不是一次性，循环的；

- (void)_trimToCost:(NSUInteger)costLimit {
    BOOL finish = NO;
    pthread_mutex_lock(&_lock);
    if (costLimit == 0) {
        [_lru removeAll];
        finish = YES;
    } else if (_lru->_totalCost <= costLimit) {
        finish = YES;
    }
    pthread_mutex_unlock(&_lock);
    if (finish) return;
    
    NSMutableArray *holder = [NSMutableArray new];
    while (!finish) {
        if (pthread_mutex_trylock(&_lock) == 0) {
            if (_lru->_totalCost > costLimit) {
                _YYLinkedMapNode *node = [_lru removeTailNode];
                if (node) [holder addObject:node];
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            usleep(10 * 1000); //10 ms
        }
    }
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            [holder count]; // release in queue
        });
    }
}

这里老版本使用了OSSpinLock，现在已经更换为pthread_mutex_lock，原因见作者的文章， http://blog.ibireme.com/2016/01/16/spinlock_is_unsafe_in_ios/

这里trylock，无法获得锁时，usleep。

 [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];

监听进入后台或者内存警告

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

注意锁。并设置访问元素的最新访问时间。并把此元素放到双向链表的头部。这里时间复杂度都是常数。
学到了获取时间的一个函数 CACurrentMediaTime()。

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

pthread_main_np 判断主线程。返回非零，则为主线程。

- (NSUInteger)totalCount {
    pthread_mutex_lock(&_lock);
    NSUInteger count = _lru->_totalCount;
    pthread_mutex_unlock(&_lock);
    return count;
}

pthread_mutex_init(&_lock, NULL);
pthread_mutex_destroy(&_lock); pthread mutex 基本使用方法。
if (pthread_mutex_trylock(&_lock) == 0) 使用trylock避免阻塞

static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue()

tatic inline 文件内，内联