#include "CFStorage.h"
#include "CFInternal.h"
#if defined(__MACH__)
#include <mach/mach.h>
#else
enum {
vm_page_size = 4096
};
#endif
enum {
__CFStorageMaxLeafCapacity = 65536
};
#define COPYMEM(src,dst,n) CF_WRITE_BARRIER_MEMMOVE((dst), (src), (n))
#define PAGE_LIMIT ((CFIndex)vm_page_size / 2)
CF_INLINE int roundToPage(int num) {
return (num + vm_page_size - 1) & ~(vm_page_size - 1);
}
typedef struct __CFStorageNode {
CFIndex numBytes;
bool isLeaf;
union {
struct {
CFIndex capacityInBytes; uint8_t *memory;
} leaf;
struct {
struct __CFStorageNode *child[3];
} notLeaf;
} info;
} CFStorageNode;
struct __CFStorage {
CFRuntimeBase base;
CFIndex valueSize;
CFRange cachedRange; CFStorageNode *cachedNode; uint8_t *cachedNodeMemory; CFIndex maxLeafCapacity; CFStorageNode rootNode;
CFOptionFlags nodeHint; };
static void __CFStorageAllocLeafNodeMemoryAux(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap) {
CF_WRITE_BARRIER_ASSIGN(allocator, 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;
}
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)) __CFStorageAllocLeafNodeMemoryAux(allocator, storage, node, cap);
}
CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, uint8_t *memory, CFIndex loc, CFIndex len) {
CFAllocatorRef allocator = __CFGetAllocator(storage);
storage->cachedRange.location = loc;
storage->cachedRange.length = len;
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNode, node);
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNodeMemory, memory);
}
CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc) {
if (!storage->cachedNodeMemory && !(storage->cachedNodeMemory = storage->cachedNode->info.leaf.memory)) {
CFAllocatorRef allocator = CFGetAllocator(storage);
__CFStorageAllocLeafNodeMemory(allocator, storage, storage->cachedNode, storage->cachedNode->numBytes, false);
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNodeMemory, storage->cachedNode->info.leaf.memory);
}
return storage->cachedNodeMemory + (loc - storage->cachedRange.location) * storage->valueSize;
}
CF_INLINE void __CFStorageFindChild(CFStorageNode *node, CFIndex byteNum, bool forInsertion, CFIndex *childNum, CFIndex *relativeByteNum) {
if (forInsertion) byteNum--;
if (byteNum < node->info.notLeaf.child[0]->numBytes) *childNum = 0;
else {
byteNum -= node->info.notLeaf.child[0]->numBytes;
if (byteNum < node->info.notLeaf.child[1]->numBytes) *childNum = 1;
else {
byteNum -= node->info.notLeaf.child[1]->numBytes;
*childNum = 2;
}
}
if (forInsertion) byteNum++;
*relativeByteNum = byteNum;
}
static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFRange *validConsecutiveByteRange) {
if (node->isLeaf) {
if (validConsecutiveByteRange) *validConsecutiveByteRange = CFRangeMake(0, node->numBytes);
__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
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, 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;
}
}
CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
uint8_t *result;
if (idx < storage->cachedRange.location + storage->cachedRange.length && idx >= storage->cachedRange.location) {
result = __CFStorageGetFromCache(storage, idx);
} else {
CFRange range;
result = __CFStorageFindByte(storage, &storage->rootNode, idx * storage->valueSize, &range);
__CFStorageSetCache(storage, NULL, result - (idx * storage->valueSize - range.location), range.location / storage->valueSize, range.length / storage->valueSize);
}
*validConsecutiveValueRange = storage->cachedRange;
return result;
}
static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, bool isLeaf, CFIndex numBytes) {
CFStorageNode *newNode = _CFAllocatorAllocateGC(allocator, sizeof(CFStorageNode), 0);
if (__CFOASafe) __CFSetLastAllocationEventName(newNode, "CFStorage (node)");
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 void __CFStorageNodeDealloc(CFAllocatorRef allocator, CFStorageNode *node, bool freeNodeItself) {
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 (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;
}
static void __CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) {
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);
}
} else {
bool childrenAreLeaves = node->info.notLeaf.child[0]->isLeaf;
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) { int cnt;
_CFAllocatorDeallocateGC(allocator, node->info.notLeaf.child[childNum]);
for (cnt = childNum; cnt < 2; cnt++) {
CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[cnt], node->info.notLeaf.child[cnt+1]);
}
node->info.notLeaf.child[2] = NULL;
}
range.length -= rangeToDelete.length;
}
if (childrenAreLeaves) {
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 {
CFStorageNode *gChildren[9];
CFIndex cCnt, gCnt, cnt;
CFIndex totalG = 0; 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; for (cCnt = 0; cCnt < 3; cCnt++) {
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};
CFIndex sCnt = (cCnt == 0) ? forChild0[totalG] : ((cCnt == 1) ? forChild1[totalG] : totalG);
if (sCnt > totalG - gCnt) sCnt = totalG - gCnt;
if (sCnt) {
if (!node->info.notLeaf.child[cCnt]) {
CFStorageNode *newNode = __CFStorageCreateNode(allocator, false, 0);
CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[cCnt], newNode);
}
for (cnt = 0; cnt < sCnt; cnt++) {
node->info.notLeaf.child[cCnt]->numBytes += gChildren[gCnt]->numBytes;
CF_WRITE_BARRIER_ASSIGN(allocator, 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;
}
}
}
}
}
}
static CFStorageNode *__CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
if (node->isLeaf) {
if (size + node->numBytes > storage->maxLeafCapacity) { if (byteNum == node->numBytes) { CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, size);
__CFStorageSetCache(storage, newNode, NULL, absoluteByteNum / storage->valueSize, size / storage->valueSize);
return newNode;
} else if (byteNum == 0) { CFStorageNode *newNode = __CFStorageCreateNode(allocator, true, 0);
CF_WRITE_BARRIER_MEMMOVE(newNode, node, sizeof(CFStorageNode));
node->isLeaf = true;
node->numBytes = size;
node->info.leaf.capacityInBytes = 0;
node->info.leaf.memory = NULL;
__CFStorageSetCache(storage, node, NULL, absoluteByteNum / storage->valueSize, size / storage->valueSize);
return newNode;
} else if (byteNum + size <= storage->maxLeafCapacity) { CFStorageNode *newNode = __CFStorageCreateNode(allocator, 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, node->info.leaf.memory, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
return newNode;
} else { CFStorageNode *newNode = __CFStorageCreateNode(allocator, 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);
}
node->numBytes = storage->maxLeafCapacity;
__CFStorageSetCache(storage, node, node->info.leaf.memory, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
return 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, node->info.leaf.memory, (absoluteByteNum - byteNum) / storage->valueSize, node->numBytes / storage->valueSize);
return NULL;
}
} 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) { if (childNum == 0) CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[2], node->info.notLeaf.child[1]); CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[childNum + 1], newNode);
node->numBytes += size;
return NULL;
} else {
CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, false, 0); if (childNum == 0) { CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[0], node->info.notLeaf.child[1]);
CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[1], node->info.notLeaf.child[2]);
CF_WRITE_BARRIER_ASSIGN(allocator, node->info.notLeaf.child[1], newNode);
node->info.notLeaf.child[2] = NULL;
} else if (childNum == 1) { CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[0], newNode);
CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[1], node->info.notLeaf.child[2]);
node->info.notLeaf.child[2] = NULL;
} else { CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[0], node->info.notLeaf.child[2]);
CF_WRITE_BARRIER_ASSIGN(allocator, anotherNode->info.notLeaf.child[1], newNode);
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;
return anotherNode;
}
} else {
node->numBytes += size;
}
}
return NULL;
}
CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) {
return storage->rootNode.numBytes / storage->valueSize;
}
static bool __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 = CFStorageGetValueAtIndex(storage1, loc, &range1);
if (loc >= range2.location + range2.length) ptr2 = 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 %d/%d\n"), node->numBytes, node->info.leaf.capacityInBytes);
} else {
CFStringAppendFormat(str, NULL, CFSTR("Node %d\n"), node->numBytes);
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 __CFStorageGetNodeCapacity(&storage->rootNode) / storage->valueSize;
}
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 = %u, capacity = %u]\n"), storage, allocator, __CFStorageGetCount(storage), __CFStorageGetCapacity(storage));
__CFStorageDescribeNode(&storage->rootNode, result, 0);
return result;
}
static void __CFStorageDeallocate(CFTypeRef cf) {
CFStorageRef storage = (CFStorageRef)cf;
CFAllocatorRef allocator = CFGetAllocator(storage);
if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) return; __CFStorageNodeDealloc(allocator, &storage->rootNode, false);
}
static CFTypeID __kCFStorageTypeID = _kCFRuntimeNotATypeID;
static const CFRuntimeClass __CFStorageClass = {
_kCFRuntimeScannedObject,
"CFStorage",
NULL, NULL, __CFStorageDeallocate,
(void *)__CFStorageEqual,
__CFStorageHash,
NULL, __CFStorageCopyDescription
};
__private_extern__ void __CFStorageInitialize(void) {
__kCFStorageTypeID = _CFRuntimeRegisterClass(&__CFStorageClass);
}
CFStorageRef CFStorageCreate(CFAllocatorRef allocator, CFIndex valueSize) {
CFStorageRef storage;
CFIndex size = sizeof(struct __CFStorage) - sizeof(CFRuntimeBase);
storage = (CFStorageRef)_CFRuntimeCreateInstance(allocator, __kCFStorageTypeID, size, NULL);
if (NULL == storage) {
return NULL;
}
storage->valueSize = valueSize;
storage->cachedRange.location = 0;
storage->cachedRange.length = 0;
storage->cachedNode = NULL;
storage->cachedNodeMemory = NULL;
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->nodeHint = AUTO_MEMORY_SCANNED;
if (__CFOASafe) __CFSetLastAllocationEventName(storage, "CFStorage");
return storage;
}
CFTypeID CFStorageGetTypeID(void) {
return __kCFStorageTypeID;
}
CFIndex CFStorageGetCount(CFStorageRef storage) {
return __CFStorageGetCount(storage);
}
void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
CFRange range;
return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &range);
}
void CFStorageInsertValues(CFStorageRef storage, CFRange range) {
CFIndex numBytesToInsert = range.length * storage->valueSize;
CFIndex byteNum = range.location * storage->valueSize;
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); CF_WRITE_BARRIER_MEMMOVE(tempRootNode, &storage->rootNode, sizeof(CFStorageNode));
storage->rootNode.isLeaf = false;
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->rootNode.info.notLeaf.child[0], tempRootNode);
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->rootNode.info.notLeaf.child[1], newNode);
storage->rootNode.info.notLeaf.child[2] = NULL;
storage->rootNode.numBytes = tempRootNode->numBytes + newNode->numBytes;
if (storage->cachedNode == &(storage->rootNode))
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, storage, storage->cachedNode, tempRootNode); }
numBytesToInsert -= insertThisTime;
byteNum += insertThisTime;
}
}
void CFStorageDeleteValues(CFStorageRef storage, CFRange range) {
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]; CF_WRITE_BARRIER_MEMMOVE(&storage->rootNode, child, sizeof(CFStorageNode));
_CFAllocatorDeallocateGC(allocator, child);
}
if (__CFStorageGetNumChildren(&storage->rootNode) == 0 && !storage->rootNode.isLeaf) {
storage->rootNode.isLeaf = true;
storage->rootNode.info.leaf.capacityInBytes = 0;
storage->rootNode.info.leaf.memory = NULL;
}
storage->cachedRange = CFRangeMake(0, 0);
}
void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values) {
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);
((uint8_t *)values) += cntThisTime * storage->valueSize;
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;
}
}
void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values) {
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);
((const uint8_t *)values) += cntThisTime * storage->valueSize;
range.location += cntThisTime;
range.length -= cntThisTime;
}
}
static void __CFStorageNodeSetLayoutType(CFStorageNode *node, auto_zone_t *zone, auto_memory_type_t type) {
if (node->isLeaf) {
auto_zone_set_layout_type(zone, node->info.leaf.memory, type);
} else {
CFStorageNode **children = node->info.notLeaf.child;
if (children[0]) __CFStorageNodeSetLayoutType(children[0], zone, type);
if (children[1]) __CFStorageNodeSetLayoutType(children[1], zone, type);
if (children[2]) __CFStorageNodeSetLayoutType(children[2], zone, type);
}
}
__private_extern__ void _CFStorageSetWeak(CFStorageRef storage) {
storage->nodeHint = AUTO_MEMORY_UNSCANNED;
__CFStorageNodeSetLayoutType(&storage->rootNode, __CFCollectableZone, storage->nodeHint);
}
#undef COPYMEM
#undef PAGE_LIMIT