YYMemeryCache之LRU算法实现

1. LRU是什么？

LRU 是Least Recently Used的缩写，即最近最少使用。其核心思想是最近最多使用的数据再将来更可能再次被使用，而最近最少使用的数据将来只有极小的概率再次被使用，所以当缓存满时将其移出缓存淘汰以达到缓存最多使用数据的目的，所以也叫内存淘汰算法。

2. LRU运行原理图示

LRU运行原理.png

3. LRU数据结构选定

再了解到LRU的运行原理之后我们就可以开始用代码实现这个算法，那我们用什么数据结构来实现呢，我们从下面的两方面来分析
这个算法需要涉及到两个需求

• 数据的查找
• 数据的移动
  1）数组实现
  如果我们用数组来实现的话，数据查找需要用for循环，数据移动也需要用for循环
  数据查找的时间复杂度: O(n)，
  数据移动的时间复杂度: O(n)，
  空间复杂度: O(n)
  那能优化嘛，当然是可以的
  2）数组+哈希表实现
  我们在缓存数据的时候，将数据插入到数组同时，用keyValue的形式再保存到哈希表中，这样在我们想查找某个数据的时候可以直接用keyValue的形式去哈希表中查找，从而将数据查找的时间复杂度降低
  数据查找的时间复杂度: O(1)
  数据移动的时间复杂度: O(n)
  空间复杂度: O(n)
  那数据移动能优化嘛，也是可以的
  3）双向链表+哈希表
  在我们哈希表命中数据的时候，要删除移动数据需要修改命中数据前驱(pre)的后继(next)，单链表在不能循环的条件下是不能拿到命中数据的前驱的，所以我们采用双链表，这样就将数据移动的时间复杂度降低
  数据查找的时间复杂度: O(1)
  数据移动的时间复杂度: O(1)
  空间复杂度: O(n)
  所以综上所述，我们最后采用向链表+哈希表来实现这种算法

---

4. 代码实现

1）首先我们先把双链表的节点实现出来
我们申明一个类ZJMemeryCache，在ZJMemeryCache.m内部实现_ZJLinkedMapNode
ZJMemeryCache.h代码如下

@interface ZJMemeryCache : NSObject

@end

ZJMemeryCache.m代码如下

#import "ZJMemeryCache.h"

//双链表节点
@interface _ZJLinkedMapNode : NSObject {
    @package
    //指针域 前驱
    __unsafe_unretained _ZJLinkedMapNode *_prev;
    //指针域 后继
    __unsafe_unretained _ZJLinkedMapNode *_next;
    //用于存哈希表的key
    id _key;
    //数据域 value
    id _value;
}
@end

@implementation _ZJLinkedMapNode
@end

@implementation ZJMemeryCache

@end

2）接下来我们再在ZJMemeryCache.m内部实现双链表_ZJLinkedMapNode
ZJMemeryCache.m代码如下

//
//  ZJMemeryCache.m
//  ZJMemeryCache
//
//  Created by zhoujie on 2022/3/14.
//  Copyright © 2022 ibireme. All rights reserved.
//

#import "ZJMemeryCache.h"

//双链表节点
@interface _ZJLinkedMapNode : NSObject { ... }
@end

@implementation _ZJLinkedMapNode
@end

@interface _ZJLinkedMap : NSObject {
    @package
    //头指针
    _ZJLinkedMapNode *_head;
    //尾指针，用于降低删除尾节点的时间复杂度
    _ZJLinkedMapNode *_tail;
}
/// 若数据没有在缓存中，将数据从头插入，代表最近最多使用
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node;
/// 若数据在缓存中，先将数据删除，再从头插入
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node;
/// 删除指定节点
- (void)removeNode:(_ZJLinkedMapNode *)node;
/// 移除尾节点，代表缓存已满，需要删除最近最少使用的数据
- (_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

我们先来实现- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node;这个方法，这个方法对应的是LRU运行原理图示中的第2、3、4步，缓存中没有数据，直接缓存，实现代码如下

/// 若数据没有在缓存中，将数据从头插入，代表最近最多使用
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node {
    if (_head) {
        //链表不为空,从头插入新节点
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    }else {
        //链表为空
        _head = node;
        _tail = node;
    }
}

再来实现- (void)bringNodeToHead:(_ZJLinkedMapNode *)node;这个方法，这个方法对应的图中的第6步，先删除对应节点，再将删除的节点从头插入

/// 若数据在缓存中，先将数据删除，再从头插入
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node {
    //如果命中的节点是头节点，则不用处理
    if (node == _head) {
        return;
    }
    //删除命中的节点
    if (node == _tail) {
        _tail = _tail->_prev;
        _tail->_next = nil;
    }else {
        node->_prev->_next = node->_next;
        node->_next->_prev = node->_prev;
    }
    //从头插入刚删除的节点
    node->_next = _head;
    node->_prev = nil;
    _head->_prev = node;
    _head = node;
}

再实现- (void)removeNode:(_ZJLinkedMapNode *)node;这个方法

/// 删除指定节点
- (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;
    }
}

最后再实现- (_ZJLinkedMapNode *)removeTailNode;这个方法，这个方法在缓存满了之后调用，删除最近最少使用的数据，对应的是图中第5步的移除数据1

/// 移除尾节点，代表缓存已满，需要删除最近最少使用的数据
- (_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中新增一个成员变量NSDictionary *_dic;

@interface _ZJLinkedMap : NSObject {
    @package
    //头指针
    _ZJLinkedMapNode *_head;
    //尾指针，用于降低删除尾节点的时间复杂度
    _ZJLinkedMapNode *_tail;
    //哈希表，存储节点
    NSMutableDictionary *_dic;
    //当前容量
    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) {
        //链表不为空,从头插入新节点
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    }else {
        //链表为空
        _head = node;
        _tail = node;
    }
}

到这里，我们双向链表+哈希表的逻辑就算写完了，我们在ZJMemeryCache.m中实现缓存功能
4）ZJMemeryCache实现缓存功能
我们申明两个方法
取缓存:- (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>

//双链表节点
@interface _ZJLinkedMapNode : NSObject { ... }
@end

@implementation _ZJLinkedMapNode
@end

@interface _ZJLinkedMap : NSObject { ... }
@end

@implementation _ZJLinkedMap { ... }
@end


@implementation ZJMemeryCache {
    //添加线程锁，保证ZJLinkedMap的线程安全
    pthread_mutex_t _lock;
    //lru(双向链表+哈希表结构)
    _ZJLinkedMap *_lru;
}

- (instancetype)init {
    if (self = [super init]) {
        //初始化锁
        pthread_mutex_init(&_lock, NULL);
        //初始化存储的数据结构
        _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，取缓存很简单，直接从缓存中查找，找到将此数据移动到最左侧代表最近最多使用

// 取缓存
- (nullable id)objectForKey:(id)key {
    if (!key) return nil;
    //加锁，保证线程安全
    pthread_mutex_lock(&_lock);
    //从缓存中查找数据，如果找到数据，将此数据变成最近最多使用，没有直接返回空
    _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);
    //从缓存中查找数据，如果找到数据，将此数据变成最近最多使用，没有直接返回空
    _ZJLinkedMapNode *node = _lru->_dic[@"key"];
    if (node) {
        //如果能查到，直接移动
        [_lru bringNodeToHead:node];
    }else {
        //不能查到,需要缓存
        //在缓存前需要判定缓存是否满了
        if (_lru->count >= _countLimit) {
            //缓存满了需要删除最近最少使用的数据
            [_lru removeTailNode];
        }
        //添加最近最多使用的数据
        node = [_ZJLinkedMapNode new];
        node->_key = key;
        node->_value = object;
        [_lru insertNodeAtHead:node];
    }
    pthread_mutex_unlock(&_lock);
}

到这里YYMemeryCache里的LRU功能就算写完了，最后附上YYMemeryCache里的代码和我们写的代码对比

ZJMemeryCache

//
//  ZJMemeryCache.m
//  ZJMemeryCache
//
//  Created by zhoujie on 2022/3/14.
//  Copyright © 2022 ibireme. All rights reserved.
//

#import "ZJMemeryCache.h"
#import <pthread.h>

//双链表节点
@interface _ZJLinkedMapNode : NSObject {
    @package
    //指针域 前驱
    __unsafe_unretained _ZJLinkedMapNode *_prev;
    //指针域 后继
    __unsafe_unretained _ZJLinkedMapNode *_next;
    //用于存哈希表的key
    id _key;
    //数据域 value
    id _value;
}
@end

@implementation _ZJLinkedMapNode
@end

@interface _ZJLinkedMap : NSObject {
    @package
    //头指针
    _ZJLinkedMapNode *_head;
    //尾指针，用于降低删除尾节点的时间复杂度
    _ZJLinkedMapNode *_tail;
    //哈希表，存储节点
    NSMutableDictionary *_dic;
    //当前容量
    NSInteger count;
}
/// 若数据没有在缓存中，将数据从头插入，代表最近最多使用
- (void)insertNodeAtHead:(_ZJLinkedMapNode *)node;
/// 若数据在缓存中，先将数据删除，再从头插入
- (void)bringNodeToHead:(_ZJLinkedMapNode *)node;
/// 删除指定节点
- (void)removeNode:(_ZJLinkedMapNode *)node;
/// 移除尾节点，代表缓存已满，需要删除最近最少使用的数据
- (_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) {
        //链表不为空,从头插入新节点
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    }else {
        //链表为空
        _head = node;
        _tail = node;
    }
}

- (void)bringNodeToHead:(_ZJLinkedMapNode *)node {
    //如果命中的节点是头节点，则不用处理
    if (node == _head) {
        return;
    }
    //删除命中的节点
    if (node == _tail) {
        _tail = _tail->_prev;
        _tail->_next = nil;
    }else {
        node->_prev->_next = node->_next;
        node->_next->_prev = node->_prev;
    }
    //从头插入刚删除的节点
    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;
    }
}

/// 移除尾节点，代表缓存已满，需要删除最近最少使用的数据
- (_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(双向链表+哈希表结构)
    _ZJLinkedMap *_lru;
}

- (instancetype)init {
    if (self = [super init]) {
        //初始化锁
        pthread_mutex_init(&_lock, NULL);
        //初始化存储的数据结构
        _lru = [_ZJLinkedMap new];
        //初始化缓存大小
        _countLimit = 10;
    }
    return self;
}

// 取缓存
- (nullable id)objectForKey:(id)key {
    if (!key) return nil;
    //加锁，保证线程安全
    pthread_mutex_lock(&_lock);
    //从缓存中查找数据，如果找到数据，将此数据变成最近最多使用，没有直接返回空
    _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);
    //从缓存中查找数据，如果找到数据，将此数据变成最近最多使用，没有直接返回空
    _ZJLinkedMapNode *node = _lru->_dic[@"key"];
    if (node) {
        //如果能查到，直接移动
        [_lru bringNodeToHead:node];
    }else {
        //不能查到,需要缓存
        //在缓存前需要判定缓存是否满了
        if (_lru->count >= _countLimit) {
            //缓存满了需要删除最近最少使用的数据
            [_lru removeTailNode];
        }
        //添加最近最多使用的数据
        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