hfscommon/Misc/VolumeAllocation.c

1586 	extent_node_t *node = NULL;
1602 	node = extent_tree_off_search_next(&hfsmp->offset_tree, &search_sentinel);
1604 	if (node) {
1605 		*actualStartBlock = node->offset;
1606 		*actualNumBlocks = node->length;
1621 				printf("bad node: %p, offset %d, length %d\n", node, node->offset,node->length);
1663 		/* just start with the first offset node */
1664 		node = extent_tree_off_search_next(&hfsmp->offset_tree, &search_sentinel);
1671 		node = extent_tree_off_search_nextWithSize (&hfsmp->offset_tree, &search_sentinel);
1673 		if (node == NULL) {
1681 			 * means no node existed at that offset.  If the previous node's offset + length crosses
1699 						node = &tempnode;
1708 	if ((!node) && useMetaZone) {
1711 		node = extent_tree_off_search_nextWithSize (&hfsmp->offset_tree, &search_sentinel);
1715 	if ((node) && (node->length >= minBlocks)) {
1716 		*actualStartBlock = node->offset;
1717 		if (node->length >= maxBlocks) {
1721 			*actualNumBlocks = node->length;
1751 				   hfsmp->vcbVN, node, startingBlock, minBlocks, maxBlocks);
2246 			this will be done before the node is removed from the tree.
2421  * appropriate node from the tree.
2466 			 * extent is free, and if it is, then find the containing node.
2468 			extent_node_t *node = NULL;
2472 			node = extent_tree_off_search_prev(&hfsmp->offset_tree, &search_sentinel);
2474 			if (node) {
2907  * existing rb-tree node if possible, or else create a new one.
3444  * embedded within each of the nodes accurately points to the correct node as its "next" pointer.
3462 			panic("hfs_checktreelinks: mismatch for node (%p), next: %p , treenext %p !\n", current, next, treenext);
3474  * If there exists a node at the specified offset, it will return the appropriate
3475  * node.
3491 	extent_node_t *node = NULL;
3501 	node = extent_tree_off_search_prev(&hfsmp->offset_tree, &search_sentinel);
3502 	if (node) {
3504 		*ret_node = node;
3505 		nextnode = extent_tree_off_next (&hfsmp->offset_tree, node);
3506 		if (nextnode != node->offset_next) {
3512 		 * with the offset or some offset prior to it, then we know the node's offset is
3513 		 * at least <= startBlock.  So, if the end of the node is greater than the end of
3517 		if ((node->offset + node->length) >= (startBlock + numBlocks)) {
3518 			if (node->offset > startBlock) {
3519 				panic ("hfs_rbtree_isallocated: bad node ordering!");
3525 	 * We got here if either our node search resulted in a node whose extent
3526 	 * was strictly before our target offset, or we couldnt' find a previous node
3528 	 * at least one block in the target range is allocated since the next node's offset
3531 	 * Either way, this means that the target node is unavailable to allocate, so
4219 		extent_node_t *node = NULL;
4229 		 * from the starting point or 1 earlier.  We may need to split apart an existing node
4232 		node = extent_tree_off_search_prev(&hfsmp->offset_tree, &search_sentinel);
4233 		if (node) {
4235 			if (node->offset == new_end_block) {
4238 				 * since this entry is biting the dust.  Update remover to node.
4241 				prev = extent_tree_off_prev (&hfsmp->offset_tree, node);
4245 				remover = node;
4248 				/* See if we need to split this node */
4249 				if ((node->offset + node->length) > new_end_block) {
4251 					 * Update node to reflect its new size up until new_end_block.
4253 					remover = node->offset_next;
4254 					node->length = new_end_block - node->offset;
4255 					/* node is becoming the last free extent in the volume.  */
4256 					node->offset_next = NULL;
4259 					if (node->offset_next == NULL) {
4261 						 * 'node' points to the last free extent in the volume.
4268 					 * Otherwise, point our temp variable 'remover' to the node where
4269 					 * we'll need to start yanking things out of the tree, and make 'node'
4272 					remover = node->offset_next;
4274 						panic ("UpdateAllocLimit: Invalid RBTree node next ptr!");
4276 					node->offset_next = NULL;
4281 			 * Remover is our "temp" pointer that points to the current node to remove from