hfscommon/Misc/HybridAllocator.c

51  * initialize the tree
52  * static void				extent_tree_offset_new(extent_tree_offset_t * tree)
54  * Get the first node in the tree.  If it is empty, return NULL
55  * static extent_node_t*	extent_tree_offset_first (extent_tree_offset_t * tree)
57  * Get the last node in the tree.  If it is empty, return NULL
58  * static extent_node_t*	extent_tree_offset_last (extent_tree_offset_t * tree)
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)
67  * static extent_node_t*	extent_tree_offset_search(extent_tree_offset_t * tree, extent_node_t * key)
71  * static extent_node_t*	extent_tree_offset_nsearch(extent_tree_offset_t * tree, extent_node_t * key)
75  * static extent_node_t*	extent_tree_offset_psearch(extent_tree_offset_t * tree, extent_node_t * key)
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)
110  * Allocate a new red-black tree node.
129  * De-allocate a red-black tree node.
141  * the red-black tree based upon the types specified here. This code will build red-black tree
151  * Create a new extent tree, composed of links sorted by offset.
166  * Destroy an extent tree
168  * This function finds the first node in the specified red-black tree, then
169  * uses the embedded linked list to walk through the tree in O(n) time and destroy
188  * Search the extent tree by offset. The "key" argument is only used to extract
190  * tree code.
193 extent_tree_off_search(extent_tree_offset_t *tree, extent_node_t *key) {
194 	return extent_tree_offset_search(tree, key);
198  * Search the extent tree by offset, finding the next node in the tree
201  * tree code.
210  * Search the extent tree by offset to find a starting position.  Then, do a linear search
211  * through the list of free extents to find the first free extent in the tree that has size
214  * tree code.
238  * Search the extent tree by offset, finding the previous node in the tree
241  * tree code.
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
287  * extant node in the tree, as it will be removed from the tree.
306 		 * requested, we do not need to remove it from the offset tree, now matter
307 		 * how much space we remove from the node.  Remember that the offset tree is
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,
340  * Search the extent tree for a region of free space after the specified
368  * Search the extent tree for a region of free space at the specified
437  * this extent into our tree.
439  * Search the offset tree, based on the new offset that we construct by adding
442  * the offset tree because our extent we wanted to add could not have been in the tree.
445  * into the tree.
462 	/* Insert our node into the tree, and coalesce with the next one if necessary */
474 		/* Find the next entry in the tree, if applicable. */
499  * must be an extant node in the tree.  This function is used by the allocator when
501  * tree without going through the normal allocation and deallocation routines.
507 		/* Just remove the entry from the tree */
518  * For each node in the tree, print out its length and block offset.