cache_t可以看做一个哈希表,以sel作为key,查找方法的imp。
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
...
}
struct bucket_t *_buckets是一个通过calloc函数得到的一块连续的内存,里面存储的是bucket_t的结构体,_buckets可以像数组一样通过下标index存取值,当存储的bucket_t超过限制时,会通过expand()函数进行扩容。
struct bucket_t {
MethodCacheIMP _imp;
cache_key_t _key;
...
};
bucket_t里面包含了我们要找的方法imp。
cache会通过一个哈希算法由sel得到一个index,然后从数组_buckets中取出对应的bucket_t得到imp。
哈希算法的实现:
static inline mask_t cache_hash(cache_key_t key, mask_t mask)
{
return (mask_t)(key & mask);
}
对于有可能出现的哈希冲突,使用了再次哈希的方式来解决:
bucket_t * cache_t::find(cache_key_t k, id receiver)
{
bucket_t *b = buckets();
mask_t m = mask();
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);
}
cache_next时出现冲突时再次hash得到的下标index。