X-Git-Url: https://git.saurik.com/apple/cf.git/blobdiff_plain/47a9ab1f151d80a00a045f81937ddac81c51a463..bd5b749cf7786ae858ab372fc8f64179736c6515:/Collections.subproj/CFArray.c diff --git a/Collections.subproj/CFArray.c b/Collections.subproj/CFArray.c deleted file mode 100644 index f741077..0000000 --- a/Collections.subproj/CFArray.c +++ /dev/null @@ -1,1199 +0,0 @@ -/* - * Copyright (c) 2005 Apple Computer, Inc. All rights reserved. - * - * @APPLE_LICENSE_HEADER_START@ - * - * This file contains Original Code and/or Modifications of Original Code - * as defined in and that are subject to the Apple Public Source License - * Version 2.0 (the 'License'). You may not use this file except in - * compliance with the License. Please obtain a copy of the License at - * http://www.opensource.apple.com/apsl/ and read it before using this - * file. - * - * The Original Code and all software distributed under the License are - * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER - * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, - * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. - * Please see the License for the specific language governing rights and - * limitations under the License. - * - * @APPLE_LICENSE_HEADER_END@ - */ -/* CFArray.c - Copyright 1998-2002, Apple, Inc. All rights reserved. - Responsibility: Christopher Kane -*/ - -#include -#include "CFStorage.h" -#include "CFUtilitiesPriv.h" -#include "CFInternal.h" -#include - -const CFArrayCallBacks kCFTypeArrayCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual}; -static const CFArrayCallBacks __kCFNullArrayCallBacks = {0, NULL, NULL, NULL, NULL}; - -struct __CFArrayBucket { - const void *_item; -}; - -struct __CFArrayImmutable { - CFRuntimeBase _base; - CFIndex _count; /* number of objects */ -}; - -struct __CFArrayFixedMutable { - CFRuntimeBase _base; - CFIndex _count; /* number of objects */ - CFIndex _capacity; /* maximum number of objects */ -}; - -enum { - __CF_MAX_BUCKETS_PER_DEQUE = 262140 -}; - -CF_INLINE CFIndex __CFArrayDequeRoundUpCapacity(CFIndex capacity) { - if (capacity < 4) return 4; - return __CFMin((1 << (CFLog2(capacity) + 1)), __CF_MAX_BUCKETS_PER_DEQUE); -} - -struct __CFArrayDeque { - uint32_t _leftIdx; - uint32_t _capacity; - int32_t _bias; - /* struct __CFArrayBucket buckets follow here */ -}; - -struct __CFArrayMutable { - CFRuntimeBase _base; - CFIndex _count; /* number of objects */ - void *_store; /* can be NULL when MutableDeque */ -}; - -/* convenience for debugging. */ -struct __CFArray { - CFRuntimeBase _base; - CFIndex _count; /* number of objects */ - union { - CFIndex _capacity; /* maximum number of objects */ - void *_store; /* can be NULL when MutableDeque */ - }; -}; - -/* Flag bits */ -enum { /* Bits 0-1 */ - __kCFArrayImmutable = 0, - __kCFArrayFixedMutable = 1, - __kCFArrayMutableDeque = 2, - __kCFArrayMutableStore = 3 -}; - -enum { /* Bits 2-3 */ - __kCFArrayHasNullCallBacks = 0, - __kCFArrayHasCFTypeCallBacks = 1, - __kCFArrayHasCustomCallBacks = 3 /* callbacks are at end of header */ -}; - -/* Bits 4-5 are used by GC */ - -static bool isStrongMemory(CFTypeRef collection) { - return ! __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_info, 4, 4); -} - -static bool needsRestore(CFTypeRef collection) { - return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_info, 5, 5); -} - - -CF_INLINE CFIndex __CFArrayGetType(CFArrayRef array) { - return __CFBitfieldGetValue(((const CFRuntimeBase *)array)->_info, 1, 0); -} - -CF_INLINE CFIndex __CFArrayGetSizeOfType(CFIndex t) { - CFIndex size = 0; - switch (__CFBitfieldGetValue(t, 1, 0)) { - case __kCFArrayImmutable: - size += sizeof(struct __CFArrayImmutable); - break; - case __kCFArrayFixedMutable: - size += sizeof(struct __CFArrayFixedMutable); - break; - case __kCFArrayMutableDeque: - case __kCFArrayMutableStore: - size += sizeof(struct __CFArrayMutable); - break; - } - if (__CFBitfieldGetValue(t, 3, 2) == __kCFArrayHasCustomCallBacks) { - size += sizeof(CFArrayCallBacks); - } - return size; -} - -CF_INLINE CFIndex __CFArrayGetCount(CFArrayRef array) { - return ((struct __CFArrayImmutable *)array)->_count; -} - -CF_INLINE void __CFArraySetCount(CFArrayRef array, CFIndex v) { - ((struct __CFArrayImmutable *)array)->_count = v; -} - -/* Only applies to immutable, fixed-mutable, and mutable-deque-using arrays; - * Returns the bucket holding the left-most real value in the latter case. */ -CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketsPtr(CFArrayRef array) { - switch (__CFArrayGetType(array)) { - case __kCFArrayImmutable: - case __kCFArrayFixedMutable: - return (struct __CFArrayBucket *)((uint8_t *)array + __CFArrayGetSizeOfType(((CFRuntimeBase *)array)->_info)); - case __kCFArrayMutableDeque: { - struct __CFArrayDeque *deque = ((struct __CFArrayMutable *)array)->_store; - return (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque) + deque->_leftIdx * sizeof(struct __CFArrayBucket)); - } - } - return NULL; -} - -/* This shouldn't be called if the array count is 0. */ -CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRef array, CFIndex idx) { - switch (__CFArrayGetType(array)) { - case __kCFArrayImmutable: - case __kCFArrayFixedMutable: - case __kCFArrayMutableDeque: - return __CFArrayGetBucketsPtr(array) + idx; - case __kCFArrayMutableStore: { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - return (struct __CFArrayBucket *)CFStorageGetValueAtIndex(store, idx, NULL); - } - } - return NULL; -} - -CF_INLINE CFArrayCallBacks *__CFArrayGetCallBacks(CFArrayRef array) { - CFArrayCallBacks *result = NULL; - switch (__CFBitfieldGetValue(((const CFRuntimeBase *)array)->_info, 3, 2)) { - case __kCFArrayHasNullCallBacks: - return (CFArrayCallBacks *)&__kCFNullArrayCallBacks; - case __kCFArrayHasCFTypeCallBacks: - return (CFArrayCallBacks *)&kCFTypeArrayCallBacks; - case __kCFArrayHasCustomCallBacks: - break; - } - switch (__CFArrayGetType(array)) { - case __kCFArrayImmutable: - result = (CFArrayCallBacks *)((uint8_t *)array + sizeof(struct __CFArrayImmutable)); - break; - case __kCFArrayFixedMutable: - result = (CFArrayCallBacks *)((uint8_t *)array + sizeof(struct __CFArrayFixedMutable)); - break; - case __kCFArrayMutableDeque: - case __kCFArrayMutableStore: - result = (CFArrayCallBacks *)((uint8_t *)array + sizeof(struct __CFArrayMutable)); - break; - } - return result; -} - -CF_INLINE bool __CFArrayCallBacksMatchNull(const CFArrayCallBacks *c) { - return (NULL == c || - (c->retain == __kCFNullArrayCallBacks.retain && - c->release == __kCFNullArrayCallBacks.release && - c->copyDescription == __kCFNullArrayCallBacks.copyDescription && - c->equal == __kCFNullArrayCallBacks.equal)); -} - -CF_INLINE bool __CFArrayCallBacksMatchCFType(const CFArrayCallBacks *c) { - return (&kCFTypeArrayCallBacks == c || - (c->retain == kCFTypeArrayCallBacks.retain && - c->release == kCFTypeArrayCallBacks.release && - c->copyDescription == kCFTypeArrayCallBacks.copyDescription && - c->equal == kCFTypeArrayCallBacks.equal)); -} - -struct _releaseContext { - void (*release)(CFAllocatorRef, const void *); - CFAllocatorRef allocator; -}; - -static void __CFArrayStorageRelease(const void *itemptr, void *context) { - struct _releaseContext *rc = (struct _releaseContext *)context; - INVOKE_CALLBACK2(rc->release, rc->allocator, *(const void **)itemptr); - *(const void **)itemptr = NULL; // GC: clear item to break strong reference. -} - -static void __CFArrayReleaseValues(CFArrayRef array, CFRange range, bool releaseStorageIfPossible) { - const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array); - CFAllocatorRef allocator; - CFIndex idx; - switch (__CFArrayGetType(array)) { - case __kCFArrayImmutable: - case __kCFArrayFixedMutable: - if (NULL != cb->release && 0 < range.length) { - struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(array); - allocator = __CFGetAllocator(array); - for (idx = 0; idx < range.length; idx++) { - INVOKE_CALLBACK2(cb->release, allocator, buckets[idx + range.location]._item); - buckets[idx + range.location]._item = NULL; // GC: break strong reference. - } - } - break; - case __kCFArrayMutableDeque: { - struct __CFArrayDeque *deque = ((struct __CFArrayMutable *)array)->_store; - if (0 < range.length && NULL != deque) { - struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(array); - if (NULL != cb->release) { - allocator = __CFGetAllocator(array); - for (idx = 0; idx < range.length; idx++) { - INVOKE_CALLBACK2(cb->release, allocator, buckets[idx + range.location]._item); - buckets[idx + range.location]._item = NULL; // GC: break strong reference. - } - } else { - for (idx = 0; idx < range.length; idx++) { - buckets[idx + range.location]._item = NULL; // GC: break strong reference. - } - } - } - if (releaseStorageIfPossible && 0 == range.location && __CFArrayGetCount(array) == range.length) { - allocator = __CFGetAllocator(array); - if (NULL != deque) _CFAllocatorDeallocateGC(allocator, deque); - ((struct __CFArrayMutable *)array)->_count = 0; // GC: _count == 0 ==> _store == NULL. - ((struct __CFArrayMutable *)array)->_store = NULL; - } - break; - } - case __kCFArrayMutableStore: { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - if (NULL != cb->release && 0 < range.length) { - struct _releaseContext context; - allocator = __CFGetAllocator(array); - context.release = cb->release; - context.allocator = allocator; - CFStorageApplyFunction(store, range, __CFArrayStorageRelease, &context); - } - if (releaseStorageIfPossible && 0 == range.location && __CFArrayGetCount(array) == range.length) { - CFRelease(store); - ((struct __CFArrayMutable *)array)->_count = 0; // GC: _count == 0 ==> _store == NULL. - ((struct __CFArrayMutable *)array)->_store = NULL; - __CFBitfieldSetValue(((CFRuntimeBase *)array)->_info, 1, 0, __kCFArrayMutableDeque); - } - break; - } - } -} - -CF_INLINE void __CFArrayValidateRange(CFArrayRef array, CFRange range, const char *func) { -#if defined(DEBUG) - CFAssert3(0 <= range.location && range.location <= CFArrayGetCount(array), __kCFLogAssertion, "%s(): range.location index (%d) out of bounds (0, %d)", func, range.location, CFArrayGetCount(array)); - CFAssert2(0 <= range.length, __kCFLogAssertion, "%s(): range.length (%d) cannot be less than zero", func, range.length); - CFAssert3(range.location + range.length <= CFArrayGetCount(array), __kCFLogAssertion, "%s(): ending index (%d) out of bounds (0, %d)", func, range.location + range.length, CFArrayGetCount(array)); -#endif -} - -static bool __CFArrayEqual(CFTypeRef cf1, CFTypeRef cf2) { - CFArrayRef array1 = (CFArrayRef)cf1; - CFArrayRef array2 = (CFArrayRef)cf2; - const CFArrayCallBacks *cb1, *cb2; - CFIndex idx, cnt; - if (array1 == array2) return true; - cnt = __CFArrayGetCount(array1); - if (cnt != __CFArrayGetCount(array2)) return false; - cb1 = __CFArrayGetCallBacks(array1); - cb2 = __CFArrayGetCallBacks(array2); - if (cb1->equal != cb2->equal) return false; - if (0 == cnt) return true; /* after function comparison! */ - for (idx = 0; idx < cnt; idx++) { - const void *val1 = __CFArrayGetBucketAtIndex(array1, idx)->_item; - const void *val2 = __CFArrayGetBucketAtIndex(array2, idx)->_item; - if (val1 != val2 && cb1->equal && !INVOKE_CALLBACK2(cb1->equal, val1, val2)) return false; - } - return true; -} - -static CFHashCode __CFArrayHash(CFTypeRef cf) { - CFArrayRef array = (CFArrayRef)cf; - return __CFArrayGetCount(array); -} - -static CFStringRef __CFArrayCopyDescription(CFTypeRef cf) { - CFArrayRef array = (CFArrayRef)cf; - CFMutableStringRef result; - const CFArrayCallBacks *cb; - CFAllocatorRef allocator; - CFIndex idx, cnt; - cnt = __CFArrayGetCount(array); - allocator = CFGetAllocator(array); - result = CFStringCreateMutable(allocator, 0); - switch (__CFArrayGetType(array)) { - case __kCFArrayImmutable: - CFStringAppendFormat(result, NULL, CFSTR("{type = immutable, count = %u, values = (\n"), cf, allocator, cnt); - break; - case __kCFArrayFixedMutable: - CFStringAppendFormat(result, NULL, CFSTR("{type = fixed-mutable, count = %u, capacity = %u, values = (\n"), cf, allocator, cnt, ((struct __CFArrayFixedMutable *)array)->_capacity); - break; - case __kCFArrayMutableDeque: - CFStringAppendFormat(result, NULL, CFSTR("{type = mutable-small, count = %u, values = (\n"), cf, allocator, cnt); - break; - case __kCFArrayMutableStore: - CFStringAppendFormat(result, NULL, CFSTR("{type = mutable-large, count = %u, values = (\n"), cf, allocator, cnt); - break; - } - cb = __CFArrayGetCallBacks(array); - for (idx = 0; idx < cnt; idx++) { - CFStringRef desc = NULL; - const void *val = __CFArrayGetBucketAtIndex(array, idx)->_item; - if (NULL != cb->copyDescription) { - desc = (CFStringRef)INVOKE_CALLBACK1(cb->copyDescription, val); - } - if (NULL != desc) { - CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, desc); - CFRelease(desc); - } else { - CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, val); - } - } - CFStringAppend(result, CFSTR(")}")); - return result; -} - -static void __CFArrayDeallocate(CFTypeRef cf) { - CFArrayRef array = (CFArrayRef)cf; - // Under GC, keep contents alive when we know we can, either standard callbacks or NULL - // if (__CFBitfieldGetValue(cf->info, 5, 4)) return; // bits only ever set under GC - CFAllocatorRef allocator = __CFGetAllocator(array); - if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { - const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array); - if (cb->retain == NULL && cb->release == NULL) - return; // XXX_PCB keep array intact during finalization. - } - __CFArrayReleaseValues(array, CFRangeMake(0, __CFArrayGetCount(array)), true); -} - -static CFTypeID __kCFArrayTypeID = _kCFRuntimeNotATypeID; - -static const CFRuntimeClass __CFArrayClass = { - _kCFRuntimeScannedObject, - "CFArray", - NULL, // init - NULL, // copy - __CFArrayDeallocate, - (void *)__CFArrayEqual, - __CFArrayHash, - NULL, // - __CFArrayCopyDescription -}; - -__private_extern__ void __CFArrayInitialize(void) { - __kCFArrayTypeID = _CFRuntimeRegisterClass(&__CFArrayClass); -} - -CFTypeID CFArrayGetTypeID(void) { - return __kCFArrayTypeID; -} - -static CFArrayRef __CFArrayInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFArrayCallBacks *callBacks) { - struct __CFArrayImmutable *memory; - UInt32 size; - CFArrayCallBacks nonRetainingCallbacks; - __CFBitfieldSetValue(flags, 31, 2, 0); - if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { - if (!callBacks || (callBacks->retain == NULL && callBacks->release == NULL)) { - __CFBitfieldSetValue(flags, 4, 4, 1); // setWeak - } - else { - if (callBacks->retain == __CFTypeCollectionRetain && callBacks->release == __CFTypeCollectionRelease) { - nonRetainingCallbacks = *callBacks; - nonRetainingCallbacks.retain = NULL; - nonRetainingCallbacks.release = NULL; - callBacks = &nonRetainingCallbacks; - __CFBitfieldSetValue(flags, 5, 5, 1); // setNeedsRestore - } - } - } - if (__CFArrayCallBacksMatchNull(callBacks)) { - __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasNullCallBacks); - } else if (__CFArrayCallBacksMatchCFType(callBacks)) { - __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasCFTypeCallBacks); - } else { - __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasCustomCallBacks); - } - size = __CFArrayGetSizeOfType(flags) - sizeof(CFRuntimeBase); - switch (__CFBitfieldGetValue(flags, 1, 0)) { - case __kCFArrayImmutable: - case __kCFArrayFixedMutable: - size += capacity * sizeof(struct __CFArrayBucket); - break; - case __kCFArrayMutableDeque: - case __kCFArrayMutableStore: - break; - } - memory = (struct __CFArrayImmutable *)_CFRuntimeCreateInstance(allocator, __kCFArrayTypeID, size, NULL); - if (NULL == memory) { - return NULL; - } - __CFBitfieldSetValue(memory->_base._info, 6, 0, flags); - __CFArraySetCount((CFArrayRef)memory, 0); - switch (__CFBitfieldGetValue(flags, 1, 0)) { - case __kCFArrayImmutable: - if (!isStrongMemory(memory)) { // if weak, don't scan - auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED); - } - if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFArray (immutable)"); - break; - case __kCFArrayFixedMutable: - if (!isStrongMemory(memory)) { // if weak, don't scan - auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED); - } - if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFArray (mutable-fixed)"); - ((struct __CFArrayFixedMutable *)memory)->_capacity = capacity; - break; - case __kCFArrayMutableDeque: - case __kCFArrayMutableStore: - if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFArray (mutable-variable)"); - ((struct __CFArrayMutable *)memory)->_store = NULL; - break; - } - if (__kCFArrayHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) { - CFArrayCallBacks *cb = (CFArrayCallBacks *)__CFArrayGetCallBacks((CFArrayRef)memory); - *cb = *callBacks; - FAULT_CALLBACK((void **)&(cb->retain)); - FAULT_CALLBACK((void **)&(cb->release)); - FAULT_CALLBACK((void **)&(cb->copyDescription)); - FAULT_CALLBACK((void **)&(cb->equal)); - } - return (CFArrayRef)memory; -} - -CFArrayRef CFArrayCreate(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFArrayCallBacks *callBacks) { - CFArrayRef result; - const CFArrayCallBacks *cb; - struct __CFArrayBucket *buckets; - CFAllocatorRef bucketsAllocator; - void* bucketsBase; - CFIndex idx; - CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues); - result = __CFArrayInit(allocator, __kCFArrayImmutable, numValues, callBacks); - cb = __CFArrayGetCallBacks(result); - buckets = __CFArrayGetBucketsPtr(result); - bucketsAllocator = isStrongMemory(result) ? allocator : kCFAllocatorNull; - bucketsBase = CF_IS_COLLECTABLE_ALLOCATOR(bucketsAllocator) ? auto_zone_base_pointer(__CFCollectableZone, buckets) : NULL; - for (idx = 0; idx < numValues; idx++) { - if (NULL != cb->retain) { - CF_WRITE_BARRIER_BASE_ASSIGN(bucketsAllocator, bucketsBase, buckets->_item, (void *)INVOKE_CALLBACK2(cb->retain, allocator, *values)); - } else { - CF_WRITE_BARRIER_BASE_ASSIGN(bucketsAllocator, bucketsBase, buckets->_item, *values); - } - values++; - buckets++; - } - __CFArraySetCount(result, numValues); - return result; -} - -CFMutableArrayRef CFArrayCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFArrayCallBacks *callBacks) { - CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity); - return (CFMutableArrayRef)__CFArrayInit(allocator, (0 == capacity) ? __kCFArrayMutableDeque : __kCFArrayFixedMutable, capacity, callBacks); -} - -// This creates an array which is for CFTypes or NSObjects, with an ownership transfer -- -// the array does not take a retain, and the caller does not need to release the inserted objects. -// The incoming objects must also be collectable if allocated out of a collectable allocator. -CFArrayRef _CFArrayCreate_ex(CFAllocatorRef allocator, bool mutable, const void **values, CFIndex numValues) { - CFArrayRef result; - result = __CFArrayInit(allocator, mutable ? __kCFArrayMutableDeque : __kCFArrayImmutable, numValues, &kCFTypeArrayCallBacks); - if (!mutable) { - struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(result); - CF_WRITE_BARRIER_MEMMOVE(buckets, values, numValues * sizeof(struct __CFArrayBucket)); - } else { - if (__CF_MAX_BUCKETS_PER_DEQUE <= numValues) { - CFStorageRef store = CFStorageCreate(allocator, sizeof(const void *)); - if (__CFOASafe) __CFSetLastAllocationEventName(store, "CFArray (store-storage)"); - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, result, ((struct __CFArrayMutable *)result)->_store, store); - CFStorageInsertValues(store, CFRangeMake(0, numValues)); - CFStorageReplaceValues(store, CFRangeMake(0, numValues), values); - __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFArrayMutableStore); - } else if (0 <= numValues) { - struct __CFArrayDeque *deque; - struct __CFArrayBucket *raw_buckets; - CFIndex capacity = __CFArrayDequeRoundUpCapacity(numValues); - CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); - deque = _CFAllocatorAllocateGC(allocator, size, isStrongMemory(result) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED); - if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)"); - deque->_leftIdx = (capacity - numValues) / 2; - deque->_capacity = capacity; - deque->_bias = 0; - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, result, ((struct __CFArrayMutable *)result)->_store, deque); - raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); - CF_WRITE_BARRIER_MEMMOVE(raw_buckets + deque->_leftIdx + 0, values, numValues * sizeof(struct __CFArrayBucket)); - __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFArrayMutableDeque); - } - } - __CFArraySetCount(result, numValues); - return result; -} - -CFArrayRef CFArrayCreateCopy(CFAllocatorRef allocator, CFArrayRef array) { - CFArrayRef result; - const CFArrayCallBacks *cb; - CFArrayCallBacks patchedCB; - struct __CFArrayBucket *buckets; - CFAllocatorRef bucketsAllocator; - void* bucketsBase; - CFIndex numValues = CFArrayGetCount(array); - CFIndex idx; - if (CF_IS_OBJC(__kCFArrayTypeID, array)) { - cb = &kCFTypeArrayCallBacks; - } else { - cb = __CFArrayGetCallBacks(array); - if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { - if (needsRestore(array)) { - patchedCB = *cb; // copy - cb = &patchedCB; // reset to copy - patchedCB.retain = __CFTypeCollectionRetain; - patchedCB.release = __CFTypeCollectionRelease; - } - } - } - result = __CFArrayInit(allocator, __kCFArrayImmutable, numValues, cb); - cb = __CFArrayGetCallBacks(result); // GC: use the new array's callbacks so we don't leak. - buckets = __CFArrayGetBucketsPtr(result); - bucketsAllocator = isStrongMemory(result) ? allocator : kCFAllocatorNull; - bucketsBase = CF_IS_COLLECTABLE_ALLOCATOR(bucketsAllocator) ? auto_zone_base_pointer(__CFCollectableZone, buckets) : NULL; - for (idx = 0; idx < numValues; idx++) { - const void *value = CFArrayGetValueAtIndex(array, idx); - if (NULL != cb->retain) { - value = (void *)INVOKE_CALLBACK2(cb->retain, allocator, value); - } - CF_WRITE_BARRIER_BASE_ASSIGN(bucketsAllocator, bucketsBase, buckets->_item, value); - buckets++; - } - __CFArraySetCount(result, numValues); - return result; -} - -CFMutableArrayRef CFArrayCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFArrayRef array) { - CFMutableArrayRef result; - const CFArrayCallBacks *cb; - CFIndex idx, numValues = CFArrayGetCount(array); - UInt32 flags; - CFArrayCallBacks patchedCB; - CFAssert3(0 == capacity || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable arrays, capacity (%d) must be greater than or equal to initial number of values (%d)", __PRETTY_FUNCTION__, capacity, numValues); - if (CF_IS_OBJC(__kCFArrayTypeID, array)) { - cb = &kCFTypeArrayCallBacks; - } - else { - cb = __CFArrayGetCallBacks(array); - if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { - if (needsRestore(array)) { - patchedCB = *cb; // copy - cb = &patchedCB; // reset to copy - patchedCB.retain = __CFTypeCollectionRetain; - patchedCB.release = __CFTypeCollectionRelease; - } - } - } - flags = (0 == capacity) ? __kCFArrayMutableDeque : __kCFArrayFixedMutable; - result = (CFMutableArrayRef)__CFArrayInit(allocator, flags, capacity, cb); - if (0 == capacity) _CFArraySetCapacity(result, numValues); - for (idx = 0; idx < numValues; idx++) { - const void *value = CFArrayGetValueAtIndex(array, idx); - CFArrayAppendValue(result, value); - } - return result; -} - -CFIndex CFArrayGetCount(CFArrayRef array) { - CF_OBJC_FUNCDISPATCH0(__kCFArrayTypeID, CFIndex, array, "count"); - __CFGenericValidateType(array, __kCFArrayTypeID); - return __CFArrayGetCount(array); -} - -CFIndex CFArrayGetCountOfValue(CFArrayRef array, CFRange range, const void *value) { - const CFArrayCallBacks *cb; - CFIndex idx, count = 0; -// CF: this ignores range - CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, CFIndex, array, "countOccurrences:", value); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - cb = __CFArrayGetCallBacks(array); - for (idx = 0; idx < range.length; idx++) { - const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item; - if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item))) { - count++; - } - } - return count; -} - -Boolean CFArrayContainsValue(CFArrayRef array, CFRange range, const void *value) { - CFIndex idx; - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, char, array, "containsObject:inRange:", value, range); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - for (idx = 0; idx < range.length; idx++) { - const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item; - if (value == item) { - return true; - } - } - const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array); - if (cb->equal) { - for (idx = 0; idx < range.length; idx++) { - const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item; - if (INVOKE_CALLBACK2(cb->equal, value, item)) { - return true; - } - } - } - return false; -} - -const void *CFArrayGetValueAtIndex(CFArrayRef array, CFIndex idx) { - CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, void *, array, "objectAtIndex:", idx); - __CFGenericValidateType(array, __kCFArrayTypeID); - CFAssert2(0 <= idx && idx < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx); - return __CFArrayGetBucketAtIndex(array, idx)->_item; -} - -// This is for use by NSCFArray; it avoids ObjC dispatch, and checks for out of bounds -const void *_CFArrayCheckAndGetValueAtIndex(CFArrayRef array, CFIndex idx) { - if (0 <= idx && idx < __CFArrayGetCount(array)) return __CFArrayGetBucketAtIndex(array, idx)->_item; - return (void *)(-1); -} - - -void CFArrayGetValues(CFArrayRef array, CFRange range, const void **values) { - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "getObjects:inRange:", values, range); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); - CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__); -#endif - if (0 < range.length) { - switch (__CFArrayGetType(array)) { - case __kCFArrayImmutable: - case __kCFArrayFixedMutable: - case __kCFArrayMutableDeque: - CF_WRITE_BARRIER_MEMMOVE(values, __CFArrayGetBucketsPtr(array) + range.location, range.length * sizeof(struct __CFArrayBucket)); - break; - case __kCFArrayMutableStore: { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - CFStorageGetValues(store, range, values); - break; - } - } - } -} - -void CFArrayApplyFunction(CFArrayRef array, CFRange range, CFArrayApplierFunction applier, void *context) { - CFIndex idx; - FAULT_CALLBACK((void **)&(applier)); - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "apply:context:", applier, context); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); - CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__); -#endif - for (idx = 0; idx < range.length; idx++) { - const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item; - INVOKE_CALLBACK2(applier, item, context); - } -} - -CFIndex CFArrayGetFirstIndexOfValue(CFArrayRef array, CFRange range, const void *value) { - const CFArrayCallBacks *cb; - CFIndex idx; - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, CFIndex, array, "_cfindexOfObject:inRange:", value, range); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - cb = __CFArrayGetCallBacks(array); - for (idx = 0; idx < range.length; idx++) { - const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item; - if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item))) - return idx + range.location; - } - return kCFNotFound; -} - -CFIndex CFArrayGetLastIndexOfValue(CFArrayRef array, CFRange range, const void *value) { - const CFArrayCallBacks *cb; - CFIndex idx; - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, CFIndex, array, "_cflastIndexOfObject:inRange:", value, range); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - cb = __CFArrayGetCallBacks(array); - for (idx = range.length; idx--;) { - const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item; - if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item))) - return idx + range.location; - } - return kCFNotFound; -} - -void CFArrayAppendValue(CFMutableArrayRef array, const void *value) { - CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, void, array, "addObject:", value); - __CFGenericValidateType(array, __kCFArrayTypeID); - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); - _CFArrayReplaceValues(array, CFRangeMake(__CFArrayGetCount(array), 0), &value, 1); -} - -void CFArraySetValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) { - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "setObject:atIndex:", value, idx); - __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); - if (idx == __CFArrayGetCount(array)) { - _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1); - } else { - const void *old_value; - const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array); - CFAllocatorRef allocator = __CFGetAllocator(array); - CFAllocatorRef bucketsAllocator = isStrongMemory(array) ? allocator : kCFAllocatorNull; - struct __CFArrayBucket *bucket = __CFArrayGetBucketAtIndex(array, idx); - if (NULL != cb->retain) { - value = (void *)INVOKE_CALLBACK2(cb->retain, allocator, value); - } - old_value = bucket->_item; - CF_WRITE_BARRIER_ASSIGN(bucketsAllocator, bucket->_item, value); // GC: handles deque/CFStorage cases. - if (NULL != cb->release) { - INVOKE_CALLBACK2(cb->release, allocator, old_value); - } - } -} - -void CFArrayInsertValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) { - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "insertObject:atIndex:", value, idx); - __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); - _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1); -} - -void CFArrayExchangeValuesAtIndices(CFMutableArrayRef array, CFIndex idx1, CFIndex idx2) { - const void *tmp; - struct __CFArrayBucket *bucket1, *bucket2; - CFAllocatorRef bucketsAllocator; - CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "exchange::", idx1, idx2); - __CFGenericValidateType(array, __kCFArrayTypeID); - CFAssert2(0 <= idx1 && idx1 < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index #1 (%d) out of bounds", __PRETTY_FUNCTION__, idx1); - CFAssert2(0 <= idx2 && idx2 < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index #2 (%d) out of bounds", __PRETTY_FUNCTION__, idx2); - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); - bucket1 = __CFArrayGetBucketAtIndex(array, idx1); - bucket2 = __CFArrayGetBucketAtIndex(array, idx2); - tmp = bucket1->_item; - bucketsAllocator = isStrongMemory(array) ? __CFGetAllocator(array) : kCFAllocatorNull; - CF_WRITE_BARRIER_ASSIGN(bucketsAllocator, bucket1->_item, bucket2->_item); - CF_WRITE_BARRIER_ASSIGN(bucketsAllocator, bucket2->_item, tmp); -} - -void CFArrayRemoveValueAtIndex(CFMutableArrayRef array, CFIndex idx) { - CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, void, array, "removeObjectAtIndex:", idx); - __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); - _CFArrayReplaceValues(array, CFRangeMake(idx, 1), NULL, 0); -} - -void CFArrayRemoveAllValues(CFMutableArrayRef array) { - CF_OBJC_FUNCDISPATCH0(__kCFArrayTypeID, void, array, "removeAllObjects"); - __CFGenericValidateType(array, __kCFArrayTypeID); - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); - __CFArrayReleaseValues(array, CFRangeMake(0, __CFArrayGetCount(array)), true); - __CFArraySetCount(array, 0); -} - -static void __CFArrayConvertDequeToStore(CFMutableArrayRef array) { - struct __CFArrayDeque *deque = ((struct __CFArrayMutable *)array)->_store; - struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); - CFStorageRef store; - CFIndex count = CFArrayGetCount(array); - CFAllocatorRef allocator = __CFGetAllocator(array); - store = CFStorageCreate(allocator, sizeof(const void *)); - if (__CFOASafe) __CFSetLastAllocationEventName(store, "CFArray (store-storage)"); - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, array, ((struct __CFArrayMutable *)array)->_store, store); - CFStorageInsertValues(store, CFRangeMake(0, count)); - CFStorageReplaceValues(store, CFRangeMake(0, count), raw_buckets + deque->_leftIdx); - _CFAllocatorDeallocateGC(__CFGetAllocator(array), deque); - __CFBitfieldSetValue(((CFRuntimeBase *)array)->_info, 1, 0, __kCFArrayMutableStore); -} - -static void __CFArrayConvertStoreToDeque(CFMutableArrayRef array) { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - struct __CFArrayDeque *deque; - struct __CFArrayBucket *raw_buckets; - CFIndex count = CFStorageGetCount(store);// storage, not array, has correct count at this point - // do not resize down to a completely tight deque - CFIndex capacity = __CFArrayDequeRoundUpCapacity(count + 6); - CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); - CFAllocatorRef allocator = __CFGetAllocator(array); - deque = _CFAllocatorAllocateGC(allocator, size, isStrongMemory(array) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED); - if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)"); - deque->_leftIdx = (capacity - count) / 2; - deque->_capacity = capacity; - deque->_bias = 0; - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, array, ((struct __CFArrayMutable *)array)->_store, deque); - raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); - CFStorageGetValues(store, CFRangeMake(0, count), raw_buckets + deque->_leftIdx); - CFRelease(store); - __CFBitfieldSetValue(((CFRuntimeBase *)array)->_info, 1, 0, __kCFArrayMutableDeque); -} - -// may move deque storage, as it may need to grow deque -static void __CFArrayRepositionDequeRegions(CFMutableArrayRef array, CFRange range, CFIndex newCount) { - // newCount elements are going to replace the range, and the result will fit in the deque - struct __CFArrayDeque *deque = ((struct __CFArrayMutable *)array)->_store; - struct __CFArrayBucket *buckets; - CFIndex cnt, futureCnt, numNewElems; - CFIndex L, A, B, C, R; - - buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); - cnt = __CFArrayGetCount(array); - futureCnt = cnt - range.length + newCount; - - L = deque->_leftIdx; // length of region to left of deque - A = range.location; // length of region in deque to left of replaced range - B = range.length; // length of replaced range - C = cnt - B - A; // length of region in deque to right of replaced range - R = deque->_capacity - cnt - L; // length of region to right of deque - numNewElems = newCount - B; - - CFIndex wiggle = deque->_capacity >> 17; - if (wiggle < 4) wiggle = 4; - if (deque->_capacity < futureCnt || (cnt < futureCnt && L + R < wiggle)) { - // must be inserting or space is tight, reallocate and re-center everything - CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt + wiggle); - CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); - CFAllocatorRef allocator = __CFGetAllocator(array); - struct __CFArrayDeque *newDeque = _CFAllocatorAllocateGC(allocator, size, isStrongMemory(array) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED); - if (__CFOASafe) __CFSetLastAllocationEventName(newDeque, "CFArray (store-deque)"); - struct __CFArrayBucket *newBuckets = (struct __CFArrayBucket *)((uint8_t *)newDeque + sizeof(struct __CFArrayDeque)); - CFIndex oldL = L; - CFIndex newL = (capacity - futureCnt) / 2; - CFIndex oldC0 = oldL + A + B; - CFIndex newC0 = newL + A + newCount; - newDeque->_leftIdx = newL; - newDeque->_capacity = capacity; - if (0 < A) CF_WRITE_BARRIER_MEMMOVE(newBuckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket)); - if (0 < C) CF_WRITE_BARRIER_MEMMOVE(newBuckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket)); - if (deque) _CFAllocatorDeallocateGC(allocator, deque); - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, array, ((struct __CFArrayMutable *)array)->_store, newDeque); - return; - } - - if ((numNewElems < 0 && C < A) || (numNewElems <= R && C < A)) { // move C - // deleting: C is smaller - // inserting: C is smaller and R has room - CFIndex oldC0 = L + A + B; - CFIndex newC0 = L + A + newCount; - if (0 < C) CF_WRITE_BARRIER_MEMMOVE(buckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket)); - // GrP GC: zero-out newly exposed space on the right, if any - if (oldC0 > newC0) bzero(buckets + newC0 + C, (oldC0 - newC0) * sizeof(struct __CFArrayBucket)); - } else if ((numNewElems < 0) || (numNewElems <= L && A <= C)) { // move A - // deleting: A is smaller or equal (covers remaining delete cases) - // inserting: A is smaller and L has room - CFIndex oldL = L; - CFIndex newL = L - numNewElems; - deque->_leftIdx = newL; - if (0 < A) CF_WRITE_BARRIER_MEMMOVE(buckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket)); - // GrP GC: zero-out newly exposed space on the left, if any - if (newL > oldL) bzero(buckets + oldL, (newL - oldL) * sizeof(struct __CFArrayBucket)); - } else { - // now, must be inserting, and either: - // A<=C, but L doesn't have room (R might have, but don't care) - // C_bias; - deque->_bias = (newL < oldL) ? -1 : 1; - if (oldBias < 0) { - newL = newL - newL / 2; - } else if (0 < oldBias) { - newL = newL + newL / 2; - } - CFIndex oldC0 = oldL + A + B; - CFIndex newC0 = newL + A + newCount; - deque->_leftIdx = newL; - if (newL < oldL) { - if (0 < A) CF_WRITE_BARRIER_MEMMOVE(buckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket)); - if (0 < C) CF_WRITE_BARRIER_MEMMOVE(buckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket)); - // GrP GC: zero-out newly exposed space on the right, if any - if (oldC0 > newC0) bzero(buckets + newC0 + C, (oldC0 - newC0) * sizeof(struct __CFArrayBucket)); - } else { - if (0 < C) CF_WRITE_BARRIER_MEMMOVE(buckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket)); - if (0 < A) CF_WRITE_BARRIER_MEMMOVE(buckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket)); - // GrP GC: zero-out newly exposed space on the left, if any - if (newL > oldL) bzero(buckets + oldL, (newL - oldL) * sizeof(struct __CFArrayBucket)); - } - } -} - -// This function is for Foundation's benefit; no one else should use it. -void _CFArraySetCapacity(CFMutableArrayRef array, CFIndex cap) { - if (CF_IS_OBJC(__kCFArrayTypeID, array)) return; -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable && __CFArrayGetType(array) != __kCFArrayFixedMutable, __kCFLogAssertion, "%s(): array is immutable or fixed-mutable", __PRETTY_FUNCTION__); - CFAssert3(__CFArrayGetCount(array) <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, __CFArrayGetCount(array)); -#endif - // Currently, attempting to set the capacity of an array which is the CFStorage - // variant, or set the capacity larger than __CF_MAX_BUCKETS_PER_DEQUE, has no - // effect. The primary purpose of this API is to help avoid a bunch of the - // resizes at the small capacities 4, 8, 16, etc. - if (__CFArrayGetType(array) == __kCFArrayMutableDeque) { - struct __CFArrayDeque *deque = ((struct __CFArrayMutable *)array)->_store; - CFIndex capacity = __CFArrayDequeRoundUpCapacity(cap); - CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); - CFAllocatorRef allocator = __CFGetAllocator(array); - if (NULL == deque) { - deque = _CFAllocatorAllocateGC(allocator, size, isStrongMemory(array) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED); - if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)"); - deque->_leftIdx = capacity / 2; - } else { - deque = _CFAllocatorReallocateGC(allocator, deque, size, isStrongMemory(array) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED); - if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)"); - } - deque->_capacity = capacity; - deque->_bias = 0; - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, array, ((struct __CFArrayMutable *)array)->_store, deque); - } -} - - -void CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) { - CF_OBJC_FUNCDISPATCH3(__kCFArrayTypeID, void, array, "replaceObjectsInRange:withObjects:count:", range, (void **)newValues, newCount); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); - CFAssert2(0 <= newCount, __kCFLogAssertion, "%s(): newCount (%d) cannot be less than zero", __PRETTY_FUNCTION__, newCount); - return _CFArrayReplaceValues(array, range, newValues, newCount); -} - -// 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 -void _CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) { - const CFArrayCallBacks *cb; - CFAllocatorRef allocator; - CFIndex idx, cnt, futureCnt; - const void **newv, *buffer[256]; - cnt = __CFArrayGetCount(array); - futureCnt = cnt - range.length + newCount; - CFAssert1((__kCFArrayFixedMutable != __CFArrayGetType(array)) || (futureCnt <= ((struct __CFArrayFixedMutable *)array)->_capacity), __kCFLogAssertion, "%s(): fixed-capacity array is full (or will overflow)", __PRETTY_FUNCTION__); - CFAssert1(newCount <= futureCnt, __kCFLogAssertion, "%s(): internal error 1", __PRETTY_FUNCTION__); - cb = __CFArrayGetCallBacks(array); - allocator = __CFGetAllocator(array); - /* Retain new values if needed, possibly allocating a temporary buffer for them */ - if (NULL != cb->retain) { - newv = (newCount <= 256) ? buffer : CFAllocatorAllocate(allocator, 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; - } - /* 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. - */ - if (__kCFArrayFixedMutable == __CFArrayGetType(array)) { - struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(array); -// CF: we should treat a fixed mutable array like a deque too - if (0 < range.length) { - __CFArrayReleaseValues(array, range, false); - } - if (newCount != range.length && range.location + range.length < cnt) { - /* This neatly moves region C in the proper direction */ - CF_WRITE_BARRIER_MEMMOVE(buckets + range.location + newCount, buckets + range.location + range.length, (cnt - range.location - range.length) * sizeof(struct __CFArrayBucket)); - } - if (0 < newCount) { - CF_WRITE_BARRIER_MEMMOVE(buckets + range.location, newv, newCount * sizeof(void *)); - } - __CFArraySetCount(array, futureCnt); - if (newv != buffer && newv != newValues) CFAllocatorDeallocate(allocator, newv); // GC OK - return; - } - if (0 < range.length) { - __CFArrayReleaseValues(array, range, false); - } - // region B elements are now "dead" - if (__kCFArrayMutableStore == __CFArrayGetType(array)) { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - // reposition regions A and C for new region B elements in gap - if (range.length < newCount) { - CFStorageInsertValues(store, CFRangeMake(range.location + range.length, newCount - range.length)); - } else if (newCount < range.length) { - CFStorageDeleteValues(store, CFRangeMake(range.location + newCount, range.length - newCount)); - } - if (futureCnt <= __CF_MAX_BUCKETS_PER_DEQUE / 2) { - __CFArrayConvertStoreToDeque(array); - } - } else if (NULL == ((struct __CFArrayMutable *)array)->_store) { - if (__CF_MAX_BUCKETS_PER_DEQUE <= futureCnt) { - CFStorageRef store = CFStorageCreate(allocator, sizeof(const void *)); - if (! isStrongMemory(array)) _CFStorageSetWeak(store); - if (__CFOASafe) __CFSetLastAllocationEventName(store, "CFArray (store-storage)"); - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, array, ((struct __CFArrayMutable *)array)->_store, store); - CFStorageInsertValues(store, CFRangeMake(0, newCount)); - __CFBitfieldSetValue(((CFRuntimeBase *)array)->_info, 1, 0, __kCFArrayMutableStore); - } else if (0 <= futureCnt) { - struct __CFArrayDeque *deque; - CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt); - CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); - deque = _CFAllocatorAllocateGC(allocator, size, isStrongMemory(array) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED); - if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)"); - deque->_leftIdx = (capacity - newCount) / 2; - deque->_capacity = capacity; - deque->_bias = 0; - CF_WRITE_BARRIER_BASE_ASSIGN(allocator, array, ((struct __CFArrayMutable *)array)->_store, deque); - } - } else { // Deque - // reposition regions A and C for new region B elements in gap - if (__CF_MAX_BUCKETS_PER_DEQUE <= futureCnt) { - CFStorageRef store; - __CFArrayConvertDequeToStore(array); - store = ((struct __CFArrayMutable *)array)->_store; - if (range.length < newCount) { - CFStorageInsertValues(store, CFRangeMake(range.location + range.length, newCount - range.length)); - } else if (newCount < range.length) { // this won't happen, but is here for completeness - CFStorageDeleteValues(store, CFRangeMake(range.location + newCount, range.length - newCount)); - } - } else if (range.length != newCount) { - __CFArrayRepositionDequeRegions(array, range, newCount); - } - } - // copy in new region B elements - if (0 < newCount) { - if (__kCFArrayMutableStore == __CFArrayGetType(array)) { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - CFStorageReplaceValues(store, CFRangeMake(range.location, newCount), newv); - } else { // Deque - struct __CFArrayDeque *deque = ((struct __CFArrayMutable *)array)->_store; - struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); - CFAllocatorRef bucketsAllocator = isStrongMemory(array) ? allocator : kCFAllocatorNull; - if (newCount == 1) - CF_WRITE_BARRIER_ASSIGN(bucketsAllocator, *((const void **)raw_buckets + deque->_leftIdx + range.location), newv[0]); - else - CF_WRITE_BARRIER_MEMMOVE(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket)); - } - } - __CFArraySetCount(array, futureCnt); - if (newv != buffer && newv != newValues) CFAllocatorDeallocate(allocator, newv); -} - -struct _acompareContext { - CFComparatorFunction func; - void *context; -}; - -static CFComparisonResult __CFArrayCompareValues(const void *v1, const void *v2, struct _acompareContext *context) { - const void **val1 = (const void **)v1; - const void **val2 = (const void **)v2; - return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context)); -} - -void CFArraySortValues(CFMutableArrayRef array, CFRange range, CFComparatorFunction comparator, void *context) { - FAULT_CALLBACK((void **)&(comparator)); - CF_OBJC_FUNCDISPATCH3(__kCFArrayTypeID, void, array, "sortUsingFunction:context:range:", comparator, context, range); -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); - CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__); - if (1 < range.length) { - struct _acompareContext ctx; - struct __CFArrayBucket *bucket; - ctx.func = comparator; - ctx.context = context; - switch (__CFArrayGetType(array)) { - case __kCFArrayFixedMutable: - case __kCFArrayMutableDeque: - bucket = __CFArrayGetBucketsPtr(array) + range.location; - if (CF_USING_COLLECTABLE_MEMORY && isStrongMemory(array)) __CFObjCWriteBarrierRange(bucket, range.length * sizeof(void *)); - CFQSortArray(bucket, range.length, sizeof(void *), (CFComparatorFunction)__CFArrayCompareValues, &ctx); - break; - case __kCFArrayMutableStore: { - CFStorageRef store = ((struct __CFArrayMutable *)array)->_store; - CFAllocatorRef allocator = __CFGetAllocator(array); - const void **values, *buffer[256]; - values = (range.length <= 256) ? buffer : CFAllocatorAllocate(allocator, range.length * sizeof(void *), 0); // GC OK - if (values != buffer && __CFOASafe) __CFSetLastAllocationEventName(values, "CFArray (temp)"); - CFStorageGetValues(store, range, values); - CFQSortArray(values, range.length, sizeof(void *), (CFComparatorFunction)__CFArrayCompareValues, &ctx); - CFStorageReplaceValues(store, range, values); - if (values != buffer) CFAllocatorDeallocate(allocator, values); // GC OK - break; - } - } - } -} - -CFIndex CFArrayBSearchValues(CFArrayRef array, CFRange range, const void *value, CFComparatorFunction comparator, void *context) { - bool isObjC = CF_IS_OBJC(__kCFArrayTypeID, array); - CFIndex idx = 0; - FAULT_CALLBACK((void **)&(comparator)); - if (!isObjC) { -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__); -#endif - } - CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__); - if (range.length <= 0) return range.location; - if (isObjC || __kCFArrayMutableStore == __CFArrayGetType(array)) { - const void *item; - SInt32 lg; - item = CFArrayGetValueAtIndex(array, range.location + range.length - 1); - if ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, item, value, context)) < 0) { - return range.location + range.length; - } - item = CFArrayGetValueAtIndex(array, range.location); - if ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, value, item, context)) < 0) { - return range.location; - } - lg = CFLog2(range.length); - item = CFArrayGetValueAtIndex(array, range.location + -1 + (1 << lg)); - idx = range.location + ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, item, value, context)) < 0) ? range.length - (1 << lg) : -1; - while (lg--) { - item = CFArrayGetValueAtIndex(array, range.location + idx + (1 << lg)); - if ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, item, value, context)) < 0) { - idx += (1 << lg); - } - } - idx++; - } else { - struct _acompareContext ctx; - ctx.func = comparator; - ctx.context = context; - idx = CFBSearch(&value, sizeof(void *), __CFArrayGetBucketsPtr(array) + range.location, range.length, (CFComparatorFunction)__CFArrayCompareValues, &ctx); - } - return idx + range.location; -} - -void CFArrayAppendArray(CFMutableArrayRef array, CFArrayRef otherArray, CFRange otherRange) { - CFIndex idx; -#if defined(DEBUG) - __CFGenericValidateType(array, __kCFArrayTypeID); - __CFGenericValidateType(otherArray, __kCFArrayTypeID); - CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__); - __CFArrayValidateRange(otherArray, otherRange, __PRETTY_FUNCTION__); -#endif - for (idx = otherRange.location; idx < otherRange.location + otherRange.length; idx++) { - CFArrayAppendValue(array, CFArrayGetValueAtIndex(otherArray, idx)); - } -}