1. LRU是什么台汇？
LRU 是Least Recently Used的縮寫，即最近最少使用篱瞎。其核心思想是最近最多使用的數(shù)據(jù)再將來更可能再次被使用苟呐，而最近最少使用的數(shù)據(jù)將來只有極小的概率再次被使用，所以當(dāng)緩存滿時(shí)將其移出緩存淘汰以達(dá)到緩存最多使用數(shù)據(jù)的目的俐筋，所以也叫內(nèi)存淘汰算法牵素。
2. LRU運(yùn)行原理圖示
LRU運(yùn)行原理.png
3. LRU數(shù)據(jù)結(jié)構(gòu)選定
再了解到LRU的運(yùn)行原理之后我們就可以開始用代碼實(shí)現(xiàn)這個(gè)算法，那我們用什么數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)呢澄者，我們從下面的兩方面來分析
這個(gè)算法需要涉及到兩個(gè)需求
- 數(shù)據(jù)的查找
- 數(shù)據(jù)的移動(dòng)
1）數(shù)組實(shí)現(xiàn)
如果我們用數(shù)組來實(shí)現(xiàn)的話笆呆，數(shù)據(jù)查找需要用for循環(huán)请琳，數(shù)據(jù)移動(dòng)也需要用for循環(huán)
數(shù)據(jù)查找的時(shí)間復(fù)雜度: O(n)，
數(shù)據(jù)移動(dòng)的時(shí)間復(fù)雜度: O(n)赠幕，
空間復(fù)雜度: O(n)
那能優(yōu)化嘛俄精，當(dāng)然是可以的
2）數(shù)組+哈希表實(shí)現(xiàn)
我們在緩存數(shù)據(jù)的時(shí)候，將數(shù)據(jù)插入到數(shù)組同時(shí)榕堰，用keyValue的形式再保存到哈希表中竖慧，這樣在我們想查找某個(gè)數(shù)據(jù)的時(shí)候可以直接用keyValue的形式去哈希表中查找，從而將數(shù)據(jù)查找的時(shí)間復(fù)雜度降低
數(shù)據(jù)查找的時(shí)間復(fù)雜度: O(1)
數(shù)據(jù)移動(dòng)的時(shí)間復(fù)雜度: O(n)
空間復(fù)雜度: O(n)
那數(shù)據(jù)移動(dòng)能優(yōu)化嘛逆屡，也是可以的
3）雙向鏈表+哈希表
在我們哈希表命中數(shù)據(jù)的時(shí)候圾旨，要?jiǎng)h除移動(dòng)數(shù)據(jù)需要修改命中數(shù)據(jù)前驅(qū)(pre)的后繼(next)，單鏈表在不能循環(huán)的條件下是不能拿到命中數(shù)據(jù)的前驅(qū)的康二，所以我們采用雙鏈表碳胳，這樣就將數(shù)據(jù)移動(dòng)的時(shí)間復(fù)雜度降低
數(shù)據(jù)查找的時(shí)間復(fù)雜度: O(1)
數(shù)據(jù)移動(dòng)的時(shí)間復(fù)雜度: O(1)
空間復(fù)雜度: O(n)
所以綜上所述，我們最后采用向鏈表+哈希表來實(shí)現(xiàn)這種算法
4. 代碼實(shí)現(xiàn)
1）首先我們先把雙鏈表的節(jié)點(diǎn)實(shí)現(xiàn)出來
我們申明一個(gè)類ZJMemeryCache沫勿，在ZJMemeryCache.m內(nèi)部實(shí)現(xiàn)_ZJLinkedMapNode
ZJMemeryCache.h代碼如下
@interface ZJMemeryCache : NSObject
@end
ZJMemeryCache.m代碼如下
#import "ZJMemeryCache.h"
//雙鏈表節(jié)點(diǎn)
@interface _ZJLinkedMapNode : NSObject {
@package
//指針域 前驅(qū)
__unsafe_unretained _ZJLinkedMapNode *_prev;
//指針域 后繼
__unsafe_unretained _ZJLinkedMapNode *_next;
//用于存哈希表的key
id _key;
//數(shù)據(jù)域 value
id _value;
}
@end
@implementation _ZJLinkedMapNode
@end
@implementation ZJMemeryCache
@end
2）接下來我們再在ZJMemeryCache.m內(nèi)部實(shí)現(xiàn)雙鏈表_ZJLinkedMapNode
ZJMemeryCache.m代碼如下
//
// ZJMemeryCache.m
// ZJMemeryCache
//
// Created by zhoujie on 2022/3/14.
// Copyright ? 2022 ibireme. All rights reserved.
//
#import "ZJMemeryCache.h"
//雙鏈表節(jié)點(diǎn)
@interface _ZJLinkedMapNode : NSObject { ... }
@end
@implementation _ZJLinkedMapNode
@end
@interface _ZJLinkedMap : NSObject {
@package
//頭指針
_ZJLinkedMapNode *_head;
//尾指針，用于降低刪除尾節(jié)點(diǎn)的時(shí)間復(fù)雜度
_ZJLinkedMapNode *_tail;
}
/// 若數(shù)據(jù)沒有在緩存中味混，將數(shù)據(jù)從頭插入产雹，代表最近最多使用
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node;
/// 若數(shù)據(jù)在緩存中，先將數(shù)據(jù)刪除翁锡，再從頭插入
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node;
/// 刪除指定節(jié)點(diǎn)
- (void)removeNode:(_ZJLinkedMapNode *)node;
/// 移除尾節(jié)點(diǎn)蔓挖，代表緩存已滿，需要?jiǎng)h除最近最少使用的數(shù)據(jù)
- (_ZJLinkedMapNode *)removeTailNode;
@end
@implementation _ZJLinkedMap
- (instancetype)init {
if (self = [super init]) {
}
return self;
}
- (void)dealloc {
}
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node {
}
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node {
}
- (void)removeNode:(_ZJLinkedMapNode *)node {
}
- (_ZJLinkedMapNode *)removeTailNode {
return nil;
}
@end
@implementation ZJMemeryCache
@end
我們先來實(shí)現(xiàn)- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node;這個(gè)方法馆衔，這個(gè)方法對(duì)應(yīng)的是LRU運(yùn)行原理圖示中的第2瘟判、3、4步角溃，緩存中沒有數(shù)據(jù)拷获，直接緩存，實(shí)現(xiàn)代碼如下
/// 若數(shù)據(jù)沒有在緩存中减细，將數(shù)據(jù)從頭插入匆瓜，代表最近最多使用
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node {
if (_head) {
//鏈表不為空,從頭插入新節(jié)點(diǎn)
node->_next = _head;
_head->_prev = node;
_head = node;
}else {
//鏈表為空
_head = node;
_tail = node;
}
}
再來實(shí)現(xiàn)- (void)bringNodeToHead:(_ZJLinkedMapNode *)node;這個(gè)方法，這個(gè)方法對(duì)應(yīng)的圖中的第6步未蝌，先刪除對(duì)應(yīng)節(jié)點(diǎn)驮吱，再將刪除的節(jié)點(diǎn)從頭插入
/// 若數(shù)據(jù)在緩存中，先將數(shù)據(jù)刪除萧吠，再從頭插入
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node {
//如果命中的節(jié)點(diǎn)是頭節(jié)點(diǎn)左冬，則不用處理
if (node == _head) {
return;
}
//刪除命中的節(jié)點(diǎn)
if (node == _tail) {
_tail = _tail->_prev;
_tail->_next = nil;
}else {
node->_prev->_next = node->_next;
node->_next->_prev = node->_prev;
}
//從頭插入剛刪除的節(jié)點(diǎn)
node->_next = _head;
node->_prev = nil;
_head->_prev = node;
_head = node;
}
再實(shí)現(xiàn)- (void)removeNode:(_ZJLinkedMapNode *)node;這個(gè)方法
/// 刪除指定節(jié)點(diǎn)
- (void)removeNode:(_ZJLinkedMapNode *)node {
if (node->_prev) {
node->_prev->_next = node->_next;
}
if (node->_next) {
node->_next->_prev = node->_prev;
}
if (node == _head) {
_head = node->_next;
}
if (node == _tail) {
_tail = node->_prev;
}
}
最后再實(shí)現(xiàn)- (_ZJLinkedMapNode *)removeTailNode;這個(gè)方法，這個(gè)方法在緩存滿了之后調(diào)用纸型，刪除最近最少使用的數(shù)據(jù)拇砰，對(duì)應(yīng)的是圖中第5步的移除數(shù)據(jù)1
/// 移除尾節(jié)點(diǎn)九昧，代表緩存已滿，需要?jiǎng)h除最近最少使用的數(shù)據(jù)
- (_ZJLinkedMapNode *)removeTailNode {
if (!_tail) {
return nil;
}
_ZJLinkedMapNode *tail = _tail;
if (_head == _tail) {
_head = nil;
_tail = nil;
}else {
_tail = _tail->_prev;
_tail->_next = nil;
}
return tail;
}
至此雙向鏈表的主要功能算是完成了毕匀，我們再把哈希表的邏輯加入
3）加入哈希表邏輯
我們在_ZJLinkedMap中新增一個(gè)成員變量NSDictionary *_dic;
@interface _ZJLinkedMap : NSObject {
@package
//頭指針
_ZJLinkedMapNode *_head;
//尾指針铸鹰，用于降低刪除尾節(jié)點(diǎn)的時(shí)間復(fù)雜度
_ZJLinkedMapNode *_tail;
//哈希表，存儲(chǔ)節(jié)點(diǎn)
NSMutableDictionary *_dic;
//當(dāng)前容量
NSInteger count;
}
在_ZJLinkedMap中的init中初始化它
- (instancetype)init {
if (self = [super init]) {
_dic = [NSMutableDictionary dictionary];
}
return self;
}
然后在insertNodeAtHead和removeNode皂岔、removeTailNode中添加增刪邏輯
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node {
_dic[node->_key] = node->_value;
count++;
if (_head) {
//鏈表不為空,從頭插入新節(jié)點(diǎn)
node->_next = _head;
_head->_prev = node;
_head = node;
}else {
//鏈表為空
_head = node;
_tail = node;
}
}
到這里蹋笼，我們雙向鏈表+哈希表的邏輯就算寫完了，我們在ZJMemeryCache.m中實(shí)現(xiàn)緩存功能
4）ZJMemeryCache實(shí)現(xiàn)緩存功能
我們申明兩個(gè)方法
取緩存:- (nullable id)objectForKey:(id)key;
存緩存:- (void)setObject:(nullable id)object forKey:(id)key;
代碼如下
ZJMemeryCache.h
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface ZJMemeryCache : NSObject
// 緩存大小限制
@property NSUInteger countLimit;
// 取緩存
- (nullable id)objectForKey:(id)key;
// 存緩存
- (void)setObject:(nullable id)object forKey:(id)key;
@end
NS_ASSUME_NONNULL_END
ZJMemeryCache.m
//
// ZJMemeryCache.m
// ZJMemeryCache
//
// Created by zhoujie on 2022/3/14.
// Copyright ? 2022 ibireme. All rights reserved.
//
#import "ZJMemeryCache.h"
#import <pthread.h>
//雙鏈表節(jié)點(diǎn)
@interface _ZJLinkedMapNode : NSObject { ... }
@end
@implementation _ZJLinkedMapNode
@end
@interface _ZJLinkedMap : NSObject { ... }
@end
@implementation _ZJLinkedMap { ... }
@end
@implementation ZJMemeryCache {
//添加線程鎖躁垛，保證ZJLinkedMap的線程安全
pthread_mutex_t _lock;
//lru(雙向鏈表+哈希表結(jié)構(gòu))
_ZJLinkedMap *_lru;
}
- (instancetype)init {
if (self = [super init]) {
//初始化鎖
pthread_mutex_init(&_lock, NULL);
//初始化存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)
_lru = [_ZJLinkedMap new];
//初始化緩存大小
_countLimit = 10;
}
return self;
}
// 取緩存
- (nullable id)objectForKey:(id)key {
}
// 存緩存
- (void)setObject:(nullable id)object forKey:(id)key {
}
@end
我們先來完成取緩存的操作- (nullable id)objectForKey:(id)key剖毯，取緩存很簡單，直接從緩存中查找教馆，找到將此數(shù)據(jù)移動(dòng)到最左側(cè)代表最近最多使用
// 取緩存
- (nullable id)objectForKey:(id)key {
if (!key) return nil;
//加鎖逊谋，保證線程安全
pthread_mutex_lock(&_lock);
//從緩存中查找數(shù)據(jù)，如果找到數(shù)據(jù)土铺，將此數(shù)據(jù)變成最近最多使用胶滋，沒有直接返回空
_ZJLinkedMapNode *node = _lru->_dic[@"key"];
if (node) {
[_lru bringNodeToHead:node];
}
pthread_mutex_unlock(&_lock);
return node ? node->_value : nil;
}
再來處理存緩存操作
// 存緩存
- (void)setObject:(nullable id)object forKey:(id)key {
if (!key) return;
if (!object) return;
//加鎖，保證線程安全
pthread_mutex_lock(&_lock);
//從緩存中查找數(shù)據(jù)悲敷，如果找到數(shù)據(jù)究恤，將此數(shù)據(jù)變成最近最多使用，沒有直接返回空
_ZJLinkedMapNode *node = _lru->_dic[@"key"];
if (node) {
//如果能查到后德，直接移動(dòng)
[_lru bringNodeToHead:node];
}else {
//不能查到,需要緩存
//在緩存前需要判定緩存是否滿了
if (_lru->count >= _countLimit) {
//緩存滿了需要?jiǎng)h除最近最少使用的數(shù)據(jù)
[_lru removeTailNode];
}
//添加最近最多使用的數(shù)據(jù)
node = [_ZJLinkedMapNode new];
node->_key = key;
node->_value = object;
[_lru insertNodeAtHead:node];
}
pthread_mutex_unlock(&_lock);
}
到這里YYMemeryCache里的LRU功能就算寫完了部宿，最后附上YYMemeryCache里的代碼和我們寫的代碼對(duì)比
ZJMemeryCache
//
// ZJMemeryCache.m
// ZJMemeryCache
//
// Created by zhoujie on 2022/3/14.
// Copyright ? 2022 ibireme. All rights reserved.
//
#import "ZJMemeryCache.h"
#import <pthread.h>
//雙鏈表節(jié)點(diǎn)
@interface _ZJLinkedMapNode : NSObject {
@package
//指針域 前驅(qū)
__unsafe_unretained _ZJLinkedMapNode *_prev;
//指針域 后繼
__unsafe_unretained _ZJLinkedMapNode *_next;
//用于存哈希表的key
id _key;
//數(shù)據(jù)域 value
id _value;
}
@end
@implementation _ZJLinkedMapNode
@end
@interface _ZJLinkedMap : NSObject {
@package
//頭指針
_ZJLinkedMapNode *_head;
//尾指針，用于降低刪除尾節(jié)點(diǎn)的時(shí)間復(fù)雜度
_ZJLinkedMapNode *_tail;
//哈希表瓢湃，存儲(chǔ)節(jié)點(diǎn)
NSMutableDictionary *_dic;
//當(dāng)前容量
NSInteger count;
}
/// 若數(shù)據(jù)沒有在緩存中理张，將數(shù)據(jù)從頭插入，代表最近最多使用
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node;
/// 若數(shù)據(jù)在緩存中绵患，先將數(shù)據(jù)刪除雾叭，再從頭插入
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node;
/// 刪除指定節(jié)點(diǎn)
- (void)removeNode:(_ZJLinkedMapNode *)node;
/// 移除尾節(jié)點(diǎn)，代表緩存已滿藏雏，需要?jiǎng)h除最近最少使用的數(shù)據(jù)
- (_ZJLinkedMapNode *)removeTailNode;
@end
@implementation _ZJLinkedMap
- (instancetype)init {
if (self = [super init]) {
_dic = [NSMutableDictionary dictionary];
}
return self;
}
- (void)dealloc {
}
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node {
_dic[node->_key] = node->_value;
count++;
if (_head) {
//鏈表不為空,從頭插入新節(jié)點(diǎn)
node->_next = _head;
_head->_prev = node;
_head = node;
}else {
//鏈表為空
_head = node;
_tail = node;
}
}
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node {
//如果命中的節(jié)點(diǎn)是頭節(jié)點(diǎn)拷况，則不用處理
if (node == _head) {
return;
}
//刪除命中的節(jié)點(diǎn)
if (node == _tail) {
_tail = _tail->_prev;
_tail->_next = nil;
}else {
node->_prev->_next = node->_next;
node->_next->_prev = node->_prev;
}
//從頭插入剛刪除的節(jié)點(diǎn)
node->_next = _head;
node->_prev = nil;
_head->_prev = node;
_head = node;
}
- (void)removeNode:(_ZJLinkedMapNode *)node {
[_dic removeObjectForKey:node->_key];
count--;
if (node->_prev) {
node->_prev->_next = node->_next;
}
if (node->_next) {
node->_next->_prev = node->_prev;
}
if (node == _head) {
_head = node->_next;
}
if (node == _tail) {
_tail = node->_prev;
}
}
/// 移除尾節(jié)點(diǎn)，代表緩存已滿掘殴，需要?jiǎng)h除最近最少使用的數(shù)據(jù)
- (_ZJLinkedMapNode *)removeTailNode {
if (!_tail) {
return nil;
}
_ZJLinkedMapNode *tail = _tail;
[_dic removeObjectForKey:tail->_key];
count--;
if (_head == _tail) {
_head = nil;
_tail = nil;
}else {
_tail = _tail->_prev;
_tail->_next = nil;
}
return tail;
}
@end
@implementation ZJMemeryCache {
//添加線程鎖赚瘦，保證ZJLinkedMap的線程安全
pthread_mutex_t _lock;
//lru(雙向鏈表+哈希表結(jié)構(gòu))
_ZJLinkedMap *_lru;
}
- (instancetype)init {
if (self = [super init]) {
//初始化鎖
pthread_mutex_init(&_lock, NULL);
//初始化存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)
_lru = [_ZJLinkedMap new];
//初始化緩存大小
_countLimit = 10;
}
return self;
}
// 取緩存
- (nullable id)objectForKey:(id)key {
if (!key) return nil;
//加鎖，保證線程安全
pthread_mutex_lock(&_lock);
//從緩存中查找數(shù)據(jù)奏寨，如果找到數(shù)據(jù)起意，將此數(shù)據(jù)變成最近最多使用，沒有直接返回空
_ZJLinkedMapNode *node = _lru->_dic[@"key"];
if (node) {
[_lru bringNodeToHead:node];
}
pthread_mutex_unlock(&_lock);
return node ? node->_value : nil;
}
// 存緩存
- (void)setObject:(nullable id)object forKey:(id)key {
if (!key) return;
if (!object) return;
//加鎖病瞳，保證線程安全
pthread_mutex_lock(&_lock);
//從緩存中查找數(shù)據(jù)揽咕，如果找到數(shù)據(jù)悲酷，將此數(shù)據(jù)變成最近最多使用，沒有直接返回空
_ZJLinkedMapNode *node = _lru->_dic[@"key"];
if (node) {
//如果能查到亲善，直接移動(dòng)
[_lru bringNodeToHead:node];
}else {
//不能查到,需要緩存
//在緩存前需要判定緩存是否滿了
if (_lru->count >= _countLimit) {
//緩存滿了需要?jiǎng)h除最近最少使用的數(shù)據(jù)
[_lru removeTailNode];
}
//添加最近最多使用的數(shù)據(jù)
node = [_ZJLinkedMapNode new];
node->_key = key;
node->_value = object;
[_lru insertNodeAtHead:node];
}
pthread_mutex_unlock(&_lock);
}
@end
YYMemeryCache
//
// YYMemoryCache.m
// YYCache <https://github.com/ibireme/YYCache>
//
// Created by ibireme on 15/2/7.
// Copyright (c) 2015 ibireme.
//
// This source code is licensed under the MIT-style license found in the
// LICENSE file in the root directory of this source tree.
//
#import "YYMemoryCache.h"
#import <UIKit/UIKit.h>
#import <CoreFoundation/CoreFoundation.h>
#import <QuartzCore/QuartzCore.h>
#import <pthread.h>
static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue() {
return dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0);
}
/**
A node in linked map.
Typically, you should not use this class directly.
*/
@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
@implementation _YYLinkedMapNode
@end
/**
A linked map used by YYMemoryCache.
It's not thread-safe and does not validate the parameters.
Typically, you should not use this class directly.
*/
@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;
BOOL _releaseAsynchronously;
}
/// Insert a node at head and update the total cost.
/// Node and node.key should not be nil.
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
/// Bring a inner node to header.
/// Node should already inside the dic.
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
/// Remove a inner node and update the total cost.
/// Node should already inside the dic.
- (void)removeNode:(_YYLinkedMapNode *)node;
/// Remove tail node if exist.
- (_YYLinkedMapNode *)removeTailNode;
/// Remove all node in background queue.
- (void)removeAll;
@end
@implementation _YYLinkedMap
- (instancetype)init {
self = [super init];
_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
_releaseOnMainThread = NO;
_releaseAsynchronously = YES;
return self;
}
- (void)dealloc {
CFRelease(_dic);
}
- (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;
}
}
- (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 {
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;
}
- (_YYLinkedMapNode *)removeTailNode {
if (!_tail) return nil;
_YYLinkedMapNode *tail = _tail;
CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
_totalCost -= _tail->_cost;
_totalCount--;
if (_head == _tail) {
_head = _tail = nil;
} else {
_tail = _tail->_prev;
_tail->_next = nil;
}
return tail;
}
- (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);
}
}
}
@end
@implementation YYMemoryCache {
pthread_mutex_t _lock;
_YYLinkedMap *_lru;
dispatch_queue_t _queue;
}
- (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];
[self _trimRecursively];
});
}
- (void)_trimInBackground {
dispatch_async(_queue, ^{
[self _trimToCost:self->_costLimit];
[self _trimToCount:self->_countLimit];
[self _trimToAge:self->_ageLimit];
});
}
- (void)_trimToCost:(NSUInteger)costLimit {
BOOL finish = NO;
pthread_mutex_lock(&_lock);
if (costLimit == 0) {
[_lru removeAll];
finish = YES;
} else if (_lru->_totalCost <= costLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_totalCost > costLimit) {
_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]; // release in queue
});
}
}
- (void)_trimToCount:(NSUInteger)countLimit {
BOOL finish = NO;
pthread_mutex_lock(&_lock);
if (countLimit == 0) {
[_lru removeAll];
finish = YES;
} else if (_lru->_totalCount <= countLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_totalCount > countLimit) {
_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]; // release in queue
});
}
}
- (void)_trimToAge:(NSTimeInterval)ageLimit {
BOOL finish = NO;
NSTimeInterval now = CACurrentMediaTime();
pthread_mutex_lock(&_lock);
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;
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]; // release in queue
});
}
}
- (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];
}
}
#pragma mark - public
- (instancetype)init {
self = super.init;
pthread_mutex_init(&_lock, NULL);
_lru = [_YYLinkedMap new];
_queue = dispatch_queue_create("com.ibireme.cache.memory", DISPATCH_QUEUE_SERIAL);
_countLimit = NSUIntegerMax;
_costLimit = NSUIntegerMax;
_ageLimit = DBL_MAX;
_autoTrimInterval = 5.0;
_shouldRemoveAllObjectsOnMemoryWarning = YES;
_shouldRemoveAllObjectsWhenEnteringBackground = YES;
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
[self _trimRecursively];
return self;
}
- (void)dealloc {
[[NSNotificationCenter defaultCenter] removeObserver:self name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] removeObserver:self name:UIApplicationDidEnterBackgroundNotification object:nil];
[_lru removeAll];
pthread_mutex_destroy(&_lock);
}
- (NSUInteger)totalCount {
pthread_mutex_lock(&_lock);
NSUInteger count = _lru->_totalCount;
pthread_mutex_unlock(&_lock);
return count;
}
- (NSUInteger)totalCost {
pthread_mutex_lock(&_lock);
NSUInteger totalCost = _lru->_totalCost;
pthread_mutex_unlock(&_lock);
return totalCost;
}
- (BOOL)releaseOnMainThread {
pthread_mutex_lock(&_lock);
BOOL releaseOnMainThread = _lru->_releaseOnMainThread;
pthread_mutex_unlock(&_lock);
return releaseOnMainThread;
}
- (void)setReleaseOnMainThread:(BOOL)releaseOnMainThread {
pthread_mutex_lock(&_lock);
_lru->_releaseOnMainThread = releaseOnMainThread;
pthread_mutex_unlock(&_lock);
}
- (BOOL)releaseAsynchronously {
pthread_mutex_lock(&_lock);
BOOL releaseAsynchronously = _lru->_releaseAsynchronously;
pthread_mutex_unlock(&_lock);
return releaseAsynchronously;
}
- (void)setReleaseAsynchronously:(BOOL)releaseAsynchronously {
pthread_mutex_lock(&_lock);
_lru->_releaseAsynchronously = releaseAsynchronously;
pthread_mutex_unlock(&_lock);
}
- (BOOL)containsObjectForKey:(id)key {
if (!key) return NO;
pthread_mutex_lock(&_lock);
BOOL contains = CFDictionaryContainsKey(_lru->_dic, (__bridge const void *)(key));
pthread_mutex_unlock(&_lock);
return contains;
}
- (id)objectForKey:(id)key {
if (!key) return nil;
pthread_mutex_lock(&_lock);
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
if (node) {
node->_time = CACurrentMediaTime();
[_lru bringNodeToHead:node];
}
pthread_mutex_unlock(&_lock);
return node ? node->_value : nil;
}
- (void)setObject:(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));
NSTimeInterval now = 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]; //hold and release in queue
});
} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
[node class]; //hold and release in queue
});
}
}
pthread_mutex_unlock(&_lock);
}
- (void)removeObjectForKey:(id)key {
if (!key) return;
pthread_mutex_lock(&_lock);
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
if (node) {
[_lru removeNode:node];
if (_lru->_releaseAsynchronously) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[node class]; //hold and release in queue
});
} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
[node class]; //hold and release in queue
});
}
}
pthread_mutex_unlock(&_lock);
}
- (void)removeAllObjects {
pthread_mutex_lock(&_lock);
[_lru removeAll];
pthread_mutex_unlock(&_lock);
}
- (void)trimToCount:(NSUInteger)count {
if (count == 0) {
[self removeAllObjects];
return;
}
[self _trimToCount:count];
}
- (void)trimToCost:(NSUInteger)cost {
[self _trimToCost:cost];
}
- (void)trimToAge:(NSTimeInterval)age {
[self _trimToAge:age];
}
- (NSString *)description {
if (_name) return [NSString stringWithFormat:@"<%@: %p> (%@)", self.class, self, _name];
else return [NSString stringWithFormat:@"<%@: %p>", self.class, self];
}
@end
