/*
- * Copyright (c) 2009 Apple Inc. All rights reserved.
+ * Copyright (c) 2011 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
*
* @APPLE_LICENSE_HEADER_END@
*/
+
/* CFStorage.c
- Copyright (c) 1999-2009, Apple Inc. All rights reserved.
- Responsibility: Ali Ozer
-*/
+ Copyright (c) 1999-2011, Apple Inc. All rights reserved.
+ Responsibility: Ali Ozer
+ */
/*
-2-3 tree storing arbitrary sized values.
+ 2-3 tree storing arbitrary sized values.
+
+ ??? Currently elementSize cannot be greater than storage->maxLeafCapacity, which is less than or equal to __CFStorageMaxLeafCapacity
+
+ CFStorage is thread-safe for multiple readers, but not thread safe for simultaneous reading and writing.
+ */
-??? Currently elementSize cannot be greater than storage->maxLeafCapacity, which is less than or equal to __CFStorageMaxLeafCapacity
-CFStorage is thread-safe for multiple readers, but not thread safe for simultaneous reading and writing.
-*/
+/* pammon notes on FrozenStorage
+ 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.
+
+ 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.
+
+ If a node is frozen, all of its descendants should be considered frozen.
+
+ The root node, which is defined inline within the CFStorage struct itself, can never be frozen.
+
+ */
+
+#define NO_SHIFTER ((uint32_t)(-1))
-#include "CFStorage.h"
+#include <CoreFoundation/CFStorage.h>
#include "CFInternal.h"
+#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
+#include <dispatch/dispatch.h>
+#endif
+
+#if DEPLOYMENT_TARGET_WINDOWS
+// No C99 support
+#define restrict
+
+// Replace bzero
+#define bzero(dst, size) ZeroMemory(dst, size)
+
+#endif
#if !defined(PAGE_SIZE)
#define PAGE_SIZE 4096
// Also, tests with StorageTimer.c done in 4/07 indicate that 4096 * 3 is better than smaller or larger node sizes.
#define __CFStorageMaxLeafCapacity (4096 * 3)
-// If the max length of a node is less than can fit in a half-word (half of a long), we can get away without ever caching the high half-word the cachedRange
-#if __LP64__
-#if __CFStorageMaxLeafCapacity > 0xFFFFFFFFULL
-#define POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD 1
-#endif
-#else
-#if __CFStorageMaxLeafCapacity > 0xFFFFUL
-#define POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD 1
-#endif
-#endif
-
#define COPYMEM(src,dst,n) objc_memmove_collectable((dst), (src), (n))
#define PAGE_LIMIT ((CFIndex)PAGE_SIZE / 2)
return (num + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1);
}
-
+typedef const struct __CFStorage *ConstCFStorageRef;
/* 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.)
-*/
+ */
typedef struct __CFStorageNode {
CFIndex numBytes; /* Number of actual bytes in this node and all its children */
+ 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. */
+ bool isFrozen; /* Indicates that the node is frozen, i.e. may be shared. */
bool isLeaf;
union {
struct {
CFIndex capacityInBytes; // capacityInBytes is capacity of memory; this is either 0, or >= numBytes
uint8_t *memory;
+ 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
} leaf;
struct {
struct __CFStorageNode *child[3];
} info;
} CFStorageNode;
-/* This is the struct used to store the cache in the CFStorage; it enables us to make the cache thread-safe for multiple readers (which update the cache). The values in this cache store half the desired value in the top half, and the genCount of the writer in the low half. This cache is consistent only if all of the genCounts are the same. Note that the cache does not provide thread-safety for readers in the presence of a writer.
-The cached range (location, length) is in terms of values; if the cached range is not (0,0), then the cached node needs to be non-NULL and pointing at a leaf node.
-*/
+/* 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). */
typedef struct {
- unsigned long locationHi, locationLo; // cachedRange.location
-#if POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD
- unsigned long lengthHi;
-#endif
- unsigned long lengthLo; // cachedRange.length; note that we actually do not bother with lengthHi if __CFStorageMaxLeafCapacity is less than half-word
- unsigned long cachedNodeHi, cachedNodeLo; // cachedNode
-} CFStorageAccessCacheParts;
+ CFStorageNode *child;
+ CFStorageNode *sibling;
+} CFStorageDoubleNodeReturn;
+
+CF_INLINE CFStorageDoubleNodeReturn CFStorageDoubleNodeReturnMake(CFStorageNode *child, CFStorageNode *sibling) {
+ CFStorageDoubleNodeReturn v;
+ v.child = child;
+ v.sibling = sibling;
+ return v;
+}
/* The CFStorage object.
-*/
+ */
struct __CFStorage {
CFRuntimeBase base;
CFIndex valueSize;
+ uint32_t byteToValueShifter;
CFSpinLock_t cacheReaderMemoryAllocationLock;
- int cacheGenerationCount;
- CFStorageAccessCacheParts cacheParts;
+ bool alwaysFrozen;
+ CFStorageNode * volatile cacheNode;
CFIndex maxLeafCapacity; // In terms of bytes
CFStorageNode rootNode;
CFOptionFlags nodeHint; // __kCFAllocatorGCScannedMemory or 0.
};
-
-
-
-/* Allocates the memory and initializes the capacity in a leaf. __CFStorageAllocLeafNodeMemory() is the entry point; __CFStorageAllocLeafNodeMemoryAux is called if actual reallocation is needed. __CFStorageAllocLeafNodeMemoryAux() locks not for mutations (mutations are not thread-safe in general), but for lazy allocation of storage during reading.
-*/
-static void __CFStorageAllocLeafNodeMemoryAux(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap) {
- __CFSpinLock(&(storage->cacheReaderMemoryAllocationLock));
- __CFAssignWithWriteBarrier((void **)&node->info.leaf.memory, _CFAllocatorReallocateGC(allocator, node->info.leaf.memory, cap, storage->nodeHint)); // This will free...
- if (__CFOASafe) __CFSetLastAllocationEventName(node->info.leaf.memory, "CFStorage (node bytes)");
- node->info.leaf.capacityInBytes = cap;
- __CFSpinUnlock(&(storage->cacheReaderMemoryAllocationLock));
+/* Helper function to return the intersection of two ranges */
+static inline CFRange intersectionRange(CFRange a, CFRange b) {
+ CFIndex start = __CFMax(a.location, b.location);
+ CFIndex end = __CFMin(a.location + a.length, b.location + b.length);
+ if (end <= start) {
+ return CFRangeMake(0, 0);
+ }
+ else {
+ return CFRangeMake(start, end - start);
+ }
}
+/* 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.
+ */
CF_INLINE void __CFStorageAllocLeafNodeMemory(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap, bool compact) {
if (cap > PAGE_LIMIT) {
cap = roundToPage(cap);
} else {
cap = (((cap + 63) / 64) * 64);
}
- if (compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes)) __CFStorageAllocLeafNodeMemoryAux(allocator, storage, node, cap);
+ /* 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. */
+ if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) {
+ __CFSpinLock(&(storage->cacheReaderMemoryAllocationLock));
+ /* 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. */
+ if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) {
+ __CFAssignWithWriteBarrier((void **)&node->info.leaf.memory, _CFAllocatorReallocateGC(allocator, node->info.leaf.memory, cap, storage->nodeHint)); // This will free...
+ if (__CFOASafe) __CFSetLastAllocationEventName(node->info.leaf.memory, "CFStorage (node bytes)");
+ node->info.leaf.capacityInBytes = cap;
+ }
+ __CFSpinUnlock(&(storage->cacheReaderMemoryAllocationLock));
+ }
}
+#if 0
+#define ASSERT(x) do { if (! (x)) { fprintf(stderr, "Assertion %s failed on line %d\n", #x, __LINE__); abort(); } } while (0)
+#else
+#define ASSERT(x) do { if (0 && ! (x)) { } } while(0)
+#endif
+static void __CFStorageCheckIntegrity(CFStorageRef storage);
+#define CHECK_INTEGRITY() do { if (0) __CFStorageCheckIntegrity(storage); } while (0)
+static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node);
+#define CHECK_NODE_INTEGRITY(X) do { if (0) __CFStorageCheckNodeIntegrity(storage, X); } while (0)
-#if __LP64__
-#define genCountMask 0x00000000FFFFFFFFUL
-#define dataMask 0xFFFFFFFF00000000UL
-#define shiftLowWordBy 32
-#else
-#define genCountMask 0x0000FFFFUL
-#define dataMask 0xFFFF0000UL
-#define shiftLowWordBy 16
-#endif
+#pragma mark Byte <-> Value Functions
-/* 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.
- At least one of node or memory should be non-NULL. memory is consulted first when using the cache.
-*/
-CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, CFIndex loc, CFIndex len) {
- unsigned int genCount = ((unsigned int)OSAtomicIncrement32(&storage->cacheGenerationCount)) & genCountMask;
- CFStorageAccessCacheParts cacheParts;
- cacheParts.locationHi = (loc & dataMask) | genCount;
- cacheParts.locationLo = (loc << shiftLowWordBy) | genCount;
-#if POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD
- cacheParts.lengthHi = (len & dataMask) | genCount;
-#endif
- cacheParts.lengthLo = (len << shiftLowWordBy) | genCount;
- cacheParts.cachedNodeHi = ((unsigned long)node & dataMask) | genCount;
- cacheParts.cachedNodeLo = ((unsigned long)node << shiftLowWordBy) | genCount;
- storage->cacheParts = cacheParts;
+CF_INLINE CFIndex __CFStorageConvertByteToValue(ConstCFStorageRef storage, CFIndex byte) {
+ if (storage->byteToValueShifter != NO_SHIFTER) {
+ return byte >> storage->byteToValueShifter;
+ }
+ return byte / storage->valueSize;
}
-/* Thread-safely get the cached range and node info.
-*/
-CF_INLINE Boolean __CFStorageGetCache(CFStorageRef storage, CFRange *cachedRangePtr, CFStorageNode **cachedNodePtr) {
- CFStorageAccessCacheParts cacheParts = storage->cacheParts;
+CF_INLINE CFRange __CFStorageConvertBytesToValueRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) {
+ if (storage->byteToValueShifter != NO_SHIFTER) {
+ return CFRangeMake(offset >> storage->byteToValueShifter, length >> storage->byteToValueShifter);
+ }
+ return CFRangeMake(offset / storage->valueSize, length / storage->valueSize);
+}
- unsigned int genCount = cacheParts.locationHi & genCountMask;
-
- // Check to make sure the genCounts of all the items are the same; if not, the cache was inconsistent
- if ((cacheParts.locationLo & genCountMask) == genCount &&
-#if POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD
- (cacheParts.lengthHi & genCountMask) == genCount &&
-#endif
- (cacheParts.lengthLo & genCountMask) == genCount &&
- (cacheParts.cachedNodeHi & genCountMask) == genCount &&
- (cacheParts.cachedNodeLo & genCountMask) == genCount) {
-
- *cachedNodePtr = (CFStorageNode *)((cacheParts.cachedNodeHi & dataMask) | ((cacheParts.cachedNodeLo & dataMask) >> shiftLowWordBy));
- cachedRangePtr->location = (cacheParts.locationHi & dataMask) | ((cacheParts.locationLo & dataMask) >> shiftLowWordBy);
- cachedRangePtr->length = (cacheParts.lengthLo & dataMask) >> shiftLowWordBy;
-#if POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD
- cachedRangePtr->length |= (cacheParts.lengthHi & dataMask);
-#endif
+CF_INLINE CFIndex __CFStorageConvertValueToByte(ConstCFStorageRef storage, CFIndex value) {
+ if (storage->byteToValueShifter != NO_SHIFTER) {
+ return value << storage->byteToValueShifter;
+ }
+ return value * storage->valueSize;
+}
+
+CF_INLINE CFRange __CFStorageConvertValuesToByteRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) {
+ if (storage->byteToValueShifter != NO_SHIFTER) {
+ return CFRangeMake(offset << storage->byteToValueShifter, length << storage->byteToValueShifter);
+ }
+ return CFRangeMake(offset * storage->valueSize, length * storage->valueSize);
+}
+
+
+#pragma mark Node reference counting and freezing
+
+CF_INLINE CFStorageNode *__CFStorageRetainNode(CFStorageNode *node) {
+ if (node->refCount > 0) OSAtomicIncrement32((int32_t *)&node->refCount);
+ return node;
+}
+
+/* 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 */
+CF_INLINE CFStorageNode *__CFStorageRetainNodeThreadUnsafe(CFStorageNode *node) {
+ if (node->refCount > 0) node->refCount++;
+ return node;
+}
+
+static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node);
+
+CF_INLINE void __CFStorageReleaseNode(CFStorageRef storage, CFStorageNode *node) {
+ if (node->refCount > 0) {
+ uint32_t newRefCount = OSAtomicDecrement32((int32_t *)&node->refCount);
+ if (newRefCount == 0) {
+ __CFStorageDeallocateNode(storage, node);
+ }
+ }
+}
+
+CF_INLINE void __CFStorageReleaseNodeWithNullCheck(CFStorageRef storage, CFStorageNode *node) {
+ if (node) __CFStorageReleaseNode(storage, node);
+}
+
+static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node) {
+ CFAllocatorRef allocator = CFGetAllocator(storage);
+ if (node->isLeaf) {
+ if (node->info.leaf.memory) _CFAllocatorDeallocateGC(allocator, node->info.leaf.memory);
+ } else {
+ __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[0]);
+ __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]);
+ __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]);
+ }
+ _CFAllocatorDeallocateGC(allocator, node);
+}
+static inline void __CFStorageFreezeNode(CFStorageNode *node) {
+ node->isFrozen = true;
+}
+
+/* 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. */
+static inline bool __CFStorageThawNodeDuringMutation(CFStorageRef storage, CFStorageNode *node) {
+ if (node->refCount == 1) {
+ node->isFrozen = false;
return true;
}
return false;
}
-/* Gets the location for the specified absolute loc from the cached info.
- Returns NULL if the location is not in the cache.
-*/
-CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc, CFRange *validConsecutiveValueRange) {
- CFRange cachedRange = {0, 0};
- CFStorageNode *cachedNode = 0;
+static inline void __CFStorageSetChild(CFStorageNode *parentNode, CFIndex childIndex, CFStorageNode *newChild) {
+ ASSERT(! parentNode->isLeaf);
+ ASSERT(childIndex < 3);
+ __CFAssignWithWriteBarrier((void **)&parentNode->info.notLeaf.child[childIndex], newChild);
+}
- // If we can't get values from the cache, return NULL
- if (!__CFStorageGetCache(storage, &cachedRange, &cachedNode)) return NULL;
+static inline void __CFStorageGetChildren(const CFStorageNode *parent, CFStorageNode ** restrict resultArray, bool shouldRetain, bool shouldFreeze) {
+ ASSERT(! parent->isLeaf);
+ CFIndex i;
+ for (i=0; i < 3; i++) {
+ CFStorageNode *node = parent->info.notLeaf.child[i];
+ if (node != NULL && shouldRetain) __CFStorageRetainNode(node);
+ if (node != NULL && shouldFreeze) __CFStorageFreezeNode(node);
+ resultArray[i] = node;
+ }
+}
- // Check to see if the index is in the cache
- if (loc < cachedRange.location || loc >= cachedRange.location + cachedRange.length) return NULL;
+#pragma mark Storage cache handling
- // If the cached node has no memory, return here; it will be allocated as a result of the non-cached lookup.
- if (!cachedNode->info.leaf.memory) return NULL;
+
+/* 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.
+ At least one of node or memory should be non-NULL. memory is consulted first when using the cache.
+ */
+CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, CFIndex locInBytes) {
+ if (node) {
+ ASSERT(node->isLeaf);
+ node->info.leaf.cachedRange = __CFStorageConvertBytesToValueRange(storage, locInBytes, node->numBytes);
+ }
+ storage->cacheNode = node;
+}
+
+/* Gets the location for the specified absolute loc from the cached info.
+ Returns NULL if the location is not in the cache.
+ */
+CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc, CFRange * restrict validConsecutiveValueRange, bool requireUnfrozenNode) {
+ 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. */
+ if (! cachedNode) return NULL; /* No cache */
+
+ /* We only allow caching leaf nodes. */
+ ASSERT(cachedNode->isLeaf);
+
+ /* If the node is frozen, and we require an unfrozen node, then return NULL */
+ if (requireUnfrozenNode && cachedNode->isFrozen) return NULL;
+
+ /* If there's no memory allocated yet, then allocate it now*/
+ if (! cachedNode->info.leaf.memory) {
+ __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, cachedNode, cachedNode->numBytes, false);
+ }
- // The cache has consistent values, and in fact, the values we're looking for!
- uint8_t *result = cachedNode->info.leaf.memory + (loc - cachedRange.location) * storage->valueSize;
- *validConsecutiveValueRange = cachedRange;
+ /* If the node's range starts after loc, or ends before or at loc, return NULL */
+ CFIndex nodeOffset = cachedNode->info.leaf.cachedRange.location;
+ CFIndex nodeLength = cachedNode->info.leaf.cachedRange.length;
+ if (loc < nodeOffset || loc >= nodeOffset + nodeLength) {
+ return NULL;
+ }
+ /* The cache is valid, so return it */
+ validConsecutiveValueRange->location = nodeOffset;
+ validConsecutiveValueRange->length = nodeLength;
+ uint8_t *result = cachedNode->info.leaf.memory + __CFStorageConvertValueToByte(storage, loc - nodeOffset);
return result;
}
-
-
/* Returns the number of the child containing the desired value and the relative index of the value in that child.
- forInsertion = true means that we are looking for the child in which to insert; this changes the behavior when the index is at the end of a child
- relativeByteNum (not optional, for performance reasons) returns the relative byte number of the specified byte in the child.
- Don't call with leaf nodes!
-*/
-CF_INLINE void __CFStorageFindChild(CFStorageNode *node, CFIndex byteNum, bool forInsertion, CFIndex *childNum, CFIndex *relativeByteNum) {
- if (forInsertion) byteNum--; /* If for insertion, we do <= checks, not <, so this accomplishes the same thing */
- if (byteNum < node->info.notLeaf.child[0]->numBytes) *childNum = 0;
+ 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
+ relativeByteNum (not optional, for performance reasons) returns the relative byte number of the specified byte in the child.
+ Don't call with leaf nodes!
+ */
+CF_INLINE CFStorageNode *__CFStorageFindChild(const CFStorageNode * restrict node, CFIndex byteNum, bool forInsertionOrDeletion, CFIndex * restrict childNum, CFIndex * restrict relativeByteNum) {
+ if (forInsertionOrDeletion) byteNum--; /* If for insertion, we do <= checks, not <, so this accomplishes the same thing */
+ CFStorageNode *result;
+ result = node->info.notLeaf.child[0];
+ if (byteNum < result->numBytes) *childNum = 0;
else {
- byteNum -= node->info.notLeaf.child[0]->numBytes;
- if (byteNum < node->info.notLeaf.child[1]->numBytes) *childNum = 1;
+ byteNum -= result->numBytes;
+ result = node->info.notLeaf.child[1];
+ if (byteNum < result->numBytes) *childNum = 1;
else {
- byteNum -= node->info.notLeaf.child[1]->numBytes;
+ byteNum -= result->numBytes;
*childNum = 2;
+ result = node->info.notLeaf.child[2];
}
}
- if (forInsertion) byteNum++;
+ if (forInsertionOrDeletion) byteNum++;
*relativeByteNum = byteNum;
+ return result;
}
+static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node);
+
/* Finds the location where the specified byte is stored. If validConsecutiveByteRange is not NULL, returns
- the range of bytes that are consecutive with this one.
- !!! Assumes the byteNum is within the range of this node.
-*/
-static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFStorageNode **resultNode, CFRange *validConsecutiveByteRange) {
+ the range of bytes that are consecutive with this one.
+ !!! Assumes the byteNum is within the range of this node.
+ */
+static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex absoluteByteOffsetOfNode, CFStorageNode **resultNode, CFRange *validConsecutiveByteRange, bool requireUnfreezing) {
if (node->isLeaf) {
- if (validConsecutiveByteRange) *validConsecutiveByteRange = CFRangeMake(0, node->numBytes);
+ *validConsecutiveByteRange = CFRangeMake(absoluteByteOffsetOfNode, node->numBytes);
+ *resultNode = node;
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
- if (resultNode) *resultNode = node;
- return node->info.leaf.memory + byteNum;
+ return node->info.leaf.memory + byteNum;
} else {
- void *result;
CFIndex childNum;
CFIndex relativeByteNum;
- __CFStorageFindChild(node, byteNum, false, &childNum, &relativeByteNum);
- result = __CFStorageFindByte(storage, node->info.notLeaf.child[childNum], relativeByteNum, resultNode, validConsecutiveByteRange);
- if (validConsecutiveByteRange) {
- if (childNum > 0) validConsecutiveByteRange->location += node->info.notLeaf.child[0]->numBytes;
- if (childNum > 1) validConsecutiveByteRange->location += node->info.notLeaf.child[1]->numBytes;
- }
- return result;
+ CFStorageNode *child = __CFStorageFindChild(node, byteNum, false, &childNum, &relativeByteNum);
+ if (requireUnfreezing && child->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, child)) {
+ /* Replace the child with an unfrozen variant */
+ CFStorageNode *unfrozenReplacement = __CFStorageCopyNode(storage, child);
+ /* Release the old node, set the new one */
+ __CFStorageSetChild(node, childNum, unfrozenReplacement);
+ __CFStorageReleaseNode(storage, child);
+ child = unfrozenReplacement;
+ }
+ return __CFStorageFindByte(storage, child, relativeByteNum, absoluteByteOffsetOfNode + (byteNum - relativeByteNum), resultNode, validConsecutiveByteRange, requireUnfreezing);
}
}
/* Guts of CFStorageGetValueAtIndex(); note that validConsecutiveValueRange is not optional.
- Consults and updates cache.
-*/
-CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
+ Consults and updates cache.
+ */
+CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange, bool requireUnfreezing) {
uint8_t *result;
- if (!(result = __CFStorageGetFromCache(storage, idx, validConsecutiveValueRange))) {
- CFRange rangeInBytes;
+ if (!(result = __CFStorageGetFromCache(storage, idx, validConsecutiveValueRange, requireUnfreezing))) {
CFStorageNode *resultNode;
- result = (uint8_t *)__CFStorageFindByte(storage, &storage->rootNode, idx * storage->valueSize, &resultNode, &rangeInBytes);
- CFRange rangeInValues = CFRangeMake(rangeInBytes.location / storage->valueSize, rangeInBytes.length / storage->valueSize);
- __CFStorageSetCache(storage, resultNode, rangeInValues.location, rangeInValues.length);
- *validConsecutiveValueRange = rangeInValues;
+ CFRange rangeInBytes;
+ result = (uint8_t *)__CFStorageFindByte(storage, &storage->rootNode, __CFStorageConvertValueToByte(storage, idx), 0, &resultNode, &rangeInBytes, requireUnfreezing);
+ __CFStorageSetCache(storage, resultNode, rangeInBytes.location);
+ *validConsecutiveValueRange = __CFStorageConvertBytesToValueRange(storage, rangeInBytes.location, rangeInBytes.length);
}
return result;
}
-// returns refcount==1 node under GC
-static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, bool isLeaf, CFIndex numBytes) {
+/* 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.
+ */
+static void __CFLeafCopyRangeToOffset(const CFStorageNode *srcLeaf, CFRange srcRange, CFStorageNode *dstLeaf, CFIndex dstLocation) {
+ ASSERT(srcLeaf->isLeaf);
+ ASSERT(dstLeaf->isLeaf);
+ if (srcRange.length > 0) {
+ ASSERT(srcLeaf->info.leaf.memory != NULL);
+ ASSERT(dstLeaf->info.leaf.memory != NULL);
+ ASSERT(srcRange.location + srcRange.length <= srcLeaf->numBytes);
+ ASSERT(dstLocation + srcRange.length <= dstLeaf->info.leaf.capacityInBytes);
+ COPYMEM(srcLeaf->info.leaf.memory + srcRange.location, dstLeaf->info.leaf.memory + dstLocation, srcRange.length);
+ }
+}
+
+#pragma mark Node creation and destruction
+
+// returns a node with a refCount of 1, and an auto_zone_retain() under GC
+static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, CFStorageRef storage, bool isLeaf, CFIndex numBytes) {
CFStorageNode *newNode = (CFStorageNode *)CFAllocatorAllocate(allocator, sizeof(CFStorageNode), __kCFAllocatorGCScannedMemory);
if (__CFOASafe) __CFSetLastAllocationEventName(newNode, "CFStorage (node)");
+ if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
+ auto_zone_release(objc_collectableZone(), newNode); //remove the implicit retain so we can be collected
+ }
+ newNode->refCount = 1;
+ newNode->isFrozen = storage->alwaysFrozen;
newNode->isLeaf = isLeaf;
newNode->numBytes = numBytes;
if (isLeaf) {
return newNode;
}
-static void __CFStorageNodeDealloc(CFAllocatorRef allocator, CFStorageNode *node, bool freeNodeItself) {
+/* 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. */
+static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node) {
+ CFAllocatorRef allocator = CFGetAllocator(storage);
+ CFStorageNode *result = __CFStorageCreateNode(allocator, storage, node->isLeaf, node->numBytes);
if (node->isLeaf) {
- _CFAllocatorDeallocateGC(allocator, node->info.leaf.memory);
- } else {
- int cnt;
- for (cnt = 0; cnt < 3; cnt++) if (node->info.notLeaf.child[cnt]) __CFStorageNodeDealloc(allocator, node->info.notLeaf.child[cnt], true);
+ if (node->info.leaf.memory != NULL) {
+ __CFStorageAllocLeafNodeMemory(allocator, storage, result, result->numBytes, false);
+ COPYMEM(node->info.leaf.memory, result->info.leaf.memory, result->numBytes);
+ }
+ }
+ else {
+ CFStorageNode *child = node->info.notLeaf.child[0];
+ __CFStorageSetChild(result, 0, __CFStorageRetainNode(child));
+ if ((child = node->info.notLeaf.child[1])) __CFStorageSetChild(result, 1, __CFStorageRetainNode(child));
+ if ((child = node->info.notLeaf.child[2])) __CFStorageSetChild(result, 2, __CFStorageRetainNode(child));
+
+ /* If we are copying children from a frozen node to an unfrozen node, we need to freeze the children */
+ if (node->isFrozen) {
+ __CFStorageFreezeNode(result->info.notLeaf.child[0]);
+ if ((child = result->info.notLeaf.child[1])) __CFStorageFreezeNode(child);
+ if ((child = result->info.notLeaf.child[2])) __CFStorageFreezeNode(child);
+ }
+ }
+ return result;
+}
+
+
+static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node);
+
+
+#pragma mark Insertion and Deletion prototypes
+/* 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).
+
+ 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.
+
+ 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.
+ */
+static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
+static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact);
+
+static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
+static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range);
+
+static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
+static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode);
+
+#pragma mark Frozen Deletion
+
+static CFStorageNode *__CFStorageDeleteLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
+ ASSERT(node->isLeaf);
+ const CFIndex rangeToDeleteEnd = range.location + range.length;
+ ASSERT(rangeToDeleteEnd <= node->numBytes);
+ CFIndex remainingBytes = node->numBytes - range.length;
+ if (remainingBytes == 0) {
+ /* The range to delete encompasses our entire range of bytes. Return NULL to indicate that we should be deleted. */
+ return NULL;
+ }
+ else {
+ /* Need to create a new node */
+ CFStorageNode *newNode = __CFStorageCreateNode(allocator, storage, true, remainingBytes);
+ if (node->info.leaf.memory) {
+ /* Our node had memory allocated, so copy in the non-deleted portion */
+ CFRange nonDeletedPrefix = CFRangeMake(0, range.location);
+ CFRange nonDeletedSuffix = CFRangeMake(rangeToDeleteEnd, node->numBytes - rangeToDeleteEnd);
+ ASSERT(nonDeletedPrefix.length + nonDeletedSuffix.length == remainingBytes);
+ __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, remainingBytes, false); // no point in compacting since we're freshly allocated
+ __CFLeafCopyRangeToOffset(node, nonDeletedPrefix, newNode, 0);
+ __CFLeafCopyRangeToOffset(node, nonDeletedSuffix, newNode, nonDeletedPrefix.length);
+ }
+ return newNode;
+ }
+}
+
+/* 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!
+ */
+static inline CFIndex __CFStoragePopulateBranchChildrenAfterDeletion(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range, CFStorageNode *newChildren[3], bool childrenAreDefinitelyFrozen, bool compact) {
+ CFIndex newChildIndex = 0;
+ CFIndex childByteOffset = 0; //will track the current start byte of this child
+ for (CFIndex existingChildIndex = 0; existingChildIndex < 3; existingChildIndex++) {
+ CFStorageNode *existingChild = node->info.notLeaf.child[existingChildIndex];
+ if (! existingChild) break; //no more children
+ const CFIndex existingChildLength = existingChild->numBytes;
+ /* The child's range is {byteOffset, existingChildLength}. Figure out what part of the range to delete is intersected by this child's range */
+ CFRange deletionRangeIntersectedByChild = intersectionRange(range, CFRangeMake(childByteOffset, existingChildLength));
+ if (! deletionRangeIntersectedByChild.length) {
+ /* The range to delete does not overlap this child's range, so preserve the child */
+ newChildren[newChildIndex++] = __CFStorageRetainNode(existingChild); //bump the refcount like we promised we would
+ if (childrenAreDefinitelyFrozen) {
+ /* Because we are about to add this child from a frozen node to a possibly unfrozen node, mark the child as frozen */
+ __CFStorageFreezeNode(existingChild);
+ }
+ }
+ else {
+ /* We have something from this child to delete */
+ CFRange rangeOfChildToDelete = CFRangeMake(deletionRangeIntersectedByChild.location - childByteOffset, deletionRangeIntersectedByChild.length);
+ CFStorageNode *newChild;
+ if (childrenAreDefinitelyFrozen) {
+ newChild = __CFStorageDeleteFrozen(allocator, storage, existingChild, rangeOfChildToDelete);
+ }
+ else {
+ newChild = __CFStorageDelete(allocator, storage, existingChild, rangeOfChildToDelete, compact);
+ }
+ /* We may get null back if we deleted the entire child */
+ if (newChild != NULL) {
+ newChildren[newChildIndex++] = newChild; // Transfers the reference count
+ }
+
+ if (rangeOfChildToDelete.length == existingChildLength) {
+ ASSERT(newChild == NULL); //should have deleted everything
+ }
+ else {
+ ASSERT(newChild != NULL);
+ ASSERT(newChild->numBytes == existingChildLength - rangeOfChildToDelete.length);
+ }
+ }
+ childByteOffset += existingChildLength;
+ }
+ return newChildIndex;
+}
+
+static CFStorageNode *__CFStorageDeleteBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
+ ASSERT(! node->isLeaf);
+ ASSERT(range.location + range.length <= node->numBytes);
+ if (range.length == node->numBytes) {
+ /* They're deleting everything, so return NULL to indicate that this node should be deleted. */
+ return NULL;
+ }
+
+ /* Construct our new children in this array. */
+ CFStorageNode *newChildren[3];
+ CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, true/*childrenAreDefinitelyFrozen*/, false/*compact*/);
+
+ /* 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. */
+
+ /* 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. */
+ ASSERT(newChildIndex >= 1);
+ if (newChildIndex == 1) {
+ /* Only one child, so just return it, transferring its retain count */
+ return newChildren[0];
+ }
+ else {
+ CFStorageNode *result = __CFStorageCreateNode(allocator, storage, false, 0);
+ while (newChildIndex--) {
+ __CFStorageSetChild(result, newChildIndex, newChildren[newChildIndex]); //transfers the reference count
+ }
+ result->numBytes = node->numBytes - range.length;
+ return result;
}
- if (freeNodeItself) _CFAllocatorDeallocateGC(allocator, node);
}
-static CFIndex __CFStorageGetNumChildren(CFStorageNode *node) {
- if (!node || node->isLeaf) return 0;
- if (node->info.notLeaf.child[2]) return 3;
- if (node->info.notLeaf.child[1]) return 2;
- if (node->info.notLeaf.child[0]) return 1;
- return 0;
+/* Returns a new node, or NULL if the entire thing was deleted.
+ */
+static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
+ if (node->isLeaf) {
+ return __CFStorageDeleteLeafFrozen(allocator, storage, node, range);
+ }
+ else {
+ return __CFStorageDeleteBranchFrozen(allocator, storage, node, range);
+ }
}
+#pragma mark Unfrozen Deletion
+
/* The boolean compact indicates whether leaf nodes that get smaller should be realloced.
-*/
-static void __CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) {
+ */
+static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode) {
+ ASSERT(! node->isFrozen);
+ ASSERT(range.location + range.length <= node->numBytes);
+ CHECK_NODE_INTEGRITY(node);
+
+ if (range.length == node->numBytes) {
+ /* We are deleting everything, so return NULL */
+ return NULL;
+ }
+
if (node->isLeaf) {
node->numBytes -= range.length;
- // If this node had memory allocated, readjust the bytes...
+ // If this node had memory allocated, readjust the bytes...
if (node->info.leaf.memory) {
- COPYMEM(node->info.leaf.memory + range.location + range.length, node->info.leaf.memory + range.location, node->numBytes - range.location);
+ COPYMEM(node->info.leaf.memory + range.location + range.length, node->info.leaf.memory + range.location, node->numBytes - range.location);
if (compact) __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes, true);
}
- } else {
- bool childrenAreLeaves = node->info.notLeaf.child[0]->isLeaf;
+ CHECK_NODE_INTEGRITY(node);
+ return __CFStorageRetainNodeThreadUnsafe(node); //we can use the ThreadUnsafe calls because this is the Unfrozen variant, so we are not shared
+ } else {
+ CFStorageNode *newChildren[3] = {NULL, NULL, NULL};
+ CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, false/*childrenAreDefinitelyFrozen*/, compact);
node->numBytes -= range.length;
- while (range.length > 0) {
- CFRange rangeToDelete;
- CFIndex relativeByteNum;
- CFIndex childNum;
- __CFStorageFindChild(node, range.location + range.length, true, &childNum, &relativeByteNum);
- if (range.length > relativeByteNum) {
- rangeToDelete.length = relativeByteNum;
- rangeToDelete.location = 0;
- } else {
- rangeToDelete.length = range.length;
- rangeToDelete.location = relativeByteNum - range.length;
- }
- __CFStorageDelete(allocator, storage, node->info.notLeaf.child[childNum], rangeToDelete, compact);
- if (node->info.notLeaf.child[childNum]->numBytes == 0) { // Delete empty node and compact
- int cnt;
- _CFAllocatorDeallocateGC(allocator, node->info.notLeaf.child[childNum]);
- for (cnt = childNum; cnt < 2; cnt++) {
- __CFAssignWithWriteBarrier((void **)&node->info.notLeaf.child[cnt], node->info.notLeaf.child[cnt+1]);
- }
- node->info.notLeaf.child[2] = NULL;
- }
- range.length -= rangeToDelete.length;
+ ASSERT(newChildIndex >= 1); //we expect to have at least one child; else we would have deleted everything up above
+
+ /* 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 */
+ __CFStorageReleaseNode(storage, node->info.notLeaf.child[0]);
+ __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]);
+ __CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]);
+ node->info.notLeaf.child[0] = node->info.notLeaf.child[1] = node->info.notLeaf.child[2] = NULL;
+
+ if (newChildIndex == 1) {
+ /* We have only one child, so return it, transferring the refcount that __CFStoragePopulate gives it */
+ return newChildren[0];
}
- // At this point the remaining children are packed
- if (childrenAreLeaves) {
- // Children are leaves; if their total bytes is smaller than a leaf's worth, collapse into one...
- if (node->numBytes > 0 && node->numBytes <= storage->maxLeafCapacity) {
- __CFStorageAllocLeafNodeMemory(allocator, storage, node->info.notLeaf.child[0], node->numBytes, false);
- if (node->info.notLeaf.child[1] && node->info.notLeaf.child[1]->numBytes) {
- COPYMEM(node->info.notLeaf.child[1]->info.leaf.memory, node->info.notLeaf.child[0]->info.leaf.memory + node->info.notLeaf.child[0]->numBytes, node->info.notLeaf.child[1]->numBytes);
- if (node->info.notLeaf.child[2] && node->info.notLeaf.child[2]->numBytes) {
- COPYMEM(node->info.notLeaf.child[2]->info.leaf.memory, node->info.notLeaf.child[0]->info.leaf.memory + node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes, node->info.notLeaf.child[2]->numBytes);
- __CFStorageNodeDealloc(allocator, node->info.notLeaf.child[2], true);
- node->info.notLeaf.child[2] = NULL;
- }
- __CFStorageNodeDealloc(allocator, node->info.notLeaf.child[1], true);
- node->info.notLeaf.child[1] = NULL;
- }
- node->info.notLeaf.child[0]->numBytes = node->numBytes;
- }
- } else {
- // Children are not leaves; combine their children to assure each node has 2 or 3 children...
- // (Could try to bypass all this by noting up above whether the number of grandchildren changed...)
- CFStorageNode *gChildren[9];
- CFIndex cCnt, gCnt, cnt;
- CFIndex totalG = 0; // Total number of grandchildren
- for (cCnt = 0; cCnt < 3; cCnt++) {
- CFStorageNode *child = node->info.notLeaf.child[cCnt];
- if (child) {
- for (gCnt = 0; gCnt < 3; gCnt++) if (child->info.notLeaf.child[gCnt]) {
- gChildren[totalG++] = child->info.notLeaf.child[gCnt];
- child->info.notLeaf.child[gCnt] = NULL;
- }
- child->numBytes = 0;
- }
- }
- gCnt = 0; // Total number of grandchildren placed
- for (cCnt = 0; cCnt < 3; cCnt++) {
- // These tables indicate how many children each child should have, given the total number of grandchildren (last child gets remainder)
- static const unsigned char forChild0[10] = {0, 1, 2, 3, 2, 3, 3, 3, 3, 3};
- static const unsigned char forChild1[10] = {0, 0, 0, 0, 2, 2, 3, 2, 3, 3};
- // sCnt is the number of grandchildren to be placed into child cCnt
- // Depending on child number, pick the right number
- CFIndex sCnt = (cCnt == 0) ? forChild0[totalG] : ((cCnt == 1) ? forChild1[totalG] : totalG);
- // Assure we have that many grandchildren...
- if (sCnt > totalG - gCnt) sCnt = totalG - gCnt;
- if (sCnt) {
- if (!node->info.notLeaf.child[cCnt]) {
- CFStorageNode *newNode = __CFStorageCreateNode(allocator, false, 0);
- __CFAssignWithWriteBarrier((void **)&node->info.notLeaf.child[cCnt], newNode);
- Boolean GC = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
- if (GC) auto_zone_release(auto_zone(), newNode);
- }
- for (cnt = 0; cnt < sCnt; cnt++) {
- node->info.notLeaf.child[cCnt]->numBytes += gChildren[gCnt]->numBytes;
- __CFAssignWithWriteBarrier((void **)&node->info.notLeaf.child[cCnt]->info.notLeaf.child[cnt], gChildren[gCnt++]);
- }
- } else {
- if (node->info.notLeaf.child[cCnt]) {
- _CFAllocatorDeallocateGC(allocator, node->info.notLeaf.child[cCnt]);
- node->info.notLeaf.child[cCnt] = NULL;
- }
- }
+ else {
+ CFIndex i;
+ for (i=0; i < 3; i++) {
+ __CFStorageSetChild(node, i, newChildren[i]); //set the new child, transferring the refcount to us (or set NULL)
}
- }
+ CHECK_NODE_INTEGRITY(node);
+ return __CFStorageRetainNodeThreadUnsafe(node);
+ }
+ }
+}
+
+#pragma mark Frozen Insertion
+
+/* 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. */
+static CFStorageDoubleNodeReturn __CFStorageInsertLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ /* 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. */
+ CFStorageNode *leftResult, *rightResult;
+ CHECK_NODE_INTEGRITY(node);
+ ASSERT(byteNum <= node->numBytes);
+ CFIndex newTotalSize = size + node->numBytes;
+ if (newTotalSize <= storage->maxLeafCapacity) {
+ /* We can fit into a single node */
+ rightResult = NULL;
+ leftResult = __CFStorageCreateNode(allocator, storage, true, newTotalSize);
+ if (node->info.leaf.memory != NULL) { // Beware lazy memory allocation
+ __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, newTotalSize, false);
+ COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum); //copy first byteNum bytes from existing node
+ //middle we don't touch
+ COPYMEM(node->info.leaf.memory + byteNum, leftResult->info.leaf.memory + byteNum + size, node->numBytes - byteNum); //copy last part from existing node
+ }
+ __CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
+ }
+ else {
+ /* We cannot fit into a single node. See if we can preserve self (i.e. we're inserting at beginning or end). */
+ if (byteNum == node->numBytes) {
+ /* 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 */
+ leftResult = (CFStorageNode *)node;
+ rightResult = __CFStorageCreateNode(allocator, storage, true, size);
+ __CFStorageSetCache(storage, rightResult, absoluteByteNum);
+ }
+ else if (byteNum == 0) {
+ /* 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. */
+ rightResult = __CFStorageRetainNode((CFStorageNode *)node);
+ leftResult = __CFStorageCreateNode(allocator, storage, true, size);
+ __CFStorageSetCache(storage, leftResult, absoluteByteNum);
+ }
+ else {
+ /* 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. */
+ CFIndex leftAmount = storage->maxLeafCapacity, rightAmount = newTotalSize - storage->maxLeafCapacity;
+ leftResult = __CFStorageCreateNode(allocator, storage, true, leftAmount);
+ rightResult = __CFStorageCreateNode(allocator, storage, true, rightAmount);
+ __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, leftAmount, false);
+ __CFStorageAllocLeafNodeMemory(allocator, storage, rightResult, rightAmount, false);
+ ASSERT(node->info.leaf.capacityInBytes >= node->numBytes);
+
+ /* The existing node has length node->numBytes, so it has the following range: {0, node->numBytes}
+
+ 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}:
+ {0, byteNum}, {byteNum + size, node->numBytes - byteNum}
+
+ We need to divide these among our new nodes with the following logical ranges:
+ {0, leftAmount}, {leftAmount, rightAmount}
+
+ 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.
+ */
+
+ ASSERT(byteNum <= leftAmount);
+ COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum);
+
+ const CFRange leftNodeRange = {0, leftAmount}, rightNodeRange = {leftAmount, rightAmount};
+ const CFRange preservedData = {byteNum + size, node->numBytes - byteNum};
+ CFRange overlap;
+ if ((overlap = intersectionRange(leftNodeRange, preservedData)).length > 0) COPYMEM(node->info.leaf.memory + overlap.location - size, leftResult->info.leaf.memory + overlap.location, overlap.length);
+ if ((overlap = intersectionRange(rightNodeRange, preservedData)).length > 0) COPYMEM(node->info.leaf.memory + overlap.location - size, rightResult->info.leaf.memory + overlap.location - leftAmount, overlap.length);
+ __CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
+ }
+ }
+ return CFStorageDoubleNodeReturnMake(leftResult, rightResult);
+}
+
+static CFStorageDoubleNodeReturn __CFStorageInsertBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ /* 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. */
+ CHECK_NODE_INTEGRITY(node);
+ CFStorageNode *copyOfMe = __CFStorageCreateNode(allocator, storage, false, 0);
+ CFStorageNode *siblingOfMe = NULL;
+ CFIndex relativeByteNum;
+ CFIndex childNum;
+ CFStorageNode *child = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
+ ASSERT(childNum >= 0 && childNum <= 2);
+ CFStorageDoubleNodeReturn childReturn = __CFStorageInsertFrozen(allocator, storage, child, relativeByteNum, size, absoluteByteNum);
+ ASSERT(childReturn.child); //we always get at least one back
+
+ /* Make a local array of all new children (retained). We'll then move them to the new nodes. */
+ CFStorageNode *newChildren[4] = {NULL};
+ __CFStorageGetChildren(node, newChildren, true/*retain*/, true/*freeze*/);
+ if (newChildren[childNum] != childReturn.child) {
+ __CFStorageReleaseNode(storage, newChildren[childNum]);
+ newChildren[childNum] = childReturn.child; // Transfers the retain
+ }
+ if (childReturn.sibling != NULL) {
+ if (childNum < 2) newChildren[3] = newChildren[2];
+ if (childNum < 1) newChildren[2] = newChildren[1];
+ newChildren[childNum + 1] = childReturn.sibling; // Transfers the retain
+ }
+
+ /* First two always go to our clone */
+ __CFStorageSetChild(copyOfMe, 0, newChildren[0]);
+ __CFStorageSetChild(copyOfMe, 1, newChildren[1]);
+ if (newChildren[3] == NULL) {
+ /* 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'. */
+ __CFStorageSetChild(copyOfMe, 2, newChildren[2]);
+ copyOfMe->numBytes = node->numBytes + size;
+ }
+ else {
+ /* We have four children to distribute. The first two go to us, the last two go to our new sibling. */
+ siblingOfMe = __CFStorageCreateNode(allocator, storage, false, 0);
+ __CFStorageSetChild(siblingOfMe, 0, newChildren[2]);
+ __CFStorageSetChild(siblingOfMe, 1, newChildren[3]);
+ copyOfMe->numBytes = newChildren[0]->numBytes + newChildren[1]->numBytes;
+ siblingOfMe->numBytes = newChildren[2]->numBytes + newChildren[3]->numBytes;
+ }
+ CHECK_NODE_INTEGRITY(node);
+ CHECK_NODE_INTEGRITY(copyOfMe);
+ if (siblingOfMe) CHECK_NODE_INTEGRITY(siblingOfMe);
+ return CFStorageDoubleNodeReturnMake(copyOfMe, siblingOfMe);
+}
+
+static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ if (node->isLeaf) {
+ return __CFStorageInsertLeafFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
+ }
+ else {
+ return __CFStorageInsertBranchFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
}
+#pragma mark Unfrozen Insertion
+
+/* Insertion into an unfrozen leaf. We return two nodes, one of which is 'node'. This always sets the cache. */
+static CFStorageDoubleNodeReturn __CFStorageInsertLeafUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ if (size + node->numBytes > storage->maxLeafCapacity) { // Need to create more child nodes
+ CFStorageNode *newNode;
+ if (byteNum == node->numBytes) { // Inserting at end; easy...
+ newNode = __CFStorageCreateNode(allocator, storage, true, size);
+ __CFStorageSetCache(storage, newNode, absoluteByteNum);
+ } else if (byteNum == 0) { // Inserting at front; also easy, but we need to swap node and newNode
+ newNode = __CFStorageCreateNode(allocator, storage, true, 0);
+
+ /* Transfer our memory to the new node */
+ newNode->numBytes = node->numBytes;
+ newNode->info.leaf.capacityInBytes = node->info.leaf.capacityInBytes;
+ __CFAssignWithWriteBarrier((void **)&newNode->info.leaf.memory, node->info.leaf.memory);
+
+ /* Stomp on our existing node */
+ node->numBytes = size;
+ node->info.leaf.capacityInBytes = 0;
+ node->info.leaf.memory = NULL;
+
+ /* Cache our existing node */
+ __CFStorageSetCache(storage, node, absoluteByteNum);
+ } else if (byteNum + size <= storage->maxLeafCapacity) { // Inserting at middle; inserted region will fit into existing child
+ // Create new node to hold the overflow
+ newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes - byteNum);
+ if (node->info.leaf.memory) { // We allocate memory lazily...
+ __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes - byteNum, false);
+ COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory, node->numBytes - byteNum);
+ __CFStorageAllocLeafNodeMemory(allocator, storage, node, byteNum + size, false);
+ }
+ node->numBytes = byteNum + size;
+ __CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
+ } else { // Inserting some of new into one node, rest into another; remember that the assumption is size <= storage->maxLeafCapacity
+ newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes + size - storage->maxLeafCapacity); // New stuff
+ if (node->info.leaf.memory) { // We allocate memory lazily...
+ __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes + size - storage->maxLeafCapacity, false);
+ COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory + byteNum + size - storage->maxLeafCapacity, node->numBytes - byteNum);
+ __CFStorageAllocLeafNodeMemory(allocator, storage, node, storage->maxLeafCapacity, false);
+ }
+ __CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
+ node->numBytes = storage->maxLeafCapacity;
+ }
+ return CFStorageDoubleNodeReturnMake(node, newNode); // We do not retain 'node' because it is the given node.
+ } else { // No need to create new nodes!
+ if (node->info.leaf.memory) {
+ __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes + size, false);
+ COPYMEM(node->info.leaf.memory + byteNum, node->info.leaf.memory + byteNum + size, node->numBytes - byteNum);
+ }
+ node->numBytes += size;
+ __CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
+ 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.
+ }
+}
+
+static CFStorageDoubleNodeReturn __CFStorageInsertBranchUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ CFIndex relativeByteNum;
+ 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.
+ CFStorageNode *childNode = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
+ CFStorageDoubleNodeReturn newNodes = __CFStorageInsert(allocator, storage, childNode, relativeByteNum, size, absoluteByteNum);
+ 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
+ ASSERT(childNode != NULL);
+ ASSERT(newNodes.child != NULL);
+
+ if (newNodes.child != childNode) {
+ /* We got back a replacement for the current child, so replace it. */
+ __CFStorageReleaseNode(storage, childNode);
+ __CFStorageSetChild(node, childNum, newNodes.child);
+ }
+
+ if (newNodes.sibling == NULL) {
+ /* The insertion happened successfully without requiring us to add any new nodes. */
+ node->numBytes += size;
+ } else {
+ /* We got back an additional node to insert. */
+ CFStorageNode *newChild = newNodes.sibling;
+ if (node->info.notLeaf.child[2] == NULL) { // There's an empty slot for the new node, cool
+ if (childNum == 0) __CFStorageSetChild(node, 2, node->info.notLeaf.child[1]); // Make room
+ __CFStorageSetChild(node, childNum+1, newChild);
+ node->numBytes += size;
+ } else {
+ CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, storage, false, 0); // Create another node
+ if (childNum == 0) { // Last two children go to new node
+ __CFStorageSetChild(anotherNode, 0, node->info.notLeaf.child[1]);
+ __CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]);
+ __CFStorageSetChild(node, 1, newChild);
+ node->info.notLeaf.child[2] = NULL;
+ } else if (childNum == 1) { // Last child goes to new node
+ __CFStorageSetChild(anotherNode, 0, newChild);
+ __CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]);
+ node->info.notLeaf.child[2] = NULL;
+ } else { // New node contains the new comers...
+ __CFStorageSetChild(anotherNode, 0, node->info.notLeaf.child[2]);
+ __CFStorageSetChild(anotherNode, 1, newChild);
+ node->info.notLeaf.child[2] = NULL;
+ }
+ node->numBytes = node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes;
+ anotherNode->numBytes = anotherNode->info.notLeaf.child[0]->numBytes + anotherNode->info.notLeaf.child[1]->numBytes;
+ /* node should not be retained because it is the passed in node. anotherNode was created so we transfer its retain count */
+ result.sibling = anotherNode;
+ }
+ }
+ return result;
+}
+
+
+
/* Returns NULL or additional node to come after this node
- Assumption: size is never > storage->maxLeafCapacity
- Under GC node has a retain count to keep it alive in unregistered pthreads
-*/
-static CFStorageNode *__CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ Assumption: size is never > storage->maxLeafCapacity
+ */
+static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ ASSERT(! node->isFrozen);
if (node->isLeaf) {
- if (size + node->numBytes > storage->maxLeafCapacity) { // Need to create more child nodes
- if (byteNum == node->numBytes) { // Inserting at end; easy...
- CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, size);
- __CFStorageSetCache(storage, newNode, absoluteByteNum / storage->valueSize, size / storage->valueSize);
- return newNode;
- } else if (byteNum == 0) { // Inserting at front; also easy, but we need to swap node and newNode
- CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, 0);
- objc_memmove_collectable(newNode, node, sizeof(CFStorageNode));
- node->isLeaf = true;
- node->numBytes = size;
- node->info.leaf.capacityInBytes = 0;
- node->info.leaf.memory = NULL;
- __CFStorageSetCache(storage, node, absoluteByteNum / storage->valueSize, size / storage->valueSize);
- return newNode;
- } else if (byteNum + size <= storage->maxLeafCapacity) { // Inserting at middle; inserted region will fit into existing child
- // Create new node to hold the overflow
- CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, node->numBytes - byteNum);
- if (node->info.leaf.memory) { // We allocate memory lazily...
- __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes - byteNum, false);
- COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory, node->numBytes - byteNum);
- __CFStorageAllocLeafNodeMemory(allocator, storage, node, byteNum + size, false);
- }
- node->numBytes = byteNum + size;
- __CFStorageSetCache(storage, node, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
- return newNode;
- } else { // Inserting some of new into one node, rest into another; remember that the assumption is size <= storage->maxLeafCapacity
- CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, node->numBytes + size - storage->maxLeafCapacity); // New stuff
- if (node->info.leaf.memory) { // We allocate memory lazily...
- __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes + size - storage->maxLeafCapacity, false);
- COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory + byteNum + size - storage->maxLeafCapacity, node->numBytes - byteNum);
- __CFStorageAllocLeafNodeMemory(allocator, storage, node, storage->maxLeafCapacity, false);
- }
- node->numBytes = storage->maxLeafCapacity;
- __CFStorageSetCache(storage, node, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
- return newNode;
- }
- } else { // No need to create new nodes!
- if (node->info.leaf.memory) {
- __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes + size, false);
- COPYMEM(node->info.leaf.memory + byteNum, node->info.leaf.memory + byteNum + size, node->numBytes - byteNum);
- }
- node->numBytes += size;
- __CFStorageSetCache(storage, node, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
- return NULL;
- }
+ return __CFStorageInsertLeafUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
} else {
- CFIndex relativeByteNum;
- CFIndex childNum;
- CFStorageNode *newNode;
- __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
- newNode = __CFStorageInsert(allocator, storage, node->info.notLeaf.child[childNum], relativeByteNum, size, absoluteByteNum);
- if (newNode) {
- if (node->info.notLeaf.child[2] == NULL) { // There's an empty slot for the new node, cool
- if (childNum == 0) __CFAssignWithWriteBarrier((void **)&node->info.notLeaf.child[2], node->info.notLeaf.child[1]); // Make room
- __CFAssignWithWriteBarrier((void **)&node->info.notLeaf.child[childNum + 1], newNode);
- Boolean GC = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
- if (GC) auto_zone_release(auto_zone(), newNode);
- node->numBytes += size;
- return NULL;
- } else {
- CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, false, 0); // Create another node
- if (childNum == 0) { // Last two children go to new node
- __CFAssignWithWriteBarrier((void **)&anotherNode->info.notLeaf.child[0], node->info.notLeaf.child[1]);
- __CFAssignWithWriteBarrier((void **)&anotherNode->info.notLeaf.child[1], node->info.notLeaf.child[2]);
- __CFAssignWithWriteBarrier((void **)&node->info.notLeaf.child[1], newNode);
- node->info.notLeaf.child[2] = NULL;
- } else if (childNum == 1) { // Last child goes to new node
- __CFAssignWithWriteBarrier((void **)&anotherNode->info.notLeaf.child[0], newNode);
- __CFAssignWithWriteBarrier((void **)&anotherNode->info.notLeaf.child[1], node->info.notLeaf.child[2]);
- node->info.notLeaf.child[2] = NULL;
- } else { // New node contains the new comers...
- __CFAssignWithWriteBarrier((void **)&anotherNode->info.notLeaf.child[0], node->info.notLeaf.child[2]);
- __CFAssignWithWriteBarrier((void **)&anotherNode->info.notLeaf.child[1], newNode);
- node->info.notLeaf.child[2] = NULL;
- }
- if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
- auto_zone_release(auto_zone(), newNode);
- }
- node->numBytes = node->info.notLeaf.child[0]->numBytes + node->info.notLeaf.child[1]->numBytes;
- anotherNode->numBytes = anotherNode->info.notLeaf.child[0]->numBytes + anotherNode->info.notLeaf.child[1]->numBytes;
- return anotherNode;
- }
- } else {
- node->numBytes += size;
- }
+ return __CFStorageInsertBranchUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
- return NULL;
}
+#pragma mark Frozen or Unfrozen Dispatch Functions
+
+static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
+ if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) {
+ return __CFStorageInsertFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
+ }
+ else {
+ return __CFStorageInsertUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
+ }
+}
+
+static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) {
+ if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) {
+ return __CFStorageDeleteFrozen(allocator, storage, node, range);
+ }
+ else {
+ return __CFStorageDeleteUnfrozen(allocator, storage, node, range, compact, false/*isRootNode*/);
+ }
+}
+
+
+#pragma mark Utility functions
+
CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) {
- return storage->rootNode.numBytes / storage->valueSize;
+ return __CFStorageConvertByteToValue(storage, storage->rootNode.numBytes);
}
static Boolean __CFStorageEqual(CFTypeRef cf1, CFTypeRef cf2) {
CFIndex loc, count, valueSize;
CFRange range1, range2;
uint8_t *ptr1, *ptr2;
-
+
count = __CFStorageGetCount(storage1);
if (count != __CFStorageGetCount(storage2)) return false;
-
+
valueSize = __CFStorageGetValueSize(storage1);
if (valueSize != __CFStorageGetValueSize(storage2)) return false;
-
+
loc = range1.location = range1.length = range2.location = range2.length = 0;
ptr1 = ptr2 = NULL;
-
+
while (loc < count) {
CFIndex cntThisTime;
if (loc >= range1.location + range1.length) ptr1 = (uint8_t *)CFStorageGetValueAtIndex(storage1, loc, &range1);
static void __CFStorageDescribeNode(CFStorageNode *node, CFMutableStringRef str, CFIndex level) {
int cnt;
for (cnt = 0; cnt < level; cnt++) CFStringAppendCString(str, " ", CFStringGetSystemEncoding());
-
+
if (node->isLeaf) {
- CFStringAppendFormat(str, NULL, CFSTR("Leaf %d/%d\n"), node->numBytes, node->info.leaf.capacityInBytes);
+ 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");
} else {
- CFStringAppendFormat(str, NULL, CFSTR("Node %d\n"), node->numBytes);
+ CFStringAppendFormat(str, NULL, CFSTR("Node %ld (%p) refcount: %u frozen: %s\n"), node->numBytes, node, node->refCount, node->isFrozen ? "yes" : "no");
for (cnt = 0; cnt < 3; cnt++) if (node->info.notLeaf.child[cnt]) __CFStorageDescribeNode(node->info.notLeaf.child[cnt], str, level+1);
}
}
}
CFIndex __CFStorageGetCapacity(CFStorageRef storage) {
- return __CFStorageGetNodeCapacity(&storage->rootNode) / storage->valueSize;
+ return __CFStorageConvertByteToValue(storage, __CFStorageGetNodeCapacity(&storage->rootNode));
}
CFIndex __CFStorageGetValueSize(CFStorageRef storage) {
return result;
}
+/* Returns true if enumeration should stop, false if it should continue. */
+static bool __CFStorageEnumerateNodesInByteRangeWithBlock(CFStorageRef storage, CFStorageNode *node, CFIndex globalOffsetOfNode, CFRange range, CFIndex concurrencyToken, CFStorageApplierBlock applier) {
+ bool stop = false;
+ if (node->isLeaf) {
+ CFIndex start = range.location;
+ CFIndex length = __CFMin(range.length, node->numBytes - start);
+ if (! node->info.leaf.memory) {
+ __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
+ }
+ applier(node->info.leaf.memory + start, __CFStorageConvertBytesToValueRange(storage, globalOffsetOfNode + start, length), &stop);
+ }
+ else {
+ CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]};
+ const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0};
+ const CFIndex offsets[3] = {0, lengths[0], lengths[0] + lengths[1]};
+ 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)};
+ CFIndex numOverlappingChildren = (!! overlaps[0].length + !! overlaps[1].length + !! overlaps[2].length);
+ if (numOverlappingChildren > 1) concurrencyToken--;
+
+ if (concurrencyToken >= 0 && numOverlappingChildren > 1) {
+ CFIndex numChildren = 1 + !!children[1] + !!children[2];
+ const CFRange * overlapsPtr = overlaps; //blocks don't let us reference arrays :(
+ const CFIndex * offsetsPtr = offsets;
+ CFStorageNode ** childrenPtr = children;
+#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
+ __block bool blockStop = false;
+ dispatch_apply(numChildren, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t ind) {
+ if (! blockStop && overlapsPtr[ind].length > 0) {
+ if (__CFStorageEnumerateNodesInByteRangeWithBlock(storage, childrenPtr[ind], globalOffsetOfNode + offsetsPtr[ind], CFRangeMake(overlapsPtr[ind].location - offsetsPtr[ind], overlapsPtr[ind].length), concurrencyToken, applier)) {
+ blockStop = true;
+ }
+ }
+ });
+ stop = blockStop;
+#else
+ for (CFIndex ind = 0; ind < numChildren; ind++) {
+ if (overlapsPtr[ind].length > 0) {
+ if (__CFStorageEnumerateNodesInByteRangeWithBlock(storage, childrenPtr[ind], globalOffsetOfNode + offsetsPtr[ind], CFRangeMake(overlapsPtr[ind].location - offsetsPtr[ind], overlapsPtr[ind].length), concurrencyToken, applier)) {
+ stop = true;
+ break;
+ }
+ }
+ }
+#endif
+ } else {
+ if (overlaps[0].length > 0) {
+ stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[0], globalOffsetOfNode + offsets[0], CFRangeMake(overlaps[0].location - offsets[0], overlaps[0].length), concurrencyToken, applier);
+ }
+ if (overlaps[1].length > 0) {
+ stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[1], globalOffsetOfNode + offsets[1], CFRangeMake(overlaps[1].location - offsets[1], overlaps[1].length), concurrencyToken, applier);
+ }
+ if (overlaps[2].length > 0) {
+ stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[2], globalOffsetOfNode + offsets[2], CFRangeMake(overlaps[2].location - offsets[2], overlaps[2].length), concurrencyToken, applier);
+ }
+ }
+ }
+ return stop;
+}
+
+static CFStorageNode *_CFStorageFindNodeContainingByteRange(ConstCFStorageRef storage, const CFStorageNode *node, CFRange nodeRange, CFIndex globalOffsetOfNode, CFRange *outGlobalByteRangeOfResult) {
+ if (! node->isLeaf) {
+ /* See how many children are overlapped by this range. If it's only 1, call us recursively on that node; otherwise we're it! */
+ CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]};
+ const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0};
+ const CFIndex offsets[3] = {0, lengths[0], lengths[0] + lengths[1]};
+ 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)};
+ CFIndex numOverlappingChildren = (!! overlaps[0].length + !! overlaps[1].length + !! overlaps[2].length);
+ ASSERT(numOverlappingChildren > 0);
+ if (numOverlappingChildren == 1) {
+ CFIndex overlappingChild = (overlaps[0].length ? 0 : (overlaps[1].length ? 1 : 2));
+ return _CFStorageFindNodeContainingByteRange(storage, children[overlappingChild], CFRangeMake(nodeRange.location - offsets[overlappingChild], nodeRange.length), globalOffsetOfNode + offsets[overlappingChild], outGlobalByteRangeOfResult);
+ }
+ }
+
+ /* 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. */
+ *outGlobalByteRangeOfResult = CFRangeMake(globalOffsetOfNode, node->numBytes);
+ return (CFStorageNode *)node;
+
+
+}
+
+/* Frees all memory associated with the root node, effectively emptying the CFStorage */
+static void __CFStorageClearRootNode(CFStorageRef storage) {
+ CFAllocatorRef allocator = CFGetAllocator(storage);
+ /* Have to release our children if we are a branch, or free our memory if we are a leaf */
+ if (storage->rootNode.isLeaf) {
+ _CFAllocatorDeallocateGC(allocator, storage->rootNode.info.leaf.memory);
+ }
+ else {
+ __CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[0]);
+ __CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[1]);
+ __CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[2]);
+ }
+ storage->rootNode.isLeaf = true;
+ storage->rootNode.numBytes = 0;
+ storage->rootNode.info.leaf.capacityInBytes = 0;
+ storage->rootNode.info.leaf.memory = NULL;
+}
+
static void __CFStorageDeallocate(CFTypeRef cf) {
+ /* 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.
+
+ 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.
+ */
CFStorageRef storage = (CFStorageRef)cf;
- CFAllocatorRef allocator = CFGetAllocator(storage);
- if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) return; // XXX_PCB GC will take care of us.
- __CFStorageNodeDealloc(allocator, &storage->rootNode, false);
+ if (! CF_IS_COLLECTABLE_ALLOCATOR(CFGetAllocator(storage))) {
+ __CFStorageClearRootNode(storage);
+ }
}
static CFTypeID __kCFStorageTypeID = _kCFRuntimeNotATypeID;
return NULL;
}
storage->valueSize = valueSize;
- CF_SPINLOCK_INIT_FOR_STRUCTS(storage->cacheReaderMemoryAllocationLock);
- storage->cacheGenerationCount = 0;
- storage->cacheParts.locationHi = 0;
- storage->cacheParts.locationLo = 0;
-#if POSSIBLE_TO_HAVE_LENGTH_MORE_THAN_HALFWORD
- storage->cacheParts.lengthHi = 0;
+ /* if valueSize is a power of 2, then set the shifter to the log base 2 of valueSize. Otherwise set it to NO_SHIFTER */
+ if (valueSize > 0 && !(valueSize & (valueSize - 1))) {
+#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
+ storage->byteToValueShifter = __builtin_ctzl(valueSize);
+#else
+ CFIndex tempSize = valueSize;
+ storage->byteToValueShifter = 0;
+ while (tempSize > 1) {
+ storage->byteToValueShifter++;
+ tempSize >>= 1;
+ }
#endif
- storage->cacheParts.lengthLo = 0;
- storage->cacheParts.cachedNodeHi = 0;
- storage->cacheParts.cachedNodeLo = 0;
+ }
+ else {
+ storage->byteToValueShifter = NO_SHIFTER;
+ }
+
+ CF_SPINLOCK_INIT_FOR_STRUCTS(storage->cacheReaderMemoryAllocationLock);
storage->maxLeafCapacity = __CFStorageMaxLeafCapacity;
if (valueSize && ((storage->maxLeafCapacity % valueSize) != 0)) {
storage->maxLeafCapacity = (storage->maxLeafCapacity / valueSize) * valueSize; // Make it fit perfectly (3406853)
}
memset(&(storage->rootNode), 0, sizeof(CFStorageNode));
storage->rootNode.isLeaf = true;
- storage->nodeHint = __kCFAllocatorGCScannedMemory;
+ storage->rootNode.refCount = 0;
+ if (valueSize >= sizeof(void *)) {
+ storage->nodeHint = __kCFAllocatorGCScannedMemory;
+ }
+ else {
+ // Don't scan nodes if the value size is smaller than a pointer (8198596)
+ storage->nodeHint = 0;
+ }
if (__CFOASafe) __CFSetLastAllocationEventName(storage, "CFStorage");
return storage;
}
+CFStorageRef CFStorageCreateWithSubrange(CFStorageRef mutStorage, CFRange range) {
+ const ConstCFStorageRef storage = mutStorage; //we expect this to never modify the storage, so use a const variable to help enforce that
+ CFStorageRef result = CFStorageCreate(CFGetAllocator(storage), storage->valueSize);
+
+ if (range.length > 0) {
+ /* 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. */
+ const CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
+ CFRange byteRangeOfContainingNode;
+ CFStorageNode *nodeContainingEntireRange = _CFStorageFindNodeContainingByteRange(storage, &storage->rootNode, byteRange, 0, &byteRangeOfContainingNode);
+ ASSERT(nodeContainingEntireRange != NULL);
+
+ /* If the result is a leaf, insert the portion we care about */
+ if (nodeContainingEntireRange->isLeaf) {
+ CFStorageInsertValues(result, CFRangeMake(0, range.length));
+ if (nodeContainingEntireRange->info.leaf.memory) {
+ CFIndex offsetIntoNode = byteRange.location - byteRangeOfContainingNode.location;
+ ASSERT(offsetIntoNode >= 0);
+ CFStorageReplaceValues(result, CFRangeMake(0, range.length), nodeContainingEntireRange->info.leaf.memory + offsetIntoNode);
+ }
+ }
+ else {
+ /* The result is not a leaf. Insert all of its children into our root. */
+ ASSERT(byteRangeOfContainingNode.length == nodeContainingEntireRange->numBytes);
+ result->rootNode.isLeaf = false;
+ result->rootNode.numBytes = byteRangeOfContainingNode.length;
+ result->rootNode.info.notLeaf.child[0] = result->rootNode.info.notLeaf.child[1] = result->rootNode.info.notLeaf.child[2] = NULL;
+ for (CFIndex i=0; i < 3; i++) {
+ CFStorageNode *newNode = nodeContainingEntireRange->info.notLeaf.child[i];
+ if (! newNode) break;
+ __CFStorageFreezeNode(newNode);
+ __CFStorageSetChild(&result->rootNode, i, __CFStorageRetainNode(newNode));
+ }
+
+ /* Now delete from the beginning or end to trim this to the right size */
+ CFRange rangeOfContainingNode = __CFStorageConvertBytesToValueRange(result, byteRangeOfContainingNode.location, byteRangeOfContainingNode.length);
+ CFIndex prefixToTrim = range.location - rangeOfContainingNode.location;
+ CFIndex suffixToTrim = (rangeOfContainingNode.location + rangeOfContainingNode.length) - (range.location + range.length);
+ ASSERT(prefixToTrim >= 0);
+ ASSERT(suffixToTrim >= 0);
+ ASSERT(CFStorageGetCount(result) == rangeOfContainingNode.length);
+ if (suffixToTrim > 0) CFStorageDeleteValues(result, CFRangeMake(rangeOfContainingNode.length - suffixToTrim, suffixToTrim));
+ if (prefixToTrim > 0) CFStorageDeleteValues(result, CFRangeMake(0, prefixToTrim));
+ }
+ }
+
+ ASSERT(CFStorageGetCount(result) == range.length);
+ return result;
+}
+
CFTypeID CFStorageGetTypeID(void) {
return __kCFStorageTypeID;
}
}
/* Returns pointer to the specified value
- index and validConsecutiveValueRange are in terms of values
-*/
+ index and validConsecutiveValueRange are in terms of values
+ */
void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
- CFRange range;
- return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &range);
+ CFRange dummy;
+ return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, true/*requireUnfreezing*/);
}
+const void *CFStorageGetConstValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
+ CFRange dummy;
+ return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, false/*requireUnfreezing*/);
+}
+
+
/* Makes space for range.length values at location range.location
- This function deepens the tree if necessary...
-*/
+ This function deepens the tree if necessary...
+ */
void CFStorageInsertValues(CFStorageRef storage, CFRange range) {
- CFIndex numBytesToInsert = range.length * storage->valueSize;
- CFIndex byteNum = range.location * storage->valueSize;
+ CFIndex numBytesToInsert = __CFStorageConvertValueToByte(storage, range.length);
+ CFIndex byteNum = __CFStorageConvertValueToByte(storage, range.location);
+ const CFIndex expectedByteCount = storage->rootNode.numBytes + numBytesToInsert;
+ const CFAllocatorRef allocator = CFGetAllocator(storage);
+ const CFIndex insertionChunkSize = storage->maxLeafCapacity;
while (numBytesToInsert > 0) {
- CFStorageNode *newNode;
- CFAllocatorRef allocator = CFGetAllocator(storage);
- CFIndex insertThisTime = numBytesToInsert;
- if (insertThisTime > storage->maxLeafCapacity) {
- insertThisTime = (storage->maxLeafCapacity / storage->valueSize) * storage->valueSize;
- }
- newNode = __CFStorageInsert(allocator, storage, &storage->rootNode, byteNum, insertThisTime, byteNum);
- if (newNode) {
- CFStorageNode *tempRootNode = __CFStorageCreateNode(allocator, false, 0); // Will copy the (static) rootNode over to this
- objc_memmove_collectable(tempRootNode, &storage->rootNode, sizeof(CFStorageNode));
- storage->rootNode.isLeaf = false;
- __CFAssignWithWriteBarrier((void **)&storage->rootNode.info.notLeaf.child[0], tempRootNode);
- __CFAssignWithWriteBarrier((void **)&storage->rootNode.info.notLeaf.child[1], newNode);
- if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
- auto_zone_release(auto_zone(), tempRootNode);
- auto_zone_release(auto_zone(), newNode);
- }
+ CHECK_INTEGRITY();
+ const CFIndex insertThisTime = __CFMin(numBytesToInsert, insertionChunkSize);
+ 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
+ ASSERT(newNodes.child == &storage->rootNode);// unfrozen variant should always give us our node back. We may have another node to insert in newNodes.sibling
+ if (newNodes.sibling != NULL) {
+ CFStorageNode *newNode = newNodes.sibling;
+ /* Need to create a new root node. Copy our existing root node's contents to a new heap node. */
+ CFStorageNode *heapRoot = __CFStorageCreateNode(allocator, storage, storage->rootNode.isLeaf, storage->rootNode.numBytes); // Will copy the (static) rootNode over to this
+ objc_memmove_collectable(&heapRoot->info, &storage->rootNode.info, sizeof heapRoot->info);
+
+ /* 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) */
+ if (storage->rootNode.isLeaf) {
+ __CFStorageSetCache(storage, NULL, 0);
+ storage->rootNode.isLeaf = false;
+ }
+
+ /* 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 */
+ __CFStorageSetChild(&storage->rootNode, 0, heapRoot);
+ __CFStorageSetChild(&storage->rootNode, 1, newNode);
storage->rootNode.info.notLeaf.child[2] = NULL;
- storage->rootNode.numBytes = tempRootNode->numBytes + newNode->numBytes;
-#if 1
- // ???
- __CFStorageSetCache(storage, NULL, 0, 0);
-#else
- if (storage->cache.cachedNode == &(storage->rootNode)) __CFAssignWithWriteBarrier((void **)&storage->cache.cachedNode, tempRootNode); // The cache should follow the node
-#endif
+ storage->rootNode.numBytes = heapRoot->numBytes + newNode->numBytes;
}
numBytesToInsert -= insertThisTime;
byteNum += insertThisTime;
+ ASSERT(storage->rootNode.numBytes + numBytesToInsert == expectedByteCount);
}
+ ASSERT(expectedByteCount == storage->rootNode.numBytes);
+ CHECK_INTEGRITY();
}
/* Deletes the values in the specified range
- This function gets rid of levels if necessary...
-*/
+ This function gets rid of levels if necessary...
+ */
void CFStorageDeleteValues(CFStorageRef storage, CFRange range) {
+ CHECK_INTEGRITY();
CFAllocatorRef allocator = CFGetAllocator(storage);
- range.location *= storage->valueSize;
- range.length *= storage->valueSize;
- __CFStorageDelete(allocator, storage, &storage->rootNode, range, true);
- while (__CFStorageGetNumChildren(&storage->rootNode) == 1) {
- CFStorageNode *child = storage->rootNode.info.notLeaf.child[0]; // The single child
- objc_memmove_collectable(&storage->rootNode, child, sizeof(CFStorageNode));
- _CFAllocatorDeallocateGC(allocator, child);
+ CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
+ const CFIndex expectedByteCount = storage->rootNode.numBytes - byteRange.length;
+
+ /* We don't try to mantain the cache across deletion */
+ __CFStorageSetCache(storage, NULL, 0);
+
+ /* The root node can never be frozen, so it's always OK to modify it */
+ ASSERT(! storage->rootNode.isFrozen);
+ CFStorageNode *newRoot = __CFStorageDeleteUnfrozen(allocator, storage, &storage->rootNode, byteRange, true/*compact*/, true/*isRootNode*/);
+
+ /* There are three return values we can get:
+ NULL -> everything was deleted
+ the root node -> something was deleted, but no nodes became empty, so we don't have to replace any children
+ a different node -> represents the new root
+ */
+ if (newRoot == NULL) {
+ __CFStorageClearRootNode(storage);
}
- if (__CFStorageGetNumChildren(&storage->rootNode) == 0 && !storage->rootNode.isLeaf) {
- storage->rootNode.isLeaf = true;
- storage->rootNode.info.leaf.capacityInBytes = 0;
- storage->rootNode.info.leaf.memory = NULL;
+ else if (newRoot == &storage->rootNode) {
+ /* No need to replace any children, nothing to do for this case */
}
- // !!! Need to update the cache
- __CFStorageSetCache(storage, NULL, 0, 0);
+ else {
+ /* 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. */
+ storage->rootNode.numBytes = newRoot->numBytes;
+ storage->rootNode.isLeaf = newRoot->isLeaf;
+ bzero(&storage->rootNode.info, sizeof storage->rootNode.info); //be a little paranoid here
+ if (newRoot->isLeaf) {
+ if (! newRoot->isFrozen) {
+ /* If the leaf is not frozen, we can just steal its memory (if any)! If it is frozen, we must copy it. */
+ __CFAssignWithWriteBarrier((void **)&storage->rootNode.info.leaf.memory, newRoot->info.leaf.memory);
+ /* 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. */
+ bzero(&newRoot->info, sizeof newRoot->info);
+ }
+ else {
+ /* The leaf is frozen, so we have to copy its memory. */
+ if (newRoot->info.leaf.memory) {
+ __CFStorageAllocLeafNodeMemory(allocator, storage, &storage->rootNode, storage->rootNode.numBytes, false);
+ COPYMEM(newRoot->info.leaf.memory, storage->rootNode.info.leaf.memory, newRoot->numBytes);
+ }
+ }
+ } else {
+ /* New root is a branch. */
+ ASSERT(newRoot->info.notLeaf.child[0] && newRoot->info.notLeaf.child[1]); //never expect to get back a node with only one child
+ __CFStorageSetChild(&storage->rootNode, 0, __CFStorageRetainNode(newRoot->info.notLeaf.child[0]));
+ __CFStorageSetChild(&storage->rootNode, 1, __CFStorageRetainNode(newRoot->info.notLeaf.child[1]));
+ if (newRoot->info.notLeaf.child[2]) __CFStorageSetChild(&storage->rootNode, 2, __CFStorageRetainNode(newRoot->info.notLeaf.child[2]));
+ }
+ }
+ __CFStorageReleaseNodeWithNullCheck(storage, newRoot); //balance the retain from __CFStorageDeleteUnfrozen
+ ASSERT(expectedByteCount == storage->rootNode.numBytes);
+ CHECK_INTEGRITY();
}
void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values) {
+ CHECK_INTEGRITY();
while (range.length > 0) {
CFRange leafRange;
- void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange);
- CFIndex cntThisTime = range.length;
- if (cntThisTime > leafRange.length - (range.location - leafRange.location)) cntThisTime = leafRange.length - (range.location - leafRange.location);
- COPYMEM(storagePtr, values, cntThisTime * storage->valueSize);
- values = (uint8_t *)values + (cntThisTime * storage->valueSize);
+ void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange, false/*requireUnfreezing*/);
+ CFIndex cntThisTime = __CFMin(range.length, leafRange.length - (range.location - leafRange.location));
+ CFIndex byteCntThisTime = __CFStorageConvertValueToByte(storage, cntThisTime);
+ COPYMEM(storagePtr, values, byteCntThisTime);
+ values = (uint8_t *)values + byteCntThisTime;
range.location += cntThisTime;
range.length -= cntThisTime;
}
}
void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context) {
- while (0 < range.length) {
- CFRange leafRange;
- const void *storagePtr;
- CFIndex idx, cnt;
- storagePtr = CFStorageGetValueAtIndex(storage, range.location, &leafRange);
- cnt = __CFMin(range.length, leafRange.location + leafRange.length - range.location);
- for (idx = 0; idx < cnt; idx++) {
- applier(storagePtr, context);
- storagePtr = (const char *)storagePtr + storage->valueSize;
- }
- range.length -= cnt;
- range.location += cnt;
+ CHECK_INTEGRITY();
+ CFIndex valueSize = storage->valueSize;
+ CFStorageApplyBlock(storage, range, 0, ^(const void *storagePtr, CFRange subrange, bool *stop){
+ while (subrange.length--) {
+ applier(storagePtr, context);
+ storagePtr = valueSize + (const char *)storagePtr;
+ }
+ });
+}
+
+void CFStorageApplyBlock(CFStorageRef storage, CFRange range, CFStorageEnumerationOptionFlags options, CFStorageApplierBlock applier) {
+ if (! range.length) return;
+ CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
+ /* 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 */
+ CFIndex concurrencyToken = 0;
+ if ((options & kCFStorageEnumerationConcurrent) && (range.length >= 1024 * 1024)) {
+ concurrencyToken = 3;
}
+ __CFStorageEnumerateNodesInByteRangeWithBlock(storage, &storage->rootNode, 0/*globalOffsetOfNode*/, byteRange, concurrencyToken, applier);
}
void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values) {
+ CHECK_INTEGRITY();
while (range.length > 0) {
CFRange leafRange;
- void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange);
- CFIndex cntThisTime = range.length;
- if (cntThisTime > leafRange.length - (range.location - leafRange.location)) cntThisTime = leafRange.length - (range.location - leafRange.location);
- COPYMEM(values, storagePtr, cntThisTime * storage->valueSize);
- values = (const uint8_t *)values + (cntThisTime * storage->valueSize);
+ void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange, true/*requireUnfreezing*/);
+ ASSERT(range.location >= leafRange.location);
+ ASSERT(range.location < leafRange.location + leafRange.length);
+ CFIndex cntThisTime = __CFMin(range.length, leafRange.length - (range.location - leafRange.location));
+ CFIndex byteCntThisTime = __CFStorageConvertValueToByte(storage, cntThisTime);
+ COPYMEM(values, storagePtr, byteCntThisTime);
+ values = (const uint8_t *)values + byteCntThisTime;
range.location += cntThisTime;
range.length -= cntThisTime;
}
}
+static void __CFStorageApplyNodeBlockInterior(CFStorageRef storage, CFStorageNode *node, void (^block)(CFStorageRef storage, CFStorageNode *node)) {
+ block(storage, node);
+ if (! node->isLeaf) {
+ CFStorageNode *childNode;
+ if ((childNode = node->info.notLeaf.child[0])) __CFStorageApplyNodeBlockInterior(storage, childNode, block);
+ if ((childNode = node->info.notLeaf.child[1])) __CFStorageApplyNodeBlockInterior(storage, childNode, block);
+ if ((childNode = node->info.notLeaf.child[2])) __CFStorageApplyNodeBlockInterior(storage, childNode, block);
+ }
+}
+
+static void __CFStorageApplyNodeBlock(CFStorageRef storage, void (^block)(CFStorageRef storage, CFStorageNode *node)) {
+ __CFStorageApplyNodeBlockInterior(storage, &storage->rootNode, block);
+}
+
+static CFIndex __CFStorageEstimateTotalAllocatedSize(CFStorageRef storage) __attribute__((unused));
+static CFIndex __CFStorageEstimateTotalAllocatedSize(CFStorageRef storage) {
+ __block CFIndex nodeResult = 0;
+ __block CFIndex contentsResult = 0;
+ __CFStorageApplyNodeBlock(storage, ^(CFStorageRef storage, CFStorageNode *node) {
+ if (node != &storage->rootNode) {
+ nodeResult += malloc_size(node);
+ if (node->isLeaf && node->info.leaf.memory != NULL) {
+ contentsResult += malloc_size(node->info.leaf.memory);
+ }
+ }
+ });
+ return nodeResult + contentsResult;
+}
+
+void __CFStorageSetAlwaysFrozen(CFStorageRef storage, bool alwaysFrozen) {
+ storage->alwaysFrozen = alwaysFrozen;
+}
+
+static CFIndex __CFStorageCheckNodeCachedLengthIntegrity(ConstCFStorageRef storage, const CFStorageNode *node) {
+ if (node->isLeaf) {
+ ASSERT(node->numBytes > 0 || node == &storage->rootNode);
+ return node->numBytes;
+ } else {
+ /* Branch */
+ CFStorageNode *childNode;
+ CFIndex expectedResult = __CFStorageCheckNodeCachedLengthIntegrity(storage, node->info.notLeaf.child[0]);
+ if ((childNode = node->info.notLeaf.child[1])) {
+ expectedResult += __CFStorageCheckNodeCachedLengthIntegrity(storage, childNode);
+ if ((childNode = node->info.notLeaf.child[2])) {
+ expectedResult += __CFStorageCheckNodeCachedLengthIntegrity(storage, childNode);
+ }
+ }
+ ASSERT(expectedResult == node->numBytes);
+ return expectedResult;
+ }
+}
+
+static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node) {
+ ASSERT(node->isFrozen == 0 || node->isFrozen == 1);
+
+ __CFStorageCheckNodeCachedLengthIntegrity(storage, node);
+ /* 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 */
+ if (! node->isLeaf) {
+ ASSERT(node->info.notLeaf.child[0] != NULL);
+ if (node->info.notLeaf.child[1] == NULL) ASSERT(node->info.notLeaf.child[2] == NULL);
+ }
+}
+
+static void __CFStorageCheckIntegrity(CFStorageRef storage) {
+ __CFStorageApplyNodeBlock(storage, ^(CFStorageRef storage, CFStorageNode *node) {
+ __CFStorageCheckNodeIntegrity(storage, node);
+ });
+}
+
/* Used by CFArray.c */
static void __CFStorageNodeSetUnscanned(CFStorageNode *node, auto_zone_t *zone) {
__private_extern__ void _CFStorageSetWeak(CFStorageRef storage) {
storage->nodeHint = 0;
- __CFStorageNodeSetUnscanned(&storage->rootNode, (auto_zone_t *)auto_zone());
+ __CFStorageNodeSetUnscanned(&storage->rootNode, (auto_zone_t *)objc_collectableZone());
}
#undef COPYMEM
projects / apple / cf.git / blobdiff