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/* CFStorage.c 25 Copyright (c) 1999-2013, Apple Inc. All rights reserved. 26 Responsibility: Ali Ozer 27 */ 28 29/* 30 2-3 tree storing arbitrary sized values. 31 32 ??? Currently elementSize cannot be greater than storage->maxLeafCapacity, which is less than or equal to __CFStorageMaxLeafCapacity 33 34 CFStorage is thread-safe for multiple readers, but not thread safe for simultaneous reading and writing. 35 */ 36 37 38/* pammon notes on FrozenStorage 39 A CFStorage can be frozen, or more specifically, some or all of the nodes can be frozen. Frozen nodes can be safely shared between CFStorage instances. CFStorages containing frozen nodes are still considered mutable: frozen nodes are discarded and recreated on demand. It is a form of copy-on-write. 40 41 Freezing is usually one-way: there is no going back. However, if a node's reference count is 1, we know that no other CFStorage can reference it; and if we are in a mutating function, we know that it can be safely unfrozen. 42 43 If a node is frozen, all of its descendants should be considered frozen. 44 45 The root node, which is defined inline within the CFStorage struct itself, can never be frozen. 46 47 */ 48 49#define NO_SHIFTER ((uint32_t)(-1)) 50 51#include <CoreFoundation/CFStorage.h> 52#include "CFInternal.h" 53#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS 54#include <dispatch/dispatch.h> 55#endif 56 57#if DEPLOYMENT_TARGET_WINDOWS 58// No C99 support 59#define restrict 60 61// Replace bzero 62#define bzero(dst, size) ZeroMemory(dst, size) 63 64#endif 65 66#if !defined(PAGE_SIZE) 67#define PAGE_SIZE 4096 68#endif 69 70// Above 15K, malloc switches (??? or used to in early Leopard) to using vm allocates for blocks; it seems best to avoid that. 71// Also, tests with StorageTimer.c done in 4/07 indicate that 4096 * 3 is better than smaller or larger node sizes. 72#define __CFStorageMaxLeafCapacity (4096 * 3) 73 74#define COPYMEM(src,dst,n) objc_memmove_collectable((dst), (src), (n)) 75#define PAGE_LIMIT ((CFIndex)PAGE_SIZE / 2) 76 77CF_INLINE int32_t roundToPage(int32_t num) { 78 return (num + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1); 79} 80 81typedef const struct __CFStorage *ConstCFStorageRef; 82 83/* Each node in the storage. isLeaf determines whether the node is a leaf node or a node inside the tree. If latter, number of children are determined by the number of non-NULL entries in child[]. (NULL entries are at the end.) 84 */ 85typedef struct __CFStorageNode { 86 CFIndex numBytes; /* Number of actual bytes in this node and all its children */ 87 uint32_t refCount; /* Refcount of the node. Is always at least 1 for a normal node. For root nodes, which are stored directly in the CFStorage, this is 0. CFStorageRetain/ReleaseNode checks for a refcount of 0 and does not retain/release such nodes. */ 88 bool isFrozen; /* Indicates that the node is frozen, i.e. may be shared. */ 89 bool isLeaf; 90 union { 91 struct { 92 CFIndex capacityInBytes; // capacityInBytes is capacity of memory; this is either 0, or >= numBytes 93 uint8_t *memory; 94 CFRange cachedRange; //the absolute range of this node, in "value" units. This is valid only if this node is referenced by storage->cacheNode, and used by the cache. In general this is not valid, and the offset needs to be passed down from the tree 95 } leaf; 96 struct { 97 struct __CFStorageNode *child[3]; 98 } notLeaf; 99 } info; 100} CFStorageNode; 101 102 103/* A struct used for insertion into frozen nodes, which may need to return a new version of themselves, and a new friend! The child field is a replacement for the child that was inserted into; if the child does not need to be replaced (i.e. it was unfrozen and there was space to perform the insertion) then the child that was inserted into is returned here. The sibling field is a new child that should also be inserted (or NULL if none). */ 104typedef struct { 105 CFStorageNode *child; 106 CFStorageNode *sibling; 107} CFStorageDoubleNodeReturn; 108 109CF_INLINE CFStorageDoubleNodeReturn CFStorageDoubleNodeReturnMake(CFStorageNode *child, CFStorageNode *sibling) { 110 CFStorageDoubleNodeReturn v; 111 v.child = child; 112 v.sibling = sibling; 113 return v; 114} 115 116/* The CFStorage object. 117 */ 118struct __CFStorage { 119 CFRuntimeBase base; 120 CFIndex valueSize; 121 uint32_t byteToValueShifter; 122 CFSpinLock_t cacheReaderMemoryAllocationLock; 123 bool alwaysFrozen; 124 CFStorageNode * volatile cacheNode; 125 CFIndex maxLeafCapacity; // In terms of bytes 126 CFStorageNode rootNode; 127 CFOptionFlags nodeHint; // __kCFAllocatorGCScannedMemory or 0. 128}; 129 130/* Helper function to return the intersection of two ranges */ 131static inline CFRange intersectionRange(CFRange a, CFRange b) { 132 CFIndex start = __CFMax(a.location, b.location); 133 CFIndex end = __CFMin(a.location + a.length, b.location + b.length); 134 if (end <= start) { 135 return CFRangeMake(0, 0); 136 } 137 else { 138 return CFRangeMake(start, end - start); 139 } 140} 141 142/* Allocates the memory and initializes the capacity in a leaf. This locks not for mutations (mutations are not thread-safe in general), but for lazy allocation of storage during reading. 143 */ 144CF_INLINE void __CFStorageAllocLeafNodeMemory(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap, bool compact) { 145 if (cap > PAGE_LIMIT) { 146 cap = roundToPage(cap); 147 if (cap > storage->maxLeafCapacity) cap = storage->maxLeafCapacity; 148 } else { 149 cap = (((cap + 63) / 64) * 64); 150 } 151 /* We must be careful here, because another thread may be trying to allocate this memory at the same time (8203146). This may happen if two threads both attempt to read from a lazily-allocated node. */ 152 if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) { 153 __CFSpinLock(&(storage->cacheReaderMemoryAllocationLock)); 154 /* Check again now that we've acquired the lock. We know that we can do this because two simulaneous readers will always pass the same capacity. This is the fix for 8203146. This probably needs a memory barrier. */ 155 if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) { 156 __CFAssignWithWriteBarrier((void **)&node->info.leaf.memory, _CFAllocatorReallocateGC(allocator, node->info.leaf.memory, cap, storage->nodeHint)); // This will free... 157 if (__CFOASafe) __CFSetLastAllocationEventName(node->info.leaf.memory, "CFStorage (node bytes)"); 158 node->info.leaf.capacityInBytes = cap; 159 } 160 __CFSpinUnlock(&(storage->cacheReaderMemoryAllocationLock)); 161 } 162} 163 164#if 0 165#define ASSERT(x) do { if (! (x)) { fprintf(stderr, "Assertion %s failed on line %d\n", #x, __LINE__); HALT; } } while (0) 166#else 167#define ASSERT(x) do { if (0 && ! (x)) { } } while(0) 168#endif 169 170static void __CFStorageCheckIntegrity(CFStorageRef storage); 171#define CHECK_INTEGRITY() do { if (0) __CFStorageCheckIntegrity(storage); } while (0) 172 173static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node); 174#define CHECK_NODE_INTEGRITY(X) do { if (0) __CFStorageCheckNodeIntegrity(storage, X); } while (0) 175 176#pragma mark Byte <-> Value Functions 177 178CF_INLINE CFIndex __CFStorageConvertByteToValue(ConstCFStorageRef storage, CFIndex byte) { 179 if (storage->byteToValueShifter != NO_SHIFTER) { 180 return byte >> storage->byteToValueShifter; 181 } 182 return byte / storage->valueSize; 183} 184 185CF_INLINE CFRange __CFStorageConvertBytesToValueRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) { 186 if (storage->byteToValueShifter != NO_SHIFTER) { 187 return CFRangeMake(offset >> storage->byteToValueShifter, length >> storage->byteToValueShifter); 188 } 189 return CFRangeMake(offset / storage->valueSize, length / storage->valueSize); 190} 191 192CF_INLINE CFIndex __CFStorageConvertValueToByte(ConstCFStorageRef storage, CFIndex value) { 193 if (storage->byteToValueShifter != NO_SHIFTER) { 194 return value << storage->byteToValueShifter; 195 } 196 return value * storage->valueSize; 197} 198 199CF_INLINE CFRange __CFStorageConvertValuesToByteRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) { 200 if (storage->byteToValueShifter != NO_SHIFTER) { 201 return CFRangeMake(offset << storage->byteToValueShifter, length << storage->byteToValueShifter); 202 } 203 return CFRangeMake(offset * storage->valueSize, length * storage->valueSize); 204} 205 206 207#pragma mark Node reference counting and freezing 208 209CF_INLINE CFStorageNode *__CFStorageRetainNode(CFStorageNode *node) { 210 if (node->refCount > 0) OSAtomicIncrement32((int32_t *)&node->refCount); 211 return node; 212} 213 214/* A faster version of __CFStorageRetainNode that is not thread safe. This can be used from the Unfrozen (aka unshared) calls, or when a node was just allocated and there's no opportunity for it to have escaped yet */ 215CF_INLINE CFStorageNode *__CFStorageRetainNodeThreadUnsafe(CFStorageNode *node) { 216 if (node->refCount > 0) node->refCount++; 217 return node; 218} 219 220static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node); 221 222CF_INLINE void __CFStorageReleaseNode(CFStorageRef storage, CFStorageNode *node) { 223 if (node->refCount > 0) { 224 uint32_t newRefCount = OSAtomicDecrement32((int32_t *)&node->refCount); 225 if (newRefCount == 0) { 226 __CFStorageDeallocateNode(storage, node); 227 } 228 } 229} 230 231CF_INLINE void __CFStorageReleaseNodeWithNullCheck(CFStorageRef storage, CFStorageNode *node) { 232 if (node) __CFStorageReleaseNode(storage, node); 233} 234 235static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node) { 236 CFAllocatorRef allocator = CFGetAllocator(storage); 237 if (node->isLeaf) { 238 if (node->info.leaf.memory) _CFAllocatorDeallocateGC(allocator, node->info.leaf.memory); 239 } else { 240 __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[0]); 241 __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]); 242 __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]); 243 } 244 _CFAllocatorDeallocateGC(allocator, node); 245} 246 247static inline void __CFStorageFreezeNode(CFStorageNode *node) { 248 node->isFrozen = true; 249} 250 251/* If a node is frozen, but its reference count is 1, then we are the only reference to it and we can unfreeze it. In general, it's unsafe to do this because it may race with other threads that depend on it being frozen (e.g. we are about to copy the node). However, we do not support concurrent access while mutating a CFStorage, so if we are in a mutation function, know we have exclusive access and we can unfreeze the node. */ 252static inline bool __CFStorageThawNodeDuringMutation(CFStorageRef storage, CFStorageNode *node) { 253 if (node->refCount == 1) { 254 node->isFrozen = false; 255 return true; 256 } 257 return false; 258} 259 260static inline void __CFStorageSetChild(CFStorageNode *parentNode, CFIndex childIndex, CFStorageNode *newChild) { 261 ASSERT(! parentNode->isLeaf); 262 ASSERT(childIndex < 3); 263 __CFAssignWithWriteBarrier((void **)&parentNode->info.notLeaf.child[childIndex], newChild); 264} 265 266static inline void __CFStorageGetChildren(const CFStorageNode *parent, CFStorageNode ** restrict resultArray, bool shouldRetain, bool shouldFreeze) { 267 ASSERT(! parent->isLeaf); 268 CFIndex i; 269 for (i=0; i < 3; i++) { 270 CFStorageNode *node = parent->info.notLeaf.child[i]; 271 if (node != NULL && shouldRetain) __CFStorageRetainNode(node); 272 if (node != NULL && shouldFreeze) __CFStorageFreezeNode(node); 273 resultArray[i] = node; 274 } 275} 276 277#pragma mark Storage cache handling 278 279 280/* Sets the cache to point at the specified node. loc and len are in terms of values, not bytes. To clear the cache set these two to 0. 281 At least one of node or memory should be non-NULL. memory is consulted first when using the cache. 282 */ 283CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, CFIndex locInBytes) { 284 if (node) { 285 ASSERT(node->isLeaf); 286 node->info.leaf.cachedRange = __CFStorageConvertBytesToValueRange(storage, locInBytes, node->numBytes); 287 } 288 storage->cacheNode = node; 289} 290 291/* Gets the location for the specified absolute loc from the cached info. 292 Returns NULL if the location is not in the cache. 293 */ 294CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc, CFRange * restrict validConsecutiveValueRange, bool requireUnfrozenNode) { 295 CFStorageNode * const cachedNode = storage->cacheNode; /* It's important we read from this field no more than once, for thread safety with other concurrent reads; that is why the field is marked volatile. */ 296 if (! cachedNode) return NULL; /* No cache */ 297 298 /* We only allow caching leaf nodes. */ 299 ASSERT(cachedNode->isLeaf); 300 301 /* If the node is frozen, and we require an unfrozen node, then return NULL */ 302 if (requireUnfrozenNode && cachedNode->isFrozen) return NULL; 303 304 /* If there's no memory allocated yet, then allocate it now*/ 305 if (! cachedNode->info.leaf.memory) { 306 __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, cachedNode, cachedNode->numBytes, false); 307 } 308 309 /* If the node's range starts after loc, or ends before or at loc, return NULL */ 310 CFIndex nodeOffset = cachedNode->info.leaf.cachedRange.location; 311 CFIndex nodeLength = cachedNode->info.leaf.cachedRange.length; 312 if (loc < nodeOffset || loc >= nodeOffset + nodeLength) { 313 return NULL; 314 } 315 316 /* The cache is valid, so return it */ 317 validConsecutiveValueRange->location = nodeOffset; 318 validConsecutiveValueRange->length = nodeLength; 319 uint8_t *result = cachedNode->info.leaf.memory + __CFStorageConvertValueToByte(storage, loc - nodeOffset); 320 return result; 321} 322 323 324/* Returns the number of the child containing the desired value and the relative index of the value in that child. 325 forInsertion = true means that we are looking for the child in which to insert or delete; this changes the behavior when the index is at the end of a child 326 relativeByteNum (not optional, for performance reasons) returns the relative byte number of the specified byte in the child. 327 Don't call with leaf nodes! 328 */ 329CF_INLINE CFStorageNode *__CFStorageFindChild(const CFStorageNode * restrict node, CFIndex byteNum, bool forInsertionOrDeletion, CFIndex * restrict childNum, CFIndex * restrict relativeByteNum) { 330 if (forInsertionOrDeletion) byteNum--; /* If for insertion, we do <= checks, not <, so this accomplishes the same thing */ 331 CFStorageNode *result; 332 result = node->info.notLeaf.child[0]; 333 if (byteNum < result->numBytes) *childNum = 0; 334 else { 335 byteNum -= result->numBytes; 336 result = node->info.notLeaf.child[1]; 337 if (byteNum < result->numBytes) *childNum = 1; 338 else { 339 byteNum -= result->numBytes; 340 *childNum = 2; 341 result = node->info.notLeaf.child[2]; 342 } 343 } 344 if (forInsertionOrDeletion) byteNum++; 345 *relativeByteNum = byteNum; 346 return result; 347} 348 349static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node); 350 351/* Finds the location where the specified byte is stored. If validConsecutiveByteRange is not NULL, returns 352 the range of bytes that are consecutive with this one. 353 !!! Assumes the byteNum is within the range of this node. 354 */ 355static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex absoluteByteOffsetOfNode, CFStorageNode **resultNode, CFRange *validConsecutiveByteRange, bool requireUnfreezing) { 356 if (node->isLeaf) { 357 *validConsecutiveByteRange = CFRangeMake(absoluteByteOffsetOfNode, node->numBytes); 358 *resultNode = node; 359 __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false); 360 return node->info.leaf.memory + byteNum; 361 } else { 362 CFIndex childNum; 363 CFIndex relativeByteNum; 364 CFStorageNode *child = __CFStorageFindChild(node, byteNum, false, &childNum, &relativeByteNum); 365 if (requireUnfreezing && child->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, child)) { 366 /* Replace the child with an unfrozen variant */ 367 CFStorageNode *unfrozenReplacement = __CFStorageCopyNode(storage, child); 368 /* Release the old node, set the new one */ 369 __CFStorageSetChild(node, childNum, unfrozenReplacement); 370 __CFStorageReleaseNode(storage, child); 371 child = unfrozenReplacement; 372 } 373 return __CFStorageFindByte(storage, child, relativeByteNum, absoluteByteOffsetOfNode + (byteNum - relativeByteNum), resultNode, validConsecutiveByteRange, requireUnfreezing); 374 } 375} 376 377/* Guts of CFStorageGetValueAtIndex(); note that validConsecutiveValueRange is not optional. 378 Consults and updates cache. 379 */ 380CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange, bool requireUnfreezing) { 381 uint8_t *result; 382 if (!(result = __CFStorageGetFromCache(storage, idx, validConsecutiveValueRange, requireUnfreezing))) { 383 CFStorageNode *resultNode; 384 CFRange rangeInBytes; 385 result = (uint8_t *)__CFStorageFindByte(storage, &storage->rootNode, __CFStorageConvertValueToByte(storage, idx), 0, &resultNode, &rangeInBytes, requireUnfreezing); 386 __CFStorageSetCache(storage, resultNode, rangeInBytes.location); 387 *validConsecutiveValueRange = __CFStorageConvertBytesToValueRange(storage, rangeInBytes.location, rangeInBytes.length); 388 } 389 return result; 390} 391 392/* Copies data in the range srcRange from srcLeaf to index dstLocation in dstLeaf. Both srcLeaf and dstLeaf must be leaf nodes, and dstLeaf must not be frozen. If srcRange has a nonzero length, then both must have their memory properly allocated. This does not modify the numBytes of srcLeaf or dstLeaf. 393 */ 394static void __CFLeafCopyRangeToOffset(const CFStorageNode *srcLeaf, CFRange srcRange, CFStorageNode *dstLeaf, CFIndex dstLocation) { 395 ASSERT(srcLeaf->isLeaf); 396 ASSERT(dstLeaf->isLeaf); 397 if (srcRange.length > 0) { 398 ASSERT(srcLeaf->info.leaf.memory != NULL); 399 ASSERT(dstLeaf->info.leaf.memory != NULL); 400 ASSERT(srcRange.location + srcRange.length <= srcLeaf->numBytes); 401 ASSERT(dstLocation + srcRange.length <= dstLeaf->info.leaf.capacityInBytes); 402 COPYMEM(srcLeaf->info.leaf.memory + srcRange.location, dstLeaf->info.leaf.memory + dstLocation, srcRange.length); 403 } 404} 405 406#pragma mark Node creation and destruction 407 408// returns a node with a refCount of 1, and an auto_zone_retain() under GC 409static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, CFStorageRef storage, bool isLeaf, CFIndex numBytes) { 410 CFStorageNode *newNode = (CFStorageNode *)CFAllocatorAllocate(allocator, sizeof(CFStorageNode), __kCFAllocatorGCScannedMemory); 411 if (__CFOASafe) __CFSetLastAllocationEventName(newNode, "CFStorage (node)"); 412 if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { 413 auto_zone_release(objc_collectableZone(), newNode); //remove the implicit retain so we can be collected 414 } 415 newNode->refCount = 1; 416 newNode->isFrozen = storage->alwaysFrozen; 417 newNode->isLeaf = isLeaf; 418 newNode->numBytes = numBytes; 419 if (isLeaf) { 420 newNode->info.leaf.capacityInBytes = 0; 421 newNode->info.leaf.memory = NULL; 422 } else { 423 newNode->info.notLeaf.child[0] = newNode->info.notLeaf.child[1] = newNode->info.notLeaf.child[2] = NULL; 424 } 425 return newNode; 426} 427 428/* Creates an (unfrozen) copy of the given node. This is shallow in the sense that it shares children for branches, but deep in that it copies memory for leaves. */ 429static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node) { 430 CFAllocatorRef allocator = CFGetAllocator(storage); 431 CFStorageNode *result = __CFStorageCreateNode(allocator, storage, node->isLeaf, node->numBytes); 432 if (node->isLeaf) { 433 if (node->info.leaf.memory != NULL) { 434 __CFStorageAllocLeafNodeMemory(allocator, storage, result, result->numBytes, false); 435 COPYMEM(node->info.leaf.memory, result->info.leaf.memory, result->numBytes); 436 } 437 } 438 else { 439 CFStorageNode *child = node->info.notLeaf.child[0]; 440 __CFStorageSetChild(result, 0, __CFStorageRetainNode(child)); 441 if ((child = node->info.notLeaf.child[1])) __CFStorageSetChild(result, 1, __CFStorageRetainNode(child)); 442 if ((child = node->info.notLeaf.child[2])) __CFStorageSetChild(result, 2, __CFStorageRetainNode(child)); 443 444 /* If we are copying children from a frozen node to an unfrozen node, we need to freeze the children */ 445 if (node->isFrozen) { 446 __CFStorageFreezeNode(result->info.notLeaf.child[0]); 447 if ((child = result->info.notLeaf.child[1])) __CFStorageFreezeNode(child); 448 if ((child = result->info.notLeaf.child[2])) __CFStorageFreezeNode(child); 449 } 450 } 451 return result; 452} 453 454 455static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node); 456 457 458#pragma mark Insertion and Deletion prototypes 459/* Prototypes for deletion and insertion. The *Frozen and *Unfrozen variants should only be called for nodes that we know are frozen or unfrozen. Frozen nodes may only have frozen children, so it makes sense for the Frozen functions to call other Frozen functions. Unfrozen nodes may have frozen or unfrozen children, so they should call the non-suffixed variants (which dispatch on whether the node is frozen or not). 460 461 The only acceptable time to directly call the Unfrozen variant is for the root node of a CFStorage, because root nodes may never be frozen. The isRootNode parameter determines whether we are in this case. 462 463 The Insertion functions return two nodes. As an awful performance hack, if the first node returned from __CFStorageInsert* is the same as the node passed in, that node is *not* retained, so should not be relased. If it is a different node, it is retained. 464 */ 465static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum); 466static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact); 467 468static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum); 469static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range); 470 471static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum); 472static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode); 473 474#pragma mark Frozen Deletion 475 476static CFStorageNode *__CFStorageDeleteLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) { 477 ASSERT(node->isLeaf); 478 const CFIndex rangeToDeleteEnd = range.location + range.length; 479 ASSERT(rangeToDeleteEnd <= node->numBytes); 480 CFIndex remainingBytes = node->numBytes - range.length; 481 if (remainingBytes == 0) { 482 /* The range to delete encompasses our entire range of bytes. Return NULL to indicate that we should be deleted. */ 483 return NULL; 484 } 485 else { 486 /* Need to create a new node */ 487 CFStorageNode *newNode = __CFStorageCreateNode(allocator, storage, true, remainingBytes); 488 if (node->info.leaf.memory) { 489 /* Our node had memory allocated, so copy in the non-deleted portion */ 490 CFRange nonDeletedPrefix = CFRangeMake(0, range.location); 491 CFRange nonDeletedSuffix = CFRangeMake(rangeToDeleteEnd, node->numBytes - rangeToDeleteEnd); 492 ASSERT(nonDeletedPrefix.length + nonDeletedSuffix.length == remainingBytes); 493 __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, remainingBytes, false); // no point in compacting since we're freshly allocated 494 __CFLeafCopyRangeToOffset(node, nonDeletedPrefix, newNode, 0); 495 __CFLeafCopyRangeToOffset(node, nonDeletedSuffix, newNode, nonDeletedPrefix.length); 496 } 497 return newNode; 498 } 499} 500 501/* Helper function for both frozen and unfrozen branch deletion. Walks the children of the node, calling __CFStorageDelete (or __CFStorageDeleteFrozen if childrenAreDefinitelyFrozen is YES), and assigning the results back to newChildren. Returns the number of new children. The newChildren nodes all acquire a reference count! 502 */ 503static inline CFIndex __CFStoragePopulateBranchChildrenAfterDeletion(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range, CFStorageNode *newChildren[3], bool childrenAreDefinitelyFrozen, bool compact) { 504 CFIndex newChildIndex = 0; 505 CFIndex childByteOffset = 0; //will track the current start byte of this child 506 for (CFIndex existingChildIndex = 0; existingChildIndex < 3; existingChildIndex++) { 507 CFStorageNode *existingChild = node->info.notLeaf.child[existingChildIndex]; 508 if (! existingChild) break; //no more children 509 const CFIndex existingChildLength = existingChild->numBytes; 510 /* The child's range is {byteOffset, existingChildLength}. Figure out what part of the range to delete is intersected by this child's range */ 511 CFRange deletionRangeIntersectedByChild = intersectionRange(range, CFRangeMake(childByteOffset, existingChildLength)); 512 if (! deletionRangeIntersectedByChild.length) { 513 /* The range to delete does not overlap this child's range, so preserve the child */ 514 newChildren[newChildIndex++] = __CFStorageRetainNode(existingChild); //bump the refcount like we promised we would 515 if (childrenAreDefinitelyFrozen) { 516 /* Because we are about to add this child from a frozen node to a possibly unfrozen node, mark the child as frozen */ 517 __CFStorageFreezeNode(existingChild); 518 } 519 } 520 else { 521 /* We have something from this child to delete */ 522 CFRange rangeOfChildToDelete = CFRangeMake(deletionRangeIntersectedByChild.location - childByteOffset, deletionRangeIntersectedByChild.length); 523 CFStorageNode *newChild; 524 if (childrenAreDefinitelyFrozen) { 525 newChild = __CFStorageDeleteFrozen(allocator, storage, existingChild, rangeOfChildToDelete); 526 } 527 else { 528 newChild = __CFStorageDelete(allocator, storage, existingChild, rangeOfChildToDelete, compact); 529 } 530 /* We may get null back if we deleted the entire child */ 531 if (newChild != NULL) { 532 newChildren[newChildIndex++] = newChild; // Transfers the reference count 533 } 534 535 if (rangeOfChildToDelete.length == existingChildLength) { 536 ASSERT(newChild == NULL); //should have deleted everything 537 } 538 else { 539 ASSERT(newChild != NULL); 540 ASSERT(newChild->numBytes == existingChildLength - rangeOfChildToDelete.length); 541 } 542 } 543 childByteOffset += existingChildLength; 544 } 545 return newChildIndex; 546} 547 548static CFStorageNode *__CFStorageDeleteBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) { 549 ASSERT(! node->isLeaf); 550 ASSERT(range.location + range.length <= node->numBytes); 551 if (range.length == node->numBytes) { 552 /* They're deleting everything, so return NULL to indicate that this node should be deleted. */ 553 return NULL; 554 } 555 556 /* Construct our new children in this array. */ 557 CFStorageNode *newChildren[3]; 558 CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, true/*childrenAreDefinitelyFrozen*/, false/*compact*/); 559 560 /* We do not have to freeze anything in newChildren. __CFStoragePopulateBranchChildrenAfterDeletion() will properly freeze any existing children, and new children we get should not be marked frozen. */ 561 562 /* Now we have the children of the new node in newChildren. We expect to have at least one child (if we got no children, we should have returned NULL up above because they deleted everything. */ 563 ASSERT(newChildIndex >= 1); 564 if (newChildIndex == 1) { 565 /* Only one child, so just return it, transferring its retain count */ 566 return newChildren[0]; 567 } 568 else { 569 CFStorageNode *result = __CFStorageCreateNode(allocator, storage, false, 0); 570 while (newChildIndex--) { 571 __CFStorageSetChild(result, newChildIndex, newChildren[newChildIndex]); //transfers the reference count 572 } 573 result->numBytes = node->numBytes - range.length; 574 return result; 575 } 576} 577 578/* Returns a new node, or NULL if the entire thing was deleted. 579 */ 580static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) { 581 if (node->isLeaf) { 582 return __CFStorageDeleteLeafFrozen(allocator, storage, node, range); 583 } 584 else { 585 return __CFStorageDeleteBranchFrozen(allocator, storage, node, range); 586 } 587} 588 589#pragma mark Unfrozen Deletion 590 591/* The boolean compact indicates whether leaf nodes that get smaller should be realloced. 592 */ 593static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode) { 594 ASSERT(! node->isFrozen); 595 ASSERT(range.location + range.length <= node->numBytes); 596 CHECK_NODE_INTEGRITY(node); 597 598 if (range.length == node->numBytes) { 599 /* We are deleting everything, so return NULL */ 600 return NULL; 601 } 602 603 if (node->isLeaf) { 604 node->numBytes -= range.length; 605 // If this node had memory allocated, readjust the bytes... 606 if (node->info.leaf.memory) { 607 COPYMEM(node->info.leaf.memory + range.location + range.length, node->info.leaf.memory + range.location, node->numBytes - range.location); 608 if (compact) __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes, true); 609 } 610 CHECK_NODE_INTEGRITY(node); 611 return __CFStorageRetainNodeThreadUnsafe(node); //we can use the ThreadUnsafe calls because this is the Unfrozen variant, so we are not shared 612 } else { 613 CFStorageNode *newChildren[3] = {NULL, NULL, NULL}; 614 CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, false/*childrenAreDefinitelyFrozen*/, compact); 615 node->numBytes -= range.length; 616 ASSERT(newChildIndex >= 1); //we expect to have at least one child; else we would have deleted everything up above 617 618 /* Release all of our existing children. Either we are about to return a new child in place of us; or we are about to set our children to the new ones */ 619 __CFStorageReleaseNode(storage, node->info.notLeaf.child[0]); 620 __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]); 621 __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]); 622 node->info.notLeaf.child[0] = node->info.notLeaf.child[1] = node->info.notLeaf.child[2] = NULL; 623 624 if (newChildIndex == 1) { 625 /* We have only one child, so return it, transferring the refcount that __CFStoragePopulate gives it */ 626 return newChildren[0]; 627 } 628 else { 629 CFIndex i; 630 for (i=0; i < 3; i++) { 631 __CFStorageSetChild(node, i, newChildren[i]); //set the new child, transferring the refcount to us (or set NULL) 632 } 633 CHECK_NODE_INTEGRITY(node); 634 return __CFStorageRetainNodeThreadUnsafe(node); 635 } 636 } 637} 638 639#pragma mark Frozen Insertion 640 641/* Insertion into an frozen leaf. We return two nodes, either of which may be 'node', or possibly two new nodes. This always sets the cache. */ 642static CFStorageDoubleNodeReturn __CFStorageInsertLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 643 /* Inserting into a frozen leaf. If we can fit the new data along with our existing data into a single node, then do so (i.e. if we can return one node, do it). Otherwise, all of the data would have to fit into a second node (we are never called with more data than storage->maxLeafCapacity) so just make a new node with the data and return that. */ 644 CFStorageNode *leftResult, *rightResult; 645 CHECK_NODE_INTEGRITY(node); 646 ASSERT(byteNum <= node->numBytes); 647 CFIndex newTotalSize = size + node->numBytes; 648 if (newTotalSize <= storage->maxLeafCapacity) { 649 /* We can fit into a single node */ 650 rightResult = NULL; 651 leftResult = __CFStorageCreateNode(allocator, storage, true, newTotalSize); 652 if (node->info.leaf.memory != NULL) { // Beware lazy memory allocation 653 __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, newTotalSize, false); 654 COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum); //copy first byteNum bytes from existing node 655 //middle we don't touch 656 COPYMEM(node->info.leaf.memory + byteNum, leftResult->info.leaf.memory + byteNum + size, node->numBytes - byteNum); //copy last part from existing node 657 } 658 __CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum); 659 } 660 else { 661 /* We cannot fit into a single node. See if we can preserve self (i.e. we're inserting at beginning or end). */ 662 if (byteNum == node->numBytes) { 663 /* Inserting at end, so left is our existing node and right is the new node. Do not retain left node, because it is the same as the given node */ 664 leftResult = (CFStorageNode *)node; 665 rightResult = __CFStorageCreateNode(allocator, storage, true, size); 666 __CFStorageSetCache(storage, rightResult, absoluteByteNum); 667 } 668 else if (byteNum == 0) { 669 /* Inserting at beginning, so right is our existing node and left is the new node. Do retain left node, because it is different than the given node. */ 670 rightResult = __CFStorageRetainNode((CFStorageNode *)node); 671 leftResult = __CFStorageCreateNode(allocator, storage, true, size); 672 __CFStorageSetCache(storage, leftResult, absoluteByteNum); 673 } 674 else { 675 /* Inserting in middle. We will need to create two nodes because we overflow one. We could be lazy and only allocate up to byteNum, but since it's likely that they're about to insert into us and we'd have to reallocate, just allocate everything requested up front. */ 676 CFIndex leftAmount = storage->maxLeafCapacity, rightAmount = newTotalSize - storage->maxLeafCapacity; 677 leftResult = __CFStorageCreateNode(allocator, storage, true, leftAmount); 678 rightResult = __CFStorageCreateNode(allocator, storage, true, rightAmount); 679 __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, leftAmount, false); 680 __CFStorageAllocLeafNodeMemory(allocator, storage, rightResult, rightAmount, false); 681 ASSERT(node->info.leaf.capacityInBytes >= node->numBytes); 682 683 /* The existing node has length node->numBytes, so it has the following range: {0, node->numBytes} 684 685 We are inserting (garbage) data of length 'size' into offset 'byteNum'. Therefore we end up with the following two logical ranges, expressed as {start, length}: 686 {0, byteNum}, {byteNum + size, node->numBytes - byteNum} 687 688 We need to divide these among our new nodes with the following logical ranges: 689 {0, leftAmount}, {leftAmount, rightAmount} 690 691 The first range must be fit entirely within the left node (byteNum <= leftAmount). The second range may or may be divided between the left and right nodes. 692 */ 693 694 ASSERT(byteNum <= leftAmount); 695 COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum); 696 697 const CFRange leftNodeRange = {0, leftAmount}, rightNodeRange = {leftAmount, rightAmount}; 698 const CFRange preservedData = {byteNum + size, node->numBytes - byteNum}; 699 CFRange overlap; 700 if ((overlap = intersectionRange(leftNodeRange, preservedData)).length > 0) COPYMEM(node->info.leaf.memory + overlap.location - size, leftResult->info.leaf.memory + overlap.location, overlap.length); 701 if ((overlap = intersectionRange(rightNodeRange, preservedData)).length > 0) COPYMEM(node->info.leaf.memory + overlap.location - size, rightResult->info.leaf.memory + overlap.location - leftAmount, overlap.length); 702 __CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum); 703 } 704 } 705 return CFStorageDoubleNodeReturnMake(leftResult, rightResult); 706} 707 708static CFStorageDoubleNodeReturn __CFStorageInsertBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 709 /* Inserting into a frozen branch. We definitely will need to make a new copy of us, so make that up front. We may or may not need to make a new sibling. Note that in some cases, we may be able to get away with not creating a new copy of us, e.g. inserting at the very end of the tree. In that case, we could preserve us and make a sibling containing exactly one node. However, we do not really want to have branches with exactly one child; because then why not just return the child? And then the whole tree can become unbalanced. So then instead, always distribute the children equally among our nodes. */ 710 CHECK_NODE_INTEGRITY(node); 711 CFStorageNode *copyOfMe = __CFStorageCreateNode(allocator, storage, false, 0); 712 CFStorageNode *siblingOfMe = NULL; 713 CFIndex relativeByteNum; 714 CFIndex childNum; 715 CFStorageNode *child = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum); 716 ASSERT(childNum >= 0 && childNum <= 2); 717 CFStorageDoubleNodeReturn childReturn = __CFStorageInsertFrozen(allocator, storage, child, relativeByteNum, size, absoluteByteNum); 718 ASSERT(childReturn.child); //we always get at least one back 719 720 /* Make a local array of all new children (retained). We'll then move them to the new nodes. */ 721 CFStorageNode *newChildren[4] = {NULL}; 722 __CFStorageGetChildren(node, newChildren, true/*retain*/, true/*freeze*/); 723 if (newChildren[childNum] != childReturn.child) { 724 __CFStorageReleaseNode(storage, newChildren[childNum]); 725 newChildren[childNum] = childReturn.child; // Transfers the retain 726 } 727 if (childReturn.sibling != NULL) { 728 if (childNum < 2) newChildren[3] = newChildren[2]; 729 if (childNum < 1) newChildren[2] = newChildren[1]; 730 newChildren[childNum + 1] = childReturn.sibling; // Transfers the retain 731 } 732 733 /* First two always go to our clone */ 734 __CFStorageSetChild(copyOfMe, 0, newChildren[0]); 735 __CFStorageSetChild(copyOfMe, 1, newChildren[1]); 736 if (newChildren[3] == NULL) { 737 /* We have three or fewer children to distribute, i.e. we don't need a sibling. Put them all into copy of me. Our clone's byte count is larger than our own by 'size'. */ 738 __CFStorageSetChild(copyOfMe, 2, newChildren[2]); 739 copyOfMe->numBytes = node->numBytes + size; 740 } 741 else { 742 /* We have four children to distribute. The first two go to us, the last two go to our new sibling. */ 743 siblingOfMe = __CFStorageCreateNode(allocator, storage, false, 0); 744 __CFStorageSetChild(siblingOfMe, 0, newChildren[2]); 745 __CFStorageSetChild(siblingOfMe, 1, newChildren[3]); 746 copyOfMe->numBytes = newChildren[0]->numBytes + newChildren[1]->numBytes; 747 siblingOfMe->numBytes = newChildren[2]->numBytes + newChildren[3]->numBytes; 748 } 749 CHECK_NODE_INTEGRITY(node); 750 CHECK_NODE_INTEGRITY(copyOfMe); 751 if (siblingOfMe) CHECK_NODE_INTEGRITY(siblingOfMe); 752 return CFStorageDoubleNodeReturnMake(copyOfMe, siblingOfMe); 753} 754 755static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 756 if (node->isLeaf) { 757 return __CFStorageInsertLeafFrozen(allocator, storage, node, byteNum, size, absoluteByteNum); 758 } 759 else { 760 return __CFStorageInsertBranchFrozen(allocator, storage, node, byteNum, size, absoluteByteNum); 761 } 762} 763 764 765#pragma mark Unfrozen Insertion 766 767/* Insertion into an unfrozen leaf. We return two nodes, one of which is 'node'. This always sets the cache. */ 768static CFStorageDoubleNodeReturn __CFStorageInsertLeafUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 769 if (size + node->numBytes > storage->maxLeafCapacity) { // Need to create more child nodes 770 CFStorageNode *newNode; 771 if (byteNum == node->numBytes) { // Inserting at end; easy... 772 newNode = __CFStorageCreateNode(allocator, storage, true, size); 773 __CFStorageSetCache(storage, newNode, absoluteByteNum); 774 } else if (byteNum == 0) { // Inserting at front; also easy, but we need to swap node and newNode 775 newNode = __CFStorageCreateNode(allocator, storage, true, 0); 776 777 /* Transfer our memory to the new node */ 778 newNode->numBytes = node->numBytes; 779 newNode->info.leaf.capacityInBytes = node->info.leaf.capacityInBytes; 780 __CFAssignWithWriteBarrier((void **)&newNode->info.leaf.memory, node->info.leaf.memory); 781 782 /* Stomp on our existing node */ 783 node->numBytes = size; 784 node->info.leaf.capacityInBytes = 0; 785 node->info.leaf.memory = NULL; 786 787 /* Cache our existing node */ 788 __CFStorageSetCache(storage, node, absoluteByteNum); 789 } else if (byteNum + size <= storage->maxLeafCapacity) { // Inserting at middle; inserted region will fit into existing child 790 // Create new node to hold the overflow 791 newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes - byteNum); 792 if (node->info.leaf.memory) { // We allocate memory lazily... 793 __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes - byteNum, false); 794 COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory, node->numBytes - byteNum); 795 __CFStorageAllocLeafNodeMemory(allocator, storage, node, byteNum + size, false); 796 } 797 node->numBytes = byteNum + size; 798 __CFStorageSetCache(storage, node, absoluteByteNum - byteNum); 799 } else { // Inserting some of new into one node, rest into another; remember that the assumption is size <= storage->maxLeafCapacity 800 newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes + size - storage->maxLeafCapacity); // New stuff 801 if (node->info.leaf.memory) { // We allocate memory lazily... 802 __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes + size - storage->maxLeafCapacity, false); 803 COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory + byteNum + size - storage->maxLeafCapacity, node->numBytes - byteNum); 804 __CFStorageAllocLeafNodeMemory(allocator, storage, node, storage->maxLeafCapacity, false); 805 } 806 __CFStorageSetCache(storage, node, absoluteByteNum - byteNum); 807 node->numBytes = storage->maxLeafCapacity; 808 } 809 return CFStorageDoubleNodeReturnMake(node, newNode); // We do not retain 'node' because it is the given node. 810 } else { // No need to create new nodes! 811 if (node->info.leaf.memory) { 812 __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes + size, false); 813 COPYMEM(node->info.leaf.memory + byteNum, node->info.leaf.memory + byteNum + size, node->numBytes - byteNum); 814 } 815 node->numBytes += size; 816 __CFStorageSetCache(storage, node, absoluteByteNum - byteNum); 817 return CFStorageDoubleNodeReturnMake(node, NULL); //return the existing node, meaning the parent does not have to do anything. Do not retain it because it is the given node. 818 } 819} 820 821static CFStorageDoubleNodeReturn __CFStorageInsertBranchUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 822 CFIndex relativeByteNum; 823 CFIndex childNum; // we will insert after childNum, i.e. if childNum is 0, any new node becomes index 1. This can have value 0, 1, or 2. 824 CFStorageNode *childNode = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum); 825 CFStorageDoubleNodeReturn newNodes = __CFStorageInsert(allocator, storage, childNode, relativeByteNum, size, absoluteByteNum); 826 CFStorageDoubleNodeReturn result = {node, NULL}; // the default return value meaning we did all of the work ourselves and our parent does not need to do anything 827 ASSERT(childNode != NULL); 828 ASSERT(newNodes.child != NULL); 829 830 if (newNodes.child != childNode) { 831 /* We got back a replacement for the current child, so replace it. */ 832 __CFStorageReleaseNode(storage, childNode); 833 __CFStorageSetChild(node, childNum, newNodes.child); 834 } 835 836 if (newNodes.sibling == NULL) { 837 /* The insertion happened successfully without requiring us to add any new nodes. */ 838 node->numBytes += size; 839 } else { 840 /* We got back an additional node to insert. */ 841 CFStorageNode *newChild = newNodes.sibling; 842 if (node->info.notLeaf.child[2] == NULL) { // There's an empty slot for the new node, cool 843 if (childNum == 0) __CFStorageSetChild(node, 2, node->info.notLeaf.child[1]); // Make room 844 __CFStorageSetChild(node, childNum+1, newChild); 845 node->numBytes += size; 846 } else { 847 CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, storage, false, 0); // Create another node 848 if (childNum == 0) { // Last two children go to new node 849 __CFStorageSetChild(anotherNode, 0, node->info.notLeaf.child[1]); 850 __CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]); 851 __CFStorageSetChild(node, 1, newChild); 852 node->info.notLeaf.child[2] = NULL; 853 } else if (childNum == 1) { // Last child goes to new node 854 __CFStorageSetChild(anotherNode, 0, newChild); 855 __CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]); 856 node->info.notLeaf.child[2] = NULL; 857 } else { // New node contains the new comers... 858 __CFStorageSetChild(anotherNode, 0, node->info.notLeaf.child[2]); 859 __CFStorageSetChild(anotherNode, 1, newChild); 860 node->info.notLeaf.child[2] = NULL; 861 } 862 node->numBytes = node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes; 863 anotherNode->numBytes = anotherNode->info.notLeaf.child[0]->numBytes + anotherNode->info.notLeaf.child[1]->numBytes; 864 /* node should not be retained because it is the passed in node. anotherNode was created so we transfer its retain count */ 865 result.sibling = anotherNode; 866 } 867 } 868 return result; 869} 870 871 872 873/* Returns NULL or additional node to come after this node 874 Assumption: size is never > storage->maxLeafCapacity 875 */ 876static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 877 ASSERT(! node->isFrozen); 878 if (node->isLeaf) { 879 return __CFStorageInsertLeafUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum); 880 } else { 881 return __CFStorageInsertBranchUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum); 882 } 883} 884 885#pragma mark Frozen or Unfrozen Dispatch Functions 886 887static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) { 888 if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) { 889 return __CFStorageInsertFrozen(allocator, storage, node, byteNum, size, absoluteByteNum); 890 } 891 else { 892 return __CFStorageInsertUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum); 893 } 894} 895 896static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) { 897 if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) { 898 return __CFStorageDeleteFrozen(allocator, storage, node, range); 899 } 900 else { 901 return __CFStorageDeleteUnfrozen(allocator, storage, node, range, compact, false/*isRootNode*/); 902 } 903} 904 905 906#pragma mark Utility functions 907 908CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) { 909 return __CFStorageConvertByteToValue(storage, storage->rootNode.numBytes); 910} 911 912static Boolean __CFStorageEqual(CFTypeRef cf1, CFTypeRef cf2) { 913 CFStorageRef storage1 = (CFStorageRef)cf1; 914 CFStorageRef storage2 = (CFStorageRef)cf2; 915 CFIndex loc, count, valueSize; 916 CFRange range1, range2; 917 uint8_t *ptr1, *ptr2; 918 919 count = __CFStorageGetCount(storage1); 920 if (count != __CFStorageGetCount(storage2)) return false; 921 922 valueSize = __CFStorageGetValueSize(storage1); 923 if (valueSize != __CFStorageGetValueSize(storage2)) return false; 924 925 loc = range1.location = range1.length = range2.location = range2.length = 0; 926 ptr1 = ptr2 = NULL; 927 928 while (loc < count) { 929 CFIndex cntThisTime; 930 if (loc >= range1.location + range1.length) ptr1 = (uint8_t *)CFStorageGetValueAtIndex(storage1, loc, &range1); 931 if (loc >= range2.location + range2.length) ptr2 = (uint8_t *)CFStorageGetValueAtIndex(storage2, loc, &range2); 932 cntThisTime = range1.location + range1.length; 933 if (range2.location + range2.length < cntThisTime) cntThisTime = range2.location + range2.length; 934 cntThisTime -= loc; 935 if (memcmp(ptr1, ptr2, valueSize * cntThisTime) != 0) return false; 936 ptr1 += valueSize * cntThisTime; 937 ptr2 += valueSize * cntThisTime; 938 loc += cntThisTime; 939 } 940 return true; 941} 942 943static CFHashCode __CFStorageHash(CFTypeRef cf) { 944 CFStorageRef Storage = (CFStorageRef)cf; 945 return __CFStorageGetCount(Storage); 946} 947 948static void __CFStorageDescribeNode(CFStorageNode *node, CFMutableStringRef str, CFIndex level) { 949 int cnt; 950 for (cnt = 0; cnt < level; cnt++) CFStringAppendCString(str, " ", CFStringGetSystemEncoding()); 951 952 if (node->isLeaf) { 953 CFStringAppendFormat(str, NULL, CFSTR("Leaf %ld/%ld (%p) refcount: %u frozen: %s\n"), node->numBytes, node->info.leaf.capacityInBytes, node, node->refCount, node->isFrozen ? "yes" : "no"); 954 } else { 955 CFStringAppendFormat(str, NULL, CFSTR("Node %ld (%p) refcount: %u frozen: %s\n"), node->numBytes, node, node->refCount, node->isFrozen ? "yes" : "no"); 956 for (cnt = 0; cnt < 3; cnt++) if (node->info.notLeaf.child[cnt]) __CFStorageDescribeNode(node->info.notLeaf.child[cnt], str, level+1); 957 } 958} 959 960static CFIndex __CFStorageGetNodeCapacity(CFStorageNode *node) { 961 if (!node) return 0; 962 if (node->isLeaf) return node->info.leaf.capacityInBytes; 963 return __CFStorageGetNodeCapacity(node->info.notLeaf.child[0]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[1]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[2]); 964} 965 966CFIndex __CFStorageGetCapacity(CFStorageRef storage) { 967 return __CFStorageConvertByteToValue(storage, __CFStorageGetNodeCapacity(&storage->rootNode)); 968} 969 970CFIndex __CFStorageGetValueSize(CFStorageRef storage) { 971 return storage->valueSize; 972} 973 974static CFStringRef __CFStorageCopyDescription(CFTypeRef cf) { 975 CFStorageRef storage = (CFStorageRef)cf; 976 CFMutableStringRef result; 977 CFAllocatorRef allocator = CFGetAllocator(storage); 978 result = CFStringCreateMutable(allocator, 0); 979 CFStringAppendFormat(result, NULL, CFSTR("<CFStorage %p [%p]>[count = %lu, capacity = %lu]\n"), storage, allocator, (unsigned long)__CFStorageGetCount(storage), (unsigned long)__CFStorageGetCapacity(storage)); 980 __CFStorageDescribeNode(&storage->rootNode, result, 0); 981 return result; 982} 983 984/* Returns true if enumeration should stop, false if it should continue. */ 985static bool __CFStorageEnumerateNodesInByteRangeWithBlock(CFStorageRef storage, CFStorageNode *node, CFIndex globalOffsetOfNode, CFRange range, CFIndex concurrencyToken, CFStorageApplierBlock applier) { 986 bool stop = false; 987 if (node->isLeaf) { 988 CFIndex start = range.location; 989 CFIndex length = __CFMin(range.length, node->numBytes - start); 990 if (! node->info.leaf.memory) { 991 __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false); 992 } 993 applier(node->info.leaf.memory + start, __CFStorageConvertBytesToValueRange(storage, globalOffsetOfNode + start, length), &stop); 994 } 995 else { 996 CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]}; 997 const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0}; 998 const CFIndex offsets[3] = {0, lengths[0], lengths[0] + lengths[1]}; 999 const CFRange overlaps[3] = {intersectionRange(CFRangeMake(offsets[0], lengths[0]), range), intersectionRange(CFRangeMake(offsets[1], lengths[1]), range), intersectionRange(CFRangeMake(offsets[2], lengths[2]), range)}; 1000 CFIndex numOverlappingChildren = (!! overlaps[0].length + !! overlaps[1].length + !! overlaps[2].length); 1001 if (numOverlappingChildren > 1) concurrencyToken--; 1002 1003 if (concurrencyToken >= 0 && numOverlappingChildren > 1) { 1004 CFIndex numChildren = 1 + !!children[1] + !!children[2]; 1005 const CFRange * overlapsPtr = overlaps; //blocks don't let us reference arrays :( 1006 const CFIndex * offsetsPtr = offsets; 1007 CFStorageNode ** childrenPtr = children; 1008#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS 1009 __block bool blockStop = false; 1010 dispatch_apply(numChildren, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t ind) { 1011 if (! blockStop && overlapsPtr[ind].length > 0) { 1012 if (__CFStorageEnumerateNodesInByteRangeWithBlock(storage, childrenPtr[ind], globalOffsetOfNode + offsetsPtr[ind], CFRangeMake(overlapsPtr[ind].location - offsetsPtr[ind], overlapsPtr[ind].length), concurrencyToken, applier)) { 1013 blockStop = true; 1014 } 1015 } 1016 }); 1017 stop = blockStop; 1018#else 1019 for (CFIndex ind = 0; ind < numChildren; ind++) { 1020 if (overlapsPtr[ind].length > 0) { 1021 if (__CFStorageEnumerateNodesInByteRangeWithBlock(storage, childrenPtr[ind], globalOffsetOfNode + offsetsPtr[ind], CFRangeMake(overlapsPtr[ind].location - offsetsPtr[ind], overlapsPtr[ind].length), concurrencyToken, applier)) { 1022 stop = true; 1023 break; 1024 } 1025 } 1026 } 1027#endif 1028 } else { 1029 if (overlaps[0].length > 0) { 1030 stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[0], globalOffsetOfNode + offsets[0], CFRangeMake(overlaps[0].location - offsets[0], overlaps[0].length), concurrencyToken, applier); 1031 } 1032 if (overlaps[1].length > 0) { 1033 stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[1], globalOffsetOfNode + offsets[1], CFRangeMake(overlaps[1].location - offsets[1], overlaps[1].length), concurrencyToken, applier); 1034 } 1035 if (overlaps[2].length > 0) { 1036 stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[2], globalOffsetOfNode + offsets[2], CFRangeMake(overlaps[2].location - offsets[2], overlaps[2].length), concurrencyToken, applier); 1037 } 1038 } 1039 } 1040 return stop; 1041} 1042 1043static CFStorageNode *_CFStorageFindNodeContainingByteRange(ConstCFStorageRef storage, const CFStorageNode *node, CFRange nodeRange, CFIndex globalOffsetOfNode, CFRange *outGlobalByteRangeOfResult) { 1044 if (! node->isLeaf) { 1045 /* See how many children are overlapped by this range. If it's only 1, call us recursively on that node; otherwise we're it! */ 1046 CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]}; 1047 const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0}; 1048 const CFIndex offsets[3] = {0, lengths[0], lengths[0] + lengths[1]}; 1049 const CFRange overlaps[3] = {intersectionRange(CFRangeMake(offsets[0], lengths[0]), nodeRange), intersectionRange(CFRangeMake(offsets[1], lengths[1]), nodeRange), intersectionRange(CFRangeMake(offsets[2], lengths[2]), nodeRange)}; 1050 CFIndex numOverlappingChildren = (!! overlaps[0].length + !! overlaps[1].length + !! overlaps[2].length); 1051 ASSERT(numOverlappingChildren > 0); 1052 if (numOverlappingChildren == 1) { 1053 CFIndex overlappingChild = (overlaps[0].length ? 0 : (overlaps[1].length ? 1 : 2)); 1054 return _CFStorageFindNodeContainingByteRange(storage, children[overlappingChild], CFRangeMake(nodeRange.location - offsets[overlappingChild], nodeRange.length), globalOffsetOfNode + offsets[overlappingChild], outGlobalByteRangeOfResult); 1055 } 1056 } 1057 1058 /* Either we are a leaf, in which case we contain the range, or we are a branch with multiple overlapping children. Either way, we are the minimum node containing the range in question. */ 1059 *outGlobalByteRangeOfResult = CFRangeMake(globalOffsetOfNode, node->numBytes); 1060 return (CFStorageNode *)node; 1061 1062 1063} 1064 1065/* Frees all memory associated with the root node, effectively emptying the CFStorage */ 1066static void __CFStorageClearRootNode(CFStorageRef storage) { 1067 CFAllocatorRef allocator = CFGetAllocator(storage); 1068 /* Have to release our children if we are a branch, or free our memory if we are a leaf */ 1069 if (storage->rootNode.isLeaf) { 1070 _CFAllocatorDeallocateGC(allocator, storage->rootNode.info.leaf.memory); 1071 } 1072 else { 1073 __CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[0]); 1074 __CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[1]); 1075 __CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[2]); 1076 } 1077 storage->rootNode.isLeaf = true; 1078 storage->rootNode.numBytes = 0; 1079 storage->rootNode.info.leaf.capacityInBytes = 0; 1080 storage->rootNode.info.leaf.memory = NULL; 1081} 1082 1083static void __CFStorageDeallocate(CFTypeRef cf) { 1084 /* CFStorage is used in CFArray. Under GC, CFArray references us strongly, but not retained. Thus we may be finalized before the array. When the array itself is finalized, it will call any custom deallocate callback on all of its contents, which means it has to walk the array. Thus CFStorage must be careful to not perturb its structure in Deallocate under GC. 1085 1086 CFStorage nodes have a reference count, and if a node has a reference count of one, and we are in a mutating function, we conclude that this CFStorage has exclusive ownership of the node, and we can treat it as mutable even if it's marked as frozen (see __CFStorageThawNodeDuringMutation). Therefore it would be nice if we could decrement our nodes' refcounts in Deallocate. However, if we did so, then another CFStorage might treat a node that we reference as mutable and modify it, which must not happen, because we must not perturb the structure of a CFStorage in Deallocate. Thus we just "leak" a reference count under GC. Of course, these reference counts don't actually keep the memory alive in GC, so it's not a real leak. 1087 */ 1088 CFStorageRef storage = (CFStorageRef)cf; 1089 if (! CF_IS_COLLECTABLE_ALLOCATOR(CFGetAllocator(storage))) { 1090 __CFStorageClearRootNode(storage); 1091 } 1092} 1093 1094static CFTypeID __kCFStorageTypeID = _kCFRuntimeNotATypeID; 1095 1096static const CFRuntimeClass __CFStorageClass = { 1097 _kCFRuntimeScannedObject, 1098 "CFStorage", 1099 NULL, // init 1100 NULL, // copy 1101 __CFStorageDeallocate, 1102 __CFStorageEqual, 1103 __CFStorageHash, 1104 NULL, // 1105 __CFStorageCopyDescription 1106}; 1107 1108CF_PRIVATE void __CFStorageInitialize(void) { 1109 __kCFStorageTypeID = _CFRuntimeRegisterClass(&__CFStorageClass); 1110} 1111 1112/*** Public API ***/ 1113 1114CFStorageRef CFStorageCreate(CFAllocatorRef allocator, CFIndex valueSize) { 1115 CFStorageRef storage; 1116 CFIndex size = sizeof(struct __CFStorage) - sizeof(CFRuntimeBase); 1117 storage = (CFStorageRef)_CFRuntimeCreateInstance(allocator, __kCFStorageTypeID, size, NULL); 1118 if (NULL == storage) { 1119 return NULL; 1120 } 1121 storage->valueSize = valueSize; 1122 /* if valueSize is a power of 2, then set the shifter to the log base 2 of valueSize. Otherwise set it to NO_SHIFTER */ 1123 if (valueSize > 0 && !(valueSize & (valueSize - 1))) { 1124#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED 1125 storage->byteToValueShifter = __builtin_ctzl(valueSize); 1126#else 1127 CFIndex tempSize = valueSize; 1128 storage->byteToValueShifter = 0; 1129 while (tempSize > 1) { 1130 storage->byteToValueShifter++; 1131 tempSize >>= 1; 1132 } 1133#endif 1134 } 1135 else { 1136 storage->byteToValueShifter = NO_SHIFTER; 1137 } 1138 1139 CF_SPINLOCK_INIT_FOR_STRUCTS(storage->cacheReaderMemoryAllocationLock); 1140 storage->maxLeafCapacity = __CFStorageMaxLeafCapacity; 1141 if (valueSize && ((storage->maxLeafCapacity % valueSize) != 0)) { 1142 storage->maxLeafCapacity = (storage->maxLeafCapacity / valueSize) * valueSize; // Make it fit perfectly (3406853) 1143 } 1144 memset(&(storage->rootNode), 0, sizeof(CFStorageNode)); 1145 storage->rootNode.isLeaf = true; 1146 storage->rootNode.refCount = 0; 1147 if (valueSize >= sizeof(void *)) { 1148 storage->nodeHint = __kCFAllocatorGCScannedMemory; 1149 } 1150 else { 1151 // Don't scan nodes if the value size is smaller than a pointer (8198596) 1152 storage->nodeHint = 0; 1153 } 1154 if (__CFOASafe) __CFSetLastAllocationEventName(storage, "CFStorage"); 1155 return storage; 1156} 1157 1158CFStorageRef CFStorageCreateWithSubrange(CFStorageRef mutStorage, CFRange range) { 1159 const ConstCFStorageRef storage = mutStorage; //we expect this to never modify the storage, so use a const variable to help enforce that 1160 CFStorageRef result = CFStorageCreate(CFGetAllocator(storage), storage->valueSize); 1161 1162 if (range.length > 0) { 1163 /* Start by finding the node that contains the entire range. Bump the reference count of its children and add them to the root of our new copy. */ 1164 const CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length); 1165 CFRange byteRangeOfContainingNode; 1166 CFStorageNode *nodeContainingEntireRange = _CFStorageFindNodeContainingByteRange(storage, &storage->rootNode, byteRange, 0, &byteRangeOfContainingNode); 1167 ASSERT(nodeContainingEntireRange != NULL); 1168 1169 /* If the result is a leaf, insert the portion we care about */ 1170 if (nodeContainingEntireRange->isLeaf) { 1171 CFStorageInsertValues(result, CFRangeMake(0, range.length)); 1172 if (nodeContainingEntireRange->info.leaf.memory) { 1173 CFIndex offsetIntoNode = byteRange.location - byteRangeOfContainingNode.location; 1174 ASSERT(offsetIntoNode >= 0); 1175 CFStorageReplaceValues(result, CFRangeMake(0, range.length), nodeContainingEntireRange->info.leaf.memory + offsetIntoNode); 1176 } 1177 } 1178 else { 1179 /* The result is not a leaf. Insert all of its children into our root. */ 1180 ASSERT(byteRangeOfContainingNode.length == nodeContainingEntireRange->numBytes); 1181 result->rootNode.isLeaf = false; 1182 result->rootNode.numBytes = byteRangeOfContainingNode.length; 1183 result->rootNode.info.notLeaf.child[0] = result->rootNode.info.notLeaf.child[1] = result->rootNode.info.notLeaf.child[2] = NULL; 1184 for (CFIndex i=0; i < 3; i++) { 1185 CFStorageNode *newNode = nodeContainingEntireRange->info.notLeaf.child[i]; 1186 if (! newNode) break; 1187 __CFStorageFreezeNode(newNode); 1188 __CFStorageSetChild(&result->rootNode, i, __CFStorageRetainNode(newNode)); 1189 } 1190 1191 /* Now delete from the beginning or end to trim this to the right size */ 1192 CFRange rangeOfContainingNode = __CFStorageConvertBytesToValueRange(result, byteRangeOfContainingNode.location, byteRangeOfContainingNode.length); 1193 CFIndex prefixToTrim = range.location - rangeOfContainingNode.location; 1194 CFIndex suffixToTrim = (rangeOfContainingNode.location + rangeOfContainingNode.length) - (range.location + range.length); 1195 ASSERT(prefixToTrim >= 0); 1196 ASSERT(suffixToTrim >= 0); 1197 ASSERT(CFStorageGetCount(result) == rangeOfContainingNode.length); 1198 if (suffixToTrim > 0) CFStorageDeleteValues(result, CFRangeMake(rangeOfContainingNode.length - suffixToTrim, suffixToTrim)); 1199 if (prefixToTrim > 0) CFStorageDeleteValues(result, CFRangeMake(0, prefixToTrim)); 1200 } 1201 } 1202 1203 ASSERT(CFStorageGetCount(result) == range.length); 1204 return result; 1205} 1206 1207CFTypeID CFStorageGetTypeID(void) { 1208 return __kCFStorageTypeID; 1209} 1210 1211CFIndex CFStorageGetCount(CFStorageRef storage) { 1212 return __CFStorageGetCount(storage); 1213} 1214 1215/* Returns pointer to the specified value 1216 index and validConsecutiveValueRange are in terms of values 1217 */ 1218void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) { 1219 CFRange dummy; 1220 return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, true/*requireUnfreezing*/); 1221} 1222 1223const void *CFStorageGetConstValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) { 1224 CFRange dummy; 1225 return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, false/*requireUnfreezing*/); 1226} 1227 1228 1229/* Makes space for range.length values at location range.location 1230 This function deepens the tree if necessary... 1231 */ 1232void CFStorageInsertValues(CFStorageRef storage, CFRange range) { 1233 CFIndex numBytesToInsert = __CFStorageConvertValueToByte(storage, range.length); 1234 CFIndex byteNum = __CFStorageConvertValueToByte(storage, range.location); 1235 const CFIndex expectedByteCount = storage->rootNode.numBytes + numBytesToInsert; 1236 const CFAllocatorRef allocator = CFGetAllocator(storage); 1237 const CFIndex insertionChunkSize = storage->maxLeafCapacity; 1238 while (numBytesToInsert > 0) { 1239 CHECK_INTEGRITY(); 1240 const CFIndex insertThisTime = __CFMin(numBytesToInsert, insertionChunkSize); 1241 CFStorageDoubleNodeReturn newNodes = __CFStorageInsertUnfrozen(allocator, storage, &storage->rootNode, byteNum, insertThisTime, byteNum); //we don't have to call the frozen variant because the root node is never frozen 1242 ASSERT(newNodes.child == &storage->rootNode);// unfrozen variant should always give us our node back. We may have another node to insert in newNodes.sibling 1243 if (newNodes.sibling != NULL) { 1244 CFStorageNode *newNode = newNodes.sibling; 1245 /* Need to create a new root node. Copy our existing root node's contents to a new heap node. */ 1246 CFStorageNode *heapRoot = __CFStorageCreateNode(allocator, storage, storage->rootNode.isLeaf, storage->rootNode.numBytes); // Will copy the (static) rootNode over to this 1247 objc_memmove_collectable(&heapRoot->info, &storage->rootNode.info, sizeof heapRoot->info); 1248 1249 /* Our root is about to become a branch. If our root node is currently a leaf, we need to clear the cache, because if the cache points at the root then the cache is about to start pointing at a branch node (which is not allowed) */ 1250 if (storage->rootNode.isLeaf) { 1251 __CFStorageSetCache(storage, NULL, 0); 1252 storage->rootNode.isLeaf = false; 1253 } 1254 1255 /* Set the new children in our root. Note that it's important that we overwrite the root node's info, because we wanted to transfer the refcounts of our children (or our allocated memory, if we are a leaf) to the new heap root */ 1256 __CFStorageSetChild(&storage->rootNode, 0, heapRoot); 1257 __CFStorageSetChild(&storage->rootNode, 1, newNode); 1258 storage->rootNode.info.notLeaf.child[2] = NULL; 1259 storage->rootNode.numBytes = heapRoot->numBytes + newNode->numBytes; 1260 } 1261 numBytesToInsert -= insertThisTime; 1262 byteNum += insertThisTime; 1263 ASSERT(storage->rootNode.numBytes + numBytesToInsert == expectedByteCount); 1264 } 1265 ASSERT(expectedByteCount == storage->rootNode.numBytes); 1266 CHECK_INTEGRITY(); 1267} 1268 1269/* Deletes the values in the specified range 1270 This function gets rid of levels if necessary... 1271 */ 1272void CFStorageDeleteValues(CFStorageRef storage, CFRange range) { 1273 CHECK_INTEGRITY(); 1274 CFAllocatorRef allocator = CFGetAllocator(storage); 1275 CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length); 1276 const CFIndex expectedByteCount = storage->rootNode.numBytes - byteRange.length; 1277 1278 /* We don't try to mantain the cache across deletion */ 1279 __CFStorageSetCache(storage, NULL, 0); 1280 1281 /* The root node can never be frozen, so it's always OK to modify it */ 1282 ASSERT(! storage->rootNode.isFrozen); 1283 CFStorageNode *newRoot = __CFStorageDeleteUnfrozen(allocator, storage, &storage->rootNode, byteRange, true/*compact*/, true/*isRootNode*/); 1284 1285 /* There are three return values we can get: 1286 NULL -> everything was deleted 1287 the root node -> something was deleted, but no nodes became empty, so we don't have to replace any children 1288 a different node -> represents the new root 1289 */ 1290 if (newRoot == NULL) { 1291 __CFStorageClearRootNode(storage); 1292 } 1293 else if (newRoot == &storage->rootNode) { 1294 /* No need to replace any children, nothing to do for this case */ 1295 } 1296 else { 1297 /* Got a legitimately new root back. If it is unfrozen, we can just acquire its guts. If it is frozen, we have more work to do. Note that we do not have to worry about releasing any existing children of the root, beacuse __CFStorageDeleteUnfrozen already did that. Also note that if we got a legitimately new root back, we must be a branch node, because if we were a leaf node, we would have been unfrozen and gotten ourself back. */ 1298 storage->rootNode.numBytes = newRoot->numBytes; 1299 storage->rootNode.isLeaf = newRoot->isLeaf; 1300 bzero(&storage->rootNode.info, sizeof storage->rootNode.info); //be a little paranoid here 1301 if (newRoot->isLeaf) { 1302 if (! newRoot->isFrozen) { 1303 /* If the leaf is not frozen, we can just steal its memory (if any)! If it is frozen, we must copy it. */ 1304 __CFAssignWithWriteBarrier((void **)&storage->rootNode.info.leaf.memory, newRoot->info.leaf.memory); 1305 /* Clear out the old node, because we stole its memory and we don't want it to deallocate it when teh node is destroyed below. */ 1306 bzero(&newRoot->info, sizeof newRoot->info); 1307 } 1308 else { 1309 /* The leaf is frozen, so we have to copy its memory. */ 1310 if (newRoot->info.leaf.memory) { 1311 __CFStorageAllocLeafNodeMemory(allocator, storage, &storage->rootNode, storage->rootNode.numBytes, false); 1312 COPYMEM(newRoot->info.leaf.memory, storage->rootNode.info.leaf.memory, newRoot->numBytes); 1313 } 1314 } 1315 } else { 1316 /* New root is a branch. */ 1317 ASSERT(newRoot->info.notLeaf.child[0] && newRoot->info.notLeaf.child[1]); //never expect to get back a node with only one child 1318 __CFStorageSetChild(&storage->rootNode, 0, __CFStorageRetainNode(newRoot->info.notLeaf.child[0])); 1319 __CFStorageSetChild(&storage->rootNode, 1, __CFStorageRetainNode(newRoot->info.notLeaf.child[1])); 1320 if (newRoot->info.notLeaf.child[2]) __CFStorageSetChild(&storage->rootNode, 2, __CFStorageRetainNode(newRoot->info.notLeaf.child[2])); 1321 } 1322 } 1323 __CFStorageReleaseNodeWithNullCheck(storage, newRoot); //balance the retain from __CFStorageDeleteUnfrozen 1324 ASSERT(expectedByteCount == storage->rootNode.numBytes); 1325 CHECK_INTEGRITY(); 1326} 1327 1328void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values) { 1329 CHECK_INTEGRITY(); 1330 while (range.length > 0) { 1331 CFRange leafRange; 1332 void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange, false/*requireUnfreezing*/); 1333 CFIndex cntThisTime = __CFMin(range.length, leafRange.length - (range.location - leafRange.location)); 1334 CFIndex byteCntThisTime = __CFStorageConvertValueToByte(storage, cntThisTime); 1335 COPYMEM(storagePtr, values, byteCntThisTime); 1336 values = (uint8_t *)values + byteCntThisTime; 1337 range.location += cntThisTime; 1338 range.length -= cntThisTime; 1339 } 1340} 1341 1342unsigned long _CFStorageFastEnumeration(CFStorageRef storage, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) { 1343 // without trying to understand the data structure, each time through search for block containing index 1344 CFRange leafRange; 1345 if (state->state == 0) { /* first time, get length */ 1346 state->extra[0] = __CFStorageGetCount(storage); 1347 } 1348 if (state->state >= state->extra[0]) return 0; 1349 state->itemsPtr = (unsigned long *)CFStorageGetValueAtIndex(storage, state->state, &leafRange); 1350 state->state += leafRange.length; 1351 return leafRange.length; 1352} 1353 1354void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context) { 1355 CHECK_INTEGRITY(); 1356 CFIndex valueSize = storage->valueSize; 1357 CFStorageApplyBlock(storage, range, 0, ^(const void *storagePtr, CFRange subrange, bool *stop){ 1358 while (subrange.length--) { 1359 applier(storagePtr, context); 1360 storagePtr = valueSize + (const char *)storagePtr; 1361 } 1362 }); 1363} 1364 1365void CFStorageApplyBlock(CFStorageRef storage, CFRange range, CFStorageEnumerationOptionFlags options, CFStorageApplierBlock applier) { 1366 if (! range.length) return; 1367 CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length); 1368 /* As we descend the tree, if we find we need to go down two or more children, and the concurrency token is not zero, then we decrement the concurrency token and do it concurrently. Since we have 3 children, a concurrency token of 3 yields up to 3**3 == 27 threads, which is a lot! Concurrency benefits start to kick in around one million elements */ 1369 CFIndex concurrencyToken = 0; 1370 if ((options & kCFStorageEnumerationConcurrent) && (range.length >= 1024 * 1024)) { 1371 concurrencyToken = 3; 1372 } 1373 __CFStorageEnumerateNodesInByteRangeWithBlock(storage, &storage->rootNode, 0/*globalOffsetOfNode*/, byteRange, concurrencyToken, applier); 1374} 1375 1376void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values) { 1377 CHECK_INTEGRITY(); 1378 while (range.length > 0) { 1379 CFRange leafRange; 1380 void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange, true/*requireUnfreezing*/); 1381 ASSERT(range.location >= leafRange.location); 1382 ASSERT(range.location < leafRange.location + leafRange.length); 1383 CFIndex cntThisTime = __CFMin(range.length, leafRange.length - (range.location - leafRange.location)); 1384 CFIndex byteCntThisTime = __CFStorageConvertValueToByte(storage, cntThisTime); 1385 COPYMEM(values, storagePtr, byteCntThisTime); 1386 values = (const uint8_t *)values + byteCntThisTime; 1387 range.location += cntThisTime; 1388 range.length -= cntThisTime; 1389 } 1390} 1391 1392static void __CFStorageApplyNodeBlockInterior(CFStorageRef storage, CFStorageNode *node, void (^block)(CFStorageRef storage, CFStorageNode *node)) { 1393 block(storage, node); 1394 if (! node->isLeaf) { 1395 CFStorageNode *childNode; 1396 if ((childNode = node->info.notLeaf.child[0])) __CFStorageApplyNodeBlockInterior(storage, childNode, block); 1397 if ((childNode = node->info.notLeaf.child[1])) __CFStorageApplyNodeBlockInterior(storage, childNode, block); 1398 if ((childNode = node->info.notLeaf.child[2])) __CFStorageApplyNodeBlockInterior(storage, childNode, block); 1399 } 1400} 1401 1402static void __CFStorageApplyNodeBlock(CFStorageRef storage, void (^block)(CFStorageRef storage, CFStorageNode *node)) { 1403 __CFStorageApplyNodeBlockInterior(storage, &storage->rootNode, block); 1404} 1405 1406static CFIndex __CFStorageEstimateTotalAllocatedSize(CFStorageRef storage) __attribute__((unused)); 1407static CFIndex __CFStorageEstimateTotalAllocatedSize(CFStorageRef storage) { 1408 __block CFIndex nodeResult = 0; 1409 __block CFIndex contentsResult = 0; 1410 __CFStorageApplyNodeBlock(storage, ^(CFStorageRef storage, CFStorageNode *node) { 1411 if (node != &storage->rootNode) { 1412 nodeResult += malloc_size(node); 1413 if (node->isLeaf && node->info.leaf.memory != NULL) { 1414 contentsResult += malloc_size(node->info.leaf.memory); 1415 } 1416 } 1417 }); 1418 return nodeResult + contentsResult; 1419} 1420 1421void __CFStorageSetAlwaysFrozen(CFStorageRef storage, bool alwaysFrozen) { 1422 storage->alwaysFrozen = alwaysFrozen; 1423} 1424 1425static CFIndex __CFStorageCheckNodeCachedLengthIntegrity(ConstCFStorageRef storage, const CFStorageNode *node) { 1426 if (node->isLeaf) { 1427 ASSERT(node->numBytes > 0 || node == &storage->rootNode); 1428 return node->numBytes; 1429 } else { 1430 /* Branch */ 1431 CFStorageNode *childNode; 1432 CFIndex expectedResult = __CFStorageCheckNodeCachedLengthIntegrity(storage, node->info.notLeaf.child[0]); 1433 if ((childNode = node->info.notLeaf.child[1])) { 1434 expectedResult += __CFStorageCheckNodeCachedLengthIntegrity(storage, childNode); 1435 if ((childNode = node->info.notLeaf.child[2])) { 1436 expectedResult += __CFStorageCheckNodeCachedLengthIntegrity(storage, childNode); 1437 } 1438 } 1439 ASSERT(expectedResult == node->numBytes); 1440 return expectedResult; 1441 } 1442} 1443 1444static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node) { 1445 ASSERT(node->isFrozen == 0 || node->isFrozen == 1); 1446 1447 __CFStorageCheckNodeCachedLengthIntegrity(storage, node); 1448 /* If we are a branch, make sure that we have at least one child, and that there is not a non-NULL child after a NULL child */ 1449 if (! node->isLeaf) { 1450 ASSERT(node->info.notLeaf.child[0] != NULL); 1451 if (node->info.notLeaf.child[1] == NULL) ASSERT(node->info.notLeaf.child[2] == NULL); 1452 } 1453} 1454 1455static void __CFStorageCheckIntegrity(CFStorageRef storage) { 1456 __CFStorageApplyNodeBlock(storage, ^(CFStorageRef storage, CFStorageNode *node) { 1457 __CFStorageCheckNodeIntegrity(storage, node); 1458 }); 1459} 1460 1461/* Used by CFArray.c */ 1462 1463static void __CFStorageNodeSetUnscanned(CFStorageNode *node, auto_zone_t *zone) { 1464 if (node->isLeaf) { 1465 auto_zone_set_unscanned(zone, node->info.leaf.memory); 1466 } else { 1467 CFStorageNode **children = node->info.notLeaf.child; 1468 if (children[0]) __CFStorageNodeSetUnscanned(children[0], zone); 1469 if (children[1]) __CFStorageNodeSetUnscanned(children[1], zone); 1470 if (children[2]) __CFStorageNodeSetUnscanned(children[2], zone); 1471 } 1472} 1473 1474CF_PRIVATE void _CFStorageSetWeak(CFStorageRef storage) { 1475 storage->nodeHint = 0; 1476 __CFStorageNodeSetUnscanned(&storage->rootNode, (auto_zone_t *)objc_collectableZone()); 1477} 1478 1479#undef COPYMEM 1480#undef PAGE_LIMIT 1481 1482