CFArray.c

   1 /*
   2  * Copyright (c) 2012 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*      CFArray.c
  25         Copyright (c) 1998-2011, Apple Inc. All rights reserved.
  26         Responsibility: Christopher Kane
  27 */
  28
  29 #include <CoreFoundation/CFArray.h>
  30 #include <CoreFoundation/CFPriv.h>
  31 #include "CFInternal.h"
  32 #include <string.h>
  33
  34 const CFArrayCallBacks kCFTypeArrayCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
  35 static const CFArrayCallBacks __kCFNullArrayCallBacks = {0, NULL, NULL, NULL, NULL};
  36
  37 struct __CFArrayBucket {
  38     const void *_item;
  39 };
  40
  41 enum {
  42     __CF_MAX_BUCKETS_PER_DEQUE = LONG_MAX
  43 };
  44
  45 CF_INLINE CFIndex __CFArrayDequeRoundUpCapacity(CFIndex capacity) {
  46     if (capacity < 4) return 4;
  47     return __CFMin((1 << flsl(capacity)), __CF_MAX_BUCKETS_PER_DEQUE);
  48 }
  49
  50 struct __CFArrayDeque {
  51     uintptr_t _leftIdx;
  52     uintptr_t _capacity;
  53     /* struct __CFArrayBucket buckets follow here */
  54 };
  55
  56 struct __CFArray {
  57     CFRuntimeBase _base;
  58     CFIndex _count;             /* number of objects */
  59     CFIndex _mutations;
  60     int32_t _mutInProgress;
  61     __strong void *_store;           /* can be NULL when MutableDeque */
  62 };
  63
  64 /* Flag bits */
  65 enum {          /* Bits 0-1 */
  66     __kCFArrayImmutable = 0,
  67     __kCFArrayDeque = 2,
  68 };
  69
  70 enum {          /* Bits 2-3 */
  71     __kCFArrayHasNullCallBacks = 0,
  72     __kCFArrayHasCFTypeCallBacks = 1,
  73     __kCFArrayHasCustomCallBacks = 3    /* callbacks are at end of header */
  74 };
  75
  76 /*
  77     Bits 4 & 5 are reserved for GC use.
  78     Bit 4, if set, indicates that the array is weak.
  79     Bit 5 marks whether finalization has occured and, thus, whether to continue to do special retain/release processing of elements.
  80  */
  81
  82 CF_INLINE bool isStrongMemory(CFTypeRef collection) {
  83     return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 4, 4) == 0;
  84 }
  85
  86 CF_INLINE bool isWeakMemory(CFTypeRef collection) {
  87     return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 4, 4) != 0;
  88 }
  89
  90 CF_INLINE bool hasBeenFinalized(CFTypeRef collection) {
  91     return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 5, 5) != 0;
  92 }
  93
  94 CF_INLINE void markFinalized(CFTypeRef collection) {
  95     __CFBitfieldSetValue(((CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 5, 5, 1);
  96 }
  97
  98 CF_INLINE CFIndex __CFArrayGetType(CFArrayRef array) {
  99     return __CFBitfieldGetValue(((const CFRuntimeBase *)array)->_cfinfo[CF_INFO_BITS], 1, 0);
 100 }
 101
 102 CF_INLINE CFIndex __CFArrayGetSizeOfType(CFIndex t) {
 103     CFIndex size = 0;
 104         size += sizeof(struct __CFArray);
 105     if (__CFBitfieldGetValue(t, 3, 2) == __kCFArrayHasCustomCallBacks) {
 106         size += sizeof(CFArrayCallBacks);
 107     }
 108     return size;
 109 }
 110
 111 CF_INLINE CFIndex __CFArrayGetCount(CFArrayRef array) {
 112     return array->_count;
 113 }
 114
 115 CF_INLINE void __CFArraySetCount(CFArrayRef array, CFIndex v) {
 116     ((struct __CFArray *)array)->_count = v;
 117 }
 118
 119 /* Only applies to immutable and mutable-deque-using arrays;
 120  * Returns the bucket holding the left-most real value in the latter case. */
 121 CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketsPtr(CFArrayRef array) {
 122     switch (__CFArrayGetType(array)) {
 123     case __kCFArrayImmutable:
 124         return (struct __CFArrayBucket *)((uint8_t *)array + __CFArrayGetSizeOfType(((CFRuntimeBase *)array)->_cfinfo[CF_INFO_BITS]));
 125     case __kCFArrayDeque: {
 126         struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
 127         return (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque) + deque->_leftIdx * sizeof(struct __CFArrayBucket));
 128     }
 129     }
 130     return NULL;
 131 }
 132
 133 /* This shouldn't be called if the array count is 0. */
 134 CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRef array, CFIndex idx) {
 135     switch (__CFArrayGetType(array)) {
 136     case __kCFArrayImmutable:
 137     case __kCFArrayDeque:
 138         return __CFArrayGetBucketsPtr(array) + idx;
 139     }
 140     return NULL;
 141 }
 142
 143 __private_extern__ CFArrayCallBacks *__CFArrayGetCallBacks(CFArrayRef array) {
 144     CFArrayCallBacks *result = NULL;
 145     switch (__CFBitfieldGetValue(((const CFRuntimeBase *)array)->_cfinfo[CF_INFO_BITS], 3, 2)) {
 146     case __kCFArrayHasNullCallBacks:
 147         return (CFArrayCallBacks *)&__kCFNullArrayCallBacks;
 148     case __kCFArrayHasCFTypeCallBacks:
 149         return (CFArrayCallBacks *)&kCFTypeArrayCallBacks;
 150     case __kCFArrayHasCustomCallBacks:
 151         break;
 152     }
 153     switch (__CFArrayGetType(array)) {
 154     case __kCFArrayImmutable:
 155         result = (CFArrayCallBacks *)((uint8_t *)array + sizeof(struct __CFArray));
 156         break;
 157     case __kCFArrayDeque:
 158         result = (CFArrayCallBacks *)((uint8_t *)array + sizeof(struct __CFArray));
 159         break;
 160     }
 161     return result;
 162 }
 163
 164 CF_INLINE bool __CFArrayCallBacksMatchNull(const CFArrayCallBacks *c) {
 165     return (NULL == c ||
 166         (c->retain == __kCFNullArrayCallBacks.retain &&
 167          c->release == __kCFNullArrayCallBacks.release &&
 168          c->copyDescription == __kCFNullArrayCallBacks.copyDescription &&
 169          c->equal == __kCFNullArrayCallBacks.equal));
 170 }
 171
 172 CF_INLINE bool __CFArrayCallBacksMatchCFType(const CFArrayCallBacks *c) {
 173     return (&kCFTypeArrayCallBacks == c ||
 174         (c->retain == kCFTypeArrayCallBacks.retain &&
 175          c->release == kCFTypeArrayCallBacks.release &&
 176          c->copyDescription == kCFTypeArrayCallBacks.copyDescription &&
 177          c->equal == kCFTypeArrayCallBacks.equal));
 178 }
 179
 180 #if 0
 181 #define CHECK_FOR_MUTATION(A) do { if ((A)->_mutInProgress) CFLog(3, CFSTR("*** %s: function called while the array (%p) is being mutated in this or another thread"), __PRETTY_FUNCTION__, (A)); } while (0)
 182 #define BEGIN_MUTATION(A) do { OSAtomicAdd32Barrier(1, &((struct __CFArray *)(A))->_mutInProgress); } while (0)
 183 #define END_MUTATION(A) do { OSAtomicAdd32Barrier(-1, &((struct __CFArray *)(A))->_mutInProgress); } while (0)
 184 #else
 185 #define CHECK_FOR_MUTATION(A) do { } while (0)
 186 #define BEGIN_MUTATION(A) do { } while (0)
 187 #define END_MUTATION(A) do { } while (0)
 188 #endif
 189
 190 struct _releaseContext {
 191     void (*release)(CFAllocatorRef, const void *);
 192     CFAllocatorRef allocator;
 193 };
 194
 195 static void __CFArrayReleaseValues(CFArrayRef array, CFRange range, bool releaseStorageIfPossible) {
 196     const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array);
 197     CFAllocatorRef allocator;
 198     CFIndex idx;
 199     switch (__CFArrayGetType(array)) {
 200     case __kCFArrayImmutable:
 201         if (NULL != cb->release && 0 < range.length && !hasBeenFinalized(array)) {
 202             // if we've been finalized then we know that
 203             //   1) we're using the standard callback on GC memory
 204             //   2) the slots don't' need to be zeroed
 205             struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(array);
 206             allocator = __CFGetAllocator(array);
 207             for (idx = 0; idx < range.length; idx++) {
 208                 INVOKE_CALLBACK2(cb->release, allocator, buckets[idx + range.location]._item);
 209                 buckets[idx + range.location]._item = NULL; // GC:  break strong reference.
 210             }
 211         }
 212         break;
 213     case __kCFArrayDeque: {
 214         struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
 215         if (0 < range.length && NULL != deque && !hasBeenFinalized(array)) {
 216             struct __CFArrayBucket *buckets = __CFArrayGetBucketsPtr(array);
 217             if (NULL != cb->release) {
 218                 allocator = __CFGetAllocator(array);
 219                 for (idx = 0; idx < range.length; idx++) {
 220                     INVOKE_CALLBACK2(cb->release, allocator, buckets[idx + range.location]._item);
 221                     buckets[idx + range.location]._item = NULL; // GC:  break strong reference.
 222                 }
 223             } else {
 224                 for (idx = 0; idx < range.length; idx++) {
 225                     buckets[idx + range.location]._item = NULL; // GC:  break strong reference.
 226                 }
 227             }
 228         }
 229         if (releaseStorageIfPossible && 0 == range.location && __CFArrayGetCount(array) == range.length) {
 230             allocator = __CFGetAllocator(array);
 231             if (NULL != deque && !CF_IS_COLLECTABLE_ALLOCATOR(allocator)) CFAllocatorDeallocate(allocator, deque);
 232             __CFArraySetCount(array, 0);  // GC: _count == 0 ==> _store == NULL.
 233             ((struct __CFArray *)array)->_store = NULL;
 234         }
 235         break;
 236     }
 237     }
 238 }
 239
 240 #if defined(DEBUG)
 241 CF_INLINE void __CFArrayValidateRange(CFArrayRef array, CFRange range, const char *func) {
 242     CFAssert3(0 <= range.location && range.location <= CFArrayGetCount(array), __kCFLogAssertion, "%s(): range.location index (%d) out of bounds (0, %d)", func, range.location, CFArrayGetCount(array));
 243     CFAssert2(0 <= range.length, __kCFLogAssertion, "%s(): range.length (%d) cannot be less than zero", func, range.length);
 244     CFAssert3(range.location + range.length <= CFArrayGetCount(array), __kCFLogAssertion, "%s(): ending index (%d) out of bounds (0, %d)", func, range.location + range.length, CFArrayGetCount(array));
 245 }
 246 #else
 247 #define __CFArrayValidateRange(a,r,f)
 248 #endif
 249
 250 static Boolean __CFArrayEqual(CFTypeRef cf1, CFTypeRef cf2) {
 251     CFArrayRef array1 = (CFArrayRef)cf1;
 252     CFArrayRef array2 = (CFArrayRef)cf2;
 253     const CFArrayCallBacks *cb1, *cb2;
 254     CFIndex idx, cnt;
 255     if (array1 == array2) return true;
 256     cnt = __CFArrayGetCount(array1);
 257     if (cnt != __CFArrayGetCount(array2)) return false;
 258     cb1 = __CFArrayGetCallBacks(array1);
 259     cb2 = __CFArrayGetCallBacks(array2);
 260     if (cb1->equal != cb2->equal) return false;
 261     if (0 == cnt) return true;  /* after function comparison! */
 262     for (idx = 0; idx < cnt; idx++) {
 263         const void *val1 = __CFArrayGetBucketAtIndex(array1, idx)->_item;
 264         const void *val2 = __CFArrayGetBucketAtIndex(array2, idx)->_item;
 265         if (val1 != val2) {
 266             if (NULL == cb1->equal) return false;
 267             if (!INVOKE_CALLBACK2(cb1->equal, val1, val2)) return false;
 268         }
 269     }
 270     return true;
 271 }
 272
 273 static CFHashCode __CFArrayHash(CFTypeRef cf) {
 274     CFArrayRef array = (CFArrayRef)cf;
 275     return __CFArrayGetCount(array);
 276 }
 277
 278 static CFStringRef __CFArrayCopyDescription(CFTypeRef cf) {
 279     CFArrayRef array = (CFArrayRef)cf;
 280     CFMutableStringRef result;
 281     const CFArrayCallBacks *cb;
 282     CFAllocatorRef allocator;
 283     CFIndex idx, cnt;
 284     cnt = __CFArrayGetCount(array);
 285     allocator = CFGetAllocator(array);
 286     result = CFStringCreateMutable(allocator, 0);
 287     switch (__CFArrayGetType(array)) {
 288     case __kCFArrayImmutable:
 289         CFStringAppendFormat(result, NULL, CFSTR("<CFArray %p [%p]>{type = immutable, count = %u, values = (%s"), cf, allocator, cnt, cnt ? "\n" : "");
 290         break;
 291     case __kCFArrayDeque:
 292         CFStringAppendFormat(result, NULL, CFSTR("<CFArray %p [%p]>{type = mutable-small, count = %u, values = (%s"), cf, allocator, cnt, cnt ? "\n" : "");
 293         break;
 294     }
 295     cb = __CFArrayGetCallBacks(array);
 296     for (idx = 0; idx < cnt; idx++) {
 297         CFStringRef desc = NULL;
 298         const void *val = __CFArrayGetBucketAtIndex(array, idx)->_item;
 299         if (NULL != cb->copyDescription) {
 300             desc = (CFStringRef)INVOKE_CALLBACK1(cb->copyDescription, val);
 301         }
 302         if (NULL != desc) {
 303             CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, desc);
 304             CFRelease(desc);
 305         } else {
 306             CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, val);
 307         }
 308     }
 309     CFStringAppend(result, CFSTR(")}"));
 310     return result;
 311 }
 312
 313
 314 static void __CFArrayDeallocate(CFTypeRef cf) {
 315     CFArrayRef array = (CFArrayRef)cf;
 316     BEGIN_MUTATION(array);
 317     // Under GC, keep contents alive when we know we can, either standard callbacks or NULL
 318     // if (__CFBitfieldGetValue(cf->info, 5, 4)) return; // bits only ever set under GC
 319     CFAllocatorRef allocator = __CFGetAllocator(array);
 320     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 321         // XXX_PCB keep array intact during finalization.
 322         const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array);
 323         if (cb->retain == NULL && cb->release == NULL) {
 324             END_MUTATION(array);
 325             return;
 326         }
 327         if (cb == &kCFTypeArrayCallBacks || cb->release == kCFTypeArrayCallBacks.release) {
 328             markFinalized(cf);
 329             for (CFIndex idx = 0; idx < __CFArrayGetCount(array); idx++) {
 330                 const void *item = CFArrayGetValueAtIndex(array, 0 + idx);
 331                 kCFTypeArrayCallBacks.release(kCFAllocatorSystemDefault, item);
 332             }
 333             END_MUTATION(array);
 334             return;
 335         }
 336     }
 337     __CFArrayReleaseValues(array, CFRangeMake(0, __CFArrayGetCount(array)), true);
 338     END_MUTATION(array);
 339 }
 340
 341 static CFTypeID __kCFArrayTypeID = _kCFRuntimeNotATypeID;
 342
 343 static const CFRuntimeClass __CFArrayClass = {
 344     _kCFRuntimeScannedObject,
 345     "CFArray",
 346     NULL,       // init
 347     NULL,       // copy
 348     __CFArrayDeallocate,
 349     __CFArrayEqual,
 350     __CFArrayHash,
 351     NULL,       //
 352     __CFArrayCopyDescription
 353 };
 354
 355 __private_extern__ void __CFArrayInitialize(void) {
 356     __kCFArrayTypeID = _CFRuntimeRegisterClass(&__CFArrayClass);
 357 }
 358
 359 CFTypeID CFArrayGetTypeID(void) {
 360     return __kCFArrayTypeID;
 361 }
 362
 363 static CFArrayRef __CFArrayInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFArrayCallBacks *callBacks) {
 364     struct __CFArray *memory;
 365     UInt32 size;
 366     __CFBitfieldSetValue(flags, 31, 2, 0);
 367     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 368         if (!callBacks || (callBacks->retain == NULL && callBacks->release == NULL)) {
 369             __CFBitfieldSetValue(flags, 4, 4, 1); // setWeak
 370         }
 371     }
 372     if (__CFArrayCallBacksMatchNull(callBacks)) {
 373         __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasNullCallBacks);
 374     } else if (__CFArrayCallBacksMatchCFType(callBacks)) {
 375         __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasCFTypeCallBacks);
 376     } else {
 377         __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasCustomCallBacks);
 378     }
 379     size = __CFArrayGetSizeOfType(flags) - sizeof(CFRuntimeBase);
 380     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 381     case __kCFArrayImmutable:
 382         size += capacity * sizeof(struct __CFArrayBucket);
 383         break;
 384     case __kCFArrayDeque:
 385         break;
 386     }
 387     memory = (struct __CFArray*)_CFRuntimeCreateInstance(allocator, __kCFArrayTypeID, size, NULL);
 388     if (NULL == memory) {
 389         return NULL;
 390     }
 391     __CFBitfieldSetValue(memory->_base._cfinfo[CF_INFO_BITS], 6, 0, flags);
 392     __CFArraySetCount((CFArrayRef)memory, 0);
 393     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 394     case __kCFArrayImmutable:
 395         if (isWeakMemory(memory)) {  // if weak, don't scan
 396             auto_zone_set_unscanned(objc_collectableZone(), memory);
 397         }
 398         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFArray (immutable)");
 399         break;
 400     case __kCFArrayDeque:
 401         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFArray (mutable-variable)");
 402         ((struct __CFArray *)memory)->_mutations = 1;
 403         ((struct __CFArray *)memory)->_mutInProgress = 0;
 404         ((struct __CFArray*)memory)->_store = NULL;
 405         break;
 406     }
 407     if (__kCFArrayHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
 408         CFArrayCallBacks *cb = (CFArrayCallBacks *)__CFArrayGetCallBacks((CFArrayRef)memory);
 409         *cb = *callBacks;
 410         FAULT_CALLBACK((void **)&(cb->retain));
 411         FAULT_CALLBACK((void **)&(cb->release));
 412         FAULT_CALLBACK((void **)&(cb->copyDescription));
 413         FAULT_CALLBACK((void **)&(cb->equal));
 414     }
 415     return (CFArrayRef)memory;
 416 }
 417
 418 __private_extern__ CFArrayRef __CFArrayCreateTransfer(CFAllocatorRef allocator, const void **values, CFIndex numValues) {
 419     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 420     UInt32 flags = __kCFArrayImmutable;
 421     __CFBitfieldSetValue(flags, 31, 2, 0);
 422     __CFBitfieldSetValue(flags, 3, 2, __kCFArrayHasCFTypeCallBacks);
 423     UInt32 size = __CFArrayGetSizeOfType(flags) - sizeof(CFRuntimeBase);
 424     size += numValues * sizeof(struct __CFArrayBucket);
 425     struct __CFArray *memory = (struct __CFArray*)_CFRuntimeCreateInstance(allocator, __kCFArrayTypeID, size, NULL);
 426     if (NULL == memory) {
 427         return NULL;
 428     }
 429     __CFBitfieldSetValue(memory->_base._cfinfo[CF_INFO_BITS], 6, 0, flags);
 430     __CFArraySetCount(memory, numValues);
 431     memmove(__CFArrayGetBucketsPtr(memory), values, sizeof(void *) * numValues);
 432     if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFArray (immutable)");
 433     return (CFArrayRef)memory;
 434 }
 435
 436 __private_extern__ CFArrayRef __CFArrayCreate0(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFArrayCallBacks *callBacks) {
 437     CFArrayRef result;
 438     const CFArrayCallBacks *cb;
 439     struct __CFArrayBucket *buckets;
 440     CFAllocatorRef bucketsAllocator;
 441     void* bucketsBase;
 442     CFIndex idx;
 443     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 444     result = __CFArrayInit(allocator, __kCFArrayImmutable, numValues, callBacks);
 445     cb = __CFArrayGetCallBacks(result);
 446     buckets = __CFArrayGetBucketsPtr(result);
 447     bucketsAllocator = isStrongMemory(result) ? allocator : kCFAllocatorNull;
 448     bucketsBase = CF_IS_COLLECTABLE_ALLOCATOR(bucketsAllocator) ? (void *)auto_zone_base_pointer(objc_collectableZone(), buckets) : NULL;
 449     if (NULL != cb->retain) {
 450         for (idx = 0; idx < numValues; idx++) {
 451             __CFAssignWithWriteBarrier((void **)&buckets->_item, (void *)INVOKE_CALLBACK2(cb->retain, allocator, *values));
 452             values++;
 453             buckets++;
 454         }
 455     }
 456     else {
 457         for (idx = 0; idx < numValues; idx++) {
 458             __CFAssignWithWriteBarrier((void **)&buckets->_item, (void *)*values);
 459             values++;
 460             buckets++;
 461         }
 462     }
 463     __CFArraySetCount(result, numValues);
 464     return result;
 465 }
 466
 467 __private_extern__ CFMutableArrayRef __CFArrayCreateMutable0(CFAllocatorRef allocator, CFIndex capacity, const CFArrayCallBacks *callBacks) {
 468     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 469     CFAssert2(capacity <= LONG_MAX / sizeof(void *), __kCFLogAssertion, "%s(): capacity (%d) is too large for this architecture", __PRETTY_FUNCTION__, capacity);
 470     return (CFMutableArrayRef)__CFArrayInit(allocator, __kCFArrayDeque, capacity, callBacks);
 471 }
 472
 473 __private_extern__ CFArrayRef __CFArrayCreateCopy0(CFAllocatorRef allocator, CFArrayRef array) {
 474     CFArrayRef result;
 475     const CFArrayCallBacks *cb;
 476     struct __CFArrayBucket *buckets;
 477     CFAllocatorRef bucketsAllocator;
 478     void* bucketsBase;
 479     CFIndex numValues = CFArrayGetCount(array);
 480     CFIndex idx;
 481     if (CF_IS_OBJC(__kCFArrayTypeID, array)) {
 482         cb = &kCFTypeArrayCallBacks;
 483     } else {
 484         cb = __CFArrayGetCallBacks(array);
 485             }
 486     result = __CFArrayInit(allocator, __kCFArrayImmutable, numValues, cb);
 487     cb = __CFArrayGetCallBacks(result); // GC: use the new array's callbacks so we don't leak.
 488     buckets = __CFArrayGetBucketsPtr(result);
 489     bucketsAllocator = isStrongMemory(result) ? allocator : kCFAllocatorNull;
 490         bucketsBase = CF_IS_COLLECTABLE_ALLOCATOR(bucketsAllocator) ? (void *)auto_zone_base_pointer(objc_collectableZone(), buckets) : NULL;
 491     for (idx = 0; idx < numValues; idx++) {
 492         const void *value = CFArrayGetValueAtIndex(array, idx);
 493         if (NULL != cb->retain) {
 494             value = (void *)INVOKE_CALLBACK2(cb->retain, allocator, value);
 495         }
 496         __CFAssignWithWriteBarrier((void **)&buckets->_item, (void *)value);
 497         buckets++;
 498     }
 499     __CFArraySetCount(result, numValues);
 500     return result;
 501 }
 502
 503 __private_extern__ CFMutableArrayRef __CFArrayCreateMutableCopy0(CFAllocatorRef allocator, CFIndex capacity, CFArrayRef array) {
 504     CFMutableArrayRef result;
 505     const CFArrayCallBacks *cb;
 506     CFIndex idx, numValues = CFArrayGetCount(array);
 507     UInt32 flags;
 508     if (CF_IS_OBJC(__kCFArrayTypeID, array)) {
 509         cb = &kCFTypeArrayCallBacks;
 510     }
 511     else {
 512         cb = __CFArrayGetCallBacks(array);
 513     }
 514     flags = __kCFArrayDeque;
 515     result = (CFMutableArrayRef)__CFArrayInit(allocator, flags, capacity, cb);
 516     if (0 == capacity) _CFArraySetCapacity(result, numValues);
 517     for (idx = 0; idx < numValues; idx++) {
 518         const void *value = CFArrayGetValueAtIndex(array, idx);
 519         CFArrayAppendValue(result, value);
 520     }
 521     return result;
 522 }
 523
 524 #define DEFINE_CREATION_METHODS 1
 525
 526 #if DEFINE_CREATION_METHODS
 527
 528 CFArrayRef CFArrayCreate(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFArrayCallBacks *callBacks) {
 529     return __CFArrayCreate0(allocator, values, numValues, callBacks);
 530 }
 531
 532 CFMutableArrayRef CFArrayCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFArrayCallBacks *callBacks) {
 533     return __CFArrayCreateMutable0(allocator, capacity, callBacks);
 534 }
 535
 536 CFArrayRef CFArrayCreateCopy(CFAllocatorRef allocator, CFArrayRef array) {
 537     return __CFArrayCreateCopy0(allocator, array);
 538 }
 539
 540 CFMutableArrayRef CFArrayCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFArrayRef array) {
 541     return __CFArrayCreateMutableCopy0(allocator, capacity, array);
 542 }
 543
 544 #endif
 545
 546 CFIndex CFArrayGetCount(CFArrayRef array) {
 547     CF_OBJC_FUNCDISPATCH0(__kCFArrayTypeID, CFIndex, array, "count");
 548     __CFGenericValidateType(array, __kCFArrayTypeID);
 549     CHECK_FOR_MUTATION(array);
 550     return __CFArrayGetCount(array);
 551 }
 552
 553
 554 CFIndex CFArrayGetCountOfValue(CFArrayRef array, CFRange range, const void *value) {
 555     CFIndex idx, count = 0;
 556     __CFGenericValidateType(array, __kCFArrayTypeID);
 557     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 558     CHECK_FOR_MUTATION(array);
 559     const CFArrayCallBacks *cb = CF_IS_OBJC(CFArrayGetTypeID(), array) ? &kCFTypeArrayCallBacks : __CFArrayGetCallBacks(array);
 560     for (idx = 0; idx < range.length; idx++) {
 561         const void *item = CFArrayGetValueAtIndex(array, range.location + idx);
 562         if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item))) {
 563             count++;
 564         }
 565     }
 566     return count;
 567 }
 568
 569 Boolean CFArrayContainsValue(CFArrayRef array, CFRange range, const void *value) {
 570     CFIndex idx;
 571     __CFGenericValidateType(array, __kCFArrayTypeID);
 572     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 573     CHECK_FOR_MUTATION(array);
 574     const CFArrayCallBacks *cb = CF_IS_OBJC(CFArrayGetTypeID(), array) ? &kCFTypeArrayCallBacks : __CFArrayGetCallBacks(array);
 575     for (idx = 0; idx < range.length; idx++) {
 576         const void *item = CFArrayGetValueAtIndex(array, range.location + idx);
 577         if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item))) {
 578             return true;
 579         }
 580     }
 581     return false;
 582 }
 583
 584 const void *CFArrayGetValueAtIndex(CFArrayRef array, CFIndex idx) {
 585     CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, void *, array, "objectAtIndex:", idx);
 586     __CFGenericValidateType(array, __kCFArrayTypeID);
 587     CFAssert2(0 <= idx && idx < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
 588     CHECK_FOR_MUTATION(array);
 589     return __CFArrayGetBucketAtIndex(array, idx)->_item;
 590 }
 591
 592 // This is for use by NSCFArray; it avoids ObjC dispatch, and checks for out of bounds
 593 const void *_CFArrayCheckAndGetValueAtIndex(CFArrayRef array, CFIndex idx) {
 594     CHECK_FOR_MUTATION(array);
 595     if (0 <= idx && idx < __CFArrayGetCount(array)) return __CFArrayGetBucketAtIndex(array, idx)->_item;
 596     return (void *)(-1);
 597 }
 598
 599
 600 void CFArrayGetValues(CFArrayRef array, CFRange range, const void **values) {
 601     CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "getObjects:range:", values, range);
 602     __CFGenericValidateType(array, __kCFArrayTypeID);
 603     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 604     CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__);
 605     CHECK_FOR_MUTATION(array);
 606     if (0 < range.length) {
 607         switch (__CFArrayGetType(array)) {
 608         case __kCFArrayImmutable:
 609         case __kCFArrayDeque:
 610             objc_memmove_collectable(values, __CFArrayGetBucketsPtr(array) + range.location, range.length * sizeof(struct __CFArrayBucket));
 611             break;
 612         }
 613     }
 614 }
 615
 616 CF_EXPORT unsigned long _CFArrayFastEnumeration(CFArrayRef array, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
 617     CHECK_FOR_MUTATION(array);
 618     if (array->_count == 0) return 0;
 619     enum { ATSTART = 0, ATEND = 1 };
 620     switch (__CFArrayGetType(array)) {
 621     case __kCFArrayImmutable:
 622         if (state->state == ATSTART) { /* first time */
 623             static const unsigned long const_mu = 1;
 624             state->state = ATEND;
 625             state->mutationsPtr = (unsigned long *)&const_mu;
 626             state->itemsPtr = (unsigned long *)__CFArrayGetBucketsPtr(array);
 627             return array->_count;
 628         }
 629         return 0;
 630     case __kCFArrayDeque:
 631         if (state->state == ATSTART) { /* first time */
 632             state->state = ATEND;
 633             state->mutationsPtr = (unsigned long *)&array->_mutations;
 634             state->itemsPtr = (unsigned long *)__CFArrayGetBucketsPtr(array);
 635             return array->_count;
 636         }
 637         return 0;
 638     }
 639     return 0;
 640 }
 641
 642
 643 void CFArrayApplyFunction(CFArrayRef array, CFRange range, CFArrayApplierFunction applier, void *context) {
 644     CFIndex idx;
 645     FAULT_CALLBACK((void **)&(applier));
 646     __CFGenericValidateType(array, __kCFArrayTypeID);
 647     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 648     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 649     CHECK_FOR_MUTATION(array);
 650     for (idx = 0; idx < range.length; idx++) {
 651         const void *item = CFArrayGetValueAtIndex(array, range.location + idx);
 652         INVOKE_CALLBACK2(applier, item, context);
 653     }
 654 }
 655
 656 CFIndex CFArrayGetFirstIndexOfValue(CFArrayRef array, CFRange range, const void *value) {
 657     CFIndex idx;
 658     __CFGenericValidateType(array, __kCFArrayTypeID);
 659     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 660     CHECK_FOR_MUTATION(array);
 661     const CFArrayCallBacks *cb = CF_IS_OBJC(CFArrayGetTypeID(), array) ? &kCFTypeArrayCallBacks : __CFArrayGetCallBacks(array);
 662     for (idx = 0; idx < range.length; idx++) {
 663         const void *item = CFArrayGetValueAtIndex(array, range.location + idx);
 664         if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item)))
 665             return idx + range.location;
 666     }
 667     return kCFNotFound;
 668 }
 669
 670 CFIndex CFArrayGetLastIndexOfValue(CFArrayRef array, CFRange range, const void *value) {
 671     CFIndex idx;
 672     __CFGenericValidateType(array, __kCFArrayTypeID);
 673     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 674     CHECK_FOR_MUTATION(array);
 675     const CFArrayCallBacks *cb = CF_IS_OBJC(CFArrayGetTypeID(), array) ? &kCFTypeArrayCallBacks : __CFArrayGetCallBacks(array);
 676     for (idx = range.length; idx--;) {
 677         const void *item = CFArrayGetValueAtIndex(array, range.location + idx);
 678         if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item)))
 679             return idx + range.location;
 680     }
 681     return kCFNotFound;
 682 }
 683
 684 void CFArrayAppendValue(CFMutableArrayRef array, const void *value) {
 685     CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, void, array, "addObject:", value);
 686     __CFGenericValidateType(array, __kCFArrayTypeID);
 687     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 688     CHECK_FOR_MUTATION(array);
 689     _CFArrayReplaceValues(array, CFRangeMake(__CFArrayGetCount(array), 0), &value, 1);
 690 }
 691
 692 void CFArraySetValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) {
 693     CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "setObject:atIndex:", value, idx);
 694     __CFGenericValidateType(array, __kCFArrayTypeID);
 695     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 696     CFAssert2(0 <= idx && idx <= __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
 697     CHECK_FOR_MUTATION(array);
 698     if (idx == __CFArrayGetCount(array)) {
 699         _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1);
 700     } else {
 701         BEGIN_MUTATION(array);
 702         const void *old_value;
 703         const CFArrayCallBacks *cb = __CFArrayGetCallBacks(array);
 704         CFAllocatorRef allocator = __CFGetAllocator(array);
 705         struct __CFArrayBucket *bucket = __CFArrayGetBucketAtIndex(array, idx);
 706         if (NULL != cb->retain && !hasBeenFinalized(array)) {
 707             value = (void *)INVOKE_CALLBACK2(cb->retain, allocator, value);
 708         }
 709         old_value = bucket->_item;
 710         __CFAssignWithWriteBarrier((void **)&bucket->_item, (void *)value); // GC: handles deque/CFStorage cases.
 711         if (NULL != cb->release && !hasBeenFinalized(array)) {
 712             INVOKE_CALLBACK2(cb->release, allocator, old_value);
 713         }
 714         array->_mutations++;
 715         END_MUTATION(array);
 716     }
 717 }
 718
 719 void CFArrayInsertValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) {
 720     CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "insertObject:atIndex:", value, idx);
 721     __CFGenericValidateType(array, __kCFArrayTypeID);
 722     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 723     CFAssert2(0 <= idx && idx <= __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
 724     CHECK_FOR_MUTATION(array);
 725     _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1);
 726 }
 727
 728 // NB: AddressBook on the Phone is a fragile flower, so this function cannot do anything
 729 // that causes the values to be retained or released.
 730 void CFArrayExchangeValuesAtIndices(CFMutableArrayRef array, CFIndex idx1, CFIndex idx2) {
 731     const void *tmp;
 732     struct __CFArrayBucket *bucket1, *bucket2;
 733     CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, void, array, "exchangeObjectAtIndex:withObjectAtIndex:", idx1, idx2);
 734     __CFGenericValidateType(array, __kCFArrayTypeID);
 735     CFAssert2(0 <= idx1 && idx1 < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index #1 (%d) out of bounds", __PRETTY_FUNCTION__, idx1);
 736     CFAssert2(0 <= idx2 && idx2 < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index #2 (%d) out of bounds", __PRETTY_FUNCTION__, idx2);
 737     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 738     CHECK_FOR_MUTATION(array);
 739     BEGIN_MUTATION(array);
 740     bucket1 = __CFArrayGetBucketAtIndex(array, idx1);
 741     bucket2 = __CFArrayGetBucketAtIndex(array, idx2);
 742     tmp = bucket1->_item;
 743     // XXX these aren't needed.
 744     __CFAssignWithWriteBarrier((void **)&bucket1->_item, (void *)bucket2->_item);
 745     __CFAssignWithWriteBarrier((void **)&bucket2->_item, (void *)tmp);
 746     array->_mutations++;
 747     END_MUTATION(array);
 748 }
 749
 750 void CFArrayRemoveValueAtIndex(CFMutableArrayRef array, CFIndex idx) {
 751     CF_OBJC_FUNCDISPATCH1(__kCFArrayTypeID, void, array, "removeObjectAtIndex:", idx);
 752     __CFGenericValidateType(array, __kCFArrayTypeID);
 753     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 754     CFAssert2(0 <= idx && idx < __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
 755     CHECK_FOR_MUTATION(array);
 756     _CFArrayReplaceValues(array, CFRangeMake(idx, 1), NULL, 0);
 757 }
 758
 759 void CFArrayRemoveAllValues(CFMutableArrayRef array) {
 760     CF_OBJC_FUNCDISPATCH0(__kCFArrayTypeID, void, array, "removeAllObjects");
 761     __CFGenericValidateType(array, __kCFArrayTypeID);
 762     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 763     CHECK_FOR_MUTATION(array);
 764     BEGIN_MUTATION(array);
 765     __CFArrayReleaseValues(array, CFRangeMake(0, __CFArrayGetCount(array)), true);
 766     __CFArraySetCount(array, 0);
 767     array->_mutations++;
 768     END_MUTATION(array);
 769 }
 770
 771 // may move deque storage, as it may need to grow deque
 772 static void __CFArrayRepositionDequeRegions(CFMutableArrayRef array, CFRange range, CFIndex newCount) {
 773     // newCount elements are going to replace the range, and the result will fit in the deque
 774     struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
 775     struct __CFArrayBucket *buckets;
 776     CFIndex cnt, futureCnt, numNewElems;
 777     CFIndex L, A, B, C, R;
 778
 779     buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque));
 780     cnt = __CFArrayGetCount(array);
 781     futureCnt = cnt - range.length + newCount;
 782
 783     L = deque->_leftIdx;                // length of region to left of deque
 784     A = range.location;                 // length of region in deque to left of replaced range
 785     B = range.length;                   // length of replaced range
 786     C = cnt - B - A;                    // length of region in deque to right of replaced range
 787     R = deque->_capacity - cnt - L;     // length of region to right of deque
 788     numNewElems = newCount - B;
 789
 790     CFIndex wiggle = deque->_capacity >> 17;
 791     if (wiggle < 4) wiggle = 4;
 792     if (deque->_capacity < (uint32_t)futureCnt || (cnt < futureCnt && L + R < wiggle)) {
 793         // must be inserting or space is tight, reallocate and re-center everything
 794         CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt + wiggle);
 795         CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket);
 796         CFAllocatorRef allocator = __CFGetAllocator(array);
 797         allocator = _CFConvertAllocatorToGCRefZeroEquivalent(allocator);
 798         Boolean collectableMemory = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
 799         struct __CFArrayDeque *newDeque = (struct __CFArrayDeque *)CFAllocatorAllocate(allocator, size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0);
 800         if (__CFOASafe) __CFSetLastAllocationEventName(newDeque, "CFArray (store-deque)");
 801         struct __CFArrayBucket *newBuckets = (struct __CFArrayBucket *)((uint8_t *)newDeque + sizeof(struct __CFArrayDeque));
 802         CFIndex oldL = L;
 803         CFIndex newL = (capacity - futureCnt) / 2;
 804         CFIndex oldC0 = oldL + A + B;
 805         CFIndex newC0 = newL + A + newCount;
 806         newDeque->_leftIdx = newL;
 807         newDeque->_capacity = capacity;
 808         if (0 < A) objc_memmove_collectable(newBuckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket));
 809         if (0 < C) objc_memmove_collectable(newBuckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket));
 810         __CFAssignWithWriteBarrier((void **)&array->_store, (void *)newDeque);
 811         if (!collectableMemory && deque) CFAllocatorDeallocate(allocator, deque);
 812 //printf("3:  array %p store is now %p (%lx)\n", array, array->_store, *(unsigned long *)(array->_store));
 813         return;
 814     }
 815
 816     if ((numNewElems < 0 && C < A) || (numNewElems <= R && C < A)) {    // move C
 817         // deleting: C is smaller
 818         // inserting: C is smaller and R has room
 819         CFIndex oldC0 = L + A + B;
 820         CFIndex newC0 = L + A + newCount;
 821         if (0 < C) objc_memmove_collectable(buckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket));
 822         // GrP GC: zero-out newly exposed space on the right, if any
 823         if (oldC0 > newC0) memset(buckets + newC0 + C, 0, (oldC0 - newC0) * sizeof(struct __CFArrayBucket));
 824     } else if ((numNewElems < 0) || (numNewElems <= L && A <= C)) {     // move A
 825         // deleting: A is smaller or equal (covers remaining delete cases)
 826         // inserting: A is smaller and L has room
 827         CFIndex oldL = L;
 828         CFIndex newL = L - numNewElems;
 829         deque->_leftIdx = newL;
 830         if (0 < A) objc_memmove_collectable(buckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket));
 831         // GrP GC: zero-out newly exposed space on the left, if any
 832         if (newL > oldL) memset(buckets + oldL, 0, (newL - oldL) * sizeof(struct __CFArrayBucket));
 833     } else {
 834         // now, must be inserting, and either:
 835         //    A<=C, but L doesn't have room (R might have, but don't care)
 836         //    C<A, but R doesn't have room (L might have, but don't care)
 837         // re-center everything
 838         CFIndex oldL = L;
 839         CFIndex newL = (L + R - numNewElems) / 2;
 840         newL = newL - newL / 2;
 841         CFIndex oldC0 = oldL + A + B;
 842         CFIndex newC0 = newL + A + newCount;
 843         deque->_leftIdx = newL;
 844         if (newL < oldL) {
 845             if (0 < A) objc_memmove_collectable(buckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket));
 846             if (0 < C) objc_memmove_collectable(buckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket));
 847             // GrP GC: zero-out newly exposed space on the right, if any
 848             if (oldC0 > newC0) memset(buckets + newC0 + C, 0, (oldC0 - newC0) * sizeof(struct __CFArrayBucket));
 849         } else {
 850             if (0 < C) objc_memmove_collectable(buckets + newC0, buckets + oldC0, C * sizeof(struct __CFArrayBucket));
 851             if (0 < A) objc_memmove_collectable(buckets + newL, buckets + oldL, A * sizeof(struct __CFArrayBucket));
 852             // GrP GC: zero-out newly exposed space on the left, if any
 853             if (newL > oldL) memset(buckets + oldL, 0, (newL - oldL) * sizeof(struct __CFArrayBucket));
 854         }
 855     }
 856 }
 857
 858 static void __CFArrayHandleOutOfMemory(CFTypeRef obj, CFIndex numBytes) {
 859     CFStringRef msg = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("Attempt to allocate %ld bytes for CFArray failed"), numBytes);
 860     {
 861         CFLog(kCFLogLevelCritical, CFSTR("%@"), msg);
 862         HALT;
 863     }
 864     CFRelease(msg);
 865 }
 866
 867 // This function is for Foundation's benefit; no one else should use it.
 868 void _CFArraySetCapacity(CFMutableArrayRef array, CFIndex cap) {
 869     if (CF_IS_OBJC(__kCFArrayTypeID, array)) return;
 870     __CFGenericValidateType(array, __kCFArrayTypeID);
 871     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 872     CFAssert3(__CFArrayGetCount(array) <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, __CFArrayGetCount(array));
 873     CHECK_FOR_MUTATION(array);
 874     BEGIN_MUTATION(array);
 875     // Currently, attempting to set the capacity of an array which is the CFStorage
 876     // variant, or set the capacity larger than __CF_MAX_BUCKETS_PER_DEQUE, has no
 877     // effect.  The primary purpose of this API is to help avoid a bunch of the
 878     // resizes at the small capacities 4, 8, 16, etc.
 879     if (__CFArrayGetType(array) == __kCFArrayDeque) {
 880         struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
 881         CFIndex capacity = __CFArrayDequeRoundUpCapacity(cap);
 882         CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket);
 883         CFAllocatorRef allocator = __CFGetAllocator(array);
 884         allocator = _CFConvertAllocatorToGCRefZeroEquivalent(allocator);
 885         Boolean collectableMemory = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
 886         if (NULL == deque) {
 887             deque = (struct __CFArrayDeque *)CFAllocatorAllocate(allocator, size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0);
 888             if (NULL == deque) __CFArrayHandleOutOfMemory(array, size);
 889             if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)");
 890             deque->_leftIdx = capacity / 2;
 891         } else {
 892             struct __CFArrayDeque *olddeque = deque;
 893             CFIndex oldcap = deque->_capacity;
 894             deque = (struct __CFArrayDeque *)CFAllocatorAllocate(allocator, size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0);
 895             if (NULL == deque) __CFArrayHandleOutOfMemory(array, size);
 896             objc_memmove_collectable(deque, olddeque, sizeof(struct __CFArrayDeque) + oldcap * sizeof(struct __CFArrayBucket));
 897             if (!collectableMemory) CFAllocatorDeallocate(allocator, olddeque);
 898             if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)");
 899         }
 900         deque->_capacity = capacity;
 901         __CFAssignWithWriteBarrier((void **)&array->_store, (void *)deque);
 902     }
 903     END_MUTATION(array);
 904 }
 905
 906
 907 void CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) {
 908     CF_OBJC_FUNCDISPATCH3(__kCFArrayTypeID, void, array, "replaceObjectsInRange:withObjects:count:", range, (void **)newValues, newCount);
 909     __CFGenericValidateType(array, __kCFArrayTypeID);
 910     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
 911     CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable", __PRETTY_FUNCTION__);
 912     CFAssert2(0 <= newCount, __kCFLogAssertion, "%s(): newCount (%d) cannot be less than zero", __PRETTY_FUNCTION__, newCount);
 913     CHECK_FOR_MUTATION(array);
 914     return _CFArrayReplaceValues(array, range, newValues, newCount);
 915 }
 916
 917 // This function does no ObjC dispatch or argument checking;
 918 // It should only be called from places where that dispatch and check has already been done, or NSCFArray
 919 void _CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) {
 920     CHECK_FOR_MUTATION(array);
 921     BEGIN_MUTATION(array);
 922     const CFArrayCallBacks *cb;
 923     CFIndex idx, cnt, futureCnt;
 924     const void **newv, *buffer[256];
 925     cnt = __CFArrayGetCount(array);
 926     futureCnt = cnt - range.length + newCount;
 927     CFAssert1(newCount <= futureCnt, __kCFLogAssertion, "%s(): internal error 1", __PRETTY_FUNCTION__);
 928     cb = __CFArrayGetCallBacks(array);
 929     CFAllocatorRef allocator = __CFGetAllocator(array);
 930
 931     /* Retain new values if needed, possibly allocating a temporary buffer for them */
 932     if (NULL != cb->retain && !hasBeenFinalized(array)) {
 933         newv = (newCount <= 256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, newCount * sizeof(void *), 0); // GC OK
 934         if (newv != buffer && __CFOASafe) __CFSetLastAllocationEventName(newv, "CFArray (temp)");
 935         for (idx = 0; idx < newCount; idx++) {
 936             newv[idx] = (void *)INVOKE_CALLBACK2(cb->retain, allocator, (void *)newValues[idx]);
 937         }
 938     } else {
 939         newv = newValues;
 940     }
 941     array->_mutations++;
 942
 943     /* Now, there are three regions of interest, each of which may be empty:
 944      *   A: the region from index 0 to one less than the range.location
 945      *   B: the region of the range
 946      *   C: the region from range.location + range.length to the end
 947      * Note that index 0 is not necessarily at the lowest-address edge
 948      * of the available storage. The values in region B need to get
 949      * released, and the values in regions A and C (depending) need
 950      * to get shifted if the number of new values is different from
 951      * the length of the range being replaced.
 952      */
 953     if (0 < range.length) {
 954         __CFArrayReleaseValues(array, range, false);
 955     }
 956     // region B elements are now "dead"
 957     if (0) {
 958     } else if (NULL == array->_store) {
 959         if (0) {
 960         } else if (0 <= futureCnt) {
 961             struct __CFArrayDeque *deque;
 962             CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt);
 963             CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket);
 964             deque = (struct __CFArrayDeque *)CFAllocatorAllocate(_CFConvertAllocatorToGCRefZeroEquivalent(allocator), size, isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0);
 965             if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)");
 966             deque->_leftIdx = (capacity - newCount) / 2;
 967             deque->_capacity = capacity;
 968             __CFAssignWithWriteBarrier((void **)&array->_store, (void *)deque);
 969         }
 970     } else {            // Deque
 971         // reposition regions A and C for new region B elements in gap
 972         if (0) {
 973         } else if (range.length != newCount) {
 974             __CFArrayRepositionDequeRegions(array, range, newCount);
 975         }
 976     }
 977     // copy in new region B elements
 978     if (0 < newCount) {
 979         if (0) {
 980         } else {        // Deque
 981             struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store;
 982             struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque));
 983             objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket));
 984         }
 985     }
 986     __CFArraySetCount(array, futureCnt);
 987     if (newv != buffer && newv != newValues) CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv);
 988     END_MUTATION(array);
 989 }
 990
 991 struct _acompareContext {
 992     CFComparatorFunction func;
 993     void *context;
 994 };
 995
 996 static CFComparisonResult __CFArrayCompareValues(const void *v1, const void *v2, struct _acompareContext *context) {
 997     const void **val1 = (const void **)v1;
 998     const void **val2 = (const void **)v2;
 999     return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
1000 }
1001
1002 CF_INLINE void __CFZSort(CFMutableArrayRef array, CFRange range, CFComparatorFunction comparator, void *context) {
1003     CFIndex cnt = range.length;
1004     while (1 < cnt) {
1005         for (CFIndex idx = range.location; idx < range.location + cnt - 1; idx++) {
1006             const void *a = CFArrayGetValueAtIndex(array, idx);
1007             const void *b = CFArrayGetValueAtIndex(array, idx + 1);
1008             if ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, b, a, context)) < 0) {
1009                 CFArrayExchangeValuesAtIndices(array, idx, idx + 1);
1010             }
1011         }
1012         cnt--;
1013     }
1014 }
1015
1016 __private_extern__ void _CFArraySortValues(CFMutableArrayRef array, CFComparatorFunction comparator, void *context) {
1017     CFRange range = {0, CFArrayGetCount(array)};
1018     if (range.length < 2) {
1019         return;
1020     }
1021     // implemented abstractly, careful!
1022     const void **values, *buffer[256];
1023     values = (range.length <= 256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, range.length * sizeof(void *), 0); // GC OK
1024     CFArrayGetValues(array, range, values);
1025     struct _acompareContext ctx;
1026     ctx.func = comparator;
1027     ctx.context = context;
1028     CFQSortArray(values, range.length, sizeof(void *), (CFComparatorFunction)__CFArrayCompareValues, &ctx);
1029     CFArrayReplaceValues(array, range, values, range.length);
1030     if (values != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, values);
1031 }
1032
1033 void CFArraySortValues(CFMutableArrayRef array, CFRange range, CFComparatorFunction comparator, void *context) {
1034     FAULT_CALLBACK((void **)&(comparator));
1035     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
1036     CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
1037     Boolean immutable = false;
1038     if (CF_IS_OBJC(__kCFArrayTypeID, array)) {
1039         BOOL result;
1040         CF_OBJC_CALL1(BOOL, result, array, "isKindOfClass:", objc_lookUpClass("NSMutableArray"));
1041         immutable = !result;
1042     } else if (__kCFArrayImmutable == __CFArrayGetType(array)) {
1043         immutable = true;
1044     }
1045     const CFArrayCallBacks *cb = NULL;
1046     if (CF_IS_OBJC(__kCFArrayTypeID, array)) {
1047         cb = &kCFTypeArrayCallBacks;
1048     } else {
1049         cb = __CFArrayGetCallBacks(array);
1050     }
1051     if (!immutable && ((cb->retain && !cb->release) || (!cb->retain && cb->release))) {
1052         __CFZSort(array, range, comparator, context);
1053         return;
1054     }
1055     if (range.length < 2) {
1056         return;
1057     }
1058     // implemented abstractly, careful!
1059     const void **values, *buffer[256];
1060     values = (range.length <= 256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, range.length * sizeof(void *), 0); // GC OK
1061     CFArrayGetValues(array, range, values);
1062     struct _acompareContext ctx;
1063     ctx.func = comparator;
1064     ctx.context = context;
1065     CFQSortArray(values, range.length, sizeof(void *), (CFComparatorFunction)__CFArrayCompareValues, &ctx);
1066     if (!immutable) CFArrayReplaceValues(array, range, values, range.length);
1067     if (values != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, values);
1068 }
1069
1070 CFIndex CFArrayBSearchValues(CFArrayRef array, CFRange range, const void *value, CFComparatorFunction comparator, void *context) {
1071     FAULT_CALLBACK((void **)&(comparator));
1072     __CFArrayValidateRange(array, range, __PRETTY_FUNCTION__);
1073     CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
1074     // implemented abstractly, careful!
1075     if (range.length <= 0) return range.location;
1076     const void *item = CFArrayGetValueAtIndex(array, range.location + range.length - 1);
1077     if ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, item, value, context)) < 0) {
1078         return range.location + range.length;
1079     }
1080     item = CFArrayGetValueAtIndex(array, range.location);
1081     if ((CFComparisonResult)(INVOKE_CALLBACK3(comparator, value, item, context)) < 0) {
1082         return range.location;
1083     }
1084     SInt32 lg = flsl(range.length) - 1; // lg2(range.length)
1085     item = CFArrayGetValueAtIndex(array, range.location + -1 + (1 << lg));
1086     // idx will be the current probe index into the range
1087     CFIndex idx = (comparator(item, value, context) < 0) ? range.length - (1 << lg) : -1;
1088     while (lg--) {
1089         item = CFArrayGetValueAtIndex(array, range.location + idx + (1 << lg));
1090         if (comparator(item, value, context) < 0) {
1091             idx += (1 << lg);
1092         }
1093     }
1094     idx++;
1095     return idx + range.location;
1096 }
1097
1098 void CFArrayAppendArray(CFMutableArrayRef array, CFArrayRef otherArray, CFRange otherRange) {
1099     __CFArrayValidateRange(otherArray, otherRange, __PRETTY_FUNCTION__);
1100     // implemented abstractly, careful!
1101     for (CFIndex idx = otherRange.location; idx < otherRange.location + otherRange.length; idx++) {
1102         CFArrayAppendValue(array, CFArrayGetValueAtIndex(otherArray, idx));
1103     }
1104 }
1105
1106