Collections.subproj/CFArray.c

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