CFArray 的历史渊源及实现原理

if (__CF_MAX_BUCKETS_PER_DEQUE <= futureCnt) {
    // 创建 CFStorage 引用
    CFStorageRef store
    // 转换 CFArray 为 Storage
    __CFArrayConvertDequeToStore(array);
    store = (CFStorageRef)array->_store;
}

struct __CFArrayDeque {
    uintptr_t _leftIdx; // 自左开始下标位置
    uintptr_t _capacity; // 当前容量
};

struct __CFArray {
    CFRuntimeBase _base;
    CFIndex _count; // 元素个数
    CFIndex _mutations; // 元素抖动量
    int32_t _mutInProgress;
    __strong void *_store;
};

// 通过下标查询元素值
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;
}

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);
}

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