CFArray源码解读

2020-11-19 本文已影响0人黄二瓜

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)。

参考资料：