CFArray.c

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