Lines Matching refs:tree
83 void cache_tree_init(struct cache_tree *tree) in cache_tree_init() argument
85 tree->root = RB_ROOT; in cache_tree_init()
101 int add_cache_extent(struct cache_tree *tree, u64 start, u64 size) in add_cache_extent() argument
109 ret = insert_cache_extent(tree, pe); in add_cache_extent()
116 int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe) in insert_cache_extent() argument
118 return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes); in insert_cache_extent()
121 int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe) in insert_cache_extent2() argument
123 return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes2); in insert_cache_extent2()
126 struct cache_extent *lookup_cache_extent(struct cache_tree *tree, in lookup_cache_extent() argument
135 node = rb_search(&tree->root, &range, cache_tree_comp_range, NULL); in lookup_cache_extent()
143 struct cache_extent *lookup_cache_extent2(struct cache_tree *tree, in lookup_cache_extent2() argument
153 node = rb_search(&tree->root, &range, cache_tree_comp_range2, NULL); in lookup_cache_extent2()
161 struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start) in search_cache_extent() argument
170 node = rb_search(&tree->root, &range, cache_tree_comp_range, &next); in search_cache_extent()
180 struct cache_extent *search_cache_extent2(struct cache_tree *tree, in search_cache_extent2() argument
191 node = rb_search(&tree->root, &range, cache_tree_comp_range2, &next); in search_cache_extent2()
201 struct cache_extent *first_cache_extent(struct cache_tree *tree) in first_cache_extent() argument
203 struct rb_node *node = rb_first(&tree->root); in first_cache_extent()
210 struct cache_extent *last_cache_extent(struct cache_tree *tree) in last_cache_extent() argument
212 struct rb_node *node = rb_last(&tree->root); in last_cache_extent()
237 void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe) in remove_cache_extent() argument
239 rb_erase(&pe->rb_node, &tree->root); in remove_cache_extent()
242 void cache_tree_free_extents(struct cache_tree *tree, in cache_tree_free_extents() argument
247 while ((ce = first_cache_extent(tree))) { in cache_tree_free_extents()
248 remove_cache_extent(tree, ce); in cache_tree_free_extents()
258 void free_extent_cache_tree(struct cache_tree *tree) in free_extent_cache_tree() argument
260 cache_tree_free_extents(tree, free_extent_cache); in free_extent_cache_tree()
263 int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size) in add_merge_cache_extent() argument
272 if (cache_tree_empty(tree)) in add_merge_cache_extent()
275 cache = search_cache_extent(tree, start); in add_merge_cache_extent()
282 prev = last_cache_extent(tree); in add_merge_cache_extent()
308 remove_cache_extent(tree, prev); in add_merge_cache_extent()
316 ret = add_cache_extent(tree, start, size); in add_merge_cache_extent()