YYMemoryCache文件
在分析代码之前，首先给大家介绍一下双向链表，如下图所示：
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。如果还不明白双向链表是什么可以看一下数据结构，相信你就能明白了。
_YYLinkedMapNode
这是一个链表节点类，先看代码
@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
这几行代码里需要解读的知识点很多，首先来说说这个类是干嘛的，他表示的是一个双向链表的某一个节点。
其次@package对于大家可能有点陌生，我也是第一次在OC里见到，最早见到package是在java里看到的，他表示的是一个包。在这里@package是什么意思，它也是表示在包内都能使用，准确来说是在framework内可用。
插播一下，我们对比一下@package和@private
@interface TestClass : NSObject {
@private
NSString *mNamePrivate;
@package
NSString *mTextPackage;
}
如果你这样写
我们看到当我们分别调用 t->mTextPackage 和 t->mTextPackage ，发现前者是ok的，后者会报错提示“instance variable 'mNamePrivate' is private”。@package 一般很少用（对于framework内部相当于protected 对于framework外部相当于private）。
我们再次回到刚才还没说完的_YYLinkedMapNode
_YYLinkedMapNode* _prev 定义了一个指针指向前一个节点，还有一个_YYLinkedMapNode *_next指向后一个节点。我们注意到每一个节点都使用__unsafe_unretained ，这是为了防止循环强引用，因为这里的结构是双向链表，很可能出现循环强引用，最后就都不会给释放。
_YYLinkedMap
刚才说到_YYLinkedMapNode是一个节点，那么_YYLinkedMap就是链表，链表的作用是将所有节点串联起来形成我们想要的双向链表数据结构。
@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; // 是否在主线程上，异步释放 _YYLinkedMapNode对象
BOOL _releaseAsynchronously; //是否异步释放 _YYLinkedMapNode对象
}
链表的操作
insertNodeAtHead
- (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;
}
}
插入到头部节点，首先使用字典retain住节点缓存对象，然后让内存消耗自增，然后判断如果存在头部节点插入，注意链表操作的顺序，最后一步才是_head = node ,否则head节点会丢失。
bringNodeToHead
- (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;
}
这个函数的功能是将某个节点从其他位置移到头部，操作步骤如下图所示，
removeNode
- (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;
}
先从字典移除节点，此时节点就没有retain指向了，自减内存消耗，然后判断删除的节点是否是头节点或尾节点，操作步骤类似bringNodeToHead第一个演示图。
removeAll
- (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);
}
}
}
首先清空内存统计数据，然后清空头结点和尾节点。因为全部的节点都是由字典强引用，所以获取字典判断是否还有节点。如果还存在未删除的节点，就接着往下走。如果允许异步释放，并设置的是在主线程释放，那么就在主线程释放；如果允许异步释放，并设置不能在主线程释放，则在YY的专用释放线程释放。如果允许主线程释放，并且当前不在主线程则使用主线程释放（避免死锁）。都不满足则使用同步释放。
总结：
作者这么费劲的写一个专门操作双向链表的操作类到底是出于什么目的，这个其实就是计算机操作系统里的一个算法LRU(近期最少使用缓存项)淘汰算法，这里是用头插法实现的，用这个算法对缓存数据进行淘汰控制，以便内存里的缓存数据命中率更高。因为毕竟内存大小有限，这也是YYMemoryCache精髓。
比较遗憾的YYCache是不支持存活时间的。不过这是可以理解的，作者觉得会和LRU 淘汰算法有冲突吧。
微博账号：梅嘉庆（点击关注）
