美文网首页
探索weak哈希表

探索weak哈希表

作者: 羽裳有涯 | 来源:发表于2021-01-05 18:28 被阅读0次

    前言

    • weak表其实是一个hash(哈希)表Key是所指对象的地址,Valueweak指针的地址数组。
    • weak是弱引用,所引用对象的计数器不会加一,并在引用对象被释放的时候自动被设置为nil。通常用于解决循环引用问题。

        NSObject *obj = [[NSObject alloc] init];
         static __weak id _weakObj = nil;
    
        // weak的三种赋值情况
        // (1)变量赋值
        _weakObj = obj; // 编译为:objc_storeWeak(&_weakObj, obj);
    
        //  (2) 直接初始化,strong对象赋值
        __weak NSObject *obj1 = obj; // 编译为:objc_initWeak(&obj1, obj);
        
        //  (3) 直接初始化,weak对象赋值
        __weak NSObject *obj2 = _weakObj; // 编译为:objc_copyWeak(&obj2, & _weakObj);
        
        
        // weak的访问情况,就是调用 objc_loadWeakRetained(id *location)
        NSLog(@"=====%@",_weakObj);
        // 编译为下面代码
        /*
        id temp = objc_loadWeakRetained(&weakObj);
        NSLog(@"=====%@",temp);
        objc_release(temp);
        */
    

    哈希函数

    首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。

    哈希函数的构造方法:
    1. 数字分析法
    2. 平方取中法
    3. 分段叠加法
    4. 除留余数法
    5. 伪随机数法

    处理冲突的方法:1、开放定址法 2、再哈希法3、 链地址法

    1. 开放定址法
      线性探测再散列
      二次探测再散列
      伪随机探测再散列

    2、 再哈希法

    3、 链地址法

    weak 实现原理的概括

    Runtime维护了一个weak表,用于存储指向某个对象的所有weak指针。weak表其实是一个hash(哈希)表,Key是所指对象的地址,Value是weak指针的地址(这个地址的值是所指对象指针的地址)数组。

    1. 初始化时:runtime会调用objc_initWeak函数,初始化指向某个对象位置的新的弱指针。
    id
    objc_initWeak(id *location, id newObj)
    {
    // 查看对象实例是否有效
    // 无效对象直接导致指针释放
        if (!newObj) {
            *location = nil;
            return nil;
        }
        return storeWeak<DontHaveOld, DoHaveNew, DoCrashIfDeallocating>
            (location, (objc_object*)newObj);
    }
    

    2、添加引用时:objc_initWeak函数会调用 storeWeak() 函数, storeWeak() 的作用是更新指针指向,创建对应的弱引用表。

    // HaveOld:  true - 变量有值
    //          false - 需要被及时清理,当前值可能为 nil
    // HaveNew:  true - 需要被分配的新值,当前值可能为 nil
    //          false - 不需要分配新值
    // CrashIfDeallocating: true - 说明 newObj 已经释放或者 newObj 不支持弱引用,该过程需要暂停
    //          false - 用 nil 替代存储
    template bool HaveOld, bool HaveNew, bool CrashIfDeallocating>
    static id storeWeak(id *location, objc_object *newObj) {
        // 该过程用来更新弱引用指针的指向
        // 初始化 previouslyInitializedClass 指针
        Class previouslyInitializedClass = nil;
        id oldObj;
        // 声明两个 SideTable
        // ① 新旧散列创建
        SideTable *oldTable;
        SideTable *newTable;
        // 获得新值和旧值的锁存位置(用地址作为唯一标示)
        // 通过地址来建立索引标志,防止桶重复
        // 下面指向的操作会改变旧值
    retry:
        if (HaveOld) {
            // 更改指针,获得以 oldObj 为索引所存储的值地址
            oldObj = *location;
            oldTable = &SideTables()[oldObj];
        } else {
            oldTable = nil;
        }
        if (HaveNew) {
            // 更改新值指针,获得以 newObj 为索引所存储的值地址
            newTable = &SideTables()[newObj];
        } else {
            newTable = nil;
        }
        // 加锁操作,防止多线程中竞争冲突
        SideTable::lockTwo<HaveOld, HaveNew>(oldTable, newTable);
        // 避免线程冲突重处理
        // location 应该与 oldObj 保持一致,如果不同,说明当前的 location 已经处理过 oldObj 可是又被其他线程所修改
        if (HaveOld  &&  *location != oldObj) {
            SideTable::unlockTwoHaveOld, HaveNew>(oldTable, newTable);
            goto retry;
        }
        // 防止弱引用间死锁
        // 并且通过 +initialize 初始化构造器保证所有弱引用的 isa 非空指向
        if (HaveNew  &&  newObj) {
            // 获得新对象的 isa 指针
            Class cls = newObj->getIsa();
            // 判断 isa 非空且已经初始化
            if (cls != previouslyInitializedClass  &&
                !((objc_class *)cls)->isInitialized()) {
                // 解锁
                SideTable::unlockTwoHaveOld, HaveNew>(oldTable, newTable);
                // 对其 isa 指针进行初始化
                class_initialize(_class_getNonMetaClass(cls, (id)newObj));
                // 如果该类已经完成执行 +initialize 方法是最理想情况
                // 如果该类 +initialize 在线程中
                // 例如 +initialize 正在调用 storeWeak 方法
                // 需要手动对其增加保护策略,并设置 previouslyInitializedClass 指针进行标记
                previouslyInitializedClass = cls;
                // 重新尝试
                goto retry;
            }
        }
        // ② 清除旧值
        if (HaveOld) {
            weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
        }
        // ③ 分配新值
        if (HaveNew) {
            newObj = (objc_object *)weak_register_no_lock(&newTable->weak_table,
                                                          (id)newObj, location,
                                                          CrashIfDeallocating);
            // 如果弱引用被释放 weak_register_no_lock 方法返回 nil
            // 在引用计数表中设置若引用标记位
            if (newObj  &&  !newObj->isTaggedPointer()) {
                // 弱引用位初始化操作
                // 引用计数那张散列表的weak引用对象的引用计数中标识为weak引用
                newObj->setWeaklyReferenced_nolock();
            }
            // 之前不要设置 location 对象,这里需要更改指针指向
            *location = (id)newObj;
        }
        else {
            // 没有新值,则无需更改
        }
        SideTable::unlockTwoHaveOld, HaveNew>(oldTable, newTable);
        return (id)newObj;
    }
    

    3、释放时,调用clearDeallocating函数。clearDeallocating函数首先根据对象地址获取所有weak指针地址的数组,然后遍历这个数组把其中的数据设为nil,最后把这个entry从weak表中删除,最后清理对象的记录。

    SideTable

    SideTable 这个结构体,我给他起名引用计数和弱引用依赖表,因为它主要用于管理对象的引用计数和 weak 表。在 NSObject.mm 中声明其数据结构:

    struct SideTable {
    // 保证原子操作的自旋锁
        spinlock_t slock;
        // 引用计数的 hash 表
        RefcountMap refcnts;
        // weak 引用全局 hash 表
        weak_table_t weak_table;
    

    weak表

    weak表是一个弱引用表,实现为一个weak_table_t结构体,存储了某个对象相关的的所有的弱引用信息。其定义如下(具体定义在objc-weak.h中):

       struct weak_table_t {
        // 保存了所有指向指定对象的 weak 指针
        weak_entry_t *weak_entries;
        // 存储空间
        size_t    num_entries;
        // 参与判断引用计数辅助量
        uintptr_t mask;
        // hash key 最大偏移值
        uintptr_t max_hash_displacement;
    };
    

    这是一个全局弱引用hash表。使用不定类型对象的地址作为 key ,用weak_entry_t类型结构体对象作为value 。其中的 weak_entries成员,从字面意思上看,即为弱引用表入口。其实现也是这样的。

    其中weak_entry_t是存储在弱引用表中的一个内部结构体,它负责维护和存储指向一个对象的所有弱引用hash表。其定义如下:

    struct weak_entry_t {
        DisguisedPtr<objc_object> referent;
        union {
            struct {
                weak_referrer_t *referrers;
                uintptr_t        out_of_line_ness : 2;
                uintptr_t        num_refs : PTR_MINUS_2;
                uintptr_t        mask;
                uintptr_t        max_hash_displacement;
            };
            struct {
                // out_of_line_ness field is low bits of inline_referrers[1]
                weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
            };
        };
    

    weak_entry_t 的结构中,DisguisedPtr referent 是对泛型对象的指针做了一个封装,通过这个泛型类来解决内存泄漏的问题。从注释中写 out_of_line 成员为最低有效位,当其为0的时候, weak_referrer_t 成员将扩展为多行静态 hash table。其实其中的 weak_referrer_t 是二维 objc_object 的别名,通过一个二维指针地址偏移,用下标作为 hash 的 key,做成了一个弱引用散列。

    out_of_line:最低有效位,也是标志位。当标志位 0 时,增加引用表指针纬度。这里标记是否超过内联边界
    num_refs:引用数值。这里记录弱引用表中引用有效数字,因为弱引用表使用的是静态 hash 结构,所以需要使用变量来记录数目。
    mask:计数辅助量。
    max_hash_displacement:hash 元素上限阀值。

    总结一下 StripedMap[] : StripedMap 是一个模板类,在这个类中有一个 array 成员,用来存储 PaddedT 对象,并且其中对于 [] 符的重载定义中,会返回这个 PaddedT 的 value 成员,这个 value 就是我们传入的 T 泛型成员,也就是 SideTable 对象。在 array 的下标中,这里使用了 indexForPointer 方法通过位运算计算下标,实现了静态的 Hash Table。而在 weak_table 中,其成员 weak_entry 会将传入对象的地址加以封装起来,并且其中也有访问全局弱引用表的入口。


    SideTable

    参考:
    哈希函数
    【iOS】weak的底层实现
    iOS 底层解析weak的实现原理(包含weak对象的初始化,引用,释放的分析)
    weak的生命周期:具体实现方法

    相关文章

      网友评论

          本文标题:探索weak哈希表

          本文链接:https://www.haomeiwen.com/subject/nksioktx.html