Class的結(jié)構(gòu)
通過(guò)上一章中對(duì)isa本質(zhì)結(jié)構(gòu)有了新的認(rèn)識(shí)狠半，今天來(lái)回顧C(jī)lass的結(jié)構(gòu)宰翅，重新認(rèn)識(shí)Class內(nèi)部結(jié)構(gòu)弃甥。
首先來(lái)看一下Class的內(nèi)部結(jié)構(gòu)代碼，對(duì)探尋Class的本質(zhì)做簡(jiǎn)單回顧汁讼。
struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache; // formerly cache pointer and vtable
class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
class_rw_t *data() {
return bits.data();
}
void setData(class_rw_t *newData) {
bits.setData(newData);
}
}
class_rw_t* data() {
return (class_rw_t *)(bits & FAST_DATA_MASK);
}
class_rw_t
上述源碼中我們知道bits & FAST_DATA_MASK位運(yùn)算之后淆攻，可以得到class_rw_t，而class_rw_t中存儲(chǔ)著方法列表嘿架、屬性列表以及協(xié)議列表卜录，來(lái)看一下class_rw_t部分代碼
struct class_rw_t {
// Be warned that Symbolication knows the layout of this structure.
uint32_t flags;
uint32_t version;
const class_ro_t *ro;
method_array_t methods; // 方法列表
property_array_t properties; // 屬性列表
protocol_array_t protocols; // 協(xié)議列表
Class firstSubclass;
Class nextSiblingClass;
char *demangledName;
};
上述源碼中，method_array_t眶明、property_array_t艰毒、protocol_array_t其實(shí)都是二維數(shù)組，來(lái)到method_array_t搜囱、property_array_t丑瞧、protocol_array_t內(nèi)部看一下。這里以method_array_t為例蜀肘，method_array_t本身就是一個(gè)數(shù)組绊汹，數(shù)組里面存放的是數(shù)組method_list_t，method_list_t里面最終存放的是method_t
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>();
}
};
class property_array_t :
public list_array_tt<property_t, property_list_t>
{
typedef list_array_tt<property_t, property_list_t> Super;
public:
property_array_t duplicate() {
return Super::duplicate<property_array_t>();
}
};
class protocol_array_t :
public list_array_tt<protocol_ref_t, protocol_list_t>
{
typedef list_array_tt<protocol_ref_t, protocol_list_t> Super;
public:
protocol_array_t duplicate() {
return Super::duplicate<protocol_array_t>();
}
};
class_rw_t里面的methods扮宠、properties西乖、protocols是二維數(shù)組，是可讀可寫(xiě)的，其中包含了類(lèi)的初始內(nèi)容以及分類(lèi)的內(nèi)容获雕。
這里以method_array_t為例薄腻，圖示其中的結(jié)構(gòu)。
class_ro_t
我們之前提到過(guò)class_ro_t中也有存儲(chǔ)方法届案、屬性庵楷、協(xié)議列表，另外還有成員變量列表楣颠。
接著來(lái)看一下class_ro_t部分代碼
struct class_ro_t {
uint32_t flags;
uint32_t instanceStart;
uint32_t instanceSize;
#ifdef __LP64__
uint32_t reserved;
#endif
const uint8_t * ivarLayout;
const char * name;
method_list_t * baseMethodList;
protocol_list_t * baseProtocols;
const ivar_list_t * ivars;
const uint8_t * weakIvarLayout;
property_list_t *baseProperties;
method_list_t *baseMethods() const {
return baseMethodList;
}
};
上述源碼中可以看到class_ro_t *ro是只讀的尽纽，內(nèi)部直接存儲(chǔ)的直接就是method_list_t、protocol_list_t 童漩、property_list_t類(lèi)型的一維數(shù)組弄贿，數(shù)組里面分別存放的是類(lèi)的初始信息，以method_list_t為例矫膨，method_list_t中直接存放的就是method_t挎春，但是是只讀的，不允許增加刪除修改豆拨。
總結(jié)
以方法列表為例直奋，class_rw_t中的methods是二維數(shù)組的結(jié)構(gòu)，并且可讀可寫(xiě)施禾，因此可以動(dòng)態(tài)的添加方法脚线，并且更加便于分類(lèi)方法的添加。因?yàn)槲覀冊(cè)?a href="http://www.reibang.com/p/d3e6839921dd" target="_blank">Category的本質(zhì)里面提到過(guò)弥搞，attachList函數(shù)內(nèi)通過(guò)memmove 和 memcpy兩個(gè)操作將分類(lèi)的方法列表合并在本類(lèi)的方法列表中邮绿。那么此時(shí)就將分類(lèi)的方法和本類(lèi)的方法統(tǒng)一整合到一起了。
其實(shí)一開(kāi)始類(lèi)的方法攀例，屬性船逮，成員變量 屬性 協(xié)議等等都是存放在class_ro_t中的，當(dāng)程序運(yùn)行的時(shí)候粤铭，需要將分類(lèi)中的列表跟類(lèi)初始的列表合并在一起的時(shí)挖胃，就會(huì)將class_ro_t中的列表和分類(lèi)中的列表合并起來(lái)存放在class_rw_t中，也就是說(shuō)class_rw_t中有部分列表是從class_ro_t里面拿出來(lái)的梆惯。并且最終和分類(lèi)的方法合并酱鸭。可以通過(guò)源碼提現(xiàn)這里一點(diǎn)垛吗。
realizeClass部分源碼
static Class realizeClass(Class cls)
{
runtimeLock.assertWriting();
const class_ro_t *ro;
class_rw_t *rw;
Class supercls;
Class metacls;
bool isMeta;
if (!cls) return nil;
if (cls->isRealized()) return cls;
assert(cls == remapClass(cls));
// 最開(kāi)始cls->data是指向ro的
ro = (const class_ro_t *)cls->data();
if (ro->flags & RO_FUTURE) {
// rw已經(jīng)初始化并且分配內(nèi)存空間
rw = cls->data(); // cls->data指向rw
ro = cls->data()->ro; // cls->data()->ro指向ro
cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE);
} else {
// 如果rw并不存在凹髓，則為rw分配空間
rw = (class_rw_t *)calloc(sizeof(class_rw_t), 1); // 分配空間
rw->ro = ro; // rw->ro重新指向ro
rw->flags = RW_REALIZED|RW_REALIZING;
// 將rw傳入setData函數(shù)，等于cls->data()重新指向rw
cls->setData(rw);
}
}
那么從上述源碼中就可以發(fā)現(xiàn)怯屉，類(lèi)的初始信息本來(lái)其實(shí)是存儲(chǔ)在class_ro_t中的蔚舀，并且ro本來(lái)是指向cls->data()的饵沧，也就是說(shuō)bits.data()得到的是ro，但是在運(yùn)行過(guò)程中創(chuàng)建了class_rw_t赌躺，并將cls->data指向rw狼牺，同時(shí)將初始信息ro賦值給rw中的ro。最后在通過(guò)setData(rw)設(shè)置data寿谴。那么此時(shí)bits.data()得到的就是rw锁右，之后再去檢查是否有分類(lèi)失受，同時(shí)將分類(lèi)的方法讶泰，屬性，協(xié)議列表整合存儲(chǔ)在class_rw_t的方法拂到，屬性及協(xié)議列表中痪署。
通過(guò)上述對(duì)源碼的分析，我們對(duì)class_rw_t內(nèi)存儲(chǔ)方法兄旬、屬性狼犯、協(xié)議列表的過(guò)程有了更清晰的認(rèn)識(shí)，那么接下來(lái)探尋class_rw_t中是如何存儲(chǔ)方法的领铐。
class_rw_t中是如何存儲(chǔ)方法的
method_t
我們知道method_array_t悯森、property_array_t、protocol_array_t中以method_array_t為例绪撵，method_array_t中最終存儲(chǔ)的是method_t瓢姻，method_t是對(duì)方法、函數(shù)的封裝音诈，每一個(gè)方法對(duì)象就是一個(gè)method_t幻碱。通過(guò)源碼看一下method_t的結(jié)構(gòu)體
struct method_t {
SEL name; // 函數(shù)名
const char *types; // 編碼（返回值類(lèi)型，參數(shù)類(lèi)型）
IMP imp; // 指向函數(shù)的指針（函數(shù)地址）
};
method_t結(jié)構(gòu)體中可以看到三個(gè)成員變量细溅，我們依次來(lái)看三個(gè)成員變量分別代表什么褥傍。
SEL
SEL代表方法\函數(shù)名，一般叫做選擇器喇聊，底層結(jié)構(gòu)跟char *類(lèi)似 typedef struct objc_selector *SEL;恍风，可以把SEL看做是方法名字符串。
SEL可以通過(guò)@selector()和sel_registerName()獲得
SEL sel1 = @selector(test);
SEL sel2 = sel_registerName("test");
也可以通過(guò)sel_getName()和NSStringFromSelector()將SEL轉(zhuǎn)成字符串
char *string = sel_getName(sel1);
NSString *string2 = NSStringFromSelector(sel2);
不同類(lèi)中相同名字的方法誓篱，所對(duì)應(yīng)的方法選擇器是相同的邻耕。
NSLog(@"%p,%p", sel1,sel2);
Runtime-test[23738:8888825] 0x1017718a3,0x1017718a3
SEL僅僅代表方法的名字，并且不同類(lèi)中相同的方法名的SEL是全局唯一的燕鸽。
types
types包含了函數(shù)返回值兄世，參數(shù)編碼的字符串。通過(guò)字符串拼接的方式將返回值和參數(shù)拼接成一個(gè)字符串啊研，來(lái)代表函數(shù)返回值及參數(shù)御滩。
我們通過(guò)代碼查看一下types是如何代表函數(shù)返回值及參數(shù)的鸥拧，首先通過(guò)自己模擬Class的內(nèi)部實(shí)現(xiàn)，通過(guò)強(qiáng)制轉(zhuǎn)化來(lái)探尋內(nèi)部數(shù)據(jù)削解，相關(guān)代碼在探尋Class的本質(zhì)中提到過(guò)富弦，這里不在贅述。
Person *person = [[Person alloc] init];
xx_objc_class *cls = (__bridge xx_objc_class *)[Person class];
class_rw_t *data = cls->data();
通過(guò)斷點(diǎn)可以在data中找到types的值
上圖中可以看出types的值為v16@0:8氛驮，那么這個(gè)值代表什么呢腕柜？apple為了能夠清晰的使用字符串表示方法及其返回值，制定了一系列對(duì)應(yīng)規(guī)則矫废，通過(guò)下表可以看到一一對(duì)應(yīng)關(guān)系
將types的值同表中的一一對(duì)照查看types的值v16@0:8 代表什么
- (void) test;
v 16 @ 0 : 8
void id SEL
// 16表示參數(shù)的占用空間大小盏缤，id后面跟的0表示從0位開(kāi)始存儲(chǔ)，id占8位空間蓖扑。
// SEL后面的8表示從第8位開(kāi)始存儲(chǔ)唉铜，SEL同樣占8位空間
我們知道任何方法都默認(rèn)有兩個(gè)參數(shù)的，id類(lèi)型的self律杠，和SEL類(lèi)型的_cmd潭流，而上述通過(guò)對(duì)types的分析同時(shí)也驗(yàn)證了這個(gè)說(shuō)法。
為了能夠看的更加清晰柜去，我們?yōu)閠est添加返回值及參數(shù)之后重新查看types的值灰嫉。
同樣通過(guò)上表找出一一對(duì)應(yīng)的值，查看types的值代表的方法
- (int)testWithAge:(int)age Height:(float)height
{
return 0;
}
i 24 @ 0 : 8 i 16 f 20
int id SEL int float
// 參數(shù)的總占用空間為 8 + 8 + 4 + 4 = 24
// id 從第0位開(kāi)始占據(jù)8位空間
// SEL 從第8位開(kāi)始占據(jù)8位空間
// int 從第16位開(kāi)始占據(jù)4位空間
// float 從第20位開(kāi)始占據(jù)4位空間
iOS提供了@encode的指令嗓奢，可以將具體的類(lèi)型轉(zhuǎn)化成字符串編碼讼撒。
NSLog(@"%s",@encode(int));
NSLog(@"%s",@encode(float));
NSLog(@"%s",@encode(id));
NSLog(@"%s",@encode(SEL));
// 打印內(nèi)容
Runtime-test[25275:9144176] i
Runtime-test[25275:9144176] f
Runtime-test[25275:9144176] @
Runtime-test[25275:9144176] :
上述代碼中可以看到，對(duì)應(yīng)關(guān)系確實(shí)如上表所示蔓罚。
IMP
IMP代表函數(shù)的具體實(shí)現(xiàn)椿肩，存儲(chǔ)的內(nèi)容是函數(shù)地址。也就是說(shuō)當(dāng)找到imp的時(shí)候就可以找到函數(shù)實(shí)現(xiàn)豺谈，進(jìn)而對(duì)函數(shù)進(jìn)行調(diào)用郑象。
在上述代碼中打印IMP的值
Printing description of data->methods->first.imp:
(IMP) imp = 0x000000010c66a4a0 (Runtime-test`-[Person testWithAge:Height:] at Person.m:13)
之后在test方法內(nèi)部打印斷點(diǎn)，并來(lái)到其方法內(nèi)部可以看出imp中的存儲(chǔ)的地址也就是方法實(shí)現(xiàn)的地址茬末。
通過(guò)上面的學(xué)習(xí)我們知道了方法列表是如何存儲(chǔ)在Class類(lèi)對(duì)象中的厂榛，但是當(dāng)多次繼承的子類(lèi)想要調(diào)用基類(lèi)方法時(shí)，就需要通過(guò)superclass指針一層一層找到基類(lèi)丽惭，在從基類(lèi)方法列表中找到對(duì)應(yīng)的方法進(jìn)行調(diào)用击奶。如果多次調(diào)用基類(lèi)方法，那么就需要多次遍歷每一層父類(lèi)的方法列表责掏，這對(duì)性能來(lái)說(shuō)無(wú)疑是傷害巨大的柜砾。
apple通過(guò)方法緩存的形式解決了這一問(wèn)題，接下來(lái)我們來(lái)探尋Class類(lèi)對(duì)象是如何進(jìn)行方法緩存的
方法緩存 cache_t
回到類(lèi)對(duì)象結(jié)構(gòu)體换衬，成員變量cache就是用來(lái)對(duì)方法進(jìn)行緩存的痰驱。
struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache; // formerly cache pointer and vtable
class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
class_rw_t *data() {
return bits.data();
}
void setData(class_rw_t *newData) {
bits.setData(newData);
}
}
cache_t cache;用來(lái)緩存曾經(jīng)調(diào)用過(guò)的方法证芭，可以提高方法的查找速度。
回顧方法調(diào)用過(guò)程：
調(diào)用方法的時(shí)候担映，需要去方法列表里面進(jìn)行遍歷查找废士。如果方法不在列表里面，就會(huì)通過(guò)
superclass找到父類(lèi)的類(lèi)對(duì)象蝇完，在去父類(lèi)類(lèi)對(duì)象方法列表里面遍歷查找官硝。如果方法需要調(diào)用很多次的話，那就相當(dāng)于每次調(diào)用都需要去遍歷多次方法列表短蜕，為了能夠快速查找方法氢架，
apple設(shè)計(jì)了cache_t來(lái)進(jìn)行方法緩存。每當(dāng)調(diào)用方法的時(shí)候忿危，會(huì)先去
cache中查找是否有緩存的方法达箍，
如果沒(méi)有緩存没龙，在去類(lèi)對(duì)象方法列表中查找铺厨，以此類(lèi)推直到找到方法之后，就會(huì)將方法直接存儲(chǔ)在cache中硬纤，下一次在調(diào)用這個(gè)方法的時(shí)候解滓，就會(huì)在類(lèi)對(duì)象的cache里面找到這個(gè)方法，直接調(diào)用了筝家。
cache_t 如何進(jìn)行緩存
那么cache_t是如何對(duì)方法進(jìn)行緩存的呢洼裤？首先來(lái)看一下cache_t的內(nèi)部結(jié)構(gòu)。
struct cache_t {
struct bucket_t *_buckets; // 散列表 數(shù)組
mask_t _mask; // 散列表的長(zhǎng)度 -1
mask_t _occupied; // 已經(jīng)緩存的方法數(shù)量
};
bucket_t是以數(shù)組的方式存儲(chǔ)方法列表的溪王，看一下bucket_t內(nèi)部結(jié)構(gòu)
struct bucket_t {
private:
cache_key_t _key; // SEL作為Key
IMP _imp; // 函數(shù)的內(nèi)存地址
};
從源碼中可以看出bucket_t中存儲(chǔ)著SEL和_imp腮鞍，通過(guò)key->value的形式，以SEL為key莹菱，函數(shù)實(shí)現(xiàn)的內(nèi)存地址 _imp為value來(lái)存儲(chǔ)方法移国。
通過(guò)一張圖來(lái)展示一下cache_t的結(jié)構(gòu)。
上述bucket_t列表我們稱之為散列表（哈希表）
散列表（Hash table道伟，也叫哈希表）迹缀，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)蜜徽，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄祝懂，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)拘鞋，存放記錄的數(shù)組叫做散列表砚蓬。
那么apple如何在散列表中快速并且準(zhǔn)確的找到對(duì)應(yīng)的key以及函數(shù)實(shí)現(xiàn)呢？這就需要我們通過(guò)源碼來(lái)看一下apple的散列函數(shù)是如何設(shè)計(jì)的盆色。
散列函數(shù)及散列表原理
首先來(lái)看一下存儲(chǔ)的源碼灰蛙，主要查看幾個(gè)函數(shù)颅和，關(guān)鍵代碼都有注釋，不在贅述缕允。
cache_fill 及 cache_fill_nolock 函數(shù)
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
#if !DEBUG_TASK_THREADS
mutex_locker_t lock(cacheUpdateLock);
cache_fill_nolock(cls, sel, imp, receiver);
#else
_collecting_in_critical();
return;
#endif
}
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
cacheUpdateLock.assertLocked();
// 如果沒(méi)有initialize直接return
if (!cls->isInitialized()) return;
// 確保線程安全峡扩，沒(méi)有其他線程添加緩存
if (cache_getImp(cls, sel)) return;
// 通過(guò)類(lèi)對(duì)象獲取到cache
cache_t *cache = getCache(cls);
// 將SEL包裝成Key
cache_key_t key = getKey(sel);
// 占用空間+1
mask_t newOccupied = cache->occupied() + 1;
// 獲取緩存列表的緩存能力，能存儲(chǔ)多少個(gè)鍵值對(duì)
mask_t capacity = cache->capacity();
if (cache->isConstantEmptyCache()) {
// 如果為空的障本，則創(chuàng)建空間教届，這里創(chuàng)建的空間為4個(gè)。
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}
else if (newOccupied <= capacity / 4 * 3) {
// 如果所占用的空間占總數(shù)的3/4一下驾霜，則繼續(xù)使用現(xiàn)在的空間
}
else {
// 如果占用空間超過(guò)3/4則擴(kuò)展空間
cache->expand();
}
// 通過(guò)key查找合適的存儲(chǔ)空間案训。
bucket_t *bucket = cache->find(key, receiver);
// 如果key==0則說(shuō)明之前未存儲(chǔ)過(guò)這個(gè)key，占用空間+1
if (bucket->key() == 0) cache->incrementOccupied();
// 存儲(chǔ)key粪糙，imp
bucket->set(key, imp);
}
reallocate 函數(shù)
通過(guò)上述源碼看到reallocate函數(shù)負(fù)責(zé)分配散列表空間强霎，來(lái)到reallocate函數(shù)內(nèi)部。
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
// 舊的散列表能否被釋放
bool freeOld = canBeFreed();
// 獲取舊的散列表
bucket_t *oldBuckets = buckets();
// 通過(guò)新的空間需求量創(chuàng)建新的散列表
bucket_t *newBuckets = allocateBuckets(newCapacity);
assert(newCapacity > 0);
assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
// 設(shè)置Buckets和Mash蓉冈，Mask的值為散列表長(zhǎng)度-1
setBucketsAndMask(newBuckets, newCapacity - 1);
// 釋放舊的散列表
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
cache_collect(false);
}
}
上述源碼中首次傳入reallocate函數(shù)的newCapacity為INIT_CACHE_SIZE城舞，INIT_CACHE_SIZE是個(gè)枚舉值，也就是4寞酿。因此散列表最初創(chuàng)建的空間就是4個(gè)家夺。
enum {
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2)
};
expand ()函數(shù)
當(dāng)散列表的空間被占用超過(guò)3/4的時(shí)候，散列表會(huì)調(diào)用expand ()函數(shù)進(jìn)行擴(kuò)展伐弹，我們來(lái)看一下expand ()函數(shù)內(nèi)散列表如何進(jìn)行擴(kuò)展的拉馋。
void cache_t::expand()
{
cacheUpdateLock.assertLocked();
// 獲取舊的散列表的存儲(chǔ)空間
uint32_t oldCapacity = capacity();
// 將舊的散列表存儲(chǔ)空間擴(kuò)容至兩倍
uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
// 為新的存儲(chǔ)空間賦值
if ((uint32_t)(mask_t)newCapacity != newCapacity) {
newCapacity = oldCapacity;
}
// 調(diào)用reallocate函數(shù)，重新創(chuàng)建存儲(chǔ)空間
reallocate(oldCapacity, newCapacity);
}
上述源碼中可以發(fā)現(xiàn)散列表進(jìn)行擴(kuò)容時(shí)會(huì)將容量增至之前的2倍惨好。
find 函數(shù)
最后來(lái)看一下散列表中如何快速的通過(guò)key找到相應(yīng)的bucket呢煌茴？我們來(lái)到find函數(shù)內(nèi)部
bucket_t * cache_t::find(cache_key_t k, id receiver)
{
assert(k != 0);
// 獲取散列表
bucket_t *b = buckets();
// 獲取mask
mask_t m = mask();
// 通過(guò)key找到key在散列表中存儲(chǔ)的下標(biāo)
mask_t begin = cache_hash(k, m);
// 將下標(biāo)賦值給i
mask_t i = begin;
// 如果下標(biāo)i中存儲(chǔ)的bucket的key==0說(shuō)明當(dāng)前沒(méi)有存儲(chǔ)相應(yīng)的key，將b[i]返回出去進(jìn)行存儲(chǔ)
// 如果下標(biāo)i中存儲(chǔ)的bucket的key==k日川，說(shuō)明當(dāng)前空間內(nèi)已經(jīng)存儲(chǔ)了相應(yīng)key蔓腐，將b[i]返回出去進(jìn)行存儲(chǔ)
do {
if (b[i].key() == 0 || b[i].key() == k) {
// 如果滿足條件則直接reutrn出去
return &b[i];
}
// 如果走到這里說(shuō)明上面不滿足，那么會(huì)往前移動(dòng)一個(gè)空間重新進(jìn)行判定逗鸣，知道可以成功return為止
} while ((i = cache_next(i, m)) != begin);
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
函數(shù)cache_hash (k, m)用來(lái)通過(guò)key找到方法在散列表中存儲(chǔ)的下標(biāo)合住，來(lái)到cache_hash (k, m)函數(shù)內(nèi)部
static inline mask_t cache_hash(cache_key_t key, mask_t mask)
{
return (mask_t)(key & mask);
}
可以發(fā)現(xiàn)cache_hash (k, m)函數(shù)內(nèi)部?jī)H僅是進(jìn)行了key & mask的按位與運(yùn)算，得到下標(biāo)即存儲(chǔ)在相應(yīng)的位置上撒璧。按位與運(yùn)算在上文中已詳細(xì)講解過(guò)透葛，這里不在贅述。
_mask
通過(guò)上面的分析我們知道_mask的值是散列表的長(zhǎng)度減一卿樱，那么任何數(shù)通過(guò)與_mask進(jìn)行按位與運(yùn)算之后獲得的值都會(huì)小于等于_mask僚害，因此不會(huì)出現(xiàn)數(shù)組溢出的情況。
舉個(gè)例子，假設(shè)散列表的長(zhǎng)度為8萨蚕，那么mask的值為7
0101 1011 // 任意值
& 0000 0111 // mask = 7
------------
0000 0011 //獲取的值始終等于或小于mask的值
總結(jié)
-
當(dāng)?shù)谝淮问褂梅椒〞r(shí)靶草，消息機(jī)制通過(guò)isa找到方法之后，會(huì)對(duì)方法以
SEL為keyIMP為value的方式緩存在cache的_buckets中岳遥，當(dāng)?shù)谝淮未鎯?chǔ)的時(shí)候奕翔，會(huì)創(chuàng)建具有4個(gè)空間的散列表，并將_mask的值置為散列表的長(zhǎng)度減一浩蓉，之后通過(guò)SEL & mask計(jì)算出方法存儲(chǔ)的下標(biāo)值派继，并將方法存儲(chǔ)在散列表中。舉個(gè)例子捻艳，如果計(jì)算出下標(biāo)值為3驾窟，那么就將方法直接存儲(chǔ)在下標(biāo)為3的空間中，前面的空間會(huì)留空认轨。 -
當(dāng)散列表中存儲(chǔ)的方法占據(jù)散列表長(zhǎng)度超過(guò)3/4的時(shí)候绅络，散列表會(huì)進(jìn)行
擴(kuò)容操作，將創(chuàng)建一個(gè)新的散列表并且空間擴(kuò)容至原來(lái)空間的兩倍嘁字，并重置_mask的值恩急，最后釋放舊的散列表，此時(shí)再有方法要進(jìn)行緩存的話拳锚，就需要重新通過(guò)SEL & mask計(jì)算出下標(biāo)值之后在按照下標(biāo)進(jìn)行存儲(chǔ)了假栓。 -
如果一個(gè)類(lèi)中方法很多寻行，其中很可能會(huì)出現(xiàn)多個(gè)方法的
SEL & mask得到的值為同一個(gè)下標(biāo)值霍掺，那么會(huì)調(diào)用cache_next函數(shù)往下標(biāo)值-1位去進(jìn)行存儲(chǔ)，如果下標(biāo)值-1位空間中有存儲(chǔ)方法拌蜘，并且key不與要存儲(chǔ)的key相同杆烁，那么再到前面一位進(jìn)行比較，直到找到一位空間沒(méi)有存儲(chǔ)方法或者key與要存儲(chǔ)的key相同為止简卧，如果到下標(biāo)0的話就會(huì)到下標(biāo)為_mask的空間也就是最大空間處進(jìn)行比較兔魂。 -
當(dāng)要查找方法時(shí)，并不需要遍歷散列表举娩，同樣通過(guò)
SEL & mask計(jì)算出下標(biāo)值析校，直接去下標(biāo)值的空間取值即可，同上铜涉，如果下標(biāo)值中存儲(chǔ)的key與要查找的key不相同智玻，就去前面一位查找。這樣雖然占用了少量控件芙代，但是大大節(jié)省了時(shí)間吊奢，也就是說(shuō)其實(shí)apple是使用空間換取了存取的時(shí)間。
通過(guò)一張圖更清晰的看一下其中的流程纹烹。
驗(yàn)證上述流程
通過(guò)一段代碼演示一下 页滚。同樣使用仿照objc_class結(jié)構(gòu)體自定義一個(gè)結(jié)構(gòu)體召边，并進(jìn)行強(qiáng)制轉(zhuǎn)化來(lái)查看其內(nèi)部數(shù)據(jù)，自定義結(jié)構(gòu)體在之前的文章中使用過(guò)多次這里不在贅述裹驰。
我們創(chuàng)建Person類(lèi)繼承NSObject隧熙，Student類(lèi)繼承Person，CollegeStudent繼承Student幻林。三個(gè)類(lèi)分別有personTest贱鼻，studentTest，colleaeStudentTest方法
通過(guò)打印斷點(diǎn)來(lái)看一下方法緩存的過(guò)程
int main(int argc, const char * argv[]) {
@autoreleasepool {
CollegeStudent *collegeStudent = [[CollegeStudent alloc] init];
xx_objc_class *collegeStudentClass = (__bridge xx_objc_class *)[CollegeStudent class];
cache_t cache = collegeStudentClass->cache;
bucket_t *buckets = cache._buckets;
[collegeStudent personTest];
[collegeStudent studentTest];
NSLog(@"----------------------------");
for (int i = 0; i <= cache._mask; i++) {
bucket_t bucket = buckets[i];
NSLog(@"%s %p", bucket._key, bucket._imp);
}
NSLog(@"----------------------------");
[collegeStudent colleaeStudentTest];
cache = collegeStudentClass->cache;
buckets = cache._buckets;
NSLog(@"----------------------------");
for (int i = 0; i <= cache._mask; i++) {
bucket_t bucket = buckets[i];
NSLog(@"%s %p", bucket._key, bucket._imp);
}
NSLog(@"----------------------------");
NSLog(@"%p",@selector(colleaeStudentTest));
NSLog(@"----------------------------");
}
return 0;
}
我們分別在collegeStudent實(shí)例對(duì)象調(diào)用personTest滋将，studentTest邻悬，colleaeStudentTest方法處打斷點(diǎn)查看cache的變化。
personTest方法調(diào)用之前
從上圖中可以發(fā)現(xiàn)随闽，personTest方法調(diào)用之前父丰，cache中僅僅存儲(chǔ)了init方法，上圖中可以看出init方法恰好存儲(chǔ)在下標(biāo)為0的位置因此我們可以看到掘宪，_mask的值為3驗(yàn)證我們上述源碼中提到的散列表第一次存儲(chǔ)時(shí)會(huì)分配4個(gè)內(nèi)存空間蛾扇，_occupied的值為1證明此時(shí)_buckets中僅僅存儲(chǔ)了一個(gè)方法。
當(dāng)collegeStudent在調(diào)用personTest的時(shí)候魏滚，首先發(fā)現(xiàn)collegeStudent類(lèi)對(duì)象的cache中沒(méi)有personTest方法镀首，就會(huì)去collegeStudent類(lèi)對(duì)象的方法列表中查找，方法列表中也沒(méi)有鼠次，那么就通過(guò)superclass指針找到Student類(lèi)對(duì)象更哄，Studeng類(lèi)對(duì)象中cache和方法列表同樣沒(méi)有，再通過(guò)superclass指針找到Person類(lèi)對(duì)象腥寇，最終在Person類(lèi)對(duì)象方法列表中找到之后進(jìn)行調(diào)用成翩，并緩存在collegeStudent類(lèi)對(duì)象的cache中。
執(zhí)行personTest方法之后查看cache方法的變化
上圖中可以發(fā)現(xiàn)_occupied值為2赦役，說(shuō)明此時(shí)personTest方法已經(jīng)被緩存在collegeStudent類(lèi)對(duì)象的cache中麻敌。
同理執(zhí)行過(guò)studentTest方法之后，我們通過(guò)打印查看一下此時(shí)cache內(nèi)存儲(chǔ)的信息
上圖中可以看到cache中確實(shí)存儲(chǔ)了 init 掂摔、personTest 术羔、studentTest三個(gè)方法。
那么執(zhí)行過(guò)colleaeStudentTest方法之后此時(shí)cache中應(yīng)該對(duì)colleaeStudentTest方法進(jìn)行緩存乙漓。上面源碼提到過(guò)级历，當(dāng)存儲(chǔ)的方法數(shù)超過(guò)散列表長(zhǎng)度的3/4時(shí)，系統(tǒng)會(huì)重新創(chuàng)建一個(gè)容量為原來(lái)兩倍的新的散列表替代原來(lái)的散列表簇秒。過(guò)掉colleaeStudentTest方法鱼喉，重新打印cache內(nèi)存儲(chǔ)的方法查看。
可以看出上圖中_bucket散列表擴(kuò)容之后僅僅存儲(chǔ)了colleaeStudentTest方法，并且上圖中打印SEL & _mask 位運(yùn)算得出下標(biāo)的值確實(shí)是_bucket列表中colleaeStudentTest方法存儲(chǔ)的位置扛禽。
至此已經(jīng)對(duì)Class的結(jié)構(gòu)及方法緩存的過(guò)程有了新的認(rèn)知锋边，apple通過(guò)散列表的形式對(duì)方法進(jìn)行緩存，以少量的空間節(jié)省了大量查找方法的時(shí)間编曼。
Runtime 博文推薦
Runtime圖解
Runtime 10種實(shí)際用法
完整總結(jié)
objc_msgSend
詳解
快速上手
消息機(jī)制
Method Swizzling開(kāi)發(fā)實(shí)例匯總
最實(shí)用的runtime總結(jié)
實(shí)際開(kāi)發(fā)中的應(yīng)用
