NSCache 源码分析

读代码是一种修行，也是一种乐趣。读好代码尤其如此。

作者：@nixzhu

引用：Foundation/NSCache.swift

因为 NSCache 的代码并不多，所以先从其下手。顺便体会一下 Foundation 的编程风格。

首先要明确 NSCache 是什么：一个类似集合的容器，内里放置“键值对”，感觉上类似 NSDictionary 或者 Swift 的内置字典类型。

我们之所以用缓存，是为了以空间换时间（占用访问速度更快的内存，节省IO时间），自然是期望其带来性能提升，这就要求用“键”访问缓存得到“值”的速度非常快。不过受限于系统资源，NSCache 会自动管理缓存里的内容（通常是移除一些键值），这就和字典不一样了。

我们使用 NSCache 的方式就是以“键”为名，往里面添加、移除以及查询“值”。

初始化

NSCache 的 init 方法里没有内容，也就是说，以

let cache = NSCache()

即可创建一个缓存。但随之就可以设置几个公开属性：

public var name: String = ""
public var totalCostLimit: Int = -1 // limits are imprecise/not strict
public var countLimit: Int = -1 // limits are imprecise/not strict
public var evictsObjectsWithDiscardedContent: Bool = false

其中，totalCostLimit 和 countLimit 都是为了限制缓存里数据的多少，但并不严格，系统仍然会考虑可调整性。
evictsObjectsWithDiscardedContent不知何意，似乎没有被使用。

还有几个私有属性，比较重要：

private var _entries = Dictionary<UnsafePointer<Void>, NSCacheEntry>()
private let _lock = NSLock()
private var _totalCost = 0
private var _byCost: NSCacheEntry?

_entries 是一个字典，它的 key 为指针（之后会看到用法），value 为私有类 NSCacheEntry：

private class NSCacheEntry {
    var key: AnyObject
    var value: AnyObject
    var cost: Int
    var prevByCost: NSCacheEntry?
    var nextByCost: NSCacheEntry?
    init(key: AnyObject, value: AnyObject, cost: Int) {
        self.key = key
        self.value = value
        self.cost = cost
    }
}

可见 NSCacheEntry 就是对“键值对”的封装，因为缓存对象有重要性的分别，自然有 cost 作为表示。

_lock 作为锁，是为了防止多线程访问时出现不一致的问题，后面分析代码会看到其用法。

_totalCost 为缓存里所有对象的价值。

_byCost 会指向一个 NSCacheEntry，即一个“键值对”，但它用于何处后面再看。

添加

NSCache 提供的 API 是 setObject() 和 setObject(cost:)，实际上前者会调用后者，只不过 cost 默认为 0。下面随我一起来阅读并注释其代码：

public func setObject(obj: AnyObject, forKey key: AnyObject, cost g: Int) {
    let keyRef = unsafeBitCast(key, UnsafePointer<Void>.self) // 生成 key 指针（这样应该会少占用一些内存）
    _lock.lock()  // 因为是添加（即修改），先锁起来，防止其他线程改动
    _totalCost += g   // 整体价值自然增加了
    var purgeAmount = 0   // 计算应该被清除的“价值”（因为缓存容量有限，现在要添加新的进来，很可能超过限制，需要移除一些旧的）
    if totalCostLimit > 0 {
        purgeAmount = (_totalCost + g) - totalCostLimit // 前面刚加过 g，这里再加有些难解
    }
    var purgeCount = 0  // 计算应该被清除的数量，理由同上
    if countLimit > 0 {
        purgeCount = (_entries.count + 1) - countLimit // 这里加 1 好理解，毕竟还没有正式放进去，但也可能同样的 key 已存在，难解
    }
    // 用前面生成的 keyRef 来做查询，看看是否已有此 key 的值，有的话就要更新 value 了，顺便修改其“价值”
    if let entry = _entries[keyRef] {
        entry.value = obj
        if entry.cost != g {
            entry.cost = g
            remove(entry) // 之所以要 remove 又 insert，是为了修改 entry 的 prevByCost 和 nextByCost
            insert(entry) // 由此可见，所有的 entry 会组成一个链表，以 cost 排序（但这要建立在每个 entry 的 cost 不相同的前提下）
        }
    } else {
        _entries[keyRef] = NSCacheEntry(key: key, value: obj, cost: g) // 初次设置此 key 的 value
    }
    _lock.unlock() // 这时候写入已经结束，就尽快打开锁，其它线程可能嗷嗷待哺呢
    // 上面算了 purgeAmount 和 purgeCount，此时自然该做一做处理
    // 但如果用户没有设置 totalCostLimit 和 countLimit，下面的代码其实不会工作（而通常我们都不会设置它们，但系统本身也会使用 NSCache，需要更好地控制）
    var toRemove = [NSCacheEntry]()
    if purgeAmount > 0 { // 删除一些对象以便满足 totalCostLimit
        _lock.lock()
        while _totalCost - totalCostLimit > 0 {
            if let entry = _byCost {
                _totalCost -= entry.cost
                toRemove.append(entry)
                remove(entry)
            } else {
                break
            }
        }
        if countLimit > 0 {
            purgeCount = (_entries.count - toRemove.count) - countLimit // 因为删除了一些，重新计算 purgeCount
        }
        _lock.unlock()
    }
    if purgeCount > 0 { // 同样的道理，整体数量可能仍然过多，再删除一些以满足 countLimit
        _lock.lock()
        while (_entries.count - toRemove.count) - countLimit > 0 {
            if let entry = _byCost {
                _totalCost -= entry.cost
                toRemove.append(entry)
                remove(entry)
            } else {
                break
            }
        }
        _lock.unlock()
    }
    // 告诉 delegate 要删除的对象
    if let del = delegate {
        for entry in toRemove {
            del.cache(self, willEvictObject: entry.value)
        }
    }
    // 真正做移除工作
    _lock.lock()
    for entry in toRemove {
        _entries.removeValueForKey(unsafeBitCast(entry.key, UnsafePointer<Void>.self)) // the cost list is already fixed up in the purge routines
    }
    _lock.unlock()
}

由此可见，作为程序员，我们使用 NSCache 时基本是不需要操心管理的问题，只管往里面添加即可。

访问

而访问极其简单：

public func objectForKey(key: AnyObject) -> AnyObject? {
    var object: AnyObject?
    let keyRef = unsafeBitCast(key, UnsafePointer<Void>.self) // 一样生成 key 指针
    _lock.lock()
    if let entry = _entries[keyRef] { // 查找
        object = entry.value  // 找到“值”即可
    }
    _lock.unlock()
    return object
}

注意上面仍然用了锁，按理说，查询（读）是不需要锁的，但这里的代码是要先找到 entry 再取出其 value，这个过程不能被打断，所以加锁保护。

删除

最后是删除，以便程序员需要更仔细地控制缓存里的内容：

public func removeObjectForKey(key: AnyObject) {
    let keyRef = unsafeBitCast(key, UnsafePointer<Void>.self)
    _lock.lock()
    if let entry = _entries.removeValueForKey(keyRef) { // 找到 entry 的时候就已经移除了其 value
        _totalCost -= entry.cost
        remove(entry)
    }
    _lock.unlock()
}

还有一个 removeAllObjects：

public func removeAllObjects() {
    _lock.lock()
    _entries.removeAll()
    _byCost = nil
    _totalCost = 0
    _lock.unlock()
}

因为是全删，自然更容易（破坏比建立容易）。

上面的分析的三个方法里，用了两个私有方法：remove 和 insert，也稍微看看它们的实现：

private func remove(entry: NSCacheEntry) {
    let oldPrev = entry.prevByCost
    let oldNext = entry.nextByCost
    oldPrev?.nextByCost = oldNext
    oldNext?.prevByCost = oldPrev
    if entry === _byCost {
        _byCost = entry.nextByCost
    }
}

因为要被移除的是 entry，其前驱节点（如果有的话）的后续节点就要改为当前 entry 的后续节点了，很好理解。同理处理其后续节点的前驱节点。这就像将链条里的一个环节去除，旁边两个再连起来，以便维持为一条链子。

同时更新 _byCost 这个全局变量。

private func insert(entry: NSCacheEntry) {
    if _byCost == nil {
        _byCost = entry
    } else {
        var element = _byCost
        while let e = element {
            if e.cost > entry.cost {
                let newPrev = e.prevByCost
                entry.prevByCost = newPrev
                entry.nextByCost = e
                break
            }
            element = e.nextByCost
        }
    }
}

插入的代码类似。如果 _byCost 没有指向任何值，就指向本次插入的 entry（说明第一个 entry 会由 _byCost 指向）。否则：

以 _byCost 所代表的 entry 开始，寻找第一个“价值”大于本次将插入的 entry 的元素，找到了就好放置 entry 了，设置好它的 prevByCost 和 nextByCost。注意这里并没有修改 e 的 prevByCost，这说明价值越小的排越前。（但似乎链表被破坏了，也许该在 break 前加一句 e.prevByCost = entry。）

但平常我们使用 NSCache 时，并不管“价值”，上面的 insert 其实不会被调用。这说明，链表只在我们很关心 entry 的价值时才会建立起来，且 _byCost 指向当前价值最小的一个，便于实现删除逻辑。

以上是个人的粗浅理解，如有错漏，欢迎指正！

欢迎转载，但请一定注明出处！ https://github.com/nixzhu/dev-blog