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