iOS - 弱引用表（Weak Reference Table）

1. 基本数据结构

// 弱引用表的基本结构
struct weak_table_t {
    weak_entry_t *weak_entries;      // 保存所有的弱引用对象
    size_t    num_entries;           // 当前存储的弱引用数量
    uintptr_t mask;                  // 哈希表大小掩码
    uintptr_t max_hash_displacement; // 最大哈希偏移值
};

// 单个对象的弱引用信息
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 {
            // 内联存储，用于优化少量弱引用的情况
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };
};

2. 核心操作

2.1 添加弱引用

id weak_register_no_lock(weak_table_t *weak_table, id referent, 
                        id *referrer, bool crashIfDeallocating) {
    // 1. 查找或创建 entry
    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
    if (entry == nil) {
        entry = new_entry_for_referent(referent, referrer);
        weak_entry_insert(weak_table, entry);
    }
    
    // 2. 添加弱引用
    append_referrer(entry, referrer);
    
    return referent;
}

2.2 移除弱引用

void weak_unregister_no_lock(weak_table_t *weak_table, 
                            id referent, id *referrer) {
    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
    if (entry == nil) return;
    
    // 移除引用
    remove_referrer(entry, referrer);
    
    // 如果 entry 为空，则移除
    if (entry->out_of_line && entry->num_refs == 0) {
        weak_entry_remove(weak_table, entry);
    }
}

3. 存储优化

3.1 内联存储

#define WEAK_INLINE_COUNT 4

struct weak_entry_t {
    union {
        // 当弱引用数量少时，使用内联数组
        struct {
            weak_referrer_t inline_referrers[WEAK_INLINE_COUNT];
        };
        // 当弱引用数量多时，使用动态数组
        struct {
            weak_referrer_t *referrers;
            uintptr_t out_of_line : 1;
        };
    };
};

3.2 动态扩展

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;
    
    // 分配新空间
    weak_referrer_t *new_refs = (weak_referrer_t *)
        calloc(new_size, sizeof(weak_referrer_t));
    
    // 迁移数据
    for (size_t i = 0; i < old_size; i++) {
        weak_referrer_t oldref = entry->referrers[i];
        if (oldref) {
            weak_referrer_t *new_ref = new_refs + hash_pointer(oldref);
            *new_ref = oldref;
        }
    }
}

4. 线程安全

4.1 锁保护

struct SideTable {
    spinlock_t slock;      // 自旋锁
    RefcountMap refcnts;
    weak_table_t weak_table;
    
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
};

// 使用示例
void weak_register_no_lock(weak_table_t *weak_table, id referent) {
    SideTable& table = SideTables()[referent];
    table.lock();
    // 操作 weak_table
    table.unlock();
}

4.2 原子操作

bool weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry) {
    return OSAtomicCompareAndSwapPtr(nil, new_entry, 
           (void * volatile *)&weak_table->weak_entries);
}

5. 清理机制

5.1 对象释放时的清理

void weak_clear_no_lock(weak_table_t *weak_table, id referent) {
    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
    if (entry == nil) return;
    
    // 将所有弱引用置为 nil
    weak_referrer_t *referrers = entry->referrers;
    size_t count = entry->num_refs;
    
    for (size_t i = 0; i < count; ++i) {
        objc_object **referrer = referrers[i];
        if (referrer) {
            *referrer = nil;
        }
    }
    
    // 移除 entry
    weak_entry_remove(weak_table, entry);
}

5.2 表格清理

void weak_compact_maybe(weak_table_t *weak_table) {
    size_t old_size = TABLE_SIZE(weak_table);
    
    // 当表使用率低于 1/4 时进行收缩
    if (weak_table->num_entries < old_size / 4) {
        weak_resize(weak_table, old_size / 2);
    }
}

6. 性能优化

6.1 哈希优化

static inline uintptr_t hash_pointer(objc_object **p) {
    return ((uintptr_t)p) >> 3;  // 去除对齐位
}

static inline size_t index_for_pointer(uintptr_t ptr, size_t mask) {
    return ptr & mask;  // 快速取模
}

6.2 空间优化

// 使用内联数组优化小对象
if (entry->num_refs < WEAK_INLINE_COUNT) {
    // 使用内联存储
    entry->inline_referrers[entry->num_refs++] = referrer;
} else {
    // 转换为动态数组
    move_to_dynamic_storage(entry);
}