hfscommon/Misc/HybridAllocator.c

54  * Get the first node in the tree.  If it is empty, return NULL
57  * Get the last node in the tree.  If it is empty, return NULL
61  * static extent_node_t*	extent_tree_offset_next (extent_tree_offset_t * tree, extent_node_t * node)
64  * static extent_node_t*	extent_tree_offset_prev(extent_tree_offset_t * tree, extent_node_t * node)
70  * either grab the next node, if possible, or return NULL
74  * either grab the previous node, if possible, or return NULL
77  * Insert the specified node into the tree.
78  * static void				extent_tree_offset_insert(extent_tree_offset_t * tree, extent_node_t * node)
80  * Remove the specified node from the tree.
81  * static void				extent_tree_offset_remove(extent_tree_offset_t * tree, extent_node_t * node)
89 								 u_int32_t size, u_int32_t offset, extent_node_t *node);
97  * -1 if node 1's offset < node 2's offset.
98  *  1 if node 1's offset > node 2's offset.
110  * Allocate a new red-black tree node.
117 	extent_node_t *node;
118 	MALLOC(node, extent_node_t *, sizeof(extent_node_t), M_TEMP, M_WAITOK);
120 	if (node) {
121 		node->offset = offset;
122 		node->length = length;
123 		node->offset_next = NULL;
125 	return node;
129  * De-allocate a red-black tree node.
135 free_node(extent_node_t *node) {
136 	FREE(node, M_TEMP);
156 	extent_node_t *node = NULL;
159 	node = extent_tree_off_first (offset_tree);
160 	if (node) {
161 		node->offset_next = NULL;
168  * This function finds the first node in the specified red-black tree, then
174 	extent_node_t *node = NULL;
177 	node = extent_tree_offset_first (off_tree);
179 	while (node) {
180 		next = node->offset_next;
181 		extent_tree_offset_remove (off_tree, node);
182 		free_node (node);
183 		node = next;
198  * Search the extent tree by offset, finding the next node in the tree
238  * Search the extent tree by offset, finding the previous node in the tree
251  * Find the first node in the extent tree, by offset.  This will be the first
260  * From a given tree node (sorted by offset), get the next node in the tree.
263 extent_tree_off_next(extent_tree_offset_t * tree, extent_node_t *node)
265 	return extent_tree_offset_next(tree, node);
269  * From a given tree node (sorted by offset), get the previous node in the tree.
272 extent_tree_off_prev(extent_tree_offset_t * tree, extent_node_t *node)
274 	return extent_tree_offset_prev(tree, node);
279  * For a node of a given offset and size, remove it from the extent tree and
280  * insert a new node that:
282  *	A) increase its offset by that of the node we just removed
283  *  B) decreases its size by that of the node we just removed.
286  * length of the extent represented by node.  The node pointer must point to an
287  * extant node in the tree, as it will be removed from the tree.
291 								 u_int32_t offset, extent_node_t *node)
293 	if (node) {
298 			assert ((size <= node->length));
299 			assert ((offset == node->offset));
302 		prev = extent_tree_offset_prev(offset_tree, node);
305 		 * Note that, unless the node is exactly the size of the amount of space
307 		 * how much space we remove from the node.  Remember that the offset tree is
308 		 * sorting the extents based on their offsets, and that each node is a discrete
311 		 * If node A has offset B, with length C, in the offset tree, by definition, there
312 		 * can be no other node in the extent tree within the range {B, B+C}.  If there were,
315 		 * So in the normal case, we'll just update the offset node in place with the new offset
318 		 * Otherwise, if we have an exact match, then just remove the node altogether.  Don't forget
321 		if (node->length == size) {
322 			next = node->offset_next;
323 			extent_tree_offset_remove(offset_tree, node);
324 			free_node(node);
330 			node->offset = node->offset + size;
331 			node->length -= size;
332 			/* The next pointer does not change since we keep the node in place */
347  * variant, so if no node exists at the specified offset we'll fail out.
354 	extent_node_t *node = extent_tree_offset_search(offset_tree, &search_sentinel);
355 	if (node && (node->length < size)) {
358 			printf("HFS Allocator: internal_alloc_space, ptr (%p) node->length (%d), node->offset (%d), off(%d), size (%d) \n",
359 				   node, node->length, node->offset, offset, size);
363 	return extent_tree_internal_alloc_space(offset_tree, size, offset, node);
372  * we may be allocating space from the middle of an existing extent node.
380 	extent_node_t *node= NULL;
382 	node = extent_tree_off_search_prev(offset_tree, &search_sentinel);
384 	if (node == NULL) {
388 	if (node && (node->length < size)) {
391 			printf("HFS Allocator: internal_alloc_space, ptr (%p) node->length (%d), node->offset (%d), off(%d), size (%d) \n",
392 				   node, node->length, node->offset, offset, size);
397 	/* Now see if we need to split this node because we're not allocating from the beginning */
398 	if (offset != node->offset) {
401 			assert ((offset + size) <= (node->offset + node->length));
402 			if (node->offset_next) {
403 				assert ((offset > node->offset) && (offset < node->offset_next->offset));
407 		u_int32_t end = node->offset + node->length;
408 		node->length = offset - node->offset;
411 		 * Do we need to create a new node?  If our extent we're carving away ends earlier than
423 			node->offset_next = newnode;
429 		return extent_tree_internal_alloc_space(offset_tree, size, offset, node);
444  * If no node existed at the specified offset, then create a new one and insert it
447  * Finally, search based on the node that would precede our newly created/inserted one.
448  * If possible, coalesce the previous node into our new one.
450  * We return the node which we are modifying in this function.
457 	extent_node_t *node = NULL;
461 	node = extent_tree_offset_nsearch(offset_tree, &search_sentinel);
462 	/* Insert our node into the tree, and coalesce with the next one if necessary */
464 	if ((node) && (node->offset == search_sentinel.offset)) {
465         node->offset = offset;
466         node->length += size;
467 		next = node->offset_next;
470 		node = alloc_node(size, offset);
471         assert(node);
472         extent_tree_offset_insert(offset_tree, node);
475 		next = extent_tree_offset_next(offset_tree, node);
476 		node->offset_next = next;
480 	prev = extent_tree_offset_prev(offset_tree, node);
483         node->offset = prev->offset;
484         node->length += prev->length;
486 		prev = extent_tree_offset_prev(offset_tree, node);
491 		prev->offset_next = node;
494 	return node;
498  * Remove the specified node from the offset_tree.  Note that the parameter node
499  * must be an extant node in the tree.  This function is used by the allocator when
504 extent_tree_remove_node (extent_tree_offset_t *offset_tree, extent_node_t * node) {
506 	if (node) {
508 		extent_tree_offset_remove(offset_tree, node);
518  * For each node in the tree, print out its length and block offset.
523 	extent_node_t *node = NULL;
525 	node = extent_tree_offset_first(offset_tree);
526 	while (node) {
527 		printf("length: %u, offset: %u\n", node->length, node->offset);
528 		node = node->offset_next;