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.)
86     CFIndex numBytes;	/* Number of actual bytes in this node and all its children */
428 /* Creates an (unfrozen) copy of the given node.  This is shallow in the sense that it shares children for branches, but deep in that it copies memory for leaves.  */
444 	/* If we are copying children from a frozen node to an unfrozen node, we need to freeze the children */
459 /* Prototypes for deletion and insertion.  The *Frozen and *Unfrozen variants should only be called for nodes that we know are frozen or unfrozen.  Frozen nodes may only have frozen children, so it makes sense for the Frozen functions to call other Frozen functions.  Unfrozen nodes may have frozen or unfrozen children, so they should call the non-suffixed variants (which dispatch on whether the node is frozen or not).  
501 /* Helper function for both frozen and unfrozen branch deletion.  Walks the children of the node, calling __CFStorageDelete (or __CFStorageDeleteFrozen if childrenAreDefinitelyFrozen is YES), and assigning the results back to newChildren.  Returns the number of new children.  The newChildren nodes all acquire a reference count! 
508 	if (! existingChild) break; //no more children
556     /* Construct our new children in this array. */
560     /* We do not have to freeze anything in newChildren.  __CFStoragePopulateBranchChildrenAfterDeletion() will properly freeze any existing children, and new children we get should not be marked frozen. */
562     /* Now we have the children of the new node in newChildren.  We expect to have at least one child (if we got no children, we should have returned NULL up above because they deleted everything. */
618 	/* Release all of our existing children.  Either we are about to return a new child in place of us; or we are about to set our children to the new ones */
709     /* Inserting into a frozen branch.  We definitely will need to make a new copy of us, so make that up front.  We may or may not need to make a new sibling.  Note that in some cases, we may be able to get away with not creating a new copy of us, e.g. inserting at the very end of the tree.  In that case, we could preserve us and make a sibling containing exactly one node.  However, we do not really want to have branches with exactly one child; because then why not just return the child?  And then the whole tree can become unbalanced.  So then instead, always distribute the children equally among our nodes. */
720     /* Make a local array of all new children (retained).  We'll then move them to the new nodes. */
737 	/* We have three or fewer children to distribute, i.e. we don't need a sibling.  Put them all into copy of me.  Our clone's byte count is larger than our own by 'size'. */
742 	/* We have four children to distribute.  The first two go to us, the last two go to our new sibling.  */
848 	    if (childNum == 0) {	// Last two children go to new node
996 	CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]};
997 	const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0};
1004 	    CFIndex numChildren = 1 + !!children[1] + !!children[2];
1007 	    CFStorageNode ** childrenPtr = children;
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);
1045 	/* See how many children are overlapped by this range.  If it's only 1, call us recursively on that node; otherwise we're it! */
1046 	CFStorageNode *children[3] = {node->info.notLeaf.child[0], node->info.notLeaf.child[1], node->info.notLeaf.child[2]};
1047 	const CFIndex lengths[3] = {children[0]->numBytes, children[1] ? children[1]->numBytes : 0, children[2] ? children[2]->numBytes : 0};
1054 	    return _CFStorageFindNodeContainingByteRange(storage, children[overlappingChild], CFRangeMake(nodeRange.location - offsets[overlappingChild], nodeRange.length), globalOffsetOfNode + offsets[overlappingChild], outGlobalByteRangeOfResult);
1058     /* Either we are a leaf, in which case we contain the range, or we are a branch with multiple overlapping children.  Either way, we are the minimum node containing the range in question. */
1068     /* Have to release our children if we are a branch, or free our memory if we are a leaf */
1163 	/* Start by finding the node that contains the entire range.  Bump the reference count of its children and add them to the root of our new copy. */
1179 	    /* The result is not a leaf.  Insert all of its children into our root. */
1255 	    /* Set the new children in our root.  Note that it's important that we overwrite the root node's info, because we wanted to transfer the refcounts of our children (or our allocated memory, if we are a leaf) to the new heap root */
1287      the root node -> something was deleted, but no nodes became empty, so we don't have to replace any children
1294 	/* No need to replace any children, nothing to do for this case */
1297 	/* Got a legitimately new root back.  If it is unfrozen, we can just acquire its guts.  If it is frozen, we have more work to do.  Note that we do not have to worry about releasing any existing children of the root, beacuse __CFStorageDeleteUnfrozen already did that.  Also note that if we got a legitimately new root back, we must be a branch node, because if we were a leaf node, we would have been unfrozen and gotten ourself back. */
1368     /* As we descend the tree, if we find we need to go down two or more children, and the concurrency token is not zero, then we decrement the concurrency token and do it concurrently.  Since we have 3 children, a concurrency token of 3 yields up to 3**3 == 27 threads, which is a lot!  Concurrency benefits start to kick in around one million elements */
1467         CFStorageNode **children = node->info.notLeaf.child;
1468         if (children[0]) __CFStorageNodeSetUnscanned(children[0], zone);
1469         if (children[1]) __CFStorageNodeSetUnscanned(children[1], zone);
1470         if (children[2]) __CFStorageNodeSetUnscanned(children[2], zone);

Indexes created Sun Jun 23 19:15:37 MDT 2024