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