YYCache 源码分析(二)

（点击上方公众号，可快速关注）来源：汉斯哈哈哈链接：http://www.jianshu.com/p/492...

来源：汉斯哈哈哈

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

本文分析YYMemoryCache实现原理：



YYMemoryCache是内存缓存，所以存取速度非常快，主要用到两种数据结构的LRU淘汰算法

1.LRU

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

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

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

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

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

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



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 constvoid*)(node->_key),(__bridge constvoid*)(node));

// 叠加该缓存开销到总内存开销

_totalCost += node->_cost;

// 总缓存数+1

_totalCount++;

if(_head){

// 存在链表头，取代当前表头

node->_next = _head;

_head->_prev = node;

// 重新赋值链表表头临时变量_head

_head = node;

}else{

// 不存在链表头

_head = _tail = node;

}

}

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

// 移动当前节点到链表头节点

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

}

// 移除节点

- (void)removeNode:(_YYLinkedMapNode *)node{

// 从字典中移除node

CFDictionaryRemoveValue(_dic,(__bridge constvoid*)(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)returnnil;

// 拷贝一份要删除的尾节点指针

_YYLinkedMapNode *tail = _tail;

// 移除链表尾节点

CFDictionaryRemoveValue(_dic,(__bridge constvoid*)(_tail->_key));

// 减掉总内存消耗

_totalCost -= _tail->_cost;

// 总缓存数-1

_totalCount--;

if(_head == _tail){

// 清除节点，链表上已无节点了

_head = _tail = nil;

}else{

// 设倒数第二个节点为链表尾节点

_tail = _tail->_prev;

_tail->_next = nil;

}

// 返回完tail后_tail将会释放

returntail;

}

// 移除所有缓存

- (void)removeAll{

// 清空内存开销与缓存数量

_totalCost = 0;

_totalCount = 0;

// 清空头尾节点

_head = nil;

_tail = nil;

if(CFDictionaryGetCount(_dic) > 0){

// 拷贝一份字典

CFMutableDictionaryRefholder = _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

});

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

// 加锁，防止资源竞争

// OSSpinLock 自旋锁，性能最高的锁。原理很简单，就是一直 do while 忙等。它的缺点是当等待时会消耗大量 CPU 资源，所以它不适用于较长时间的任务。对于内存缓存的存取来说，它非常合适。

pthread_mutex_lock(&_lock);

// _lru为链表_YYLinkedMap，全部节点存在_lru->_dic中

// 获取节点

_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic,(__bridge constvoid*)(key));

if(node){

//** 有对应缓存 **

// 重新更新缓存时间

node->_time = CACurrentMediaTime();

// 把当前node移到链表表头(为什么移到表头？根据LRU淘汰算法:Cache的容量是有限的，当Cache的空间都被占满后，如果再次发生缓存失效，就必须选择一个缓存块来替换掉.LRU法是依据各块使用的情况， 总是选择那个最长时间未被使用的块替换。这种方法比较好地反映了程序局部性规律)

[_lru bringNodeToHead:node];

}

// 解锁

pthread_mutex_unlock(&_lock);

// 有缓存则返回缓存值

returnnode?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 constvoid*)(key));

// 当前时间

NSTimeIntervalnow = 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

});

}elseif(_lru->_releaseOnMainThread && !pthread_main_np()){

dispatch_async(dispatch_get_main_queue(), ^{

[node class];//hold and release in queue

});

}

}

pthread_mutex_unlock(&_lock);

}

接下来会分析YYDiskCache实现原理其中推荐了包括技术、设计、极客 和 IT相亲相关的热门公众号。技术涵盖：Python、Web前端、Java、安卓、iOS、PHP、C/C++、.NET、Linux、数据库、运维、大数据、算法、IT职场等。点击《值得关注的技术和设计公众号》，发现精彩！

    关注 iOS大全