YYMemoryCache分析

YYMemoryCache主要分析

• LRU算法+双链表+哈希表
• 线程操作锁
• cache内部变量内存释放队列
• 哈希表保存节点与key。通过key直接能够取到节点避免循环遍历链表的时间开销
• 基于双向链表特性。当新增，移动或者删除时可以避免循环遍历链表的时间开销
• 内存警告时清除缓存

缓存的核心原则是所有操作快速，所以应该尽量避免所有的遍历数据操作

双向链表

@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;
    id _value;
    ...
}
@end

哈希表与虚拟头节点

@interface _YYLinkedMap : NSObject {
    @package
    CFMutableDictionaryRef _dic; // do not set object directly
    ...
    _YYLinkedMapNode *_head; // MRU, do not change it directly
    _YYLinkedMapNode *_tail; // LRU, do not change it directly
    ...
}

LRU算法实现

新增节点添加到链表首位

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
    //...
    if (_head) {// 链表不为空
        //新增节点变为新的首节点
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    } else {//链表为空
        _head = _tail = node;
    }
}

移动节点到首位

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

删除节点

- (void)removeNode:(_YYLinkedMapNode *)node {
    ...
    //更新后继节点的前驱
    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;
}

LRU算法是最近最先使用，那么存在着最远最少使用淘汰，即需要删除尾节点操作

- (_YYLinkedMapNode *)removeTailNode {
    //空链表
    if (!_tail) return nil;
    
    _YYLinkedMapNode *tail = _tail;
    //...
    //一个节点
    if (_head == _tail) {
        _head = _tail = nil;
    } else {//多个节点
        //尾节点更新即可
        _tail = _tail->_prev;
        _tail->_next = nil;
    }
    return tail;
}

线程操作锁

最开始是自旋锁OSSpinLock

OSSpinLock _lock;

_lock = OS_SPINLOCK_INIT;//忙等待锁，线程反复检查锁变量是否可用，不会挂起

OSSpinLockLock(&_lock);
//Code..
OSSpinLockUnlock(&_lock);

后因为自旋锁有优先级反转问题，因此改为互斥锁

互斥锁 - 每个对象都对应于一个可称为" 互斥锁" 的标记，这个标记用来保证在任一时刻，只能有一个线程访问该对象

pthread_mutex_t _lock;

pthread_mutex_init(&_lock, NULL); //互斥锁  

pthread_mutex_lock(&_lock);
//Code
pthread_mutex_unlock(&_lock);

线程优先级反转

共享资源Data
任务线程Task1 优先级Low
任务线程Taks2 优先级High
自旋锁Lock 

1. Task1访问Data  Lock加锁
2. Task2访问Data  等待锁释放，因为忙等，不会挂起并且Task2优先级高，占用大量CPU时间
3. Task1需要的CPU时间不够，任务无法完成，Lock无法解开
4. 形成短暂死锁

cache内部变量内存释放队列

cache内部用到的对象内存在异步线程释放，减少主线程压力

// 一个对象释放常驻队列
static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue() {
    return dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0);
}

xxx   ...
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
    [xxx func]; //利用block将对象捕获，在异步线程释放
});

内存警告时清除缓存

// 系统通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];


//双链表清空
- (void)removeAll {
    ...
    //头节点清空
    _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);//当前线程释放
        }
    }
}