#define NO_SHIFTER ((uint32_t)(-1))
#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
#define restrict
#define bzero(dst, size) ZeroMemory(dst, size)
#endif
#if !defined(PAGE_SIZE)
#define PAGE_SIZE 4096
#endif
#define __CFStorageMaxLeafCapacity (4096 * 3)
#define COPYMEM(src,dst,n) objc_memmove_collectable((dst), (src), (n))
#define PAGE_LIMIT ((CFIndex)PAGE_SIZE / 2)
CF_INLINE int32_t roundToPage(int32_t num) {
return (num + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1);
}
typedef const struct __CFStorage *ConstCFStorageRef;
typedef struct __CFStorageNode {
CFIndex numBytes;
uint32_t refCount;
bool isFrozen;
bool isLeaf;
union {
struct {
CFIndex capacityInBytes; uint8_t *memory;
CFRange cachedRange; } leaf;
struct {
struct __CFStorageNode *child[3];
} notLeaf;
} info;
} CFStorageNode;
typedef struct {
CFStorageNode *child;
CFStorageNode *sibling;
} CFStorageDoubleNodeReturn;
CF_INLINE CFStorageDoubleNodeReturn CFStorageDoubleNodeReturnMake(CFStorageNode *child, CFStorageNode *sibling) {
CFStorageDoubleNodeReturn v;
v.child = child;
v.sibling = sibling;
return v;
}
struct __CFStorage {
CFRuntimeBase base;
CFIndex valueSize;
uint32_t byteToValueShifter;
CFLock_t cacheReaderMemoryAllocationLock;
bool alwaysFrozen;
CFStorageNode * volatile cacheNode;
CFIndex maxLeafCapacity; CFStorageNode rootNode;
CFOptionFlags nodeHint; };
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);
}
}
CF_INLINE void __CFStorageAllocLeafNodeMemory(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap, bool compact) {
if (cap > PAGE_LIMIT) {
cap = roundToPage(cap);
if (cap > storage->maxLeafCapacity) cap = storage->maxLeafCapacity;
} else {
cap = (((cap + 63) / 64) * 64);
}
if ((compact ? (cap != node->info.leaf.capacityInBytes) : (cap > node->info.leaf.capacityInBytes))) {
__CFLock(&(storage->cacheReaderMemoryAllocationLock));
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)); if (__CFOASafe) __CFSetLastAllocationEventName(node->info.leaf.memory, "CFStorage (node bytes)");
node->info.leaf.capacityInBytes = cap;
}
__CFUnlock(&(storage->cacheReaderMemoryAllocationLock));
}
}
#if 0
#define ASSERT(x) do { if (! (x)) { fprintf(stderr, "Assertion %s failed on line %d\n", #x, __LINE__); HALT; } } 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)
#pragma mark Byte <-> Value Functions
CF_INLINE CFIndex __CFStorageConvertByteToValue(ConstCFStorageRef storage, CFIndex byte) {
if (storage->byteToValueShifter != NO_SHIFTER) {
return byte >> storage->byteToValueShifter;
}
return byte / storage->valueSize;
}
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);
}
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;
}
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;
}
static inline bool __CFStorageThawNodeDuringMutation(CFStorageRef storage, CFStorageNode *node) {
if (node->refCount == 1) {
node->isFrozen = false;
return true;
}
return false;
}
static inline void __CFStorageSetChild(CFStorageNode *parentNode, CFIndex childIndex, CFStorageNode *newChild) {
ASSERT(! parentNode->isLeaf);
ASSERT(childIndex < 3);
__CFAssignWithWriteBarrier((void **)&parentNode->info.notLeaf.child[childIndex], newChild);
}
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;
}
}
#pragma mark Storage cache handling
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;
}
CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc, CFRange * restrict validConsecutiveValueRange, bool requireUnfrozenNode) {
CFStorageNode * const cachedNode = storage->cacheNode;
if (! cachedNode) return NULL;
ASSERT(cachedNode->isLeaf);
if (requireUnfrozenNode && cachedNode->isFrozen) return NULL;
if (! cachedNode->info.leaf.memory) {
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, cachedNode, cachedNode->numBytes, false);
}
CFIndex nodeOffset = cachedNode->info.leaf.cachedRange.location;
CFIndex nodeLength = cachedNode->info.leaf.cachedRange.length;
if (loc < nodeOffset || loc >= nodeOffset + nodeLength) {
return NULL;
}
validConsecutiveValueRange->location = nodeOffset;
validConsecutiveValueRange->length = nodeLength;
uint8_t *result = cachedNode->info.leaf.memory + __CFStorageConvertValueToByte(storage, loc - nodeOffset);
return result;
}
CF_INLINE CFStorageNode *__CFStorageFindChild(const CFStorageNode * restrict node, CFIndex byteNum, bool forInsertionOrDeletion, CFIndex * restrict childNum, CFIndex * restrict relativeByteNum) {
if (forInsertionOrDeletion) byteNum--;
CFStorageNode *result;
result = node->info.notLeaf.child[0];
if (byteNum < result->numBytes) *childNum = 0;
else {
byteNum -= result->numBytes;
result = node->info.notLeaf.child[1];
if (byteNum < result->numBytes) *childNum = 1;
else {
byteNum -= result->numBytes;
*childNum = 2;
result = node->info.notLeaf.child[2];
}
}
if (forInsertionOrDeletion) byteNum++;
*relativeByteNum = byteNum;
return result;
}
static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node);
static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex absoluteByteOffsetOfNode, CFStorageNode **resultNode, CFRange *validConsecutiveByteRange, bool requireUnfreezing) {
if (node->isLeaf) {
*validConsecutiveByteRange = CFRangeMake(absoluteByteOffsetOfNode, node->numBytes);
*resultNode = node;
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
return node->info.leaf.memory + byteNum;
} else {
CFIndex childNum;
CFIndex relativeByteNum;
CFStorageNode *child = __CFStorageFindChild(node, byteNum, false, &childNum, &relativeByteNum);
if (requireUnfreezing && child->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, child)) {
CFStorageNode *unfrozenReplacement = __CFStorageCopyNode(storage, child);
__CFStorageSetChild(node, childNum, unfrozenReplacement);
__CFStorageReleaseNode(storage, child);
child = unfrozenReplacement;
}
return __CFStorageFindByte(storage, child, relativeByteNum, absoluteByteOffsetOfNode + (byteNum - relativeByteNum), resultNode, validConsecutiveByteRange, requireUnfreezing);
}
}
CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange, bool requireUnfreezing) {
uint8_t *result;
if (!(result = __CFStorageGetFromCache(storage, idx, validConsecutiveValueRange, requireUnfreezing))) {
CFStorageNode *resultNode;
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;
}
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
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); }
newNode->refCount = 1;
newNode->isFrozen = storage->alwaysFrozen;
newNode->isLeaf = isLeaf;
newNode->numBytes = numBytes;
if (isLeaf) {
newNode->info.leaf.capacityInBytes = 0;
newNode->info.leaf.memory = NULL;
} else {
newNode->info.notLeaf.child[0] = newNode->info.notLeaf.child[1] = newNode->info.notLeaf.child[2] = NULL;
}
return newNode;
}
static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node) {
CFAllocatorRef allocator = CFGetAllocator(storage);
CFStorageNode *result = __CFStorageCreateNode(allocator, storage, node->isLeaf, node->numBytes);
if (node->isLeaf) {
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 (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
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) {
return NULL;
}
else {
CFStorageNode *newNode = __CFStorageCreateNode(allocator, storage, true, remainingBytes);
if (node->info.leaf.memory) {
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); __CFLeafCopyRangeToOffset(node, nonDeletedPrefix, newNode, 0);
__CFLeafCopyRangeToOffset(node, nonDeletedSuffix, newNode, nonDeletedPrefix.length);
}
return newNode;
}
}
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; for (CFIndex existingChildIndex = 0; existingChildIndex < 3; existingChildIndex++) {
CFStorageNode *existingChild = node->info.notLeaf.child[existingChildIndex];
if (! existingChild) break; const CFIndex existingChildLength = existingChild->numBytes;
CFRange deletionRangeIntersectedByChild = intersectionRange(range, CFRangeMake(childByteOffset, existingChildLength));
if (! deletionRangeIntersectedByChild.length) {
newChildren[newChildIndex++] = __CFStorageRetainNode(existingChild); if (childrenAreDefinitelyFrozen) {
__CFStorageFreezeNode(existingChild);
}
}
else {
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);
}
if (newChild != NULL) {
newChildren[newChildIndex++] = newChild; }
if (rangeOfChildToDelete.length == existingChildLength) {
ASSERT(newChild == NULL); }
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) {
return NULL;
}
CFStorageNode *newChildren[3];
CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, true, false);
ASSERT(newChildIndex >= 1);
if (newChildIndex == 1) {
return newChildren[0];
}
else {
CFStorageNode *result = __CFStorageCreateNode(allocator, storage, false, 0);
while (newChildIndex--) {
__CFStorageSetChild(result, newChildIndex, newChildren[newChildIndex]); }
result->numBytes = node->numBytes - range.length;
return result;
}
}
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
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) {
return NULL;
}
if (node->isLeaf) {
node->numBytes -= range.length;
if (node->info.leaf.memory) {
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);
}
CHECK_NODE_INTEGRITY(node);
return __CFStorageRetainNodeThreadUnsafe(node); } else {
CFStorageNode *newChildren[3] = {NULL, NULL, NULL};
CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, false, compact);
node->numBytes -= range.length;
ASSERT(newChildIndex >= 1);
__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) {
return newChildren[0];
}
else {
CFIndex i;
for (i=0; i < 3; i++) {
__CFStorageSetChild(node, i, newChildren[i]); }
CHECK_NODE_INTEGRITY(node);
return __CFStorageRetainNodeThreadUnsafe(node);
}
}
}
#pragma mark Frozen Insertion
static CFStorageDoubleNodeReturn __CFStorageInsertLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
CFStorageNode *leftResult, *rightResult;
CHECK_NODE_INTEGRITY(node);
ASSERT(byteNum <= node->numBytes);
CFIndex newTotalSize = size + node->numBytes;
if (newTotalSize <= storage->maxLeafCapacity) {
rightResult = NULL;
leftResult = __CFStorageCreateNode(allocator, storage, true, newTotalSize);
if (node->info.leaf.memory != NULL) { __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, newTotalSize, false);
COPYMEM(node->info.leaf.memory, leftResult->info.leaf.memory, byteNum); COPYMEM(node->info.leaf.memory + byteNum, leftResult->info.leaf.memory + byteNum + size, node->numBytes - byteNum); }
__CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
}
else {
if (byteNum == node->numBytes) {
leftResult = (CFStorageNode *)node;
rightResult = __CFStorageCreateNode(allocator, storage, true, size);
__CFStorageSetCache(storage, rightResult, absoluteByteNum);
}
else if (byteNum == 0) {
rightResult = __CFStorageRetainNode((CFStorageNode *)node);
leftResult = __CFStorageCreateNode(allocator, storage, true, size);
__CFStorageSetCache(storage, leftResult, absoluteByteNum);
}
else {
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);
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) {
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);
CFStorageNode *newChildren[4] = {NULL};
__CFStorageGetChildren(node, newChildren, true, true);
if (newChildren[childNum] != childReturn.child) {
__CFStorageReleaseNode(storage, newChildren[childNum]);
newChildren[childNum] = childReturn.child; }
if (childReturn.sibling != NULL) {
if (childNum < 2) newChildren[3] = newChildren[2];
if (childNum < 1) newChildren[2] = newChildren[1];
newChildren[childNum + 1] = childReturn.sibling; }
__CFStorageSetChild(copyOfMe, 0, newChildren[0]);
__CFStorageSetChild(copyOfMe, 1, newChildren[1]);
if (newChildren[3] == NULL) {
__CFStorageSetChild(copyOfMe, 2, newChildren[2]);
copyOfMe->numBytes = node->numBytes + size;
}
else {
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
static CFStorageDoubleNodeReturn __CFStorageInsertLeafUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
if (size + node->numBytes > storage->maxLeafCapacity) { CFStorageNode *newNode;
if (byteNum == node->numBytes) { newNode = __CFStorageCreateNode(allocator, storage, true, size);
__CFStorageSetCache(storage, newNode, absoluteByteNum);
} else if (byteNum == 0) { newNode = __CFStorageCreateNode(allocator, storage, true, 0);
newNode->numBytes = node->numBytes;
newNode->info.leaf.capacityInBytes = node->info.leaf.capacityInBytes;
__CFAssignWithWriteBarrier((void **)&newNode->info.leaf.memory, node->info.leaf.memory);
node->numBytes = size;
node->info.leaf.capacityInBytes = 0;
node->info.leaf.memory = NULL;
__CFStorageSetCache(storage, node, absoluteByteNum);
} else if (byteNum + size <= storage->maxLeafCapacity) { newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes - byteNum);
if (node->info.leaf.memory) { __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 { newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes + size - storage->maxLeafCapacity); if (node->info.leaf.memory) { __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); } else { 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); }
}
static CFStorageDoubleNodeReturn __CFStorageInsertBranchUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
CFIndex relativeByteNum;
CFIndex childNum; CFStorageNode *childNode = __CFStorageFindChild(node, byteNum, true, &childNum, &relativeByteNum);
CFStorageDoubleNodeReturn newNodes = __CFStorageInsert(allocator, storage, childNode, relativeByteNum, size, absoluteByteNum);
CFStorageDoubleNodeReturn result = {node, NULL}; ASSERT(childNode != NULL);
ASSERT(newNodes.child != NULL);
if (newNodes.child != childNode) {
__CFStorageReleaseNode(storage, childNode);
__CFStorageSetChild(node, childNum, newNodes.child);
}
if (newNodes.sibling == NULL) {
node->numBytes += size;
} else {
CFStorageNode *newChild = newNodes.sibling;
if (node->info.notLeaf.child[2] == NULL) { if (childNum == 0) __CFStorageSetChild(node, 2, node->info.notLeaf.child[1]); __CFStorageSetChild(node, childNum+1, newChild);
node->numBytes += size;
} else {
CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, storage, false, 0); if (childNum == 0) { __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) { __CFStorageSetChild(anotherNode, 0, newChild);
__CFStorageSetChild(anotherNode, 1, node->info.notLeaf.child[2]);
node->info.notLeaf.child[2] = NULL;
} else { __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;
result.sibling = anotherNode;
}
}
return result;
}
static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
ASSERT(! node->isFrozen);
if (node->isLeaf) {
return __CFStorageInsertLeafUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
} else {
return __CFStorageInsertBranchUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
}
}
#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);
}
}
#pragma mark Utility functions
CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) {
return __CFStorageConvertByteToValue(storage, storage->rootNode.numBytes);
}
static Boolean __CFStorageEqual(CFTypeRef cf1, CFTypeRef cf2) {
CFStorageRef storage1 = (CFStorageRef)cf1;
CFStorageRef storage2 = (CFStorageRef)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);
if (loc >= range2.location + range2.length) ptr2 = (uint8_t *)CFStorageGetValueAtIndex(storage2, loc, &range2);
cntThisTime = range1.location + range1.length;
if (range2.location + range2.length < cntThisTime) cntThisTime = range2.location + range2.length;
cntThisTime -= loc;
if (memcmp(ptr1, ptr2, valueSize * cntThisTime) != 0) return false;
ptr1 += valueSize * cntThisTime;
ptr2 += valueSize * cntThisTime;
loc += cntThisTime;
}
return true;
}
static CFHashCode __CFStorageHash(CFTypeRef cf) {
CFStorageRef Storage = (CFStorageRef)cf;
return __CFStorageGetCount(Storage);
}
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 %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 %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);
}
}
static CFIndex __CFStorageGetNodeCapacity(CFStorageNode *node) {
if (!node) return 0;
if (node->isLeaf) return node->info.leaf.capacityInBytes;
return __CFStorageGetNodeCapacity(node->info.notLeaf.child[0]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[1]) + __CFStorageGetNodeCapacity(node->info.notLeaf.child[2]);
}
CFIndex __CFStorageGetCapacity(CFStorageRef storage) {
return __CFStorageConvertByteToValue(storage, __CFStorageGetNodeCapacity(&storage->rootNode));
}
CFIndex __CFStorageGetValueSize(CFStorageRef storage) {
return storage->valueSize;
}
static CFStringRef __CFStorageCopyDescription(CFTypeRef cf) {
CFStorageRef storage = (CFStorageRef)cf;
CFMutableStringRef result;
CFAllocatorRef allocator = CFGetAllocator(storage);
result = CFStringCreateMutable(allocator, 0);
CFStringAppendFormat(result, NULL, CFSTR("<CFStorage %p [%p]>[count = %lu, capacity = %lu]\n"), storage, allocator, (unsigned long)__CFStorageGetCount(storage), (unsigned long)__CFStorageGetCapacity(storage));
__CFStorageDescribeNode(&storage->rootNode, result, 0);
return result;
}
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; const CFIndex * offsetsPtr = offsets;
CFStorageNode ** childrenPtr = children;
#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
__block bool blockStop = false;
dispatch_apply(numChildren, __CFDispatchQueueGetGenericMatchingCurrent(), ^(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) {
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);
}
}
*outGlobalByteRangeOfResult = CFRangeMake(globalOffsetOfNode, node->numBytes);
return (CFStorageNode *)node;
}
static void __CFStorageClearRootNode(CFStorageRef storage) {
CFAllocatorRef allocator = CFGetAllocator(storage);
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) {
CFStorageRef storage = (CFStorageRef)cf;
if (! CF_IS_COLLECTABLE_ALLOCATOR(CFGetAllocator(storage))) {
__CFStorageClearRootNode(storage);
}
}
static CFTypeID __kCFStorageTypeID = _kCFRuntimeNotATypeID;
static const CFRuntimeClass __CFStorageClass = {
_kCFRuntimeScannedObject,
"CFStorage",
NULL, NULL, __CFStorageDeallocate,
__CFStorageEqual,
__CFStorageHash,
NULL, __CFStorageCopyDescription
};
CFStorageRef CFStorageCreate(CFAllocatorRef allocator, CFIndex valueSize) {
CFStorageRef storage;
CFIndex size = sizeof(struct __CFStorage) - sizeof(CFRuntimeBase);
storage = (CFStorageRef)_CFRuntimeCreateInstance(allocator, CFStorageGetTypeID(), size, NULL);
if (NULL == storage) {
return NULL;
}
storage->valueSize = valueSize;
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
}
else {
storage->byteToValueShifter = NO_SHIFTER;
}
CF_LOCK_INIT_FOR_STRUCTS(storage->cacheReaderMemoryAllocationLock);
storage->maxLeafCapacity = __CFStorageMaxLeafCapacity;
if (valueSize && ((storage->maxLeafCapacity % valueSize) != 0)) {
storage->maxLeafCapacity = (storage->maxLeafCapacity / valueSize) * valueSize; }
memset(&(storage->rootNode), 0, sizeof(CFStorageNode));
storage->rootNode.isLeaf = true;
storage->rootNode.refCount = 0;
if (valueSize >= sizeof(void *)) {
storage->nodeHint = __kCFAllocatorGCScannedMemory;
}
else {
storage->nodeHint = 0;
}
if (__CFOASafe) __CFSetLastAllocationEventName(storage, "CFStorage");
return storage;
}
CFStorageRef CFStorageCreateWithSubrange(CFStorageRef mutStorage, CFRange range) {
const ConstCFStorageRef storage = mutStorage; CFStorageRef result = CFStorageCreate(CFGetAllocator(storage), storage->valueSize);
if (range.length > 0) {
const CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
CFRange byteRangeOfContainingNode;
CFStorageNode *nodeContainingEntireRange = _CFStorageFindNodeContainingByteRange(storage, &storage->rootNode, byteRange, 0, &byteRangeOfContainingNode);
ASSERT(nodeContainingEntireRange != NULL);
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 {
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));
}
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) {
static dispatch_once_t initOnce;
dispatch_once(&initOnce, ^{ __kCFStorageTypeID = _CFRuntimeRegisterClass(&__CFStorageClass); });
return __kCFStorageTypeID;
}
CFIndex CFStorageGetCount(CFStorageRef storage) {
return __CFStorageGetCount(storage);
}
void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
CFRange dummy;
return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, true);
}
const void *CFStorageGetConstValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
CFRange dummy;
return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, false);
}
void CFStorageInsertValues(CFStorageRef storage, CFRange range) {
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) {
CHECK_INTEGRITY();
const CFIndex insertThisTime = __CFMin(numBytesToInsert, insertionChunkSize);
CFStorageDoubleNodeReturn newNodes = __CFStorageInsertUnfrozen(allocator, storage, &storage->rootNode, byteNum, insertThisTime, byteNum); ASSERT(newNodes.child == &storage->rootNode); if (newNodes.sibling != NULL) {
CFStorageNode *newNode = newNodes.sibling;
CFStorageNode *heapRoot = __CFStorageCreateNode(allocator, storage, storage->rootNode.isLeaf, storage->rootNode.numBytes); objc_memmove_collectable(&heapRoot->info, &storage->rootNode.info, sizeof heapRoot->info);
if (storage->rootNode.isLeaf) {
__CFStorageSetCache(storage, NULL, 0);
storage->rootNode.isLeaf = false;
}
__CFStorageSetChild(&storage->rootNode, 0, heapRoot);
__CFStorageSetChild(&storage->rootNode, 1, newNode);
storage->rootNode.info.notLeaf.child[2] = NULL;
storage->rootNode.numBytes = heapRoot->numBytes + newNode->numBytes;
}
numBytesToInsert -= insertThisTime;
byteNum += insertThisTime;
ASSERT(storage->rootNode.numBytes + numBytesToInsert == expectedByteCount);
}
ASSERT(expectedByteCount == storage->rootNode.numBytes);
CHECK_INTEGRITY();
}
void CFStorageDeleteValues(CFStorageRef storage, CFRange range) {
CHECK_INTEGRITY();
CFAllocatorRef allocator = CFGetAllocator(storage);
CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
const CFIndex expectedByteCount = storage->rootNode.numBytes - byteRange.length;
__CFStorageSetCache(storage, NULL, 0);
ASSERT(! storage->rootNode.isFrozen);
CFStorageNode *newRoot = __CFStorageDeleteUnfrozen(allocator, storage, &storage->rootNode, byteRange, true, true);
if (newRoot == NULL) {
__CFStorageClearRootNode(storage);
}
else if (newRoot == &storage->rootNode) {
}
else {
storage->rootNode.numBytes = newRoot->numBytes;
storage->rootNode.isLeaf = newRoot->isLeaf;
bzero(&storage->rootNode.info, sizeof storage->rootNode.info); if (newRoot->isLeaf) {
if (! newRoot->isFrozen) {
__CFAssignWithWriteBarrier((void **)&storage->rootNode.info.leaf.memory, newRoot->info.leaf.memory);
bzero(&newRoot->info, sizeof newRoot->info);
}
else {
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 {
ASSERT(newRoot->info.notLeaf.child[0] && newRoot->info.notLeaf.child[1]); __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); 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, false);
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;
}
}
unsigned long _CFStorageFastEnumeration(CFStorageRef storage, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
CFRange leafRange;
if (state->state == 0) {
state->extra[0] = __CFStorageGetCount(storage);
}
if (state->state >= state->extra[0]) return 0;
state->itemsPtr = (unsigned long *)CFStorageGetValueAtIndex(storage, state->state, &leafRange);
state->state += leafRange.length;
return leafRange.length;
}
void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context) {
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);
CFIndex concurrencyToken = 0;
if ((options & kCFStorageEnumerationConcurrent) && (range.length >= 1024 * 1024)) {
concurrencyToken = 3;
}
__CFStorageEnumerateNodesInByteRangeWithBlock(storage, &storage->rootNode, 0, 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, true);
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 {
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 (! 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);
});
}
static void __CFStorageNodeSetUnscanned(CFStorageNode *node, auto_zone_t *zone) {
if (node->isLeaf) {
auto_zone_set_unscanned(zone, node->info.leaf.memory);
} else {
CFStorageNode **children = node->info.notLeaf.child;
if (children[0]) __CFStorageNodeSetUnscanned(children[0], zone);
if (children[1]) __CFStorageNodeSetUnscanned(children[1], zone);
if (children[2]) __CFStorageNodeSetUnscanned(children[2], zone);
}
}
CF_PRIVATE void _CFStorageSetWeak(CFStorageRef storage) {
storage->nodeHint = 0;
__CFStorageNodeSetUnscanned(&storage->rootNode, (auto_zone_t *)objc_collectableZone());
}
#undef COPYMEM
#undef PAGE_LIMIT