在 iOS 開發(fā)中，NSArray是一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)。尤其 TableView 中的數(shù)據(jù)緩存與更新腰耙，NSArray來緩存數(shù)據(jù)以及對(duì)于顯示數(shù)據(jù)的修改操作氛堕。而在 Core Foundation 中CFArray與NSArray相互對(duì)應(yīng)立肘，這引起了筆者對(duì) Core Foundation 和 Foundation 庫中的原生數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)產(chǎn)生興趣边坤，所以來研究一下。
CFArray 歷史淵源
NSArray和CFArray是Toll-Free Bridged的谅年，在opensource.apple.com中茧痒，CFArray是開源的。這更有助于我們的學(xué)習(xí)與研究融蹂。在Garan no Dou大神之前在做個(gè)人工具庫的時(shí)候旺订，曾經(jīng)研究過CFArray的歷史淵源和實(shí)現(xiàn)手段，在閱讀此文之前可以參考一下前輩的優(yōu)秀博文超燃。
Array這篇 2005 年的早期文獻(xiàn)中区拳，最早介紹過CFArray，并且測試過其性能水平意乓。它將CFArray和 STL 中的Vector容器進(jìn)行了性能對(duì)比樱调，由于后者的實(shí)現(xiàn)我們可以理解成是對(duì) C 中的數(shù)組封裝，所以在性能圖上大多數(shù)操作都是線性的届良。而在CFArray的圖中笆凌，會(huì)發(fā)現(xiàn)很多不一樣的地方。
上圖分析可以看出士葫，CFArray在頭插乞而、尾插插入時(shí)候的效率近乎常數(shù)，而對(duì)于中間元素的操作會(huì)從小數(shù)據(jù)的線性效率在一個(gè)閥值上突然轉(zhuǎn)變成線性效率慢显，而這個(gè)躍變灰不由得想起在 Java 8 當(dāng)中的HashMap的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)變方式爪模。
在 ObjC 的初期，CFArray是使用deque 雙端隊(duì)列實(shí)現(xiàn)鳍怨，所以會(huì)呈現(xiàn)出頭尾操作高效呻右，而中間操作成線性的特點(diǎn)跪妥。在容量超過 300000 左右時(shí)（實(shí)際應(yīng)該是 262140 = 2^18 ）鞋喇，時(shí)間復(fù)雜度發(fā)生陡變。在源代碼中眉撵，閥值被宏定義為__CF_MAX_BUCKETS_PER_DEQUE侦香，具體代碼可以見CF-550-CFArray.c（2011 年版本）：
1
2
3
4
5
6
7if(__CF_MAX_BUCKETS_PER_DEQUEfutureCnt){
// 創(chuàng)建 CFStorage 引用
CFStorageRefstore
// 轉(zhuǎn)換 CFArray 為 Storage
__CFArrayConvertDequeToStore(array);
store=(CFStorageRef)array->_store;
}
可以看到，當(dāng)數(shù)據(jù)超出閥值__CF_MAX_BUCKETS_PER_DEQUE的時(shí)候纽疟，會(huì)將數(shù)據(jù)結(jié)構(gòu)從CFArray轉(zhuǎn)換成CFStorage罐韩。CFStorage是一個(gè)平衡二叉樹的結(jié)構(gòu)，為了維護(hù)數(shù)組的順序訪問污朽，將 Node 的權(quán)值使用下標(biāo)完成插入和旋轉(zhuǎn)操作散吵。具體的體現(xiàn)可以看CFStorageInsertValues操作。具體代碼可以查看CF-368.18-CFStorage.c。
在 2011 年以后的CF-635.15-CFArray.c版本中矾睦，CFArray取消了數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換這一功能晦款。或許是為了防止大數(shù)據(jù)時(shí)候二叉樹建樹的時(shí)間抖動(dòng)問題從而取消了這一特性枚冗。直接來看下數(shù)據(jù)結(jié)構(gòu)的描述：
1
2
3
4
5
6
7
8
9
10
11struct__CFArrayDeque{
uintptr_t_leftIdx;// 自左開始下標(biāo)位置
uintptr_t_capacity;// 當(dāng)前容量
};
struct__CFArray{
CFRuntimeBase_base;
CFIndex_count;// 元素個(gè)數(shù)
CFIndex_mutations;// 元素抖動(dòng)量
int32_t_mutInProgress;
__strongvoid*_store;
};
從命名上可以看出CFArray由單一的雙端隊(duì)列進(jìn)行實(shí)現(xiàn)缓溅，而且記錄了一些容器信息。
C 數(shù)組的一些問題
C 語言中的數(shù)組赁温，會(huì)開辟一段連續(xù)的內(nèi)存空間來進(jìn)行數(shù)據(jù)的讀寫坛怪、存儲(chǔ)操作。另外說一句股囊，數(shù)組和指針并不相同袜匿。有一種被很多教材書籍上濫用的說法：一塊被 malloc 過的內(nèi)存空間等于一個(gè)數(shù)組。這是錯(cuò)誤的稚疹。最簡單的解釋沉帮，指針需要申請一個(gè)指針區(qū)域來存儲(chǔ)（指向）一塊空間的起始位置，而數(shù)組（的頭部）是對(duì)一塊空間起始位置的直接訪問贫堰。另外想了解更多可以看Are pointers and arrays equivalent in C?這篇博文穆壕。
C 中的數(shù)組最顯著的缺點(diǎn)就是，在下標(biāo) 0 處插入時(shí)其屏，需要移動(dòng)所有的元素（即memmove()函數(shù)的原理）喇勋。類似的，當(dāng)刪除第一個(gè)元素偎行、在第一個(gè)元素前插入一個(gè)元素也會(huì)造成O(n)復(fù)雜度的操作川背。然而數(shù)組是常讀寫的容器，所以 O(n) 的操作會(huì)造成很嚴(yán)重的時(shí)間開銷蛤袒。
當(dāng)前版本中 CFArray 的部分實(shí)現(xiàn)細(xì)節(jié)
在CF-855.17中熄云，我們可以看到當(dāng)前版本的CFArray的實(shí)現(xiàn)。文檔中對(duì)CFArray有如下的描述：
CFArray實(shí)現(xiàn)了一個(gè)可被指針順序訪問的緊湊容器妙真。其值可通過整數(shù)鍵（索引下標(biāo)）進(jìn)行訪問缴允，范圍從 0 至 N-1，其中 N 是數(shù)組中值的數(shù)量珍德。稱其緊湊 (compact)的原因是該容器進(jìn)行刪除或插入某個(gè)值的時(shí)候练般，不會(huì)再內(nèi)存空間中留下間隙，訪問順序仍舊按照原有鍵值數(shù)值大小排列锈候，使得有效檢索集合范圍總是在整數(shù)范圍 [0, N-1] 之中薄料。因此，特定值的下標(biāo)可能會(huì)隨著其他元素插入至數(shù)組或被刪除時(shí)而改變泵琳。
數(shù)組有兩種類型：不可變(immutable)類型在創(chuàng)建數(shù)組之后摄职，不能向其添加或刪除元素誊役，而可變(mutable)類型可以添加或從中刪除元素」仁校可變數(shù)組的元素?cái)?shù)量無限制（或者稱只受CFArray外部的約束限制势木，例如可用內(nèi)存空間大小）歌懒。與所有的 CoreFoundation 集合類型同理啦桌，數(shù)組將保持與元素對(duì)象的強(qiáng)引用關(guān)系。
為了進(jìn)一步弄清CFArray的細(xì)節(jié)及皂，我們來分析一下CFArray的幾個(gè)操作方法：
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// 通過下標(biāo)查詢元素值
constvoid*CFArrayGetValueAtIndex(CFArrayRefarray,CFIndexidx){
// 這個(gè)函數(shù)尚未開源
// 通過給定的 CFTypeID 來驗(yàn)證指定元素是否匹配 Core Foundation 橋接類
CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID,constvoid*,(NSArray *)array,objectAtIndex:idx);
// 尚未開源
// 通過給定的 CFTypeID 來驗(yàn)證 Core Foundation 類型合法性
__CFGenericValidateType(array,__kCFArrayTypeID);
CFAssert2(0idx&&idx__CFArrayGetCount(array),__kCFLogAssertion,"%s(): index (%d) out of bounds",__PRETTY_FUNCTION__,idx);
CHECK_FOR_MUTATION(array);
// 從內(nèi)存位置取出元素
return__CFArrayGetBucketAtIndex(array,idx)->_item;
}
// 返回查詢元素的地址
CF_INLINEstruct__CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRefarray,CFIndexidx){
switch(__CFArrayGetType(array)){
// 只允許兩種數(shù)組類型
// 不可變對(duì)應(yīng)普通線性結(jié)構(gòu)甫男，可變對(duì)應(yīng)雙端隊(duì)列
case__kCFArrayImmutable:
case__kCFArrayDeque:
// 取地址再加上索引偏移量，返回元素地址
return__CFArrayGetBucketsPtr(array)+idx;
}
returnNULL;
}
通過索引下標(biāo)查詢操作中验烧，CFArray仍然繼承了傳統(tǒng)數(shù)組的連續(xù)地址空間的性質(zhì)板驳，所以其時(shí)間仍然可保持在 O(1) 復(fù)雜度，十分高效碍拆。
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109voidCFArrayInsertValueAtIndex(CFMutableArrayRefarray,CFIndexidx,constvoid*value){
// 通過給定的 CFTypeID 來驗(yàn)證指定元素是否匹配 Core Foundation 橋接
CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID,void,(NSMutableArray *)array,insertObject:(id)valueatIndex:(NSUInteger)idx);
// 通過給定的 CFTypeID 來驗(yàn)證 Core Foundation 類型合法性
__CFGenericValidateType(array,__kCFArrayTypeID);
CFAssert1(__CFArrayGetType(array)!=__kCFArrayImmutable,__kCFLogAssertion,"%s(): array is immutable",__PRETTY_FUNCTION__);
CFAssert2(0idx&&idx__CFArrayGetCount(array),__kCFLogAssertion,"%s(): index (%d) out of bounds",__PRETTY_FUNCTION__,idx);
// 類型檢查
CHECK_FOR_MUTATION(array);
// 調(diào)用該函數(shù)進(jìn)行具體的數(shù)組變動(dòng)過程
_CFArrayReplaceValues(array,CFRangeMake(idx,0),&value,1);
}
// 這個(gè)函數(shù)沒有經(jīng)過 ObjC 的調(diào)度檢查若治，即 CF_OBJC_FUNCDISPATCHV 方法
// 所以為安全考慮，只能用在已經(jīng)進(jìn)行調(diào)度檢查的函數(shù)入口之后
void_CFArrayReplaceValues(CFMutableArrayRefarray,CFRangerange,constvoid**newValues,CFIndexnewCount){
// 進(jìn)一步類型檢查
CHECK_FOR_MUTATION(array);
// 加鎖操作感混，增加自旋鎖防止競爭
BEGIN_MUTATION(array);
// 聲明回調(diào)
constCFArrayCallBacks *cb;
// 偏移下標(biāo)端幼，元素總數(shù)，數(shù)組改變后元素總數(shù)
CFIndexidx,cnt,futureCnt;
constvoid**newv,*buffer[256];
// 獲取數(shù)組中元素個(gè)數(shù)
cnt=__CFArrayGetCount(array);
// 新數(shù)組元素總數(shù) = 原數(shù)組元素總數(shù) - 刪除的元素個(gè)數(shù) + 增加的元素個(gè)數(shù)
futureCnt=cnt-range.length+newCount;
CFAssert1(newCountfutureCnt,__kCFLogAssertion,"%s(): internal error 1",__PRETTY_FUNCTION__);
// 獲取數(shù)組中定義的回調(diào)方法
cb=__CFArrayGetCallBacks(array);
// 構(gòu)造分配釋放內(nèi)存抽象
CFAllocatorRefallocator=__CFGetAllocator(array);
// 需要的情況下持有新元素弧满，并為其分配一個(gè)臨時(shí)緩沖區(qū)
// 標(biāo)準(zhǔn)是新元素的個(gè)數(shù)是否超過256
if(NULL!=cb->retain&&!hasBeenFinalized(array)){
newv=(newCount256)?(constvoid**)buffer:(constvoid**)CFAllocatorAllocate(kCFAllocatorSystemDefault,newCount *sizeof(void*),0);
if(newv!=buffer&&__CFOASafe)__CFSetLastAllocationEventName(newv,"CFArray (temp)");
// 為新元素增加數(shù)據(jù)緩沖區(qū)
for(idx=0;idxnewCount;idx++){
newv[idx]=(void*)INVOKE_CALLBACK2(cb->retain,allocator,(void*)newValues[idx]);
}
}else{
newv=newValues;
}
// 數(shù)據(jù)抖動(dòng)量自加
array->_mutations++;
// 現(xiàn)在將一個(gè)數(shù)組的存儲(chǔ)區(qū)域分成了三個(gè)部分婆跑，每個(gè)部分都有可能為空
// A: 從索引下標(biāo)零的位置到小于 range.location 的區(qū)域
// B: 傳入的 range.location 區(qū)域
// C: 從 range.location + range.length 到數(shù)組末尾
// 需要注意的是，索引0的位置不一定位于可用存儲(chǔ)的最低位庭呜，當(dāng)變化位置新值數(shù)量與舊值數(shù)量不同時(shí)滑进，B區(qū)域需要先釋放再替換，然后A和C中的值根據(jù)情況進(jìn)行位移
if(0range.length){
// 正常釋放變化區(qū)域操作
__CFArrayReleaseValues(array,range,false);
}
// B 區(qū)現(xiàn)在為清空狀態(tài)募谎，需要重新填充數(shù)據(jù)
if(0){
// 此處隱藏了判斷條件和代碼扶关。
// 大概操作是排除其他的干擾項(xiàng)，例如 B 區(qū)數(shù)據(jù)未完全釋放等数冬。
}elseif(NULL==array->_store){
// 通過數(shù)據(jù)的首地址引用指針來判斷 B 區(qū)釋放
if(0){
// 此處隱藏了判斷條件和代碼
// 排除干擾條件节槐，例如 futureCnt 不合法等
}elseif(0futureCnt){
// 聲明一個(gè)雙端隊(duì)列對(duì)象
struct__CFArrayDeque *deque;
// 根據(jù)元素總數(shù)確定環(huán)狀緩沖區(qū)域可載元素總個(gè)數(shù)
CFIndexcapacity=__CFArrayDequeRoundUpCapacity(futureCnt);
// 根據(jù)元素個(gè)數(shù)確定空間分配大小
CFIndexsize=sizeof(struct__CFArrayDeque)+capacity *sizeof(struct__CFArrayBucket);
// 通過緩沖區(qū)構(gòu)造器來構(gòu)造存儲(chǔ)緩存
deque=(struct__CFArrayDeque *)CFAllocatorAllocate((allocator),size,isStrongMemory(array)?__kCFAllocatorGCScannedMemory:0);
if(__CFOASafe)__CFSetLastAllocationEventName(deque,"CFArray (store-deque)");
// 確定雙端隊(duì)列左值
deque->_leftIdx=(capacity-newCount)/2;
deque->_capacity=capacity;
__CFAssignWithWriteBarrier((void**)&array->_store,(void*)deque);
// 完成 B 區(qū)構(gòu)造，安全釋放數(shù)組
if(CF_IS_COLLECTABLE_ALLOCATOR(allocator))auto_zone_release(objc_collectableZone(),deque);
}
}else{// Deque
// 根據(jù) B 區(qū)元素變化吉执，重新定位 A 和 C 區(qū)元素存儲(chǔ)狀態(tài)
if(0){
}elseif(range.length!=newCount){
// 傳入 array 引用疯淫，最終根據(jù)變化使得數(shù)組更新A、B戳玫、C分區(qū)規(guī)則
__CFArrayRepositionDequeRegions(array,range,newCount);
}
}
// 將區(qū)域B的新變化拷貝到B區(qū)域
if(0newCount){
if(0){
}else{// Deque
// 訪問線性存儲(chǔ)區(qū)
struct__CFArrayDeque *deque=(struct__CFArrayDeque *)array->_store;
// 在原基礎(chǔ)上，增加一段緩存區(qū)域
struct__CFArrayBucket *raw_buckets=(struct__CFArrayBucket *)((uint8_t *)deque+sizeof(struct__CFArrayDeque));
// 更改B區(qū)域數(shù)據(jù)未斑，類似與 memcpy咕宿，但是有寫屏障(write barrier)，線程安全
objc_memmove_collectable(raw_buckets+deque->_leftIdx+range.location,newv,newCount *sizeof(struct__CFArrayBucket));
}
}
// 設(shè)置新的元素個(gè)數(shù)屬性
__CFArraySetCount(array,futureCnt);
// 釋放緩存區(qū)域
if(newv!=buffer&&newv!=newValues)CFAllocatorDeallocate(kCFAllocatorSystemDefault,newv);
// 解除線程安全保護(hù)
END_MUTATION(array);
}
在CFArray的插入元素操作中，可以很清楚的看出這是一個(gè)雙端隊(duì)列(dequeue)的插入元素操作府阀，而且是一種仿照 C++ STL 標(biāo)準(zhǔn)庫的存儲(chǔ)方式缆镣，緩沖區(qū)嵌套 map 表的靜態(tài)實(shí)現(xiàn)。用示意圖來說明一下數(shù)據(jù)結(jié)構(gòu)：
在 STL 中的 deque试浙，是使用的 map 表來記錄的映射關(guān)系董瞻，而在 Core Foundation 中，CFArray在保證這樣的二次映射關(guān)系的時(shí)候很直接地運(yùn)用了二階指針_store田巴。在修改元素的操作中钠糊，CFArray也略顯得暴力一些，先對(duì)數(shù)組進(jìn)行大塊的分區(qū)操作壹哺，再按照順序填充數(shù)據(jù)抄伍，組合成為一塊新的雙端隊(duì)列，例如在上圖中的雙端隊(duì)列中管宵，在下標(biāo)為 7 的元素之前增加一個(gè)值為100的元素：
根據(jù)索引下標(biāo)會(huì)找到指定部分的緩存區(qū)截珍，將其拿出并進(jìn)行重新構(gòu)造。構(gòu)造過程中或?qū)⑵鋭澐殖?A箩朴、B岗喉、C 三個(gè)區(qū)域，B 區(qū)域是修改部分炸庞。當(dāng)然如果不夠的話沈堡，系統(tǒng)會(huì)自己進(jìn)行緩存區(qū)的擴(kuò)容，即CFAllocatorRef官方提供的內(nèi)存分配/釋放策略燕雁。
CFAllocatorRef是 Core Foundation 中的分配和釋放內(nèi)存的策略诞丽。多數(shù)情況下，只需要用默認(rèn)分配器kCFAllocatorDefault拐格，等價(jià)于傳入NULL參數(shù)僧免，這用會(huì)用 Core Foundation 所謂的“常規(guī)方法”來分配和釋放內(nèi)存。這種方法可能會(huì)有變化捏浊，我們不應(yīng)該以來與任何特殊行為懂衩。用到特殊分配器的情況很少，下來是官方文檔中給出的標(biāo)準(zhǔn)分配器及其功能金踪。
KCFALLOCATORDEFAULT默認(rèn)分配器浊洞，與傳入NULL等價(jià)。
kCFAllocatorSystemDefault原始的默認(rèn)系統(tǒng)分配器胡岔。這個(gè)分配器用來應(yīng)對(duì)萬一用CFAllocatorSetDefault改變了默認(rèn)分配器的情況法希，很少用到。
kCFAllocatorMalloc調(diào)用malloc靶瘸、realloc和free苫亦。如果用malloc創(chuàng)建了內(nèi)存毛肋，那這個(gè)分配器對(duì)于釋放CFData和CFString就很有用。
kCFAllocatorMallocZone在默認(rèn)的malloc區(qū)域中創(chuàng)建和釋放內(nèi)存屋剑。在 Mac 上開啟了垃圾收集的話润匙，這個(gè)分配器會(huì)很有用，但在 iOS 中基本上沒什么用唉匾。
kCFAllocatorNull什么都不做孕讳。跟kCFAllocatorMalloc一樣，如果不想釋放內(nèi)存巍膘，這個(gè)分配器對(duì)于釋放CFData和CFString就很有用厂财。
KCFAllocatorUseContext只有CFAllocatorCreate函數(shù)用到。創(chuàng)建CFAllocator時(shí)典徘，系統(tǒng)需要分配內(nèi)存蟀苛。就像其他所有的Create方法，也需要一個(gè)分配器逮诲。這個(gè)特殊的分配器告訴CFAllocatorCreate用傳入的函數(shù)來分配CFAllocator帜平。
在_CFArrayReplaceValues方法中的最后一個(gè)判斷：
1
2if(newv!=buffer&&newv!=newValues)
CFAllocatorDeallocate(kCFAllocatorSystemDefault,newv);
會(huì)檢查一下緩存區(qū)的數(shù)量問題，如果數(shù)量過多會(huì)釋放掉多余的緩存區(qū)梅鹦。這是因?yàn)檫@個(gè)方法具有通用性裆甩，不僅僅可以使用在插入元素操作，在增加(CFArrayAppendValue)齐唆、替換(CFArrayReplaceValues)嗤栓、刪除(CFArrayRemoveValueAtIndex)操作均可使用。由于將數(shù)據(jù)結(jié)構(gòu)采取分塊管理箍邮，所以時(shí)間分?jǐn)傑运В瑥?fù)雜度大幅度降低。所以锭弊，我們看到CFArray的時(shí)間復(fù)雜度在查詢堪澎、增添元素操作中均有較高的水平。
而在NSMutableArray的實(shí)現(xiàn)中味滞，蘋果為了解決移動(dòng)端的小內(nèi)存特點(diǎn)樱蛤，使用CFArray中在兩端增加可擴(kuò)充的緩存區(qū)則會(huì)造成大量的浪費(fèi)。在NSMutableArray原理揭露一文中使用逆向的思路剑鞍，挖掘NSMutableArray的實(shí)現(xiàn)原理昨凡，其做法是使用環(huán)形緩沖區(qū)對(duì)緩存部分做到最大化的壓縮，這是蘋果針對(duì)于移動(dòng)設(shè)備的局限而提出的方案蚁署。
參考資料：
What is the data structure behind NSMutableArray?
1贊收藏評(píng)論
相關(guān)文章
可能感興趣的話題
實(shí)習(xí)加工作一年多便脊，有點(diǎn)亂，梳理梳理·1
大二妹子求助形用，不知道以后要干什么就轧，現(xiàn)在想走前端·6
美團(tuán)點(diǎn)評(píng)2017秋招筆試真題:進(jìn)出棧·1
