前言
关于什么是weak关键字可以去看看我以前的一篇博客：【OC】 属性关键字
weak原理
1. SideTable
SideTable 这个结构体，前辈给它总结了一个很形象的名字叫引用计数和弱引用依赖表，因为它主要用于管理对象的引用计数和 weak 表。在 NSObject.mm 中声明其数据结构：
struct SideTable {
// 保证原子操作的自旋锁
spinlock_t slock;
// 引用计数的 hash 表
RefcountMap refcnts;
// weak 引用全局 hash 表
weak_table_t weak_table;
SideTable() {
memset(&weak_table, 0, sizeof(weak_table));
}
~SideTable() {
_objc_fatal("Do not delete SideTable.");
}
void lock() {
slock.lock(); }
void unlock() {
slock.unlock(); }
void reset() {
slock.reset(); }
// Address-ordered lock discipline for a pair of side tables.
template<HaveOld, HaveNew>
static void lockTwo(SideTable *lock1, SideTable *lock2);
template<HaveOld, HaveNew>
static void unlockTwo(SideTable *lock1, SideTable *lock2);
}
slock是为了防止竞争选择的自旋锁
refcnts 是协助对象的 isa 指针的 extra_rc 共同引用计数的变量（对于对象结果，在后文提到）
接着我们来看一下SideTable中的这三个成员变量：
1.1 spinlock_t slock 自旋锁
自旋锁的效率高于互斥锁。但是我们要注意由于自旋时不释放CPU，因而持有自旋锁的线程应该尽快释放自旋锁，否则等待该自旋锁的线程会一直在哪里自旋，这就会浪费CPU时间。
在操作引用计数的时候对SideTable加锁，避免数据错误。
1.2 RefcountMap
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
其中DenseMap 又是一个模板类:
template<typename KeyT, typename ValueT,
bool ZeroValuesArePurgeable = false,
typename KeyInfoT = DenseMapInfo<KeyT> >
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT,
ZeroValuesArePurgeable, KeyInfoT>, KeyT, ValueT, KeyInfoT,
ZeroValuesArePurgeable> {
...
BucketT *Buckets;
unsigned NumEntries;
unsigned NumTombstones;
unsigned NumBuckets;
...
}
比较重要的成员有这几个：
1.ZeroValuesArePurgeable 默认值是 false, 但 RefcountMap 指定其初始化为 true。 这个成员标记是否可以使用值为 0 (引用计数为 1) 的桶. 因为空桶存的初始值就是 0, 所以值为 0 的桶和空桶没什么区别.。如果允许使用值为 0 的桶, 查找桶时如果没有找到对象对应的桶, 也没有找到墓碑桶, 就会优先使用值为 0 的桶。
2.Buckets 指针管理一段连续内存空间, 也就是数组, 数组成员是 BucketT 类型的对象, 我们这里将 BucketT 对象称为桶(实际上这个数组才应该叫桶, 苹果把数组中的元素称为桶应该是为了形象一些, 而不是哈希桶中的桶的意思)。桶数组在申请空间后, 会进行初始化, 在所有位置上都放上空桶(桶的 key 为 EmptyKey 时是空桶), 之后对引用计数的操作, 都要依赖于桶。
桶的数据类型实际上是 std::pair, 类似于 swift 中的元祖类型, 就是将对象地址和对象的引用计数(这里的引用计数类似于isa, 也是使用其中的几个 bit 来保存引用计数, 留出几个 bit 来做其它标记位)组合成一个数据类型。
BucketT 的定义如下：
typedef std::pair<KeyT, ValueT> BucketT;
3.NumEntries 记录数组中已使用的非空的桶的个数.
4.NumTombstones, Tombstone 直译为墓碑, 当一个对象的引用计数为0, 要从桶中取出时, 其所处的位置会被标记为 Tombstone. NumTombstones 就是数组中的墓碑的个数. 后面会介绍到墓碑的作用.
5.NumBuckets 桶的数量, 因为数组中始终都充满桶, 所以可以理解为数组大小.
inline uint64_t NextPowerOf2(uint64_t A) {
A |= (A >> 1);
A |= (A >> 2);
A |= (A >> 4);
A |= (A >> 8);
A |= (A >> 16);
A |= (A >> 32);
return A + 1;
}
这是对应 64 位的提供数组大小的方法, 需要为桶数组开辟空间时, 会由这个方法来决定数组大小. 这个算法可以做到把最高位的 1 覆盖到所有低位. 例如 A = 0b10000, (A >> 1) = 0b01000, 按位与就会得到 A = 0b11000, 这个时候 (A >> 2) = 0b00110, 按位与就会得到 A = 0b11110. 以此类推 A 的最高位的 1, 会一直覆盖到高 2 位、高 4 位、高 8 位, 直到最低位. 最后这个充满 1 的二进制数会再加 1, 得到一个 0b1000…(N 个 0). 也就是说, 桶数组的大小会是 2^n.
RefcountMap 的工作逻辑
1.通过计算对象地址的哈希值, 来从 SideTables 中获取对应的 SideTable. 哈希值重复的对象的引用计数存储在同一个 SideTable 里.
2.SideTable 使用 find() 方法和重载 [] 运算符的方式, 通过对象地址来确定对象对应的桶. 最终执行到的查找算法是 LookupBucketFor().
3.查找算法会先对桶的个数进行判断, 如果桶数为 0 则 return false 回上一级调用插入方法. 如果查找算法找到空桶或者墓碑桶, 同样 return false 回上一级调用插入算法, 不过会先记录下找到的桶. 如果找到了对象对应的桶, 只需要对其引用计数 + 1 或者 - 1. 如果引用计数为 0 需要销毁对象, 就将这个桶中的 key 设置为 TombstoneKey
value_type& FindAndConstruct(const KeyT &Key) {
BucketT *TheBucket;
if (LookupBucketFor(Key, TheBucket))
return *TheBucket;
return *InsertIntoBucket(Key, ValueT(), TheBucket);
}
4.插入算法会先查看可用量, 如果哈希表的可用量(墓碑桶+空桶的数量)小于 1/4, 则需要为表重新开辟更大的空间, 如果表中的空桶位置少于 1/8 (说明墓碑桶过多), 则需要清理表中的墓碑. 以上两种情况下哈希查找算法会很难查找正确位置, 甚至可能会产生死循环, 所以要先处理表, 处理表之后还会重新分配所有桶的位置, 之后重新查找当前对象的可用位置并插入. 如果没有发生以上两种情况, 就直接把新的对象的引用计数放入调用者提供的桶里.
墓碑的作用：
- 如果 c 对象销毁后将下标 2 的桶设置为空桶而不置为墓碑桶的话, 此时为 e 对象增加引用计数, 根据哈希算法查找到下标为 2 的桶时, 就会直接插入, 无法为已经在下标为 4 的桶中的 e 增加引用计数，但是我们正常的流程中c 对象销毁后下标 2的桶将会被置为墓碑桶，这样的话，在对e对象增加引用计数的时候，根据哈希算法找到下标为2的桶时，就会将2跳过，往后继续查找，直至找到e对象所对应的桶为止，或者直至找到空桶新建一个存e对象的桶
- 如果此时初始化了一个新的对象 f, 根据哈希算法查找到下标为 2 的桶时发现桶中放置了墓碑, 此时会记录下来下标 2. 接下来继续哈希算法查找位置, 查找到空桶时, 就证明表中没有对象 f, 此时 f 使用记录好的下标 2 的墓碑桶而不是查找到的空桶, 就可以利用到已经释放的位置，保证哈希表中前面部分都是被利用或者待利用的状态。
查找某对象对应桶的源码如下：文章来源：https://www.toymoban.com/news/detail-604928.html
bool LookupBucketFor(const LookupKeyT &Val,
const BucketT *&FoundBucket) const {
...
if (NumBuckets == 0) {
//桶数是0
FoundBucket = 0;
return false; //返回 false 回上层调用添加函数
}
...
unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); //将哈希值与数组最大下标按位与
unsigned ProbeAmt = 1; //哈希值重复的对象需要靠它来重新寻找位置
while (1) {
const BucketT *ThisBucket = BucketsPtr + BucketNo; //头指针 + 下标, 类似于数组取值
//找到的桶中的 key 和对象地址相等, 则是找到
if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
FoundBucket = ThisBucket;
return true;
}
//找到的桶中的 key 是空桶占位符, 则表示可插入
if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
if (FoundTombstone) ThisBucket = FoundTombstone; //如果曾遇到墓碑, 则使用墓碑的位置
FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
return false; //找到空占位符, 则表明表中没有已经插入了该对象的桶
}
//如果找到了墓碑
if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
FoundTombstone = ThisBucket; // 记录下墓碑
//这里涉及到最初定义 typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap, 传入的第三个参数 true
//这个参数代表是否可以清除 0 值, 也就是说这个参数为 true 并且没有墓碑的时候, 会记录下找到的 value 为 0 的桶
if (ZeroValuesArePurgeable &&
ThisBucket->second == 0 && !FoundTombstone)
FoundTombstone = ThisBucket;
//用于计数的 ProbeAmt 如果大于了数组容量, 就会抛出异常
if (ProbeAmt > NumBuckets) {
_objc_fatal("...");
}
BucketNo += ProbeAmt++; //本次哈希计算得出的下表不符合, 则利用 ProbeAmt 寻找下一个下标
BucketNo&= (NumBuckets-1); //得到新的数字和数组下标最大值按位与
}
}
向某对象的引用计数桶插入代码如下：文章来源地址https://www.toymoban.com/news/detail-604928.html
BucketT *InsertIntoBucketImpl(const KeyT &到了这里，关于【iOS】weak关键字的实现原理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
