cache_t
增量扩展的哈希表结构。哈希表内部存储的 bucket_t
。
bucket_t
中存储的是 SEL
和 IMP
的键值对。
-
如果是有序方法列表,采用二分查找
-
如果是无序方法列表,直接遍历查找
// 缓存曾经调用过的方法,提高查找速率
struct cache_t {
struct bucket_t *_buckets; // 散列表
mask_t _mask; //散列表的长度 - 1
mask_t _occupied; // 已经缓存的方法数量,散列表的长度使大于已经缓存的数量的。
//...
}
struct bucket_t {
cache_key_t _key; //SEL作为Key @selector()
IMP _imp; // 函数的内存地址
//...
}
散列表查找过程,在objc-cache.mm
文件中
// 查询散列表,k
bucket_t * cache_t::find(cache_key_t k, id receiver)
{
assert(k != 0); // 断言
bucket_t *b = buckets(); // 获取散列表
mask_t m = mask(); // 散列表长度 - 1
mask_t begin = cache_hash(k, m); // & 操作
mask_t i = begin; // 索引值
do {
if (b[i].key() == 0 || b[i].key() == k) {
return &b[i];
}
} while ((i = cache_next(i, m)) != begin);
// i 的值最大等于mask,最小等于0。
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
上面是查询散列表函数,其中cache_hash(k, m)
是静态内联方法,将传入的key
和mask
进行&
操作返回uint32_t
索引值。do-while
循环查找过程,当发生冲突cache_next
方法将索引值减1。