NSCache 源码分析(转)
出处-> https://github.com/nixzhu/dev-blog
NSCache 源码分析
读代码是一种修行，也是一种乐趣。读好代码尤其如此。
作者：@nixzhu
因为 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(:forKey:) 和 setObject(:forKey: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 指向当前价值最小的一个，便于实现删除逻辑。
以上是个人的粗浅理解，如有错漏，欢迎指正！
