源码浅析-iOS缓存NSCache-一一网

摘要

NSCache 是 iOS 上常用的缓存机制。

其内部数据结构是「哈希表 + 双向链表」。

当需要释放空间时，它优先删除「成本」较高的。

分析

核心变量如下，可看到其中的「哈希表 + 双向链表」结构。

open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
    // note(jd): 哈希表
    private var _entries = Dictionary<NSCacheKey, NSCacheEntry<KeyType, ObjectType>>()

    private let _lock = NSLock() // note(jd): 加锁，保证线程安全

    private var _head: NSCacheEntry<KeyType, ObjectType>? // note(jd): 双向链表节点

    // note(jd): 缓存的 2 个限制
    open var totalCostLimit: Int = 0 // limits are imprecise/not strict
    open var countLimit: Int = 0 // limits are imprecise/not strict
    ...
}
复制代码

双向链表节点：

其中的 cost 可以理解为成本，由接入方设置，一般会是缓存的大小。

private class NSCacheEntry<KeyType : AnyObject, ObjectType : AnyObject> {
    var key: KeyType
    var value: ObjectType
    var cost: Int
    var prevByCost: NSCacheEntry?
    var nextByCost: NSCacheEntry?
    init(key: KeyType, value: ObjectType, cost: Int) {
        self.key = key
        self.value = value
        self.cost = cost
    }
}
复制代码

对于 get，只是从 _entries 中获取。

我们重点关注 set 的过程。

open func setObject(_ obj: ObjectType, forKey key: KeyType, cost g: Int) {
    let g = max(g, 0)
    let keyRef = NSCacheKey(key)

    _lock.lock()

    let costDiff: Int

    if let entry = _entries[keyRef] { // note(jd): 该 obj 已存在，更新 cost、value
        costDiff = g - entry.cost
        entry.cost = g

        entry.value = obj

        // note(jd): 为何 cost 不同时，需要移除后，再重新插入呢？
        // 因为需要保证链表按 cost 大小排序
        if costDiff != 0 {
            remove(entry)
            insert(entry)
        }
    } else {// note(jd): obj 不存在，直接插入
        let entry = NSCacheEntry(key: key, value: obj, cost: g)
        _entries[keyRef] = entry
        insert(entry)

        costDiff = g
    }

    _totalCost += costDiff
    // note(jd): 超过 cost 的处理
    var purgeAmount = (totalCostLimit> 0) ? (_totalCost - totalCostLimit) : 0
    while purgeAmount > 0 {
        if let entry = _head {// note(jd): 删除头节点
            delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)

            _totalCost -= entry.cost
            purgeAmount -= entry.cost

            remove(entry) // _head will be changed to next entry in remove(_:)
            _entries[NSCacheKey(entry.key)] = nil
        } else {
            break
        }
    }

    // note(jd): 超过 count 的处理

    var purgeCount = (countLimit> 0) ? (_entries.count - countLimit) : 0
    while purgeCount > 0 {
        // 与上面类似
    }

    _lock.unlock()
}
复制代码

而在插入代码节点时，会保证链表是按 cost 大小降序排列。

private func insert(_ entry: NSCacheEntry<KeyType, ObjectType>) {
    guard var currentElement = _head else {
        // The cache is empty
        entry.prevByCost = nil
        entry.nextByCost = nil

        _head = entry
        return
    }
    // note(jd): 以下代码，会保证将 cost 较大的节点，放在 head，这样在需要释放空间时，优先删除 head 即可

    guard entry.cost > currentElement.cost else {// note(jd): 若超过 head，直接插入到头部
        // Insert entry at the head
        entry.prevByCost = nil
        entry.nextByCost = currentElement
        currentElement.prevByCost = entry

        _head = entry
        return
    }

    // note(jd): 寻找合适和插入位置
    while let nextByCost = currentElement.nextByCost, nextByCost.cost < entry.cost {
        currentElement = nextByCost
    }

    // Insert entry between currentElement and nextElement
    let nextElement = currentElement.nextByCost

    currentElement.nextByCost = entry
    entry.prevByCost = currentElement

    entry.nextByCost = nextElement
    nextElement?.prevByCost = entry
}
复制代码