Collections.subproj/CFArray.c

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