前言

關于什么是weak關鍵字可以去看看我以前的一篇博客：【OC】 屬性關鍵字

weak原理

1. SideTable

SideTable 這個結構體，前輩給它總結了一個很形象的名字叫引用計數(shù)和弱引用依賴表，因為它主要用于管理對象的引用計數(shù)和 weak 表。在 NSObject.mm 中聲明其數(shù)據(jù)結構：

struct SideTable {
   
// 保證原子操作的自旋鎖
    spinlock_t slock;
    // 引用計數(shù)的 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 是協(xié)助對象的 isa 指針的 extra_rc 共同引用計數(shù)的變量（對于對象結果，在后文提到）

接著我們來看一下SideTable中的這三個成員變量：

1.1 spinlock_t slock 自旋鎖

自旋鎖的效率高于互斥鎖。但是我們要注意由于自旋時不釋放CPU，因而持有自旋鎖的線程應該盡快釋放自旋鎖，否則等待該自旋鎖的線程會一直在哪里自旋，這就會浪費CPU時間。

在操作引用計數(shù)的時候?qū)ideTable加鎖，避免數(shù)據(jù)錯誤。

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 (引用計數(shù)為 1) 的桶. 因為空桶存的初始值就是 0, 所以值為 0 的桶和空桶沒什么區(qū)別.。如果允許使用值為 0 的桶, 查找桶時如果沒有找到對象對應的桶, 也沒有找到墓碑桶, 就會優(yōu)先使用值為 0 的桶。
2.Buckets 指針管理一段連續(xù)內(nèi)存空間, 也就是數(shù)組, 數(shù)組成員是 BucketT 類型的對象, 我們這里將 BucketT 對象稱為桶(實際上這個數(shù)組才應該叫桶, 蘋果把數(shù)組中的元素稱為桶應該是為了形象一些, 而不是哈希桶中的桶的意思)。桶數(shù)組在申請空間后, 會進行初始化, 在所有位置上都放上空桶(桶的 key 為 EmptyKey 時是空桶), 之后對引用計數(shù)的操作, 都要依賴于桶。
桶的數(shù)據(jù)類型實際上是 std::pair, 類似于 swift 中的元祖類型, 就是將對象地址和對象的引用計數(shù)(這里的引用計數(shù)類似于isa, 也是使用其中的幾個 bit 來保存引用計數(shù), 留出幾個 bit 來做其它標記位)組合成一個數(shù)據(jù)類型。

BucketT 的定義如下：

typedef std::pair<KeyT, ValueT> BucketT;

3.NumEntries 記錄數(shù)組中已使用的非空的桶的個數(shù).

4.NumTombstones, Tombstone 直譯為墓碑, 當一個對象的引用計數(shù)為0, 要從桶中取出時, 其所處的位置會被標記為 Tombstone. NumTombstones 就是數(shù)組中的墓碑的個數(shù). 后面會介紹到墓碑的作用.

5.NumBuckets 桶的數(shù)量, 因為數(shù)組中始終都充滿桶, 所以可以理解為數(shù)組大小.

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 位的提供數(shù)組大小的方法, 需要為桶數(shù)組開辟空間時, 會由這個方法來決定數(shù)組大小. 這個算法可以做到把最高位的 1 覆蓋到所有低位. 例如 A = 0b10000, (A >> 1) = 0b01000, 按位與就會得到 A = 0b11000, 這個時候 (A >> 2) = 0b00110, 按位與就會得到 A = 0b11110. 以此類推 A 的最高位的 1, 會一直覆蓋到高 2 位、高 4 位、高 8 位, 直到最低位. 最后這個充滿 1 的二進制數(shù)會再加 1, 得到一個 0b1000…(N 個 0). 也就是說, 桶數(shù)組的大小會是 2^n.

RefcountMap 的工作邏輯
1.通過計算對象地址的哈希值, 來從 SideTables 中獲取對應的 SideTable. 哈希值重復的對象的引用計數(shù)存儲在同一個 SideTable 里.
2.SideTable 使用 find() 方法和重載 [] 運算符的方式, 通過對象地址來確定對象對應的桶. 最終執(zhí)行到的查找算法是 LookupBucketFor().
3.查找算法會先對桶的個數(shù)進行判斷, 如果桶數(shù)為 0 則 return false 回上一級調(diào)用插入方法. 如果查找算法找到空桶或者墓碑桶, 同樣 return false 回上一級調(diào)用插入算法, 不過會先記錄下找到的桶. 如果找到了對象對應的桶, 只需要對其引用計數(shù) + 1 或者 - 1. 如果引用計數(shù)為 0 需要銷毀對象, 就將這個桶中的 key 設置為 TombstoneKey

value_type& FindAndConstruct(const KeyT &Key) {
   
    BucketT *TheBucket;
    if (LookupBucketFor(Key, TheBucket))
      return *TheBucket;
    return *InsertIntoBucket(Key, ValueT(), TheBucket);
  }

4.插入算法會先查看可用量, 如果哈希表的可用量(墓碑桶+空桶的數(shù)量)小于 1/4, 則需要為表重新開辟更大的空間, 如果表中的空桶位置少于 1/8 (說明墓碑桶過多), 則需要清理表中的墓碑. 以上兩種情況下哈希查找算法會很難查找正確位置, 甚至可能會產(chǎn)生死循環(huán), 所以要先處理表, 處理表之后還會重新分配所有桶的位置, 之后重新查找當前對象的可用位置并插入. 如果沒有發(fā)生以上兩種情況, 就直接把新的對象的引用計數(shù)放入調(diào)用者提供的桶里.

墓碑的作用：

1. 如果 c 對象銷毀后將下標 2 的桶設置為空桶而不置為墓碑桶的話, 此時為 e 對象增加引用計數(shù), 根據(jù)哈希算法查找到下標為 2 的桶時, 就會直接插入, 無法為已經(jīng)在下標為 4 的桶中的 e 增加引用計數(shù)，但是我們正常的流程中c 對象銷毀后下標 2的桶將會被置為墓碑桶，這樣的話，在對e對象增加引用計數(shù)的時候，根據(jù)哈希算法找到下標為2的桶時，就會將2跳過，往后繼續(xù)查找，直至找到e對象所對應的桶為止，或者直至找到空桶新建一個存e對象的桶
2. 如果此時初始化了一個新的對象 f, 根據(jù)哈希算法查找到下標為 2 的桶時發(fā)現(xiàn)桶中放置了墓碑, 此時會記錄下來下標 2. 接下來繼續(xù)哈希算法查找位置, 查找到空桶時, 就證明表中沒有對象 f, 此時 f 使用記錄好的下標 2 的墓碑桶而不是查找到的空桶, 就可以利用到已經(jīng)釋放的位置，保證哈希表中前面部分都是被利用或者待利用的狀態(tài)。

查找某對象對應桶的源碼如下：

bool LookupBucketFor(const LookupKeyT &Val,
                       const BucketT *&FoundBucket) const {
   
    ...
    if (NumBuckets == 0) {
    //桶數(shù)是0
      FoundBucket = 0;
      return false; //返回 false 回上層調(diào)用添加函數(shù)
    }
    ...
    unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); //將哈希值與數(shù)組最大下標按位與
    unsigned ProbeAmt = 1; //哈希值重復的對象需要靠它來重新尋找位置
    while (1) {
   
      const BucketT *ThisBucket = BucketsPtr + BucketNo; //頭指針 + 下標, 類似于數(shù)組取值
      //找到的桶中的 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; //找到空占位符, 則表明表中沒有已經(jīng)插入了該對象的桶
      }
      //如果找到了墓碑
      if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
        FoundTombstone = ThisBucket;  // 記錄下墓碑
      //這里涉及到最初定義 typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap, 傳入的第三個參數(shù) true
      //這個參數(shù)代表是否可以清除 0 值, 也就是說這個參數(shù)為 true 并且沒有墓碑的時候, 會記錄下找到的 value 為 0 的桶
      if (ZeroValuesArePurgeable  && 
          ThisBucket->second == 0  &&  !FoundTombstone) 
        FoundTombstone = ThisBucket;

      //用于計數(shù)的 ProbeAmt 如果大于了數(shù)組容量, 就會拋出異常
      if (ProbeAmt > NumBuckets) {
   
          _objc_fatal("...");
      }
      BucketNo += ProbeAmt++; //本次哈希計算得出的下表不符合, 則利用 ProbeAmt 尋找下一個下標
      BucketNo&= (NumBuckets-1); //得到新的數(shù)字和數(shù)組下標最大值按位與
    }
  }

向某對象的引用計數(shù)桶插入代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-604928.html

BucketT *InsertIntoBucketImpl(const KeyT &

到了這里，關于【iOS】weak關鍵字的實現(xiàn)原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！