Lines Matching defs:tree

32  * Initialize the extent tree @tree.  Should be called for each new inode or
35 void extent_map_tree_init(struct extent_map_tree *tree)
37 tree->map = RB_ROOT_CACHED;
38 INIT_LIST_HEAD(&tree->modified_extents);
39 rwlock_init(&tree->lock);
132 * Search through the tree for an extent_map with a given offset. If it can't
231 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
237 * We can't modify an extent map that is in the tree and that is being
240 * the tree and 1 for this task (which is unpinning the extent map or
262 rb_erase_cached(&merge->rb_node, &tree->map);
274 rb_erase_cached(&merge->rb_node, &tree->map);
286 * @tree: tree to unpin the extent in
295 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
302 write_lock(&tree->lock);
303 em = lookup_extent_mapping(tree, start, len);
320 try_merge_map(tree, em);
329 write_unlock(&tree->lock);
334 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
336 lockdep_assert_held_write(&tree->lock);
340 try_merge_map(tree, em);
343 static inline void setup_extent_mapping(struct extent_map_tree *tree,
352 list_move(&em->list, &tree->modified_extents);
354 try_merge_map(tree, em);
391 * Add new extent map to the extent tree
393 * @tree: tree to insert new map in
398 * Insert @em into @tree or perform a simple forward/backward merge with
400 * into the tree directly, with an additional reference taken, or a
403 int add_extent_mapping(struct extent_map_tree *tree,
408 lockdep_assert_held_write(&tree->lock);
410 ret = tree_insert(&tree->map, em);
414 setup_extent_mapping(tree, em, modified);
424 __lookup_extent_mapping(struct extent_map_tree *tree,
432 rb_node = __tree_search(&tree->map.rb_root, start, &prev_or_next);
452 * @tree: tree to lookup in
456 * Find and return the first extent_map struct in @tree that intersects the
457 * [start, len] range. There may be additional objects in the tree that
461 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
464 return __lookup_extent_mapping(tree, start, len, 1);
470 * @tree: tree to lookup in
474 * Find and return the first extent_map struct in @tree that intersects the
479 struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
482 return __lookup_extent_mapping(tree, start, len, 0);
486 * Remove an extent_map from the extent tree.
488 * @tree: extent tree to remove from
491 * Remove @em from @tree. No reference counts are dropped, and no checks
494 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
496 lockdep_assert_held_write(&tree->lock);
499 rb_erase_cached(&em->rb_node, &tree->map);
507 static void replace_extent_mapping(struct extent_map_tree *tree,
512 lockdep_assert_held_write(&tree->lock);
518 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map);
521 setup_extent_mapping(tree, new, modified);
545 * Helper for btrfs_get_extent. Given an existing extent in the tree,
548 * the best fitted new extent into the tree.
590 * @em_tree: extent tree into which we want to insert the extent mapping
622 /* it is possible that someone inserted the extent into the tree
624 * an overlapping map exists in the tree
671 * Drop all extent maps from a tree in the fastest possible way, rescheduling
672 * if needed. This avoids searching the tree, from the root down to the first
675 static void drop_all_extent_maps_fast(struct extent_map_tree *tree)
677 write_lock(&tree->lock);
678 while (!RB_EMPTY_ROOT(&tree->map.rb_root)) {
682 node = rb_first_cached(&tree->map);
686 remove_extent_mapping(tree, em);
688 cond_resched_rwlock_write(&tree->lock);
690 write_unlock(&tree->lock);
705 * tree before calling this function.
878 * If the extent map is still in the tree it means that
891 * load it again from the subvolume tree's file extent
905 * Once for the tree reference (we replaced or removed the
906 * extent map from the tree).
923 * Replace a range in the inode's extent map tree with a new extent map.
926 * @new_em: The new extent map to add to the inode's extent map tree.
930 * Drops all the extent maps in the inode's extent map tree that intersect the
931 * range of the new extent map and adds the new extent map to the tree.
933 * tree before calling this function.
940 struct extent_map_tree *tree = &inode->extent_tree;
947 * tree, but getting -EEXIST when adding the new extent map can still
955 write_lock(&tree->lock);
956 ret = add_extent_mapping(tree, new_em, modified);
957 write_unlock(&tree->lock);
1043 /* Once for the tree */