在runtime中，有四個數(shù)據(jù)結(jié)構(gòu)非常重要吧彪，分別是SideTables肩狂，SideTable侨歉，weak_table_t和weak_entry_t稚字。它們和對象的引用計數(shù)物遇，以及weak引用相關(guān)。

關(guān)系

先說一下這四個數(shù)據(jù)結(jié)構(gòu)的關(guān)系香浩。 在runtime內(nèi)存空間中，SideTables是一個64個元素長度的hash數(shù)組，里面存儲了SideTable凫碌。SideTables的hash鍵值就是一個對象obj的address。
因此可以說胃榕，一個obj盛险，對應(yīng)了一個SideTable。但是一個SideTable勋又，會對應(yīng)多個obj苦掘。因為SideTable的數(shù)量只有64個，所以會有很多obj共用同一個SideTable楔壤。

而在一個SideTable中鹤啡，又有兩個成員，分別是

RefcountMap refcnts;        // 對象引用計數(shù)相關(guān) map
weak_table_t weak_table;    // 對象弱引用相關(guān) table

其中蹲嚣，refcents是一個hash map递瑰，其key是obj的地址，而value隙畜，則是obj對象的引用計數(shù)抖部。

而weak_table則存儲了弱引用obj的指針的地址，其本質(zhì)是一個以obj地址為key议惰，弱引用obj的指針的地址作為value的hash表慎颗。hash表的節(jié)點類型是weak_entry_t。

這四個數(shù)據(jù)結(jié)構(gòu)的關(guān)系如下圖：

image

SideTables

先來說一下最外層的SideTables。SideTables可以理解為一個全局的hash數(shù)組俯萎，里面存儲了SideTable類型的數(shù)據(jù)傲宜，其長度為64。

SideTabls可以通過全局的靜態(tài)函數(shù)獲确虬　：

static StripedMap<SideTable>& SideTables() {
    return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}

可以看到蛋哭，SideTabls 實質(zhì)類型為模板類型StripedMap 。StripedMap直譯過來是“有條紋的Map”涮母，不知道為什么叫做這個鳥名字谆趾。

StripedMap

我們繼續(xù)來看StripedMap模板的定義：

// StripedMap<T> is a map of void* -> T, sized appropriately 
// for cache-friendly lock striping. 
// For example, this may be used as StripedMap<spinlock_t>
// or as StripedMap<SomeStruct> where SomeStruct stores a spin lock.
template<typename T>
class StripedMap {

    enum { CacheLineSize = 64 };

#if TARGET_OS_EMBEDDED
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };  // iOS 設(shè)備的StripeCount = 64
#endif

    struct PaddedT {
        T value alignas(CacheLineSize); // T value 64字節(jié)對齊
        
    };

    PaddedT array[StripeCount]; // 所有PaddedT struct 類型數(shù)據(jù)被存儲在array數(shù)組中。iOS 設(shè)備 StripeCount == 64

    static unsigned int indexForPointer(const void *p) { // 該方法以void *作為key 來獲取void *對應(yīng)在StripedMap 中的位置
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount; // % StripeCount 防止index越界
    }

 public:
    // 取值方法 [p],
    T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    const T& operator[] (const void *p) const { 
        return const_cast<StripedMap<T>>(this)[p]; 
    }

    
    // Shortcuts for StripedMaps of locks.
    void lockAll() {
        for (unsigned int i = 0; i < StripeCount; i++) {
            array[i].value.lock();
        }
    }

    void unlockAll() {
        for (unsigned int i = 0; i < StripeCount; i++) {
            array[i].value.unlock();
        }
    }

    void forceResetAll() {
        for (unsigned int i = 0; i < StripeCount; i++) {
            array[i].value.forceReset();
        }
    }

    void defineLockOrder() {
        for (unsigned int i = 1; i < StripeCount; i++) {
            lockdebug_lock_precedes_lock(&array[i-1].value, &array[i].value);
        }
    }

    void precedeLock(const void *newlock) {
        // assumes defineLockOrder is also called
        lockdebug_lock_precedes_lock(&array[StripeCount-1].value, newlock);
    }

    void succeedLock(const void *oldlock) {
        // assumes defineLockOrder is also called
        lockdebug_lock_precedes_lock(oldlock, &array[0].value);
    }

    const void *getLock(int i) {
        if (i < StripeCount) return &array[i].value;
        else return nil;
    }
};

通過開頭的英文注釋叛本，

// StripedMap<T> is a map of void* -> T, sized appropriately

可以知道沪蓬， StripedMap 是一個以void *為hash key， T為vaule的hash 表来候。
hash定位的算法如下：

    static unsigned int indexForPointer(const void *p) { // 該方法以void *作為key 來獲取void *對應(yīng)在StripedMap 中的位置
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount; // % StripeCount 防止index越界
    }

把地址指針右移4位異或地址指針右移9位跷叉，為什么這么做，也不用關(guān)心营搅。我們只要關(guān)心重點是最后的值要取余StripeCount云挟，來防止index越界就好。

StripedMap的所有T類型數(shù)據(jù)都被封裝到PaddedT中：

    struct PaddedT {
        T value alignas(CacheLineSize); // T value 64字節(jié)對齊
        
    };

之所以再次封裝到PaddedT （有填充的T）中转质，是為了字節(jié)對齊园欣，估計是存取hash值時的效率考慮。

接下來休蟹，這些PaddedT被放到數(shù)組array中：

 PaddedT array[StripeCount]; // 所有PaddedT struct 類型數(shù)據(jù)被存儲在array數(shù)組中沸枯。iOS 設(shè)備 StripeCount == 64

然后，蘋果為array數(shù)組寫了一些公共的存取數(shù)據(jù)的方法赂弓，主要是調(diào)用indexForPointer方法绑榴，使得外部傳入的對象地址指針直接hash到對應(yīng)的array節(jié)點：

 // 取值方法 [p],
    T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    const T& operator[] (const void *p) const { 
        return const_cast<StripedMap<T>>(this)[p]; 
    }

接下來是一堆鎖的操作，由于SideTabls是一個全局的hash表盈魁，因此當(dāng)然必須要帶鎖訪問翔怎。StripedMap提供了一些便捷的鎖操作方法：

// Shortcuts for StripedMaps of locks.
    void lockAll() {
        for (unsigned int i = 0; i < StripeCount; i++) {
            array[i].value.lock();
        }
    }

    void unlockAll() {
        for (unsigned int i = 0; i < StripeCount; i++) {
            array[i].value.unlock();
        }
    }

    void forceResetAll() {
        for (unsigned int i = 0; i < StripeCount; i++) {
            array[i].value.forceReset();
        }
    }

    void defineLockOrder() {
        for (unsigned int i = 1; i < StripeCount; i++) {
            lockdebug_lock_precedes_lock(&array[i-1].value, &array[i].value);
        }
    }

    void precedeLock(const void *newlock) {
        // assumes defineLockOrder is also called
        lockdebug_lock_precedes_lock(&array[StripeCount-1].value, newlock);
    }

    void succeedLock(const void *oldlock) {
        // assumes defineLockOrder is also called
        lockdebug_lock_precedes_lock(oldlock, &array[0].value);
    }

    const void *getLock(int i) {
        if (i < StripeCount) return &array[i].value;
        else return nil;
    }

可以看到，所有的StripedMap鎖操作杨耙，最終是調(diào)用的array[i].value的相關(guān)操作赤套。因此，對于模板的抽象數(shù)據(jù)T類型按脚，必須具備相關(guān)的lock操作接口于毙。

因此，要用StripedMap作為模板hash表辅搬，對于T類型還是有所要求的唯沮。而在SideTables中脖旱，T即為SideTable類型，我們稍后會看到SideTable是如何符合StripedMap的數(shù)據(jù)類型要求的介蛉。

分析完了StripedMap, 也就分析完了SideTables這個全局的大hash表∶惹欤現(xiàn)在就來繼續(xù)分析SideTables中存儲的數(shù)據(jù)，SideTable吧币旧。

SideTable

SideTable 翻譯過來的意思是“邊桌”践险，可以放一下小東西。這里吹菱，主要存放了OC對象的引用計數(shù)和弱引用相關(guān)信息巍虫。定義如下:

struct SideTable {
    spinlock_t slock;           // 自旋鎖，防止多線程訪問沖突
    RefcountMap refcnts;        // 對象引用計數(shù)map
    weak_table_t weak_table;    // 對象弱引用map

    SideTable() {
        memset(&weak_table, 0, sizeof(weak_table));
    }

    ~SideTable() {
        _objc_fatal("Do not delete SideTable.");
    }

    // 鎖操作 符合StripedMap對T的定義
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }

    // 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);
};

SideTable的定義很清晰鳍刷，有三個成員:

• spinlock_t slock : 自旋鎖占遥，用于上鎖/解鎖 SideTable。
• RefcountMap refcnts ：以DisguisedPtr<objc_object>為key的hash表输瓜，用來存儲OC對象的引用計數(shù)(僅在未開啟isa優(yōu)化 或 在isa優(yōu)化情況下isa_t的引用計數(shù)溢出時才會用到)瓦胎。
• weak_table_t weak_table : 存儲對象弱引用指針的hash表。是OC weak功能實現(xiàn)的核心數(shù)據(jù)結(jié)構(gòu)尤揣。

除了三個成員外搔啊，蘋果為SideTable還寫了構(gòu)造和析構(gòu)函數(shù)：

// 構(gòu)造函數(shù)
    SideTable() {
        memset(&weak_table, 0, sizeof(weak_table));
    }

    //析構(gòu)函數(shù)(看看函數(shù)體，蘋果設(shè)計的SideTable其實不希望被析構(gòu)北戏，不然會引起fatal 錯誤)
    ~SideTable() {
        _objc_fatal("Do not delete SideTable.");
    }

通過析構(gòu)函數(shù)可以知道负芋，SideTable是不能被析構(gòu)的。

最后是一堆鎖的操作最欠，用于多線程訪問SideTable示罗， 同時惩猫，也符合我們上面提到的StripedMap中關(guān)于value的lock接口定義：

// 鎖操作 符合StripedMap對T的定義
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }

    // 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);

spinlock_t slock

spinlock_t的最終定義實際上是一個uint32_t類型的非公平的自旋鎖芝硬。所謂非公平，就是說獲得鎖的順序和申請鎖的順序無關(guān)轧房，也就是說拌阴，第一個申請鎖的線程有可能會是最后一個獲得到該鎖，或者是剛獲得鎖的線程會再次立刻獲得到該鎖奶镶，造成饑餓等待迟赃。 同時，在OC中厂镇，_os_unfair_lock_opaque也記錄了獲取它的線程信息纤壁，只有獲得該鎖的線程才能夠解開這把鎖。

typedef struct os_unfair_lock_s {
    uint32_t _os_unfair_lock_opaque;
} os_unfair_lock, *os_unfair_lock_t;

關(guān)于自旋鎖的實現(xiàn)捺信，蘋果并未公布酌媒，但是大體上應(yīng)該是通過操作_os_unfair_lock_opaque 這個uint32_t的值，當(dāng)大于0時，鎖可用秒咨，當(dāng)?shù)扔诨蛐∮?時喇辽，需要鎖等待。

RefcountMap refcnts

RefcountMap refcnts 用來存儲OC對象的引用計數(shù)雨席。它實質(zhì)上是一個以objc_object為key的hash表菩咨，其vaule就是OC對象的引用計數(shù)。同時陡厘，當(dāng)OC對象的引用計數(shù)變?yōu)?時抽米，會自動將相關(guān)的信息從hash表中剔除。RefcountMap的定義如下：

// RefcountMap disguises its pointers because we 
// don't want the table to act as a root for `leaks`.
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;

實質(zhì)上是模板類型objc::DenseMap糙置。模板的三個類型參數(shù)DisguisedPtr<objc_object>缨硝，size_t, true 分別表示DenseMap的hash key類型，value類型罢低，是否需要在value==0的時候自動釋放掉響應(yīng)的hash節(jié)點查辩，這里是true。

而DenseMap這個模板類型又繼承與另一個Base 模板類型DenseMapBase ：

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> 

關(guān)于DenseMap的定義网持，蘋果寫了一大坨宜岛，有些復(fù)雜，這里就不去深究了功舀，有興趣的同學(xué)可以自己去看下相關(guān)的源碼部分萍倡。

weak_table_t weak_table

重點來了，weak_table_t weak_table 用來存儲OC對象弱引用的相關(guān)信息辟汰。我們知道列敲，SideTables一共只有64個節(jié)點，而在我們的APP中帖汞，一般都會不只有64個對象戴而，因此，多個對象一定會重用同一個SideTable節(jié)點翩蘸，也就是說所意，一個weak_table會存儲多個對象的弱引用信息。因此在一個SideTable中催首，又會通過weak_table作為hash表再次分散存儲每一個對象的弱引用信息扶踊。

weak_table_t的定義如下：

/**
 * The global weak references table. Stores object ids as keys,
 * and weak_entry_t structs as their values.
 */
struct weak_table_t {
    weak_entry_t *weak_entries;        // hash數(shù)組，用來存儲弱引用對象的相關(guān)信息weak_entry_t
    size_t    num_entries;             // hash數(shù)組中的元素個數(shù)
    uintptr_t mask;                    // hash數(shù)組長度-1郎任，會參與hash計算秧耗。（注意，這里是hash數(shù)組的長度舶治，而不是元素個數(shù)分井。比如胶台，數(shù)組長度可能是64，而元素個數(shù)僅存了2個）
    uintptr_t max_hash_displacement;   // 可能會發(fā)生的hash沖突的最大次數(shù)杂抽，用于判斷是否出現(xiàn)了邏輯錯誤（hash表中的沖突次數(shù)絕不會超過改值）
};

weak_table_t是一個典型的hash結(jié)構(gòu)诈唬。其中 weak_entry_t *weak_entries是一個動態(tài)數(shù)組，用來存儲weak_table_t的數(shù)據(jù)元素weak_entry_t缩麸。
剩下的三個元素將會用于hash表的相關(guān)操作铸磅。weak_table的hash定位操作如下所示：

static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
    assert(referent);

    weak_entry_t *weak_entries = weak_table->weak_entries;

    if (!weak_entries) return nil;

    size_t begin = hash_pointer(referent) & weak_table->mask;  // 這里通過 & weak_table->mask的位操作，來確保index不會越界
    size_t index = begin;
    size_t hash_displacement = 0;
    while (weak_table->weak_entries[index].referent != referent) {
        index = (index+1) & weak_table->mask;
        if (index == begin) bad_weak_table(weak_table->weak_entries); // 觸發(fā)bad weak table crash
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) { // 當(dāng)hash沖突超過了可能的max hash 沖突時杭朱，說明元素沒有在hash表中阅仔，返回nil 
            return nil;
        }
    }
    
    return &weak_table->weak_entries[index];
}

上面的定位操作還是比較清晰的，首先通過

 size_t begin = hash_pointer(referent) & weak_table->mask;

來嘗試確定hash的初始位置弧械。注意八酒，這里做了& weak_table->mask 位操作來確保index不會越界，這同我們平時用到的取余%操作是一樣的功能刃唐。只不過這里改用了位操作羞迷，提升了效率。

然后画饥，就開始對比hash表中的數(shù)據(jù)是否與目標(biāo)數(shù)據(jù)相等while (weak_table->weak_entries[index].referent != referent)衔瓮，如果不相等，則index +1抖甘， 直到index == begin（繞了一圈）或超過了可能的hash沖突最大值热鞍。

這是weak_table_t如何進行hash定位的相關(guān)操作。

關(guān)于weak_table_t中如何添加/刪除元素衔彻，我們在上一章Objective-C runtime機制(6)——weak引用的底層實現(xiàn)原理中已有分析薇宠，在這里我們不再展開。

weak_entry_t

weak_table_t中存儲的元素是weak_entry_t類型艰额，每個weak_entry_t類型對應(yīng)了一個OC對象的弱引用信息澄港。

weak_entry_t的結(jié)構(gòu)和weak_table_t很像，同樣也是一個hash表悴晰，其存儲的元素是weak_referrer_t慢睡，實質(zhì)上是弱引用該對象的指針的指針，即 objc_object **new_referrer 铡溪， 通過操作指針的指針，就可以使得weak 引用的指針在對象析構(gòu)后泪喊，指向nil棕硫。

// The address of a __weak variable.
// These pointers are stored disguised so memory analysis tools
// don't see lots of interior pointers from the weak table into objects.

typedef DisguisedPtr<objc_object *> weak_referrer_t;

weak_entry_t 的定義如下：

/**
 * The internal structure stored in the weak references table. 
 * It maintains and stores
 * a hash set of weak references pointing to an object.
 * If out_of_line_ness != REFERRERS_OUT_OF_LINE then the set
 * is instead a small inline array.
 */
#define WEAK_INLINE_COUNT 4

// out_of_line_ness field overlaps with the low two bits of inline_referrers[1].
// inline_referrers[1] is a DisguisedPtr of a pointer-aligned address.
// The low two bits of a pointer-aligned DisguisedPtr will always be 0b00
// (disguised nil or 0x80..00) or 0b11 (any other address).
// Therefore out_of_line_ness == 0b10 is used to mark the out-of-line state.
#define REFERRERS_OUT_OF_LINE 2

struct weak_entry_t {
    DisguisedPtr<objc_object> referent; // 被弱引用的對象
    
    // 引用該對象的對象列表，聯(lián)合袒啼。 引用個數(shù)小于4哈扮，用inline_referrers數(shù)組纬纪。 用個數(shù)大于4，用動態(tài)數(shù)組weak_referrer_t *referrers
    union {
        struct {
            weak_referrer_t *referrers;                      // 弱引用該對象的對象指針地址的hash數(shù)組
            uintptr_t        out_of_line_ness : 2;           // 是否使用動態(tài)hash數(shù)組標(biāo)記位
            uintptr_t        num_refs : PTR_MINUS_2;         // hash數(shù)組中的元素個數(shù)
            uintptr_t        mask;                           // hash數(shù)組長度-1滑肉，會參與hash計算包各。（注意，這里是hash數(shù)組的長度靶庙，而不是元素個數(shù)问畅。比如，數(shù)組長度可能是64六荒，而元素個數(shù)僅存了2個）素個數(shù)）护姆。
            uintptr_t        max_hash_displacement;          // 可能會發(fā)生的hash沖突的最大次數(shù)，用于判斷是否出現(xiàn)了邏輯錯誤（hash表中的沖突次數(shù)絕不會超過改值）
        };
        struct {
            // out_of_line_ness field is low bits of inline_referrers[1]
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };

    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }

    weak_entry_t& operator=(const weak_entry_t& other) {
        memcpy(this, &other, sizeof(other));
        return *this;
    }

    weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
        : referent(newReferent) // 構(gòu)造方法掏击，里面初始化了靜態(tài)數(shù)組
    {
        inline_referrers[0] = newReferrer;
        for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
            inline_referrers[i] = nil;
        }
    }
};

weak_entry_t的結(jié)構(gòu)也比較清晰：

• DisguisedPtr<objc_object> referent ：弱引用對象指針摘要卵皂。其實可以理解為弱引用對象的指針，只不過這里使用了摘要的形式存儲砚亭。（所謂摘要灯变，其實是把地址取負）。
• union ：接下來是一個聯(lián)合捅膘，union有兩種形式：定長數(shù)組weak_referrer_t inline_referrers[WEAK_INLINE_COUNT] 和 動態(tài)數(shù)組 weak_referrer_t *referrers柒凉。這兩個數(shù)組是用來存儲弱引用該對象的指針的指針的，同樣也使用了指針摘要的形式存儲篓跛。當(dāng)弱引用該對象的指針數(shù)目小于等于WEAK_INLINE_COUNT時膝捞，使用定長數(shù)組。當(dāng)超過WEAK_INLINE_COUNT時愧沟，會將定長數(shù)組中的元素轉(zhuǎn)移到動態(tài)數(shù)組中蔬咬，并之后都是用動態(tài)數(shù)組存儲。關(guān)于定長數(shù)組/動態(tài)數(shù)組 切換這部分沐寺，我們在稍后詳細分析林艘。
• bool out_of_line()： 該方法用來判斷當(dāng)前的weak_entry_t是使用的定長數(shù)組還是動態(tài)數(shù)組。當(dāng)返回true混坞，此時使用的動態(tài)數(shù)組狐援，當(dāng)返回false，使用靜態(tài)數(shù)組究孕。
• weak_entry_t& operator=(const weak_entry_t& other) ：賦值方法
• weak_entry_t(objc_object *newReferent, objc_object **newReferrer) ：構(gòu)造方法啥酱。

定長數(shù)組 / 動態(tài)數(shù)組

weak_entry_t會存儲所有弱引用該對象的指針的指針。存儲類型為weak_referrer_t 厨诸，其實就是弱引用指針的指針镶殷。但是是以指針摘要的形式存儲的：

typedef DisguisedPtr<objc_object *> weak_referrer_t;

weak_entry_t會將weak_referrer_t存儲到hash數(shù)組中，而這個hash數(shù)組會有兩種形態(tài)：定長數(shù)組/動態(tài)數(shù)組：

   union {
        // 動態(tài)數(shù)組模式
        struct {
            weak_referrer_t *referrers;                      // 弱引用該對象的對象指針地址的hash數(shù)組
            uintptr_t        out_of_line_ness : 2;           // 是否使用動態(tài)hash數(shù)組標(biāo)記位
            uintptr_t        num_refs : PTR_MINUS_2;         // hash數(shù)組中的元素個數(shù)
            uintptr_t        mask;                           // hash數(shù)組長度-1微酬，會參與hash計算绘趋。（注意颤陶，這里是hash數(shù)組的長度，而不是元素個數(shù)陷遮。比如滓走，數(shù)組長度可能是64，而元素個數(shù)僅存了2個）素個數(shù)）帽馋。
            uintptr_t        max_hash_displacement;          // 可能會發(fā)生的hash沖突的最大次數(shù)搅方，用于判斷是否出現(xiàn)了邏輯錯誤（hash表中的沖突次數(shù)絕不會超過改值）
        };
      // 定長數(shù)組模式
        struct {
            // out_of_line_ness field is low bits of inline_referrers[1]
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };

    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }

當(dāng)弱引用指針個數(shù)少于等于WEAK_INLINE_COUNT時，會使用定長數(shù)組inline_referrers茬斧。而當(dāng)大于WEAK_INLINE_COUNT時腰懂，則會轉(zhuǎn)換到動態(tài)數(shù)組模式 weak_referrer_t *referrers。

之所以做定長/動態(tài)數(shù)組的切換项秉，應(yīng)該是蘋果考慮到弱引用的指針個數(shù)一般不會超過WEAK_INLINE_COUNT個绣溜。這時候使用定長數(shù)組，不需要動態(tài)的申請內(nèi)存空間娄蔼，而是一次分配一塊連續(xù)的內(nèi)存空間怖喻。這會得到運行效率上的提升。

至于weak_entry_t 是使用的定長/動態(tài)數(shù)組岁诉，蘋果提供了方法：

#define REFERRERS_OUT_OF_LINE 2

    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }

該方法的實質(zhì)是測試定長數(shù)組第二個元素值的2進制位第2位是否等于01锚沸。因為根據(jù)蘋果的注釋，inline_referrers[1] 中存儲的是pointer-aligned DisguisedPtr 涕癣，即指針對齊的指針摘要哗蜈，其最低位一定是0b00或0b11，因此可以用0b10 表示使用了動態(tài)數(shù)組坠韩。

下面我就來看一下weak_entry_t 中是如何插入元素的：

/** 
 * Add the given referrer to set of weak pointers in this entry.
 * Does not perform duplicate checking (b/c weak pointers are never
 * added to a set twice). 
 *
 * @param entry The entry holding the set of weak pointers. 
 * @param new_referrer The new weak pointer to be added.
 */
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    if (! entry->out_of_line()) { // 如果weak_entry 尚未使用動態(tài)數(shù)組距潘，走這里
        // Try to insert inline.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }
        
        // 如果inline_referrers的位置已經(jīng)存滿了，則要轉(zhuǎn)型為referrers只搁，做動態(tài)數(shù)組音比。
        // Couldn't insert inline. Allocate out of line.
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[I];
        }
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    // 對于動態(tài)數(shù)組的附加處理：
    assert(entry->out_of_line()); // 斷言： 此時一定使用的動態(tài)數(shù)組

    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果動態(tài)數(shù)組中元素個數(shù)大于或等于數(shù)組位置總空間的3/4，則擴展數(shù)組空間為當(dāng)前長度的一倍
        return grow_refs_and_insert(entry, new_referrer); // 擴容氢惋，并插入
    }
    
    // 如果不需要擴容洞翩，直接插入到weak_entry中
    // 注意，weak_entry是一個哈希表焰望，key：w_hash_pointer(new_referrer) value: new_referrer
    
    // 細心的人可能注意到了骚亿，這里weak_entry_t 的hash算法和 weak_table_t的hash算法是一樣的，同時擴容/減容的算法也是一樣的
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask); // '& (entry->mask)' 確保了 begin的位置只能大于或等于 數(shù)組的長度
    size_t index = begin;  // 初始的hash index
    size_t hash_displacement = 0;  // 用于記錄hash沖突的次數(shù)柿估，也就是hash再位移的次數(shù)
    while (entry->referrers[index] != nil) {
        hash_displacement++;
        index = (index+1) & entry->mask;  // index + 1, 移到下一個位置循未，再試一次能否插入。（這里要考慮到entry->mask取值秫舌，一定是：0x111, 0x1111, 0x11111, ... 的妖，因為數(shù)組每次都是*2增長，即8足陨， 16嫂粟， 32，對應(yīng)動態(tài)數(shù)組空間長度-1的mask墨缘，也就是前面的取值星虹。）
        if (index == begin) bad_weak_table(entry); // index == begin 意味著數(shù)組繞了一圈都沒有找到合適位置，這時候一定是出了什么問題镊讼。
    }
    if (hash_displacement > entry->max_hash_displacement) { // 記錄最大的hash沖突次數(shù), max_hash_displacement意味著: 我們嘗試至多max_hash_displacement次宽涌，肯定能夠找到object對應(yīng)的hash位置
        entry->max_hash_displacement = hash_displacement;
    }
    // 將ref存入hash數(shù)組，同時蝶棋，更新元素個數(shù)num_refs
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    entry->num_refs++;
}

代碼可以分成兩部分理解卸亮，一部分是使用定長數(shù)組的情況：

  if (! entry->out_of_line()) { // 如果weak_entry 尚未使用動態(tài)數(shù)組，走這里
        // Try to insert inline.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }
        
        // 如果inline_referrers的位置已經(jīng)存滿了玩裙，則要轉(zhuǎn)型為referrers兼贸，做動態(tài)數(shù)組。
        // Couldn't insert inline. Allocate out of line.
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[I];
        }
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

定長數(shù)組的邏輯很簡單吃溅，直接安裝數(shù)組順序溶诞，將new_referrer插入即可。如果定長數(shù)組已經(jīng)用盡决侈，則將定長數(shù)組轉(zhuǎn)型為動態(tài)數(shù)組：

weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
...

entry->referrers = new_referrers; // hash數(shù)組由 entry->inline_referrers轉(zhuǎn)換為 entry->referrers

<font color=blue>要注意螺垢，定長數(shù)組轉(zhuǎn)換為動態(tài)數(shù)組后，新的元素并沒有插入到數(shù)組中赖歌，而僅是將原來定長數(shù)組中的內(nèi)容轉(zhuǎn)移到了動態(tài)數(shù)組中枉圃。新元素的插入邏輯，在下面動態(tài)數(shù)組部分：</font>

    ...
    // 對于動態(tài)數(shù)組的附加處理：
    assert(entry->out_of_line()); // 斷言： 此時一定使用的動態(tài)數(shù)組

    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果動態(tài)數(shù)組中元素個數(shù)大于或等于數(shù)組位置總空間的3/4俏站，則擴展數(shù)組空間為當(dāng)前長度的一倍
        return grow_refs_and_insert(entry, new_referrer); // 擴容讯蒲，并插入
    }
    
    // 如果不需要擴容，直接插入到weak_entry中
    // 注意肄扎，weak_entry是一個哈希表墨林，key：w_hash_pointer(new_referrer) value: new_referrer
    
    // 細心的人可能注意到了，這里weak_entry_t 的hash算法和 weak_table_t的hash算法是一樣的犯祠，同時擴容/減容的算法也是一樣的
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask); // '& (entry->mask)' 確保了 begin的位置只能大于或等于 數(shù)組的長度
    size_t index = begin;  // 初始的hash index
    size_t hash_displacement = 0;  // 用于記錄hash沖突的次數(shù)旭等，也就是hash再位移的次數(shù)
    while (entry->referrers[index] != nil) {
        hash_displacement++;
        index = (index+1) & entry->mask;  // index + 1, 移到下一個位置，再試一次能否插入衡载。（這里要考慮到entry->mask取值搔耕，一定是：0x111, 0x1111, 0x11111, ... ，因為數(shù)組每次都是*2增長，即8弃榨， 16菩收， 32，對應(yīng)動態(tài)數(shù)組空間長度-1的mask鲸睛，也就是前面的取值娜饵。）
        if (index == begin) bad_weak_table(entry); // index == begin 意味著數(shù)組繞了一圈都沒有找到合適位置，這時候一定是出了什么問題官辈。
    }
    if (hash_displacement > entry->max_hash_displacement) { // 記錄最大的hash沖突次數(shù), max_hash_displacement意味著: 我們嘗試至多max_hash_displacement次箱舞，肯定能夠找到object對應(yīng)的hash位置
        entry->max_hash_displacement = hash_displacement;
    }
    // 將ref存入hash數(shù)組，同時拳亿，更新元素個數(shù)num_refs
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    entry->num_refs++;
}

其實這部分的邏輯和weak_table_t中插入weak_entry_t是非常類似的晴股。都使用了mask取余來解決hash沖突。

我們可以再細看一下動態(tài)數(shù)組是如何動態(tài)擴容的：

   if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果動態(tài)數(shù)組中元素個數(shù)大于或等于數(shù)組位置總空間的3/4肺魁，則擴展數(shù)組空間為當(dāng)前長度的一倍
        return grow_refs_and_insert(entry, new_referrer); // 擴容电湘，并插入
    }

/** 
 * Grow the entry's hash table of referrers. Rehashes each
 * of the referrers.
 * 
 * @param entry Weak pointer hash set for a particular object.
 */
__attribute__((noinline, used))
static void grow_refs_and_insert(weak_entry_t *entry, 
                                 objc_object **new_referrer)
{
    assert(entry->out_of_line());

    size_t old_size = TABLE_SIZE(entry);
    size_t new_size = old_size ? old_size * 2 : 8; // 每次擴容為上一次容量的2倍

    size_t num_refs = entry->num_refs;
    weak_referrer_t *old_refs = entry->referrers;
    entry->mask = new_size - 1;
    
    entry->referrers = (weak_referrer_t *)
        calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));
    entry->num_refs = 0;
    entry->max_hash_displacement = 0;
    
    // 這里可以看到，舊的數(shù)據(jù)需要依次轉(zhuǎn)移到新的內(nèi)存中
    for (size_t i = 0; i < old_size && num_refs > 0; i++) {
        if (old_refs[i] != nil) {
            append_referrer(entry, old_refs[i]); // 將舊的數(shù)據(jù)轉(zhuǎn)移到新的動態(tài)數(shù)組中
            num_refs--;
        }
    }
    // Insert
    append_referrer(entry, new_referrer);
    if (old_refs) free(old_refs); // 釋放舊的內(nèi)存
}

通過代碼可以看出万搔，每一次動態(tài)數(shù)組的擴容胡桨，都需要將舊的數(shù)據(jù)重新插入到新的數(shù)組中。

總結(jié)

OK瞬雹，上面就是在runtime中昧谊，關(guān)于對象引用計數(shù)和weak引用相關(guān)的數(shù)據(jù)結(jié)構(gòu)。搞清楚了它們之間的關(guān)系以及各自的實現(xiàn)細節(jié)酗捌，相信大家會對runtime有更深的理解呢诬。