在iOS开发中，NSArray是一个非常重要的数据结构。尤其是TableView中的数据缓存和更新，NSArray来缓存数据和修改显示的数据。在CoreFoundation中，CFArray和NSArray是一一对应的，这引起了笔者对CoreFoundation和Foundation类库中原生数据结构实现的兴趣，于是研究一下。CFArray的历史渊源NSArray和CFArray是Toll-FreeBridged，在opensource.apple.com，CFArray是开源的。这对我们的学习和研究更有帮助。伽蓝之道在做个人工具库的时候，研究过CFArray的历史渊源和实现方法。在阅读本文之前，可以参考一下前辈们的优秀博文。数组CFArray在2005年的这篇早期文章中首次介绍并测试了其性能水平。它比较了CFArray和STL中的Vector容器的性能。由于后者的实现可以理解为C中的数组封装，所以对性能图的大部分操作都是线性的。在CFArray的图片中，你会发现很多不同之处。从上面的分析可以看出，CFArray在插入head和tail时的效率几乎是恒定的，而中间元素的操作会突然从小数据的线性效率变成线性效率在某个阈值，这个跳跃可以'不由得灰头土脸的想到了Java8中的HashMap数据结构转换方式，在ObjC早期，CFArray是使用deque双端队列实现的，所以会表现出头尾操作高效，线性化的特点中间操作。当容量超过300000左右（实际应该是262140=2^18）时，时间复杂度急剧变化。源码中，阈值通过宏定义为__CF_MAX_BUCKETS_PER_DEQUE，具体代码可参见CF-550-CFArray.c（2011版）：(array);store=(CFStorageRef)array->_store;}可以看出，当数据超过阈值__CF_MAX_BUCKETS_PER_DEQUE时，数据结构会从CFArray转换为CFStorage。CFStorage是一种平衡二叉树结构。为了保持数组的顺序访问，Node的权重使用下标插入和旋转。具体见CFStorageInsertValues操作。具体代码可以查看CF-368.18-CFStorage.c。在CF-635.15-CFArray.c2011之后的版本中，CFArray取消了数据结构转换的功能。可能是为了防止大数据中二叉树构建的时间抖动问题，取消了这个特性。直接看数据结构的描述：struct__CFArrayDeque{uintptr_t_leftIdx;//从左开始的下标位置uintptr_t_capacity;//当前容量};struct__CFArray{CFRuntimeBase_base;CFIndex_count;//元素个数CFIndex_mutations;//元素抖动量int32_t_mutInProgress;__strongvoid*_店铺;};从命名可以看出，CFArray是由单个双端队列实现的，记录了一些容器信息。C语言数组的一些问题C语言中的数组会开辟一块连续的内存空间，用于数据的读写和存储操作。顺便说一下，数组和指针是不一样的。有一句话被很多教科书滥用：一块被malloc的内存空间就等于一个数组。这是错误的。最简单的解释就是指针需要申请一个指针区来存放（指向）一个空间的起始位置，数组（head）是直接访问一个空间的起始位置。另外，如果想了解更多，可以看ArepointersandarraysequivalentinC?这篇博文。C中数组最明显的缺点是在下标0处插入时，需要移动所有元素（即memmove()函数的原理）。同样，删除第一个元素时，在第一个元素前插入一个元素，也会造成O(n)复杂度的操作。但是数组往往是读写的容器，所以O(n)的操作会造成严重的时间开销。当前版本CFArray的部分实现细节在CF-855.17中，我们可以看到当前版本CFArray的实现。文档对CFArray的描述如下：CFArray实现了一个紧凑的容器，可以通过指针顺序访问。它的值可以通过整数键（索引下标）访问，范围从0到N-1，其中N是数组中值的个数。之所以称它为compact，是因为当容器删除或插入某个值时，内存空间不会留下空隙，访问顺序仍然按照原来的keyvalue值排列，这样有效的检索集合range总是在整数范围[0,N-1]内。因此，特定值的索引可能会随着其他元素插入数组或从数组中删除而改变。有两种类型的数组：在创建数组后不能在数组中添加或删除元素的不可变类型，以及可以在数组中添加或删除元素的可变类型。可变数组中的元素数量是有限的（或仅受CFArray外部约束的限制，例如可用内存空间的大小）。与所有CoreFoundation集合类型一样，数组将维护对其元素对象的强引用。为了进一步阐明CFArray的细节，我们来分析一下CFArray的几种操作方法：//通过下标查询元素值constvoid*CFArrayGetValueAtIndex(CFArrayRefarray,CFIndexidx){//该函数尚未开源//通过给定的CFTypeID验证指定元素是否匹配CoreFoundation桥接类CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID,constvoid*,(NSArray*)array,objectAtIndex:idx);//尚未开源//通过给定的CFTypeID验证CoreFoundation类型的有效性__CFGenericValidateType(array,__kCFArrayTypeID);CFAssert2(0idx&&idx__CFArrayGetCount(array),__kCFLogAssertion,"%s():index(%d)outofbounds",__PRETTY_FUNCTION__,idx);CHECK_FOR_MUTATION(array);//从内存位置获取元素return__CFArrayGetBucketAtIndex(array,idx)->_item;}//返回查询元素的地址CF_INLINEstruct__CFArrayBucket*__CFArrayGetBucketAtIndex(CFArrayRefarray,CFIndexidx){switch(__CFArrayGetType(array)){//只允许两种数组类型//Immutable对应普通线性结构，variable对应双端队列case__kCFArrayImmutable:case__kCFArrayDeque://获取地址加上索引偏移返回元素地址return__CFArrayGetBucketsPtr(array)+idx;}returnNULL;}在查询操作中通过索引下标，CFArray仍然继承了传统数组地址空间连续的性质，因此其时间仍然可以保持在O(1)的复杂度，非常高效。voidCFArrayInsertValueAtIndex(CFMutableArrayRefarray,CFIndexidx,constvoid*value){//通过给定的CFTypeID验证指定元素是否匹配CoreFoundation桥CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID,void,(NSMutableArray*)array,insertObject:(id)valueatIndex:(NSUInteger)idx);//通过给定的CFTypeID验证CoreFoundation类型的合法性__CFGenericValidateType(array,__kCFArrayTypeID);CFAssert1(__CFArrayGetType(array)!=__kCFArrayImmutable,__kCFLogAssertion,"%s():arrayisimmutable",__PRETTY_FUNCTION__);??CFAssert2(0idx&&idx__CFArrayGetCount(array),__kCFLogAssertion,"%s():index(%d)outofbounds",__PRETTY_FUNCTION__,idx);//类型检查CHECK_FOR_MUTATION(array);//调用此函数进行特定的数组变化过程_CFArrayReplaceValues(array,CFRangeMake(idx,0),&value,1);}//这个函数没有通过ObjC的调度检查，也就是CF_OBJC_FUNCDISPATCHV方法//所以为了安全起见，只能在已经sch的函数入口之后使用受骗了。void_CFArrayReplaceValues(CFMutableArrayRefarray,CFRangerange,constvoid**newValues,CFIndexnewCount){//进一步类型检查CHECK_FOR_MUTATION(array);//加锁操作，增加自旋锁防止竞争BEGIN_MUTATION(array);//声明回调constCFArrayCallBacks*cb;//偏移量下标，元素总数，数组变化后的元素总数CFIndexidx,cnt,futureCnt;constvoid**newv,*buffer[256];//获取数组元素个数cnt=__CFArrayGetCount(array);//新增数组元素总数=原数组元素总数-删除元素个数+新增元素个数futureCnt=cnt-range.length+newCount;CFAssert1(newCountfutureCnt,__kCFLogAssertion,"%s():internalerror1",__PRETTY_FUNCTION__);//获取数组中定义的回调方法cb=__CFArrayGetCallBacks(array);//构造分配释放内存抽象CFAllocatorRefallocator=__CFGetAllocator(array);//必要时持有新元素，并为其分配一个临时缓冲区Area//标准是新元素个数是否超过256if(NULL!=cb->retain&&!hasBeenFinalized(array)){newv=(newCount256)?(constvoid**)buffer:(constvoid**)CFAllocatorAllocate(kCFAllocatorSystemDefault,newCount*sizeof(void*),0);if(newv!=buffer&&__CFOASafe)__CFSetLastAllocationEventName(newv,"CFArray(temp)");//添加数据新元素缓冲区for(idx=0;idxnewCount;idx++){newv[idx]=(void*)INVOKE_CALLBACK2(cb->retain,allocator,(void*)newValues[idx]);}}else{newv=newValues;}//数据抖动量自动加上array->_mutations++;//现在一个数组的存储区域分为三部分，每部分都可能为空//A:from索引零位置小于range.locationarea//B:传入的range.location区域//C:从range.location+range.length到数组末尾//需要注意的是index0的位置不一定是最高的位置availablestorage，当改变位置的新值个数与旧值个数不同时，需要先释放区域B再替换，然后将A和C中的值根据情况if(0range.length){//正常释放变化的区域操作__CFArrayReleaseValues(array,range,false);}//区域B现在是空的，需要重新填充数据if(0){//这里隐藏了判断条件和代码//大概的操作是排除其他干扰项，比如B区数据没有完全放出等。}elseif(NULL==array->_store){//使用数据的首地址引用指针判断释放B区if(0){//这里隐藏判断条件和代码//排除干扰条件,如futureCntnotLegal等}elseif(0futureCnt){//声明一个双端队列对象struct__CFArrayDeque*deque;//根据总数确定环形缓冲区可以加载的元素总数ofelementsCFIndexcapacity=__CFArrayDequeRoundUpCapacity(futureCnt);//根据元素个数确定空间分配大小CFIndexsize=sizeof(struct__CFArrayDeque)+capacity*sizeof(struct__CFArrayBucket);//通过buffer构造函数构造存储缓存((allocator),size,isStrongMemory(array)?__kCFAllocatorGCScannedMemory:0);if(__CFOASafe)__CFSetLastAllocationEventName(deque,"CFArray(store-deque)");//判断双端队列左值deque->_leftIdx=(容量-新计数)/2;deque->_capacity=capacity;__CFAssignWithWriteBarrier((void**)&array->_store,(void*)deque);//完成zoneB的构建，安全释放arrayif(CF_IS_COLLECTABLE_ALLOCATOR(allocator))auto_zone_release(objc_collectableZone(),deque);}}else{//Deque//根据B区元素的变化，重新定位A区和C区元素的存储状态C分区规则__CFArrayRepositionDequeRegions(array,range,newCount);}}//将B区的新变化复制到B区if(0newCount){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，但是与写屏障（writebarrier），线程安全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插入元素的操作中，可以清楚的看到这是一个double向尾队插入元素（dequeue）的操作，是一种模仿C+的存储方式+STL标准库。buffer嵌套映射表的静态实现用示意图来说明数据结构：STL中的deque是map使用Table记录映射关系，而CoreFoundation中CFArray直接使用二阶指针_store来保证这样二级映射关系。在修改元素的操作上，CFArray也略显暴力。首先将数组划分成大块，然后按顺序填充数据，形成一个新的双端队列，比如上图中的双端队列，在下标为7的元素前添加一个值为100的元素：根据索引下标，找到指定部分的缓存区，取出并重构。在施工过程中，可分为A、B、C三个区域，B区域为改造部分。当然，如果不够，系统会自行扩展缓存区，即CFAllocatorRef官方提供的内存分配/释放策略。CFAllocatorRef是一种在CoreFoundation中分配和释放内存的策略。大多数时候，您只需要使用默认分配器kCFAllocatorDefault，这相当于将NULL作为参数传递，它使用CoreFoundation所谓的“正常方式”来分配和释放内存。此方法可能会发生变化，我们不应受制于任何特殊行为。很少使用特殊的分配器，官方文档中给出了标准的分配器及其功能。KCFALLOCATORDEFAULT默认分配器，相当于传递NULL。kCFAllocatorSystemDefault原始的默认系统分配器。如果默认分配器被CFAllocatorSetDefault更改并且很少使用，则使用此分配器。kCFAllocatorMalloc调用malloc、realloc和free。如果内存是用malloc创建的，这个分配器对于释放CFData和CFString很有用。kCFAllocatorMallocZone在默认malloc区域中创建和释放内存。这个分配器在打开垃圾回收的Mac上很有用，但在iOS上几乎没用。kCFAllocatorNull什么都不做。与kCFAllocatorMalloc一样，如果您不想释放内存，此分配器可用于释放CFData和CFString。KCFAllocatorUseContext仅由CFAllocatorCreate函数使用。当CFAllocator被创建时，系统需要分配内存。与所有其他Create方法一样，需要一个分配器。这个特殊的分配器告诉CFAllocatorCreate使用传递的函数来分配CFAllocator。_CFArrayReplaceValues方法中最后的判断：if(newv!=buffer&&newv!=newValues)CFAllocatorDeallocate(kCFAllocatorSystemDefault,newv);会检查缓冲区的数量，如果数量过多，就会释放多余的缓冲区。这是因为该方法用途广泛，不仅可以用于插入元素，还可以用于添加（CFArrayAppendValue）、替换（CFArrayReplaceValues）和删除（CFArrayRemoveValueAtIndex）。由于数据结构是以块为单位进行管理的，所以分配了时间，大大降低了复杂度。因此，我们看到CFArray的时间复杂度在查询和元素添加操作上具有比较高的水平。在NSMutableArray的实现中，为了解决移动端内存小的特点，使用CFArray在两端添加可扩展的缓存区会造成很大的浪费。在揭秘NSMutableArray原理一文中，我用逆向思维挖掘出了NSMutableArray的实现原理。方法是利用环形缓冲区最大限度地压缩缓存部分。这是苹果针对移动设备局限性的解决方案。参考资料：Let'sBuildNSMutableArrayhttp://t.cn/Rxs9e2gGNUStepNSArrayhttp://t.cn/RxsCzbjNSMutableArray背后的数据结构是什么？http://t.cn/RxsCvcGAppleSourceCode–CF-855.17http//t.cn/RxsCho3
