macosx-10.9.5/CF-855.17/CFStorage.c

32  ??? Currently elementSize cannot be greater than storage->maxLeafCapacity, which is less than or equal to __CFStorageMaxLeafCapacity
83 /* Each node in the storage.  isLeaf determines whether the node is a leaf node or a node inside the tree. If latter, number of children are determined by the number of non-NULL entries in child[]. (NULL entries are at the end.)
94 	    CFRange cachedRange;       //the absolute range of this node, in "value" units.  This is valid only if this node is referenced by storage->cacheNode, and used by the cache.  In general this is not valid, and the offset needs to be passed down from the tree
142 /* Allocates the memory and initializes the capacity in a leaf.   This locks not for mutations (mutations are not thread-safe in general), but for lazy allocation of storage during reading.
144 CF_INLINE void __CFStorageAllocLeafNodeMemory(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex cap, bool compact) {
147 	if (cap > storage->maxLeafCapacity) cap = storage->maxLeafCapacity;
153 	__CFSpinLock(&(storage->cacheReaderMemoryAllocationLock));
156 	    __CFAssignWithWriteBarrier((void **)&node->info.leaf.memory, _CFAllocatorReallocateGC(allocator, node->info.leaf.memory, cap, storage->nodeHint));	// This will free...
160 	__CFSpinUnlock(&(storage->cacheReaderMemoryAllocationLock));
170 static void __CFStorageCheckIntegrity(CFStorageRef storage);
171 #define CHECK_INTEGRITY() do { if (0) __CFStorageCheckIntegrity(storage); } while (0)
173 static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node);
174 #define CHECK_NODE_INTEGRITY(X) do { if (0) __CFStorageCheckNodeIntegrity(storage, X); } while (0)
178 CF_INLINE CFIndex __CFStorageConvertByteToValue(ConstCFStorageRef storage, CFIndex byte) {
179     if (storage->byteToValueShifter != NO_SHIFTER) {
180 	return byte >> storage->byteToValueShifter;
182     return byte / storage->valueSize;
185 CF_INLINE CFRange __CFStorageConvertBytesToValueRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) {
186     if (storage->byteToValueShifter != NO_SHIFTER) {
187 	return CFRangeMake(offset >> storage->byteToValueShifter, length >> storage->byteToValueShifter);
189     return CFRangeMake(offset / storage->valueSize, length / storage->valueSize);
192 CF_INLINE CFIndex __CFStorageConvertValueToByte(ConstCFStorageRef storage, CFIndex value) {
193     if (storage->byteToValueShifter != NO_SHIFTER) {
194 	return value << storage->byteToValueShifter;
196     return value * storage->valueSize;
199 CF_INLINE CFRange __CFStorageConvertValuesToByteRange(ConstCFStorageRef storage, CFIndex offset, CFIndex length) {
200     if (storage->byteToValueShifter != NO_SHIFTER) {
201 	return CFRangeMake(offset << storage->byteToValueShifter, length << storage->byteToValueShifter);
203     return CFRangeMake(offset * storage->valueSize, length * storage->valueSize);
220 static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node);
222 CF_INLINE void __CFStorageReleaseNode(CFStorageRef storage, CFStorageNode *node) {
226 	    __CFStorageDeallocateNode(storage, node);
231 CF_INLINE void __CFStorageReleaseNodeWithNullCheck(CFStorageRef storage, CFStorageNode *node) {
232     if (node) __CFStorageReleaseNode(storage, node);
235 static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node) {
236     CFAllocatorRef allocator = CFGetAllocator(storage);
240 	__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[0]);
241 	__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]);
242 	__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]);
252 static inline bool __CFStorageThawNodeDuringMutation(CFStorageRef storage, CFStorageNode *node) {
283 CF_INLINE void __CFStorageSetCache(CFStorageRef storage, CFStorageNode *node, CFIndex locInBytes) {
286 	node->info.leaf.cachedRange = __CFStorageConvertBytesToValueRange(storage, locInBytes, node->numBytes);
288     storage->cacheNode = node;
294 CF_INLINE uint8_t *__CFStorageGetFromCache(CFStorageRef storage, CFIndex loc, CFRange * restrict validConsecutiveValueRange, bool requireUnfrozenNode) {
295     CFStorageNode * const cachedNode = storage->cacheNode; /* It's important we read from this field no more than once, for thread safety with other concurrent reads; that is why the field is marked volatile. */
306 	__CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, cachedNode, cachedNode->numBytes, false);
319     uint8_t *result = cachedNode->info.leaf.memory + __CFStorageConvertValueToByte(storage, loc - nodeOffset);
349 static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node);
355 static void *__CFStorageFindByte(CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex absoluteByteOffsetOfNode, CFStorageNode **resultNode, CFRange *validConsecutiveByteRange, bool requireUnfreezing) {
359         __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
365 	if (requireUnfreezing && child->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, child)) {
367 	    CFStorageNode *unfrozenReplacement = __CFStorageCopyNode(storage, child);
370 	    __CFStorageReleaseNode(storage, child);
373         return __CFStorageFindByte(storage, child, relativeByteNum, absoluteByteOffsetOfNode + (byteNum - relativeByteNum), resultNode, validConsecutiveByteRange, requireUnfreezing);
380 CF_INLINE void *__CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange, bool requireUnfreezing) {
382     if (!(result = __CFStorageGetFromCache(storage, idx, validConsecutiveValueRange, requireUnfreezing))) {
385 	result = (uint8_t *)__CFStorageFindByte(storage, &storage->rootNode, __CFStorageConvertValueToByte(storage, idx), 0, &resultNode, &rangeInBytes, requireUnfreezing);
386         __CFStorageSetCache(storage, resultNode, rangeInBytes.location);
387 	*validConsecutiveValueRange = __CFStorageConvertBytesToValueRange(storage, rangeInBytes.location, rangeInBytes.length);
409 static CFStorageNode *__CFStorageCreateNode(CFAllocatorRef allocator, CFStorageRef storage, bool isLeaf, CFIndex numBytes) {
416     newNode->isFrozen = storage->alwaysFrozen;
429 static CFStorageNode *__CFStorageCopyNode(CFStorageRef storage, const CFStorageNode *node) {
430     CFAllocatorRef allocator = CFGetAllocator(storage);
431     CFStorageNode *result = __CFStorageCreateNode(allocator, storage, node->isLeaf, node->numBytes);
434 	    __CFStorageAllocLeafNodeMemory(allocator, storage, result, result->numBytes, false);
455 static void __CFStorageDeallocateNode(CFStorageRef storage, CFStorageNode *node);
465 static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
466 static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact);
468 static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
469 static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range);
471 static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum);
472 static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode);
476 static CFStorageNode *__CFStorageDeleteLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
487 	CFStorageNode *newNode = __CFStorageCreateNode(allocator, storage, true, remainingBytes);
493 	    __CFStorageAllocLeafNodeMemory(allocator, storage, newNode, remainingBytes, false);  // no point in compacting since we're freshly allocated
503 static inline CFIndex __CFStoragePopulateBranchChildrenAfterDeletion(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range, CFStorageNode *newChildren[3], bool childrenAreDefinitelyFrozen, bool compact) {
525 		newChild = __CFStorageDeleteFrozen(allocator, storage, existingChild, rangeOfChildToDelete);
528 		newChild = __CFStorageDelete(allocator, storage, existingChild, rangeOfChildToDelete, compact);
548 static CFStorageNode *__CFStorageDeleteBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
558     CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, true/*childrenAreDefinitelyFrozen*/, false/*compact*/);
569 	CFStorageNode *result = __CFStorageCreateNode(allocator, storage, false, 0);
580 static CFStorageNode *__CFStorageDeleteFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFRange range) {
582 	return __CFStorageDeleteLeafFrozen(allocator, storage, node, range);
585 	return __CFStorageDeleteBranchFrozen(allocator, storage, node, range);
593 static CFStorageNode *__CFStorageDeleteUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact, bool isRootNode) {
608 	    if (compact) __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes, true);
614 	CFIndex newChildIndex = __CFStoragePopulateBranchChildrenAfterDeletion(allocator, storage, node, range, newChildren, false/*childrenAreDefinitelyFrozen*/, compact);
619 	__CFStorageReleaseNode(storage, node->info.notLeaf.child[0]);
620 	__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[1]);
621 	__CFStorageReleaseNodeWithNullCheck(storage, node->info.notLeaf.child[2]);
642 static CFStorageDoubleNodeReturn __CFStorageInsertLeafFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
643     /* Inserting into a frozen leaf.  If we can fit the new data along with our existing data into a single node, then do so (i.e. if we can return one node, do it).  Otherwise, all of the data would have to fit into a second node (we are never called with more data than storage->maxLeafCapacity) so just make a new node with the data and return that. */
648     if (newTotalSize <= storage->maxLeafCapacity) {
651 	leftResult = __CFStorageCreateNode(allocator, storage, true, newTotalSize);
653 	    __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, newTotalSize, false);
658 	__CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
665 	    rightResult = __CFStorageCreateNode(allocator, storage, true, size);
666 	    __CFStorageSetCache(storage, rightResult, absoluteByteNum);
671 	    leftResult = __CFStorageCreateNode(allocator, storage, true, size);
672 	    __CFStorageSetCache(storage, leftResult, absoluteByteNum);
676 	    CFIndex leftAmount = storage->maxLeafCapacity, rightAmount = newTotalSize - storage->maxLeafCapacity;
677 	    leftResult = __CFStorageCreateNode(allocator, storage, true, leftAmount);
678 	    rightResult = __CFStorageCreateNode(allocator, storage, true, rightAmount);
679 	    __CFStorageAllocLeafNodeMemory(allocator, storage, leftResult, leftAmount, false);
680 	    __CFStorageAllocLeafNodeMemory(allocator, storage, rightResult, rightAmount, false);
702 	    __CFStorageSetCache(storage, leftResult, absoluteByteNum - byteNum);
708 static CFStorageDoubleNodeReturn __CFStorageInsertBranchFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
711     CFStorageNode *copyOfMe = __CFStorageCreateNode(allocator, storage, false, 0);
717     CFStorageDoubleNodeReturn childReturn = __CFStorageInsertFrozen(allocator, storage, child, relativeByteNum, size, absoluteByteNum);
724 	__CFStorageReleaseNode(storage, newChildren[childNum]);
743 	siblingOfMe = __CFStorageCreateNode(allocator, storage, false, 0);
755 static CFStorageDoubleNodeReturn __CFStorageInsertFrozen(CFAllocatorRef allocator, CFStorageRef storage, const CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
757 	return __CFStorageInsertLeafFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
760 	return __CFStorageInsertBranchFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
768 static CFStorageDoubleNodeReturn __CFStorageInsertLeafUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
769     if (size + node->numBytes > storage->maxLeafCapacity) {	// Need to create more child nodes
772 	    newNode = __CFStorageCreateNode(allocator, storage, true, size);
773 	    __CFStorageSetCache(storage, newNode, absoluteByteNum);
775 	    newNode = __CFStorageCreateNode(allocator, storage, true, 0);
788 	    __CFStorageSetCache(storage, node, absoluteByteNum);
789 	} else if (byteNum + size <= storage->maxLeafCapacity) {	// Inserting at middle; inserted region will fit into existing child
791 	    newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes - byteNum);
793 		__CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes - byteNum, false);
795 		__CFStorageAllocLeafNodeMemory(allocator, storage, node, byteNum + size, false);
798 	    __CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
799 	} else {	// Inserting some of new into one node, rest into another; remember that the assumption is size <= storage->maxLeafCapacity
800 	    newNode = __CFStorageCreateNode(allocator, storage, true, node->numBytes + size - storage->maxLeafCapacity);	// New stuff
802 		__CFStorageAllocLeafNodeMemory(allocator, storage, newNode, node->numBytes + size - storage->maxLeafCapacity, false);
803 		COPYMEM(node->info.leaf.memory + byteNum, newNode->info.leaf.memory + byteNum + size - storage->maxLeafCapacity, node->numBytes - byteNum);
804 		__CFStorageAllocLeafNodeMemory(allocator, storage, node, storage->maxLeafCapacity, false);
806 	    __CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
807 	    node->numBytes = storage->maxLeafCapacity;
812 	    __CFStorageAllocLeafNodeMemory(allocator, storage, node, node->numBytes + size, false);
816 	__CFStorageSetCache(storage, node, absoluteByteNum - byteNum);
821 static CFStorageDoubleNodeReturn __CFStorageInsertBranchUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
825     CFStorageDoubleNodeReturn newNodes = __CFStorageInsert(allocator, storage, childNode, relativeByteNum, size, absoluteByteNum);
832 	__CFStorageReleaseNode(storage, childNode);
847 	    CFStorageNode *anotherNode = __CFStorageCreateNode(allocator, storage, false, 0);	// Create another node
874  Assumption: size is never > storage->maxLeafCapacity
876 static CFStorageDoubleNodeReturn __CFStorageInsertUnfrozen(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
879 	return __CFStorageInsertLeafUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
881 	return __CFStorageInsertBranchUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
887 static CFStorageDoubleNodeReturn __CFStorageInsert(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFIndex byteNum, CFIndex size, CFIndex absoluteByteNum) {
888     if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) {
889 	return __CFStorageInsertFrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
892 	return __CFStorageInsertUnfrozen(allocator, storage, node, byteNum, size, absoluteByteNum);
896 static CFStorageNode *__CFStorageDelete(CFAllocatorRef allocator, CFStorageRef storage, CFStorageNode *node, CFRange range, bool compact) {
897     if (node->isFrozen && ! __CFStorageThawNodeDuringMutation(storage, node)) {
898 	return __CFStorageDeleteFrozen(allocator, storage, node, range);
901 	return __CFStorageDeleteUnfrozen(allocator, storage, node, range, compact, false/*isRootNode*/);
908 CF_INLINE CFIndex __CFStorageGetCount(CFStorageRef storage) {
909     return __CFStorageConvertByteToValue(storage, storage->rootNode.numBytes);
966 CFIndex __CFStorageGetCapacity(CFStorageRef storage) {
967     return __CFStorageConvertByteToValue(storage, __CFStorageGetNodeCapacity(&storage->rootNode));
970 CFIndex __CFStorageGetValueSize(CFStorageRef storage) {
971     return storage->valueSize;
975     CFStorageRef storage = (CFStorageRef)cf;
977     CFAllocatorRef allocator = CFGetAllocator(storage);
979     CFStringAppendFormat(result, NULL, CFSTR("<CFStorage %p [%p]>[count = %lu, capacity = %lu]\n"), storage, allocator, (unsigned long)__CFStorageGetCount(storage), (unsigned long)__CFStorageGetCapacity(storage));
980     __CFStorageDescribeNode(&storage->rootNode, result, 0);
985 static bool __CFStorageEnumerateNodesInByteRangeWithBlock(CFStorageRef storage, CFStorageNode *node, CFIndex globalOffsetOfNode, CFRange range, CFIndex concurrencyToken, CFStorageApplierBlock applier) {
991 	    __CFStorageAllocLeafNodeMemory(CFGetAllocator(storage), storage, node, node->numBytes, false);
993 	applier(node->info.leaf.memory + start, __CFStorageConvertBytesToValueRange(storage, globalOffsetOfNode + start, length), &stop);
1012 		    if (__CFStorageEnumerateNodesInByteRangeWithBlock(storage, childrenPtr[ind], globalOffsetOfNode + offsetsPtr[ind], CFRangeMake(overlapsPtr[ind].location - offsetsPtr[ind], overlapsPtr[ind].length), concurrencyToken, applier)) {
1021                 if (__CFStorageEnumerateNodesInByteRangeWithBlock(storage, childrenPtr[ind], globalOffsetOfNode + offsetsPtr[ind], CFRangeMake(overlapsPtr[ind].location - offsetsPtr[ind], overlapsPtr[ind].length), concurrencyToken, applier)) {
1030 		stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[0], globalOffsetOfNode + offsets[0], CFRangeMake(overlaps[0].location - offsets[0], overlaps[0].length), concurrencyToken, applier);
1033 		stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[1], globalOffsetOfNode + offsets[1], CFRangeMake(overlaps[1].location - offsets[1], overlaps[1].length), concurrencyToken, applier);
1036 		stop = stop || __CFStorageEnumerateNodesInByteRangeWithBlock(storage, children[2], globalOffsetOfNode + offsets[2], CFRangeMake(overlaps[2].location - offsets[2], overlaps[2].length), concurrencyToken, applier);
1043 static CFStorageNode *_CFStorageFindNodeContainingByteRange(ConstCFStorageRef storage, const CFStorageNode *node, CFRange nodeRange, CFIndex globalOffsetOfNode, CFRange *outGlobalByteRangeOfResult) {
1054 	    return _CFStorageFindNodeContainingByteRange(storage, children[overlappingChild], CFRangeMake(nodeRange.location - offsets[overlappingChild], nodeRange.length), globalOffsetOfNode + offsets[overlappingChild], outGlobalByteRangeOfResult);
1066 static void __CFStorageClearRootNode(CFStorageRef storage) {
1067     CFAllocatorRef allocator = CFGetAllocator(storage);
1069     if (storage->rootNode.isLeaf) {
1070 	_CFAllocatorDeallocateGC(allocator, storage->rootNode.info.leaf.memory);
1073 	__CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[0]);
1074 	__CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[1]);
1075 	__CFStorageReleaseNodeWithNullCheck(storage, storage->rootNode.info.notLeaf.child[2]);
1077     storage->rootNode.isLeaf = true;
1078     storage->rootNode.numBytes = 0;
1079     storage->rootNode.info.leaf.capacityInBytes = 0;
1080     storage->rootNode.info.leaf.memory = NULL;
1088     CFStorageRef storage = (CFStorageRef)cf;
1089     if (! CF_IS_COLLECTABLE_ALLOCATOR(CFGetAllocator(storage))) {
1090         __CFStorageClearRootNode(storage);
1115     CFStorageRef storage;
1117     storage = (CFStorageRef)_CFRuntimeCreateInstance(allocator, __kCFStorageTypeID, size, NULL);
1118     if (NULL == storage) {
1121     storage->valueSize = valueSize;
1125 	storage->byteToValueShifter = __builtin_ctzl(valueSize);
1128 	storage->byteToValueShifter = 0;
1130 	    storage->byteToValueShifter++;
1136 	storage->byteToValueShifter = NO_SHIFTER;
1139     CF_SPINLOCK_INIT_FOR_STRUCTS(storage->cacheReaderMemoryAllocationLock);
1140     storage->maxLeafCapacity = __CFStorageMaxLeafCapacity;
1141     if (valueSize && ((storage->maxLeafCapacity % valueSize) != 0)) {
1142         storage->maxLeafCapacity = (storage->maxLeafCapacity / valueSize) * valueSize;	// Make it fit perfectly (3406853)
1144     memset(&(storage->rootNode), 0, sizeof(CFStorageNode));
1145     storage->rootNode.isLeaf = true;
1146     storage->rootNode.refCount = 0;
1148 	storage->nodeHint = __kCFAllocatorGCScannedMemory;
1152 	storage->nodeHint = 0;
1154     if (__CFOASafe) __CFSetLastAllocationEventName(storage, "CFStorage");
1155     return storage;
1159     const ConstCFStorageRef storage = mutStorage; //we expect this to never modify the storage, so use a const variable to help enforce that
1160     CFStorageRef result = CFStorageCreate(CFGetAllocator(storage), storage->valueSize);
1164 	const CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
1166 	CFStorageNode *nodeContainingEntireRange = _CFStorageFindNodeContainingByteRange(storage, &storage->rootNode, byteRange, 0, &byteRangeOfContainingNode);
1211 CFIndex CFStorageGetCount(CFStorageRef storage) {
1212     return __CFStorageGetCount(storage);
1218 void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
1220     return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, true/*requireUnfreezing*/);
1223 const void *CFStorageGetConstValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange) {
1225     return __CFStorageGetValueAtIndex(storage, idx, validConsecutiveValueRange ? validConsecutiveValueRange : &dummy, false/*requireUnfreezing*/);
1232 void CFStorageInsertValues(CFStorageRef storage, CFRange range) {
1233     CFIndex numBytesToInsert = __CFStorageConvertValueToByte(storage, range.length);
1234     CFIndex byteNum = __CFStorageConvertValueToByte(storage, range.location);
1235     const CFIndex expectedByteCount = storage->rootNode.numBytes + numBytesToInsert;
1236     const CFAllocatorRef allocator = CFGetAllocator(storage);
1237     const CFIndex insertionChunkSize = storage->maxLeafCapacity;
1241         CFStorageDoubleNodeReturn newNodes = __CFStorageInsertUnfrozen(allocator, storage, &storage->rootNode, byteNum, insertThisTime, byteNum); //we don't have to call the frozen variant because the root node is never frozen
1242 	ASSERT(newNodes.child == &storage->rootNode);// unfrozen variant should always give us our node back.  We may have another node to insert in newNodes.sibling
1246 	    CFStorageNode *heapRoot = __CFStorageCreateNode(allocator, storage, storage->rootNode.isLeaf, storage->rootNode.numBytes);	// Will copy the (static) rootNode over to this
1247 	    objc_memmove_collectable(&heapRoot->info, &storage->rootNode.info, sizeof heapRoot->info);
1250 	    if (storage->rootNode.isLeaf) {
1251 		__CFStorageSetCache(storage, NULL, 0);
1252 		storage->rootNode.isLeaf = false;
1256 	    __CFStorageSetChild(&storage->rootNode, 0, heapRoot);
1257 	    __CFStorageSetChild(&storage->rootNode, 1, newNode);
1258             storage->rootNode.info.notLeaf.child[2] = NULL;
1259             storage->rootNode.numBytes = heapRoot->numBytes + newNode->numBytes;
1263 	ASSERT(storage->rootNode.numBytes + numBytesToInsert == expectedByteCount);
1265     ASSERT(expectedByteCount == storage->rootNode.numBytes);
1272 void CFStorageDeleteValues(CFStorageRef storage, CFRange range) {
1274     CFAllocatorRef allocator = CFGetAllocator(storage);
1275     CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
1276     const CFIndex expectedByteCount = storage->rootNode.numBytes - byteRange.length;
1279     __CFStorageSetCache(storage, NULL, 0);
1282     ASSERT(! storage->rootNode.isFrozen);
1283     CFStorageNode *newRoot = __CFStorageDeleteUnfrozen(allocator, storage, &storage->rootNode, byteRange, true/*compact*/, true/*isRootNode*/);
1291 	__CFStorageClearRootNode(storage);
1293     else if (newRoot == &storage->rootNode) {
1298 	storage->rootNode.numBytes = newRoot->numBytes;
1299 	storage->rootNode.isLeaf = newRoot->isLeaf;
1300 	bzero(&storage->rootNode.info, sizeof storage->rootNode.info); //be a little paranoid here
1304 		__CFAssignWithWriteBarrier((void **)&storage->rootNode.info.leaf.memory, newRoot->info.leaf.memory);
1311 		    __CFStorageAllocLeafNodeMemory(allocator, storage, &storage->rootNode, storage->rootNode.numBytes, false);
1312 		    COPYMEM(newRoot->info.leaf.memory, storage->rootNode.info.leaf.memory, newRoot->numBytes);
1318 	    __CFStorageSetChild(&storage->rootNode, 0, __CFStorageRetainNode(newRoot->info.notLeaf.child[0]));
1319 	    __CFStorageSetChild(&storage->rootNode, 1, __CFStorageRetainNode(newRoot->info.notLeaf.child[1]));
1320 	    if (newRoot->info.notLeaf.child[2]) __CFStorageSetChild(&storage->rootNode, 2, __CFStorageRetainNode(newRoot->info.notLeaf.child[2]));
1323     __CFStorageReleaseNodeWithNullCheck(storage, newRoot); //balance the retain from __CFStorageDeleteUnfrozen
1324     ASSERT(expectedByteCount == storage->rootNode.numBytes);
1328 void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values) {
1332         void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange, false/*requireUnfreezing*/);
1334 	CFIndex byteCntThisTime = __CFStorageConvertValueToByte(storage, cntThisTime);
1342 unsigned long _CFStorageFastEnumeration(CFStorageRef storage, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
1346         state->extra[0] = __CFStorageGetCount(storage);
1349     state->itemsPtr = (unsigned long *)CFStorageGetValueAtIndex(storage, state->state, &leafRange);
1354 void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context) {
1356     CFIndex valueSize = storage->valueSize;
1357     CFStorageApplyBlock(storage, range, 0, ^(const void *storagePtr, CFRange subrange, bool *stop){
1365 void CFStorageApplyBlock(CFStorageRef storage, CFRange range, CFStorageEnumerationOptionFlags options, CFStorageApplierBlock applier) {
1367     CFRange byteRange = __CFStorageConvertValuesToByteRange(storage, range.location, range.length);
1373     __CFStorageEnumerateNodesInByteRangeWithBlock(storage, &storage->rootNode, 0/*globalOffsetOfNode*/, byteRange, concurrencyToken, applier);
1376 void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values) {
1380         void *storagePtr = __CFStorageGetValueAtIndex(storage, range.location, &leafRange, true/*requireUnfreezing*/);
1384 	CFIndex byteCntThisTime = __CFStorageConvertValueToByte(storage, cntThisTime);
1392 static void __CFStorageApplyNodeBlockInterior(CFStorageRef storage, CFStorageNode *node, void (^block)(CFStorageRef storage, CFStorageNode *node)) {
1393     block(storage, node);
1396 	if ((childNode = node->info.notLeaf.child[0])) __CFStorageApplyNodeBlockInterior(storage, childNode, block);
1397 	if ((childNode = node->info.notLeaf.child[1])) __CFStorageApplyNodeBlockInterior(storage, childNode, block);
1398 	if ((childNode = node->info.notLeaf.child[2])) __CFStorageApplyNodeBlockInterior(storage, childNode, block);
1402 static void __CFStorageApplyNodeBlock(CFStorageRef storage, void (^block)(CFStorageRef storage, CFStorageNode *node)) {
1403     __CFStorageApplyNodeBlockInterior(storage, &storage->rootNode, block);
1406 static CFIndex __CFStorageEstimateTotalAllocatedSize(CFStorageRef storage) __attribute__((unused));
1407 static CFIndex __CFStorageEstimateTotalAllocatedSize(CFStorageRef storage) {
1410     __CFStorageApplyNodeBlock(storage, ^(CFStorageRef storage, CFStorageNode *node) {
1411 	if (node != &storage->rootNode) {
1421 void __CFStorageSetAlwaysFrozen(CFStorageRef storage, bool alwaysFrozen) {
1422     storage->alwaysFrozen = alwaysFrozen;
1425 static CFIndex __CFStorageCheckNodeCachedLengthIntegrity(ConstCFStorageRef storage, const CFStorageNode *node) {
1427 	ASSERT(node->numBytes > 0 || node == &storage->rootNode);
1432 	CFIndex expectedResult = __CFStorageCheckNodeCachedLengthIntegrity(storage, node->info.notLeaf.child[0]);
1434 	    expectedResult += __CFStorageCheckNodeCachedLengthIntegrity(storage, childNode);
1436 		expectedResult += __CFStorageCheckNodeCachedLengthIntegrity(storage, childNode);
1444 static void __CFStorageCheckNodeIntegrity(ConstCFStorageRef storage, const CFStorageNode *node) {
1447     __CFStorageCheckNodeCachedLengthIntegrity(storage, node);
1455 static void __CFStorageCheckIntegrity(CFStorageRef storage) {
1456     __CFStorageApplyNodeBlock(storage, ^(CFStorageRef storage, CFStorageNode *node) {
1457 	__CFStorageCheckNodeIntegrity(storage, node);
1474 CF_PRIVATE void _CFStorageSetWeak(CFStorageRef storage) {
1475     storage->nodeHint = 0;
1476     __CFStorageNodeSetUnscanned(&storage->rootNode, (auto_zone_t *)objc_collectableZone());