CFArray.c

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