类，元类的methods成员变量

在之前分析类的时候，类里面的methods存储着该类所有的实例方法信息，那么它具体是怎么存储的？

class method_array_t : 
    public list_array_tt<method_t, method_list_t> 
{
    typedef list_array_tt<method_t, method_list_t> Super;

 public:
    method_list_t **beginCategoryMethodLists() {
        return beginLists();
    }
    
    method_list_t **endCategoryMethodLists(Class cls);

    method_array_t duplicate() {
        return Super::duplicate<method_array_t>();
    }
};
// MARK: - method结构声明
struct method_t {
    SEL name;//SEL
    const char *types;//方法参数和类型
    MethodListIMP imp;//imp

    struct SortBySELAddress :
        public std::binary_function<const method_t&,
                                    const method_t&, bool>
    {
        bool operator() (const method_t& lhs,
                         const method_t& rhs)
        { return lhs.name < rhs.name; }
    };
};
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

查看源码发现其实methods是一个数组指针，这个数组的大小为（N + 1）* 8个字节（N为分类个数），也就是说这个数组里面存着一些一维数组，指向真正的实例方法列表，也就是分类1的实例方法列表，类本身的方法列表等等。方法列表里面放着一个个实例方法method_t，看看他的定义。

// MARK: - method结构声明
struct method_t {
    SEL name;//SEL
    const char *types;//方法参数和类型
    MethodListIMP imp;//imp

    struct SortBySELAddress :
        public std::binary_function<const method_t&,
                                    const method_t&, bool>
    {
        bool operator() (const method_t& lhs,
                         const method_t& rhs)
        { return lhs.name < rhs.name; }
    };
};
typedef struct method_t *Method; // 方法声明
// 方法的本质就是一个method_t结构体指针，它可以指向任何一个方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

可以发现里面就三个指针，所以它只占用了24个字节，这些内存都是在静态区的。元类的methods同理，只不过保存的是类方法列表。
下面分析一下这三个成员变量。

• SEL：方法选择器，跟方法名一一对应，是一个方法的唯一标识，可以当作方法名看待，之前使用的@selector（方法名）就是获得一个方法选择器。
• types：类型编码字符串，包含了方法的参数和返回值信息，编码中第一个值代表返回值类型，后面字母依次表示该方法的各个参数类型。第一个数字代表所有参数占用总内存，后面的数字代表各参数内存地址的偏移量。
• IMP：函数指针，存储着一个地址，指向该方法在代码区的具体实现。

类，元类的cache成员变量

当一个对象接受到消息时，会根据它的isa指针找到它所属的类，然后根据类的methods找到所有的方法列表，然后依次遍历这些方法列表来查找要执行的方法。在实际情况中，一个对象只有一部分方法是常用的，其余方法用的频率很低，如果对象每接受一次消息就要遍历一次所有的列表，性能肯定很差。
类的cache成员变量就是用来解决这个问题的。
系统每次调用一次方法，就会将这个方法存储到cache中，下次再调用方法就优先从cache中查找。找不到再去methods里面找，大大提高了方法查找的效率。
看看cache源码。

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;
}
// MARK: - bucket_t声明结构
struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
    MethodCacheIMP _imp;
    cache_key_t _key;
#else
    cache_key_t _key;
    MethodCacheIMP _imp;
#endif

public:
    inline cache_key_t key() const { return _key; }
    inline IMP imp() const { return (IMP)_imp; }
    inline void setKey(cache_key_t newKey) { _key = newKey; }
    inline void setImp(IMP newImp) { _imp = newImp; }

    void set(cache_key_t newKey, IMP newImp);
};
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

分析一下成员变量

• _buckets:方法缓存散列表
• _mask:散列表长度 - 1
• _occupied：缓存方法数量

可以看出散列表里面的元素不直接是method_t,而是bucket_t，点开它的结构可以发现，它有两个成员变量IMP和cache_key_t.IMP就是一个函数指针，令一个忙猜是函数标识。
下面看看apple如何实现这个散列表。

// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.
// 可以在这里的sel is key看出cache_key_t等同于唯一标识SEL，cahe散列表存储了IMP和SEL
// 缓存不会构建在dyld共享缓存中
static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    // 这里的散列算法很简单，就是用key&长度-1获得index
    // SEL是方法唯一标识
    return (mask_t)(key & mask);
}
1
2
3
4
5
6
7
8
9
10

cache_hash冲突

在实际过程中，有可能遇见这样的问题，不同的sel & n - 1后得到了相同的index，那么会产生数据冲突。这时如何处理？

// 散列表读取
bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);
    // 获取散列表和长度-1
    bucket_t *b = buckets();
    mask_t m = mask();
    // 通过散列算法得到某个长度的索引
    mask_t begin = cache_hash(k, m);
    mask_t i = begin;
    do {
        // 读取index的元素对比SEL，判断是否和我们需要的相等，返回
        // 或者找到空闲内存，说明第一次调用，存入
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
    // 否则Index - 1，遍历散列表，直到读取到想要的SEL
    // hack
    
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    // 判断一些错误情况
    cache_t::bad_cache(receiver, (SEL)k, cls);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

可以看见这里需要对比index处是否空闲或者元素SEL是否和我们搜索的相等，如果没找到我们就会index - 1，遍历散列表，直到找到空闲的内存，或者真正的方法。
读取我们直接根据index拿方法，不需要遍历。

cache散列表扩容

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();
    
    bucket_t *oldBuckets = buckets();
    // 开辟新的散列表
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        // 释放旧的散列表，清空其缓存
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

当散列表的内存不够用时，系统进行两倍扩容。
本文参考——参考文章