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);//当前线程释放
}
}
}
