Apple 源码用到的一些数据结构

[TOC]

本篇英文名叫 Kitchen Tools That Cook Loves，翻译过来的意思是苹果源码中出现的一些数据结构，不断积累更新。

隶属于我的第二个大系列 CWC ：Cooking With Cook，翻译过来的中文意思就是 作为一个长期热爱苹果的苹果开发者，陪着水果公司一起积累和成长。

目前：entsize_list_tt、list_array_tt、cache_t's buckets…

1. entsize_list_tt

entsize_list_tt 其实就是一个通用的容器，可以获取 内部的迭代器，用于遍历内部存储的元素

  • Element: 元素的类型
  • List: 指定容器的具体实现类型
  • uint32_t flagmask: flagmask 标记位

出现场景：

  1. 类的 ro 中的 ivar_list_t
  2. 类的 ro rw rwe 中的 property_array_t 中的 property_list_t
  3. 类的 ro rw rwe 中的 method_array_t 中的 method_list_t

三者的声明头如下：

1
2
3
struct ivar_list_t : entsize_list_tt<ivar_t, ivar_list_t, 0>
struct property_list_t : entsize_list_tt<property_t, property_list_t, 0>
struct method_list_t : entsize_list_tt<method_t, method_list_t, 0x3>

entsize_list_t 定义源码，省略大部分方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/***********************************************************************
* entsize_list_tt<Element, List, FlagMask>
* 一系列非精致结构体的数组的实现
*
* Element 元素是结构体类型 (e.g. method_t)
* List 是这个结构体的特殊实现子类 (e.g. method_list_t)
* FFlagMask 用于在 entsize 字段中存储额外的位
*   (e.g. method list fixup markers)
**********************************************************************/
template <typename Element, typename List, uint32_t FlagMask>
struct entsize_list_tt {
    uint32_t entsizeAndFlags;
    uint32_t count;
    Element first;
    struct iterator;

    struct iterator {
        uint32_t entsize;
        uint32_t index;  // keeping track of this saves a divide in operator-
        Element* element;

        typedef std::random_access_iterator_tag iterator_category;
        typedef Element value_type;
        typedef ptrdiff_t difference_type;
        typedef Element* pointer;
        typedef Element& reference;
    }
}

2. list_array_tt

这个类用来表示一个空、单数组、或者多数组。它和 list 的区别就是 多了一个多维数组的封装。

出现场景：

  1. 类的 rw rwe 中的 method_array_t
  2. 类的 rw rwe 中的 property_array_t
  3. 类的 rw rwe 中的 protocol_array_t

ro 中没有，只有三个单 List。

三者的声明头如下：

1
2
3
4
5
6
7
8
class method_array_t : 
    public list_array_tt<method_t, method_list_t> 
    
class property_array_t : 
    public list_array_tt<property_t, property_list_t> 
    
class protocol_array_t : 
    public list_array_tt<protocol_ref_t, protocol_list_t>

list_array_tt 源码部分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/***********************************************************************
* list_array_tt<Element, List>
* 元数据的通用实现，可以按类别进行扩展。
*
* Element：基础元数据类型(e.g. method_t)
* List： 元数据的列表类型(e.g. method_list_t)
*
*  list_array_tt具有以下三个值之一：
* - 空
* - 指向单个列表的指针
* - 指向多个列表的指针的数组
*
* countLists/beginLists/endLists 迭代元数据
* count/begin/end 迭代基础元数据元素
**********************************************************************/
template <typename Element, typename List>
class list_array_tt {
    struct array_t {
        uint32_t count;
        List* lists[0];

        static size_t byteSize(uint32_t count) {
            return sizeof(array_t) + count*sizeof(lists[0]);
        }
        size_t byteSize() {
            return byteSize(count);
        }
    };
}

3. cache_t 使用的 buckets

cache_t 的结构体定义：

定义类型 变量名 说明
bucket_t _buckets 这段讲解的桶
mask_t _mask 其实就是个32无符号int uint32_t
uint16_t _flags 一些位置标记
uint16_t _occupied 占位的数量，内部元素的数量

buckets 的内部是一个连续的存储空间，存储是一个散列表。
开辟声明的函数调用的是 calloc

当 msgSend 的时候，就会调用 fillCache 进行方法的缓存，存储的涉及 cls sel 和 imp

比较有意思的 bucket_t 内部的顺序定义

bucket_t 的结构体很有意思，arm64 和 i386 的两个值的顺序是反着的。

arm64 的时候是 :

定义类型 变量名
explicit_atomic<uintptr_t> _imp
explicit_atomic<SEL> _sel

armv7*，i386 和 x86_64 的时候是：

定义类型 变量名
explicit_atomic<SEL> _sel
explicit_atomic<uintptr_t> _imp

源码注释：

1
2
// IMP-first对arm64e的参数更好，而对arm64的效果更好。
// 对于armv7*，i386和x86_64，SEL-first更好。

散列表和哈希值的计算

1
2
3
4
5
6
7
// 这里 hash 的计算是用 sel 指针和「capacity-1」做与操作计算
// 下面的 do-while 去处理 hash 冲突的寻址。
// 这里解决冲突的方法不是顺序+1，
// 而是使用这个方法再次计算hash值
// 「fastpath((i = cache_next(i, m)) != begin)」
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);

扩容:

初始的 capacity 是 4。
源码中 cache_t::insert(cls, sel, imp, reveiver) 方法调用的时候，判断扩容。

fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)

也就是说当大于四分之三的时候，就会进行扩容操作，每次 double 扩容

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;

当然不是无限制的扩容，有一个最大容量的限制：

MAX_CACHE_SIZE = 1 << 16

DisguisedPtr

这个类型属于 objc-private.h 里面，是对于对象的一层包装，里面就存储一个对象而已。

出现的场景：就是关联对象的值用的就是这个包装的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// DisguisedPtr<T> 的作用类似于指针类型T*，
// 只是存储的值被伪装成对“leaks”之类的工具隐藏起来。
// nil被伪装成它自己，所以零填充内存可以像预期的那样工作，
// 这意味着0x80..00也伪装成它自己，但我们不在乎。
// 请注意，weak_entry_t 知道此编码。
template <typename T>
class DisguisedPtr {
    uintptr_t value;

    static uintptr_t disguise(T* ptr) {
        return -(uintptr_t)ptr;
    }

    static T* undisguise(uintptr_t val) {
        return (T*)-val;
    }

 public:
    DisguisedPtr() { }
    DisguisedPtr(T* ptr) 
        : value(disguise(ptr)) { }
    DisguisedPtr(const DisguisedPtr<T>& ptr) 
        : value(ptr.value) { }

    DisguisedPtr<T>& operator = (T* rhs) {
        value = disguise(rhs);
        return *this;
    }
    DisguisedPtr<T>& operator = (const DisguisedPtr<T>& rhs) {
        value = rhs.value;
        return *this;
    }

    operator T* () const {
        return undisguise(value);
    }
    T* operator -> () const { 
        return undisguise(value);
    }
    T& operator * () const { 
        return *undisguise(value);
    }
    T& operator [] (size_t i) const {
        return undisguise(value)[i];
    }
    // 省略指针算术运算符
    // 因为我们目前没有在任何地方使用它们
};

NFY 占坑 explicit_atomic

这个类型应该是执行最多次的，看一些文章说一秒钟iOS中执行几百万次

explicit_atomic用来给catchT缓存方法用，核心是原子性和线程安全。

NFY 占坑 sideTable

weak弱引用的散列表

扩展

扩展：non-fragile structs 是什么？OC 1.0 （iOS自始至终都是2.0起的，Mac最开始是1.0）译器生成了一个 ivar 布局，显示了在类中从哪可以访问ivars，对 ivar 的访问就可以通过 对象地址 ＋ ivar偏移字节 的方法。苹果更新了NSObject类，例如增加一些属性，这个又是静态库，发布新版本的系统，这个时候布局就出错了，就不得不重新编译子类来恢复兼容性。(那如果是在线上运行的app，升级系统后就没办法运行了)

使用 Non Fragile ivars 时，程序进行检测来调整类中新增的 ivar 的偏移量。 这样就可以通过 对象地址 ＋ 基类大小 + ivar偏移字节 的方法来计算出 ivar 相应的地址，并访问到相应的 ivar。(即使升级iOS系统，之前的app也能正常运行)

扩展再扩展：为什么OC类不能动态添加成员变量？runtime函数中，确实有一个class_addIvar()函数用于给类添加成员变量，但是文档中特别说明：This function may only be called after objc_allocateClassPair and before objc_registerClassPair. Adding an instance variable to an existing class is not supported. 这个函数只能在“构建一个类的过程中”调用。一旦完成类定义，就不能再添加成员变量了。经过编译的类在程序启动后就被runtime加载，没有机会调用addIvar。程序在运行时动态构建的类需要在调用objc_registerClassPair之后才可以被使用，同样没有机会再添加成员变量。
理论上说，我还是认为可以添加，只是为什么一定不可以，就不得而知了。

References

  1. objective-c non-fragile ivars 学习笔记
  2. Non Fragile ivars
赏

谢谢 请给我一支兰州

支付宝

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

把我的全部，<br>奉献给我所热爱的一切。<br><br>谢谢大家 ~