1.关键代码
关键代码如下，其中具体内容见代码注释部分。在注释文档中，以#数字开始的表示关键节点序号，后续实际分析时会使用到。
1.1 CFArrayRef 相关数据结构
// 保存数组元素的指针
struct __CFArrayBucket
{
const void *_item;
};
// 可变数组时使用的双端序列结构体
struct __CFArrayDeque
{
uintptr_t _leftIdx; //元素在deque中起始下标
uintptr_t _capacity; //数组容量，通常情况下是实际元素个数的2倍，最小为4
/* struct __CFArrayBucket buckets follow here */ // 元素容器
};
// CFArrayRef 结构体
struct __CFArray
{
CFRuntimeBase _base;
CFIndex _count; /* number of objects */ //实际元素个数
CFIndex _mutations; // 变化次数
int32_t _mutInProgress;
__strong void *_store; /* can be NULL when MutableDeque */
};
数据结构大概是这样的：
CFArray数据结构
1.2数组初始化数方法
// #1.初始化数组具体实现
static CFArrayRef __CFArrayInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFArrayCallBacks *callBacks) {
...
switch (__CFBitfieldGetValue(flags, 1, 0))
{
case __kCFArrayImmutable: //不可变数组
if (isWeakMemory(memory))
{ // if weak, don't scan
auto_zone_set_unscanned(objc_collectableZone(), memory);
}
if (__CFOASafe)
__CFSetLastAllocationEventName(memory, "CFArray (immutable)");
break;
case __kCFArrayDeque: //可变数组
if (__CFOASafe)
__CFSetLastAllocationEventName(memory, "CFArray (mutable-variable)");
((struct __CFArray *)memory)->_mutations = 1;
((struct __CFArray *)memory)->_mutInProgress = 0;
//#1.1初始化可变数组时，store为NULL
((struct __CFArray *)memory)->_store = NULL;
break;
}
...
}
1.3更新数组元素方法
// This function does no ObjC dispatch or argument checking;
// It should only be called from places where that dispatch and check has already been done, or NSCFArray
// #2 变动内部元素
void _CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount)
{
CHECK_FOR_MUTATION(array);
BEGIN_MUTATION(array); // 加锁
// #2.1 声明并初始化变量： idx, cnt: 当前元素数量, futureCnt: 更新后元素数量
const CFArrayCallBacks *cb;
CFIndex idx, cnt, futureCnt;
const void **newv, *buffer[256]; //声明 newv 数组、buffer 缓冲区
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); //获取分配器？
/* Retain new values if needed, possibly allocating a temporary buffer for them */
/* 如果有必要，retain有新的元素，并为其分配一个临时缓冲区 */
if (NULL != cb->retain && !hasBeenFinalized(array)) //如果retain存在
{
// newCount元素数量小于等于256，则使用256个长度的缓冲区， 否则使用newCount个长度的缓冲区
newv = (newCount <= 256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, newCount * sizeof(void *), 0); // GC OK
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++; //抖动量+1
/* Now, there are three regions of interest, each of which may be empty:
* A: the region from index 0 to one less than the range.location
* B: the region of the range
* C: the region from range.location + range.length to the end
* Note that index 0 is not necessarily at the lowest-address edge
* of the available storage. The values in region B need to get
* released, and the values in regions A and C (depending) need
* to get shifted if the number of new values is different from
* the length of the range being replaced.
*/
// 将数组的分为三部分
// A: 从下标0到range.location
// B: range部分，即从 range.location 到 range.location + range.length
// C: 下标从 range.location + range.length 到末尾
// | A | B | C |
// 0 range.location range.length end
if (0 < range.length)
{
__CFArrayReleaseValues(array, range, false); //释放数组中被替换的对象,即B部分
}
// region B elements are now "dead"
if (0)
{
}
// #2.2 如果 arrary->_store 为NULL, 则初始化store、deque（第一次对元素做操作时会进来）
else if (NULL == array->_store)
{
if (0)
{
}
else if (0 <= futureCnt)
{
struct __CFArrayDeque *deque; //如果store为空，声明一个双端队列
CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt); //确定容量大小， min(min(futureCnt * 2, long_max), 4), 最小为4
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);
// 释放
if (CF_IS_COLLECTABLE_ALLOCATOR(allocator))
auto_zone_release(objc_collectableZone(), deque); // GC: now safe to unroot the array body.
}
}
else
{ // Deque
// reposition regions A and C for new region B elements in gap
// #2.3 根据B区域元素，重新定位A、C区域
if (0)
{
}
else if (range.length != newCount)
{
__CFArrayRepositionDequeRegions(array, range, newCount);
}
}
// copy in new region B elements
// #2.4 将变动数据拷贝到B区域
if (0 < newCount)
{
if (0)
{
}
else
{ // Deque
struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
// raw_buckets指向deque中bucket队列头
struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque));
// 移动B objc_memmove_collectable(obj, oldObj, size): 把旧对象的内存复制到新对象
objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket));
}
}
// #2.5 设置新的元素个数
__CFArraySetCount(array, futureCnt);
// 释放newv缓冲区
if (newv != buffer && newv != newValues)
CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv);
// 解锁?
END_MUTATION(array);
}
在对数组进行操作时，会将数组分成A、B、C 三部分；
- A: 从下标0到range.location
- B: range部分，下标从 range.location 到 range.location + range.length
- C: 下标从 range.location + range.length 到末尾
/* Now, there are three regions of interest, each of which may be empty:
* A: the region from index 0 to one less than the range.location
* B: the region of the range
* C: the region from range.location + range.length to the end
* Note that index 0 is not necessarily at the lowest-address edge
* of the available storage. The values in region B need to get
* released, and the values in regions A and C (depending) need
* to get shifted if the number of new values is different from
* the length of the range being replaced.
*/
以向数组中"a"和"c"之间插入"c"为例子：
A、B、C 三部分划分.png
2.使用示例及流程分析
执行以下代码，并进行分析：
// 创建可变长度数组
CFMutableArrayRef mutableArray = CFArrayCreateMutable(NULL, 0, &kCFTypeArrayCallBacks);
// 插入"a"
CFArrayInsertValueAtIndex(mutableArray, 0, CFSTR("a"));
// 插入"b"
CFArrayInsertValueAtIndex(mutableArray, 1, CFSTR("b"));
2.1创建可变数组
CFMutableArrayRef mutableArray = CFArrayCreateMutable(NULL, 0, &kCFTypeArrayCallBacks);
内部调用顺序CFArrayCreateMutable --> __CFArrayCreateMutable0 --> __CFArrayInit
#1.1: 初始化可变数组时， _store为NULL
初始化
2.2 向可变数组中插入数据"a"
CFArrayInsertValueAtIndex(mutableArray, 0, CFSTR("a"));
当第一次插入元素“a”时：
#2.1:
range = (0, 0);
newCount = 1;
cnt = 0;
futurecnt = 1;
#2.2: 此时 array->_store 为NULL, 会初始化_store、deque
capacity = 4;
deque->_leftIdx = 1;
deque->capacity = 4;
...
deque = (struct __CFArrayDeque *)CFAllocatorAllocate((allocator), size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0);
__CFAssignWithWriteBarrier((void **)&array->_store, (void *)deque);
初始化_store、deque
#2.4: 移动B部分
使用objc_memmove_collectable(obj, oldObj, size) （把旧对象的内存复制到新对象） 方法将指向"a"的指针newv放到deque下标为1的位置。
// deque[1] = "a"
objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket));
deque[1] = "a"
#2.5: 更新元素个数，释放缓冲区等操作。
cnt = 1;
2.3数组中插入元素"b"
CFArrayInsertValueAtIndex(mutableArray, 0, CFSTR("b"));
#2.1:
range = (0,0);
newCount = 1;
cnt = 1;
futureCnt = 2;
#2.3:
调用 #3: __CFArrayRepositionDequeRegions方法 ,对 A、B、C 区域进行划分。
#3.1:
newCount = 1;
L = 1;
A = 0;
B = 0;
C = 1;
R = 2;
numNewElems = 1;
wiggle = 4;
#3.2: 空间紧凑或者不足的情况
#3.2.1: 创建一个更大的newDeque, 对buckets进行扩容操作
capacity = 12;
oldL = 1;
newL = 5;
oldC0 = 1;
newC0 = 6;
newDeque->_leftIdx = 5;
newDeque->_capacity = 12;
C > 0: queue[1] --> newQueue[6]
//移动C
objc_memmove_collectable(newBuckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket));
queue[1] --> newQueue[6]
#2.4: 移动B部分
// deque[5] = "b"
objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket));
move B
#2.5: 更新count属性, 释放缓冲区
array->count = 2
总结：
- 内部使用双端队列进行元素操作；
- 初始创建可变数组时，deque为null;
- deque 初始容量为
min(min(futureCnt * 2, long_max), 4), 最小为4， 最大为long_max。一般为元素实际个数的2倍。 - deque 扩容容量为：
min((futureCnt + 4) * 2, long_max)。
参考资料：
网友评论