一步步来读懂YYMemoryCache

来源:互联网 时间:2017-01-22


1.应该先有一个设计方案

可以先看看作者的博客关于YYMemoryCache的设计思路传送门,大概可以知道,NSCache还是挺好的,读取很快,写入的时候由于key的原因稍微慢点,但是对缓存的totalCostLimit自动清除缓存却是不可控制。那么,如果对NSCache进行改造,或者站在NSCache的设计思路上,进一步提供比较快的写入速度,提供自动清除的可控性,应该会更好一点。
那么如何选材呢?从两个方面,读写速度方面,可控方面。
NSDictionary有NSCache一样需要的的key-value对,读取速度非常快。对于控制清除缓存方面可以写入由时间先后来决定,写入value的时候带上时间并放到一个队列的前面,读取的时候把该value放到最前面(MRU),清除的时候从最后面开始(LRU)。
那么这个队列应该由什么来控制呢?
我们先看看数组,内存空间连续,读取速度快,但是修改速度慢,但是现在我们需要的是修改速度比较快的就行了,读取上已经有了NSDictionary。链表是修改速度非常快的队列,存储上内存空间不连续。虽然读取的时候慢点,但是我们不需要用它来读取啊,而且链表也能停供头尾的操作,很符合LRU。
所以选定材料是,NSDictionary+双线链表+LRU+(NSCache的线程安全+内存警告处理+转入后台处理+实时limit处理)。


2.如何来封装

应该有一个类来提供外部的接口,类似于NSCache,暂且把这个叫交互层。
应该有一个内部的类来响应交互层的command,提供数据的读写,删除,也就是双向链表和字典的操作,暂且把这个叫做处理层。
应该还有一个链表节点类。组件层。


a.先来看看对外交互层这个类YYMemoryCache。
先了解下YYMemoryCache.h


#pragma mark - Attribute
@property (nullable, copy) NSString *name;//没什么用
@property (readonly) NSUInteger totalCount;//缓存的object数量
@property (readonly) NSUInteger totalCost;//缓存cost总数
#pragma mark - Limit
@property NSUInteger countLimit;//设置cache缓存object数量的最大值,超过就会采用LRU来清除后面的,直到的totalCount <= countLimit
@property NSUInteger costLimit;//设置缓存cost的最大值,如果没有单独设置每个object的cost,那么这个并没有什么用处,因为每个object的cost默认为0。处理方式同countLimit。
@property NSTimeInterval ageLimit;//设置存活时间。每个object写入的时候,和读取的时候,都会有一个相应的时间更新为当前时间,当currentTime - objectTime > ageLimit,都会被清除,处理方式同countLimit。
@property NSTimeInterval autoTrimInterval;//定期清理缓存时间,默认为5秒。清理规则是上面的三个limit。
@property BOOL shouldRemoveAllObjectsOnMemoryWarning;//当接收到来自系统的内存警告时,是否要清除所有缓存,默认是 YES。建议使用默认。
@property BOOL shouldRemoveAllObjectsWhenEnteringBackground;//当进入后台的时候是否要清除所有缓存,默认是 YES。建议使用默认。
@property (nullable, copy) void(^didReceiveMemoryWarningBlock)(YYMemoryCache *cache);//内存警告时的block
@property (nullable, copy) void(^didEnterBackgroundBlock)(YYMemoryCache *cache);//进入后台时的block
@property BOOL releaseOnMainThread;//是否在主线程释放节点内存,默认为NO,也就是默认在后台释放内存(hold ,than release)。
@property BOOL releaseAsynchronously;//和releaseOnMainThread相反。
#pragma mark - Access Methods
- (BOOL)containsObjectForKey:(id)key;//是否存储了某个key
- (nullable id)objectForKey:(id)key;//获取object
- (void)setObject:(nullable id)object forKey:(id)key;//写入object
- (void)setObject:(nullable id)object forKey:(id)key withCost:(NSUInteger)cost;//写入object,并且设置每个object的cost
- (void)removeObjectForKey:(id)key;//删除某个object
- (void)removeAllObjects;//清空缓存
#pragma mark - Trim 根据limit规则来截取移除
- (void)trimToCount:(NSUInteger)count;//根据object数量来移除
- (void)trimToCost:(NSUInteger)cost;//根据cost数量来移除。
- (void)trimToAge:(NSTimeInterval)age;//根据存活时间来移除。

再来看看YYMemoryCache实现的私有属性。


@implementation YYMemoryCache {
pthread_mutex_t _lock;//互斥锁,保证线程安全,对于所有的属性和方法
_YYLinkedMap *_lru;//处理层类。处理链表操作
dispatch_queue_t _queue;//串联队列,
}

b.处理层_YYLinkedMap(链表操作)
//操作时需要主要双链表的两个链都要连好


@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; // 用来存储节点
NSUInteger _totalCost;//
NSUInteger _totalCount;//
_YYLinkedMapNode *_head; // MRU, 链表头节点
_YYLinkedMapNode *_tail; // LRU, 链表尾节点。链表会在这个_YYLinkedMap形成。
BOOL _releaseOnMainThread;
BOOL _releaseAsynchronously;
}
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;//在链表的head之前添加节点,如果head == nil,则head = node。也就是Cache写入一个object。
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;//把node移到head。也就是Cache读取一个object,或则从新设置key_vale的时候。
- (void)removeNode:(_YYLinkedMapNode *)node;//删除一个节点,也就时Cache移除一个object
- (_YYLinkedMapNode *)removeTailNode;
- (_YYLinkedMapNode *)removeTailNode;//根据那三个limit规则来移除节点
- (void)removeAll;//清空所有节点

c.组件层_YYLinkedMapNode


@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; //前驱指针
__unsafe_unretained _YYLinkedMapNode *_next; // 后驱指针,__unsafe_unretained 用这个是防止node在写入的时候被retain 而导致删除的时候无法清除被retain的内存。
id _key;
id _value;
NSUInteger _cost;//每个节点的cost
NSTimeInterval _time;//修改时间
}

3.具体实现流程

从交互层到处理层的一个实现。
a.存储一个object的流程。主要是处理存储,和根据limit规则来移除。


- (void)setObject:(nullable id)object forKey:(id)key;

[self setObject:object forKey:key withCost:0];

- (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));//先判断有没有这个key_node
NSTimeInterval now = CACurrentMediaTime();
if (node) {
_lru->_totalCost -= node->_cost;
_lru->_totalCost += cost;
node->_cost = cost;
node->_time = now;
node->_value = object;
[_lru bringNodeToHead:node];//如果字典中有这个key_node 则从新赋值,并移到head前面
} else {
node = [_YYLinkedMapNode new];
node->_cost = cost;
node->_time = now;
node->_key = key;
node->_value = object;
[_lru insertNodeAtHead:node];//如果没有则添加到head前面
}
if (_lru->_totalCost > _costLimit) {
//根据_costLimit来移除
dispatch_async(_queue, ^{
[self trimToCost:_costLimit];
});
}
if (_lru->_totalCount > _countLimit) {
////根据_countLimit来移除
_YYLinkedMapNode *node = [_lru removeTailNode];
//如果前面的_YYLinkedMapNode 没有用__unsafe_unretained,则这里移除的时候,只能把字典里的node移除,node里的pre和next 还会再写入的时候被retain,无法被移除。
if (_lru->_releaseAsynchronously) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[node class]; //tip,异步移除
});
} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
[node class]; //hold and release in queue
});
}
}
pthread_mutex_unlock(&_lock);
}

//如果字典中有这个key_node 则从新赋值,并移到head前面


- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
if (_head == node) return;//
if (_tail == node) {
//如果node是尾部,则改变尾部,并且连好
_tail = node->_prev;
_tail->_next = nil;
} else {
//如果不是尾部,则要把之前node 前后连个节点重新连好
node->_next->_prev = node->_prev;
node->_prev->_next = node->_next;
}
//改变head并且连好
node->_next = _head;
node->_prev = nil;
_head->_prev = node;
_head = node;
}

//如果没有则添加到head前面


- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));//set 字典 key_node
_totalCost += node->_cost;
_totalCount++;
//如果head存在 ,则连好head 和 node 并重新赋值head。如果不存在,则head=tail=node。
if (_head) {
node->_next = _head;
_head->_prev = node;
_head = node;
} else {
_head = _tail = node;
}
}

b.移除一个object的流程。


- (void)removeObjectForKey:(id)key;

- (void)removeObjectForKey:(id)key {
if (!key) return;
pthread_mutex_lock(&_lock);//线程安全
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));//获取key_node,and hold to release
if (node) {
[_lru removeNode:node];//链表移除操作
if (_lru->_releaseAsynchronously) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[node class]; //tip,异步移除。
});
} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
[node class]; //tip,异步移除
});
}
}
pthread_mutex_unlock(&_lock);
}

//链表移除操作


- (void)removeNode:(_YYLinkedMapNode *)node {
CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));//字典移除key_node
_totalCost -= node->_cost;
_totalCount--;
//重新连好node 前后两个节点,if存在。如果head=node,则重新赋值head。如果tail=node,则重新赋值tail。
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;
}

c.limit规则。单独抽取ageLimit来讲。


- (instancetype)init { 
//在cache的init中,启动定时器递归来根据limit清除
[self _trimRecursively];


- (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];//在后台根据limit规则来清除
[self _trimRecursively];//递归
});
}

- (void)_trimInBackground {
dispatch_async(_queue, ^{
//根据三个limit规则来清除
[self _trimToCost:self->_costLimit];
[self _trimToCount:self->_countLimit];
[self _trimToAge:self->_ageLimit];
});
}

//根据ageLimit来清除


- (void)_trimToAge:(NSTimeInterval)ageLimit {
BOOL finish = NO;
NSTimeInterval now = CACurrentMediaTime();//当前时间
pthread_mutex_lock(&_lock);//线程安全
//如果ageLimit,则清除全部。如果最后一个的时间规则都不成立, 则不用清
if (ageLimit <= 0) {
[_lru removeAll];
finish = YES;
} else if (!_lru->_tail || (now - _lru->_tail->_time) <= ageLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;//返回
//while 循环 来清除最后一个,直到最后一个limit时间规则不成立,并且异步释放。中间用的pthread_mutex_trylock,如果不能锁就继续其他任务usleep(10 * 1000)。
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_tail && (now - _lru->_tail->_time) > ageLimit) {
_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]; // tip,异步释放
});
}
}

d.系统内存警告和转入后台时的清空流程。


- (instancetype)init {
//cache 初始化时添加通知
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
}

- (void)_appDidReceiveMemoryWarningNotification {
if (self.didReceiveMemoryWarningBlock) {
self.didReceiveMemoryWarningBlock(self);
}
if (self.shouldRemoveAllObjectsOnMemoryWarning) {
[self removeAllObjects];
}
}
- (void)_appDidEnterBackgroundNotification {
if (self.didEnterBackgroundBlock) {
self.didEnterBackgroundBlock(self);
}
if (self.shouldRemoveAllObjectsWhenEnteringBackground) {
[self removeAllObjects];
}
}

- (void)removeAllObjects {
pthread_mutex_lock(&_lock);
[_lru removeAll];//清空缓存
pthread_mutex_unlock(&_lock);
}

//清空缓存


- (void)removeAll {
//这里并没有一个个的去清节点,而是直接把头尾置空,并且tip异步释放之前的子弹,然后重新创建一个新的字典。
_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);
}
}
}



相关阅读:
Top