CFArray.c

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