在 iOS 開發中，NSArray 是一個很重要的數據結構。尤其 TableView 中的數據緩存與更新， NSArray 來緩存數據以及對于顯示數據的修改操作。而在 Core Foundation 中 CFArray 與 NSArray 相互對應，這引起了筆者對 Core Foundation 和 Foundation 庫中的原生數據結構實現產生興趣，所以來研究一下。

CFArray 歷史淵源

NSArray 和 CFArray 是 Toll-Free Bridged 的，在 opensource.apple.com 中， CFArray 是開源的。這更有助于我們的學習與研究。在 Garan no Dou 大神之前在做個人工具庫的時候，曾經研究過 CFArray 的歷史淵源和實現手段，在閱讀此文之前可以參考一下前輩的優秀博文。

Array 這篇 2005 年的早期文獻中，最早介紹過 CFArray ，并且測試過其性能水平。它將 CFArray 和 STL 中的 Vector 容器進行了性能對比，由于后者的實現我們可以理解成是對 C 中的數組封裝，所以在性能圖上大多數操作都是線性的。而在 CFArray 的圖中，會發現很多不一樣的地方。 

上圖分析可以看出， CFArray 在頭插、尾插插入時候的效率近乎常數，而對于中間元素的操作會從小數據的線性效率在一個閥值上突然轉變成線性效率，而這個躍變灰不由得想起在 Java 8 當中的 HashMap 的數據結構轉變方式。

在 ObjC 的初期，CFArray 是使用 deque 雙端隊列 實現，所以會呈現出頭尾操作高效，而中間操作成線性的特點。在容量超過 300000 左右時(實際應該是 262140 = 2^18 )，時間復雜度發生陡變。在源代碼中，閥值被宏定義為 __CF_MAX_BUCKETS_PER_DEQUE ，具體代碼可以見 CF-550-CFArray.c (2011 年版本)：

if (__CF_MAX_BUCKETS_PER_DEQUE  futureCnt) { 
 
    // 創建 CFStorage 引用 
 
    CFStorageRef store 
 
    // 轉換 CFArray 為 Storage 
 
    __CFArrayConvertDequeToStore(array); 
 
    store = (CFStorageRef)array->_store; 
 
}  

可以看到，當數據超出閥值 __CF_MAX_BUCKETS_PER_DEQUE 的時候，會將數據結構從 CFArray 轉換成 CFStorage 。 CFStorage 是一個平衡二叉樹的結構，為了維護數組的順序訪問，將 Node 的權值使用下標完成插入和旋轉操作。具體的體現可以看 CFStorageInsertValues 操作。具體代碼可以查看 CF-368.18-CFStorage.c 。

在 2011 年以后的 CF-635.15-CFArray.c 版本中， CFArray 取消了數據結構轉換這一功能。或許是為了防止大數據時候二叉樹建樹的時間抖動問題從而取消了這一特性。直接來看下數據結構的描述：

struct __CFArrayDeque { 
 
    uintptr_t _leftIdx; // 自左開始下標位置 
 
    uintptr_t _capacity; // 當前容量 
 
}; 
 
struct __CFArray { 
 
    CFRuntimeBase _base; 
 
    CFIndex _count; // 元素個數 
 
    CFIndex _mutations; // 元素抖動量 
 
    int32_t _mutInProgress; 
 
    __strong void *_store; 
 
};  

從命名上可以看出 CFArray 由單一的雙端隊列進行實現，而且記錄了一些容器信息。

C 數組的一些問題

C 語言中的數組，會開辟一段連續的內存空間來進行數據的讀寫、存儲操作。另外說一句，數組和指針并不相同。有一種被很多教材書籍上濫用的說法：一塊被 malloc 過的內存空間等于一個數組。這是錯誤的。最簡單的解釋，指針需要申請一個指針區域來存儲(指向)一塊空間的起始位置，而數組(的頭部)是對一塊空間起始位置的直接訪問。另外想了解更多可以看 Are pointers and arrays equivalent in C? 這篇博文。

C 中的數組最顯著的缺點就是，在下標 0 處插入時，需要移動所有的元素(即 memmove() 函數的原理)。類似的，當刪除***個元素、在***個元素前插入一個元素也會造成 O(n)復雜度的操作 。然而數組是常讀寫的容器，所以 O(n) 的操作會造成很嚴重的時間開銷。

當前版本中 CFArray 的部分實現細節

在 CF-855.17 中，我們可以看到當前版本的 CFArray 的實現。文檔中對 CFArray 有如下的描述：

CFArray 實現了一個可被指針順序訪問的緊湊容器。其值可通過整數鍵(索引下標)進行訪問，范圍從 0 至 N-1，其中 N 是數組中值的數量。稱其緊湊 (compact) 的原因是該容器進行刪除或插入某個值的時候，不會再內存空間中留下間隙，訪問順序仍舊按照原有鍵值數值大小排列，使得有效檢索集合范圍總是在整數范圍 [0, N-1] 之中。因此，特定值的下標可能會隨著其他元素插入至數組或被刪除時而改變。

數組有兩種類型：不可變(immutable) 類型在創建數組之后，不能向其添加或刪除元素，而 可變(mutable) 類型可以添加或從中刪除元素。可變數組的元素數量***制(或者稱只受 CFArray 外部的約束限制，例如可用內存空間大小)。與所有的 CoreFoundation 集合類型同理，數組將保持與元素對象的強引用關系。

為了進一步弄清 CFArray 的細節，我們來分析一下 CFArray 的幾個操作方法：

// 通過下標查詢元素值 
 
const void *CFArrayGetValueAtIndex(CFArrayRef array, CFIndex idx) { 
 
    // 這個函數尚未開源 
 
    // 通過給定的 CFTypeID 來驗證指定元素是否匹配 Core Foundation 橋接類 
 
    CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID, const void *, (NSArray *)array, objectAtIndex:idx); 
 
    // 尚未開源 
 
    // 通過給定的 CFTypeID 來驗證 Core Foundation 類型合法性 
 
    __CFGenericValidateType(array, __kCFArrayTypeID); 
 
    CFAssert2(0  idx && idx  __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx); 
 
    CHECK_FOR_MUTATION(array); 
 
    // 從內存位置取出元素 
 
    return __CFArrayGetBucketAtIndex(array, idx)->_item; 
 
} 
 
// 返回查詢元素的地址 
 
CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRef array, CFIndex idx) { 
 
    switch (__CFArrayGetType(array)) { 
 
    // 只允許兩種數組類型 
 
    // 不可變對應普通線性結構，可變對應雙端隊列 
 
    case __kCFArrayImmutable: 
 
    case __kCFArrayDeque: 
 
    // 取地址再加上索引偏移量，返回元素地址 
 
return __CFArrayGetBucketsPtr(array) + idx; 
 
    } 
 
    return NULL; 
 
}  

通過索引下標查詢操作中，CFArray 仍然繼承了傳統數組的連續地址空間的性質，所以其時間仍然可保持在 O(1) 復雜度，十分高效。

void CFArrayInsertValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) { 
 
    // 通過給定的 CFTypeID 來驗證指定元素是否匹配 Core Foundation 橋接 
 
    CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID, void, (NSMutableArray *)array, insertObject:(id)value atIndex:(NSUInteger)idx); 
 
    // 通過給定的 CFTypeID 來驗證 Core Foundation 類型合法性 
 
    __CFGenericValidateType(array, __kCFArrayTypeID); 
 
    CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); 
 
    CFAssert2(0  idx && idx  __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx); 
 
    // 類型檢查 
 
    CHECK_FOR_MUTATION(array); 
 
    // 調用該函數進行具體的數組變動過程 
 
    _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1); 
 
} 
 
// 這個函數沒有經過 ObjC 的調度檢查，即 CF_OBJC_FUNCDISPATCHV 方法 
 
// 所以為安全考慮，只能用在已經進行調度檢查的函數入口之后 
 
void _CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) { 
 
    // 進一步類型檢查 
 
    CHECK_FOR_MUTATION(array); 
 
    // 加鎖操作，增加自旋鎖防止競爭 
 
    BEGIN_MUTATION(array); 
 
    // 聲明回調 
 
    const CFArrayCallBacks *cb; 
 
    // 偏移下標，元素總數，數組改變后元素總數 
 
    CFIndex idx, cnt, futureCnt; 
 
    const void **newv, *buffer[256]; 
 
    // 獲取數組中元素個數 
 
    cnt = __CFArrayGetCount(array); 
 
    // 新數組元素總數 = 原數組元素總數 - 刪除的元素個數 + 增加的元素個數 
 
    futureCnt = cnt - range.length + newCount; 
 
    CFAssert1(newCount  futureCnt, __kCFLogAssertion, "%s(): internal error 1", __PRETTY_FUNCTION__); 
 
    // 獲取數組中定義的回調方法 
 
    cb = __CFArrayGetCallBacks(array); 
 
    // 構造分配釋放內存抽象 
 
    CFAllocatorRef allocator = __CFGetAllocator(array); 
 
    // 需要的情況下持有新元素，并為其分配一個臨時緩沖區 
 
    // 標準是新元素的個數是否超過256 
 
    if (NULL != cb->retain && !hasBeenFinalized(array)) { 
 
newv = (newCount  256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, newCount * sizeof(void *), 0); 
 
if (newv != buffer && __CFOASafe) __CFSetLastAllocationEventName(newv, "CFArray (temp)"); 
 
// 為新元素增加數據緩沖區 
 
for (idx = 0; idx  newCount; idx++) { 
 
    newv[idx] = (void *)INVOKE_CALLBACK2(cb->retain, allocator, (void *)newValues[idx]); 
 
} 
 
    } else { 
 
newv = newValues; 
 
    } 
 
    // 數據抖動量自加 
 
    array->_mutations++; 
 
    // 現在將一個數組的存儲區域分成了三個部分，每個部分都有可能為空 
 
    // A: 從索引下標零的位置到小于 range.location 的區域 
 
    // B: 傳入的 range.location 區域 
 
    // C: 從 range.location + range.length 到數組末尾 
 
    // 需要注意的是，索引0的位置不一定位于可用存儲的***位，當變化位置新值數量與舊值數量不同時，B區域需要先釋放再替換，然后A和C中的值根據情況進行位移 
 
    if (0  range.length) { 
 
// 正常釋放變化區域操作 
 
__CFArrayReleaseValues(array, range, false); 
 
    } 
 
    // B 區現在為清空狀態，需要重新填充數據 
 
    if (0) { 
 
     // 此處隱藏了判斷條件和代碼。 
 
     // 大概操作是排除其他的干擾項，例如 B 區數據未完全釋放等。 
 
    } else if (NULL == array->_store) { 
 
// 通過數據的首地址引用指針來判斷 B 區釋放 
 
if (0) { 
 
// 此處隱藏了判斷條件和代碼 
 
// 排除干擾條件，例如 futureCnt 不合法等 
 
} else if (0  futureCnt) { 
 
    // 聲明一個雙端隊列對象 
 
    struct __CFArrayDeque *deque; 
 
    // 根據元素總數確定環狀緩沖區域可載元素總個數 
 
    CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt); 
 
    // 根據元素個數確定空間分配大小 
 
    CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); 
 
    // 通過緩沖區構造器來構造存儲緩存 
 
    deque = (struct __CFArrayDeque *)CFAllocatorAllocate((allocator), size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0); 
 
    if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)"); 
 
    // 確定雙端隊列左值 
 
    deque->_leftIdx = (capacity - newCount) / 2; 
 
    deque->_capacity = capacity; 
 
    __CFAssignWithWriteBarrier((void **)&array->_store, (void *)deque); 
 
    // 完成 B 區構造，安全釋放數組 
 
            if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) auto_zone_release(objc_collectableZone(), deque); 
 
} 
 
    } else {    // Deque 
 
// 根據 B 區元素變化，重新定位 A 和 C 區元素存儲狀態 
 
if (0) { 
 
} else if (range.length != newCount) { 
 
    // 傳入 array 引用，最終根據變化使得數組更新A、B、C分區規則 
 
    __CFArrayRepositionDequeRegions(array, range, newCount); 
 
} 
 
    } 
 
    // 將區域B的新變化拷貝到B區域 
 
    if (0  newCount) { 
 
if (0) { 
 
} else {    // Deque 
 
    // 訪問線性存儲區 
 
    struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store; 
 
    // 在原基礎上，增加一段緩存區域 
 
    struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); 
 
    // 更改B區域數據，類似與 memcpy，但是有寫屏障(write barrier)，線程安全 
 
    objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket)); 
 
} 
 
    } 
 
    // 設置新的元素個數屬性 
 
    __CFArraySetCount(array, futureCnt); 
 
    // 釋放緩存區域 
 
    if (newv != buffer && newv != newValues) CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv); 
 
    // 解除線程安全保護 
 
    END_MUTATION(array); 
 
}  

在 CFArray 的插入元素操作中，可以很清楚的看出這是一個雙端隊列(dequeue)的插入元素操作，而且是一種仿照 C++ STL 標準庫的存儲方式，緩沖區嵌套 map 表的靜態實現。用示意圖來說明一下數據結構： 

在 STL 中的 deque，是使用的 map 表來記錄的映射關系，而在 Core Foundation 中，CFArray 在保證這樣的二次映射關系的時候很直接地運用了二階指針 _store。在修改元素的操作中，CFArray 也略顯得暴力一些，先對數組進行大塊的分區操作，再按照順序填充數據，組合成為一塊新的雙端隊列，例如在上圖中的雙端隊列中，在下標為 7 的元素之前增加一個值為 100 的元素： 

根據索引下標會找到指定部分的緩存區，將其拿出并進行重新構造。構造過程中或將其劃分成 A、B、C 三個區域，B 區域是修改部分。當然如果不夠的話，系統會自己進行緩存區的擴容，即 CFAllocatorRef 官方提供的內存分配/釋放策略。

CFAllocatorRef 是 Core Foundation 中的分配和釋放內存的策略。多數情況下，只需要用默認分配器 kCFAllocatorDefault ，等價于傳入 NULL 參數，這用會用 Core Foundation 所謂的“常規方法”來分配和釋放內存。這種方法可能會有變化，我們不應該以來與任何特殊行為。用到特殊分配器的情況很少，下來是官方文檔中給出的標準分配器及其功能。 

在 _CFArrayReplaceValues 方法中的***一個判斷：

if (newv != buffer && newv != newValues) 
 
CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv); 

會檢查一下緩存區的數量問題，如果數量過多會釋放掉多余的緩存區。這是因為這個方法具有通用性，不僅僅可以使用在插入元素操作，在增加(CFArrayAppendValue)、替換(CFArrayReplaceValues)、刪除(CFArrayRemoveValueAtIndex)操作均可使用。由于將數據結構采取分塊管理，所以時間分攤，復雜度大幅度降低。所以，我們看到 CFArray 的時間復雜度在查詢、增添元素操作中均有較高的水平。

而在 NSMutableArray 的實現中，蘋果為了解決移動端的小內存特點，使用 CFArray 中在兩端增加可擴充的緩存區則會造成大量的浪費。在 NSMutableArray原理揭露 一文中使用逆向的思路，挖掘 NSMutableArray 的實現原理，其做法是使用環形緩沖區對緩存部分做到***化的壓縮，這是蘋果針對于移動設備的局限而提出的方案。

參考資料：

• Let’s Build NSMutableArray

http://t.cn/Rxs9e2g

• GNUStep · NSArray

http://t.cn/RxsCzbj

• What is the data structure behind NSMutableArray?

http://t.cn/RxsCvcG

• Apple Source Code – CF-855.17

http://t.cn/RxsCho3