objective-C-weak底层实现

1、OC中weak使用的数据结构分析（objc/Project Headers/objc-weak.h）

https://opensource.apple.com/tarballs/objc4/
/**
 * 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;
    size_t    num_entries;
    uintptr_t mask;
    uintptr_t max_hash_displacement;
};

struct weak_table_t是runtime维护的weak表，总共有4个成员，通过分析调用方法，我们可以得出这些参数的意义

参数	含义
weak_entries	哈希表数组，里面包含对象指针和所有引用对象的weak指针数组
num_entries	哈希表中元素个数
mask	哈希表的大小-1，对象地址的哈希值index=index&mask，使index不超过哈希表的大小
max_hash_displacement	记录着当前哈希表键值冲突后的最大位移

#define WEAK_INLINE_COUNT 4
struct weak_entry_t {
    DisguisedPtr<objc_object> referent;
    union {
        struct {
            weak_referrer_t *referrers;
            uintptr_t        out_of_line : 1;
            uintptr_t        num_refs : PTR_MINUS_1;
            uintptr_t        mask;
            uintptr_t        max_hash_displacement;
        };
        struct {
            // out_of_line=0 is LSB of one of these (don't care which)
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };
};

struct weak_entry_t是weak哈希表里的weak引用，通过对象地址计算出哈希值index对应一个weak_entry_t存储在weak哈希表中，参数分析：

参数	含义
referent	引用的对象

默认情况下先使用共用体下方的结构体存储，

参数	含义
inline_referrers	4个空间大小的指针数组，当一个对象weak引用不超过4个使用这种方式存储，weak超过4个使用共用体上面的结构体(里面也是个哈希表)存储
out_of_line	标记是否超出4个引用，和num_refs一起占用8个字节，刚好是下面数组第二个指针的第一位，当使用inline_referrers存储时，这一个位置永远是0
num_refs	哈希表成员个数
mask	哈希表的大小-1，对象地址的哈希值index=index&mask，使index不超过哈希表的大小
max_hash_displacement	记录着当前哈希表键值冲突后的最大位移

2、添加一个weak引用的过程

static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    //1、判断当前对象的weak引用不超过4个时
    if (! entry->out_of_line) {
       //2、如果不超过4个， 找出数组为空的对象插入weak引用
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }

        // 3、如果4个引用都被使用了，改成使用struct weak_entry_t上面那种哈希表存储
        //申请一个4个地址大小的地址
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            _calloc_internal(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // 4、把前面4个都引用移到新的地址
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[i];
        }
        //5、初始化哈希表形式的weak数组存储
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line = 1;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    assert(entry->out_of_line);
    //6、weak哈希表占用大于0.75时，哈希表扩容到当前2倍，在grow_refs_and_insert中
    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
        //插入新的weak引用
        return grow_refs_and_insert(entry, new_referrer);
    }
    //7、根据weak地址计算哈希值,并且&mask，相当于%size取余
    //key ^= key >> 4;
    //key *= 0x8a970be7488fda55;
    //key ^= __builtin_bswap64(key);
    size_t index = w_hash_pointer(new_referrer) & (entry->mask);
    size_t hash_displacement = 0;
    //8、找出对应的哈希key位置是否被占用，被占用就找下一个位置
    while (entry->referrers[index] != NULL) {
        //超出哈希表边界从0开始
        index = (index+1) & entry->mask;
        hash_displacement++;
    }
    //9、计算当前出入的哈希位移是否大于记录的，大于则替换
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;
    }
    //10、保存新的weak引用
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    //哈希表成员数+1
    entry->num_refs++;
}