CFArray.c

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