Lines Matching full:path
20 *root, struct btrfs_path *path, int level);
22 const struct btrfs_key *ins_key, struct btrfs_path *path,
30 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
82 /* this also releases the path */
92 * path release drops references on the extent buffers in the path
93 * and it drops any locks held by this path
860 struct btrfs_path *path, int level) in balance_level() argument
870 int orig_slot = path->slots[level]; in balance_level()
875 mid = path->nodes[level]; in balance_level()
877 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK); in balance_level()
883 parent = path->nodes[level + 1]; in balance_level()
884 pslot = path->slots[level + 1]; in balance_level()
921 path->locks[level] = 0; in balance_level()
922 path->nodes[level] = NULL; in balance_level()
925 /* once for the path */ in balance_level()
986 del_ptr(root, path, level + 1, pslot + 1); in balance_level()
1031 del_ptr(root, path, level + 1, pslot); in balance_level()
1047 /* update the path */ in balance_level()
1052 path->nodes[level] = left; in balance_level()
1053 path->slots[level + 1] -= 1; in balance_level()
1054 path->slots[level] = orig_slot; in balance_level()
1061 path->slots[level] = orig_slot; in balance_level()
1066 btrfs_node_blockptr(path->nodes[level], path->slots[level])) in balance_level()
1074 if (path->nodes[level] != left) in balance_level()
1087 struct btrfs_path *path, int level) in push_nodes_for_insert() argument
1097 int orig_slot = path->slots[level]; in push_nodes_for_insert()
1102 mid = path->nodes[level]; in push_nodes_for_insert()
1106 parent = path->nodes[level + 1]; in push_nodes_for_insert()
1107 pslot = path->slots[level + 1]; in push_nodes_for_insert()
1148 path->nodes[level] = left; in push_nodes_for_insert()
1149 path->slots[level + 1] -= 1; in push_nodes_for_insert()
1150 path->slots[level] = orig_slot; in push_nodes_for_insert()
1156 path->slots[level] = orig_slot; in push_nodes_for_insert()
1203 path->nodes[level] = right; in push_nodes_for_insert()
1204 path->slots[level + 1] += 1; in push_nodes_for_insert()
1205 path->slots[level] = orig_slot - in push_nodes_for_insert()
1226 struct btrfs_path *path, in reada_for_search() argument
1240 if (level != 1 && path->reada != READA_FORWARD_ALWAYS) in reada_for_search()
1243 if (!path->nodes[level]) in reada_for_search()
1246 node = path->nodes[level]; in reada_for_search()
1253 if (path->reada == READA_FORWARD_ALWAYS) { in reada_for_search()
1264 if (path->reada != READA_FORWARD_ALWAYS) { in reada_for_search()
1280 if (path->reada == READA_BACK) { in reada_for_search()
1284 } else if (path->reada == READA_FORWARD || in reada_for_search()
1285 path->reada == READA_FORWARD_ALWAYS) { in reada_for_search()
1290 if (path->reada == READA_BACK && objectid) { in reada_for_search()
1296 if (path->reada == READA_FORWARD_ALWAYS || in reada_for_search()
1308 static noinline void reada_for_balance(struct btrfs_path *path, int level) in reada_for_balance() argument
1314 parent = path->nodes[level + 1]; in reada_for_balance()
1319 slot = path->slots[level + 1]; in reada_for_balance()
1330 * in the tree. The exceptions are when our path goes through slot 0, because
1334 * callers might also have set path->keep_locks, which tells this code to keep
1335 * the lock if the path points to the last slot in the block. This is part of
1341 static noinline void unlock_up(struct btrfs_path *path, int level, in unlock_up() argument
1351 if (!path->nodes[i]) in unlock_up()
1353 if (!path->locks[i]) in unlock_up()
1355 if (!no_skips && path->slots[i] == 0) { in unlock_up()
1359 if (!no_skips && path->keep_locks) { in unlock_up()
1361 t = path->nodes[i]; in unlock_up()
1363 if (nritems < 1 || path->slots[i] >= nritems - 1) { in unlock_up()
1371 t = path->nodes[i]; in unlock_up()
1373 btrfs_tree_unlock_rw(t, path->locks[i]); in unlock_up()
1374 path->locks[i] = 0; in unlock_up()
1386 * in cache without setting the path to blocking. If we find the block
1387 * we return zero and the path is unchanged.
1389 * If we can't find the block, we set the path blocking and do some
1481 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1530 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path, in btrfs_find_item() argument
1538 ASSERT(path); in btrfs_find_item()
1545 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); in btrfs_find_item()
1549 eb = path->nodes[0]; in btrfs_find_item()
1550 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { in btrfs_find_item()
1551 ret = btrfs_next_leaf(fs_root, path); in btrfs_find_item()
1554 eb = path->nodes[0]; in btrfs_find_item()
1557 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); in btrfs_find_item()
1655 * @p: Holds all btree nodes along the search path
1673 * of the path (level 0)
1675 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
1744 * then we don't want to set the path blocking, in btrfs_search_slot()
1780 * Leave path with blocking locks to avoid massive in btrfs_search_slot()
1932 * The resulting path and return value will be set up as if we called
2052 * a return value of 1 means the path is at the position where the in btrfs_search_slot_for_read()
2054 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2111 struct btrfs_path *path) in btrfs_search_backwards() argument
2115 ret = btrfs_search_slot(NULL, root, key, path, 0, 0); in btrfs_search_backwards()
2117 ret = btrfs_previous_item(root, path, key->objectid, key->type); in btrfs_search_backwards()
2120 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]); in btrfs_search_backwards()
2133 static void fixup_low_keys(struct btrfs_path *path, in fixup_low_keys() argument
2141 int tslot = path->slots[i]; in fixup_low_keys()
2143 if (!path->nodes[i]) in fixup_low_keys()
2145 t = path->nodes[i]; in fixup_low_keys()
2150 btrfs_mark_buffer_dirty(path->nodes[i]); in fixup_low_keys()
2163 struct btrfs_path *path, in btrfs_set_item_key_safe() argument
2170 eb = path->nodes[0]; in btrfs_set_item_key_safe()
2171 slot = path->slots[0]; in btrfs_set_item_key_safe()
2205 fixup_low_keys(path, &disk_key, 1); in btrfs_set_item_key_safe()
2420 struct btrfs_path *path, int level) in insert_new_root() argument
2430 BUG_ON(path->nodes[level]); in insert_new_root()
2431 BUG_ON(path->nodes[level-1] != root->node); in insert_new_root()
2433 lower = path->nodes[level-1]; in insert_new_root()
2467 path->nodes[level] = c; in insert_new_root()
2468 path->locks[level] = BTRFS_WRITE_LOCK; in insert_new_root()
2469 path->slots[level] = 0; in insert_new_root()
2481 struct btrfs_path *path, in insert_ptr() argument
2489 BUG_ON(!path->nodes[level]); in insert_ptr()
2490 btrfs_assert_tree_locked(path->nodes[level]); in insert_ptr()
2491 lower = path->nodes[level]; in insert_ptr()
2520 * split the node at the specified level in path in two.
2521 * The path is corrected to point to the appropriate node after the split
2530 struct btrfs_path *path, int level) in split_node() argument
2540 c = path->nodes[level]; in split_node()
2553 ret = insert_new_root(trans, root, path, level + 1); in split_node()
2557 ret = push_nodes_for_insert(trans, root, path, level); in split_node()
2558 c = path->nodes[level]; in split_node()
2594 insert_ptr(trans, path, &disk_key, split->start, in split_node()
2595 path->slots[level + 1] + 1, level + 1); in split_node()
2597 if (path->slots[level] >= mid) { in split_node()
2598 path->slots[level] -= mid; in split_node()
2601 path->nodes[level] = split; in split_node()
2602 path->slots[level + 1] += 1; in split_node()
2661 static noinline int __push_leaf_right(struct btrfs_path *path, in __push_leaf_right() argument
2668 struct extent_buffer *left = path->nodes[0]; in __push_leaf_right()
2669 struct extent_buffer *upper = path->nodes[1]; in __push_leaf_right()
2687 if (path->slots[0] >= left_nritems) in __push_leaf_right()
2690 slot = path->slots[1]; in __push_leaf_right()
2696 if (path->slots[0] > i) in __push_leaf_right()
2698 if (path->slots[0] == i) { in __push_leaf_right()
2706 if (path->slots[0] == i) in __push_leaf_right()
2778 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
2779 if (path->slots[0] >= left_nritems) { in __push_leaf_right()
2780 path->slots[0] -= left_nritems; in __push_leaf_right()
2781 if (btrfs_header_nritems(path->nodes[0]) == 0) in __push_leaf_right()
2782 btrfs_clean_tree_block(path->nodes[0]); in __push_leaf_right()
2783 btrfs_tree_unlock(path->nodes[0]); in __push_leaf_right()
2784 free_extent_buffer(path->nodes[0]); in __push_leaf_right()
2785 path->nodes[0] = right; in __push_leaf_right()
2786 path->slots[1] += 1; in __push_leaf_right()
2800 * push some data in the path leaf to the right, trying to free up at
2810 *root, struct btrfs_path *path, in push_leaf_right() argument
2814 struct extent_buffer *left = path->nodes[0]; in push_leaf_right()
2822 if (!path->nodes[1]) in push_leaf_right()
2825 slot = path->slots[1]; in push_leaf_right()
2826 upper = path->nodes[1]; in push_leaf_right()
2830 btrfs_assert_tree_locked(path->nodes[1]); in push_leaf_right()
2866 if (path->slots[0] == left_nritems && !empty) { in push_leaf_right()
2873 path->nodes[0] = right; in push_leaf_right()
2874 path->slots[0] = 0; in push_leaf_right()
2875 path->slots[1]++; in push_leaf_right()
2879 return __push_leaf_right(path, min_data_size, empty, in push_leaf_right()
2888 * push some data in the path leaf to the left, trying to free up at
2895 static noinline int __push_leaf_left(struct btrfs_path *path, int data_size, in __push_leaf_left() argument
2902 struct extent_buffer *right = path->nodes[0]; in __push_leaf_left()
2923 if (path->slots[0] < i) in __push_leaf_left()
2925 if (path->slots[0] == i) { in __push_leaf_left()
2933 if (path->slots[0] == i) in __push_leaf_left()
3017 fixup_low_keys(path, &disk_key, 1); in __push_leaf_left()
3019 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3020 if (path->slots[0] < push_items) { in __push_leaf_left()
3021 path->slots[0] += old_left_nritems; in __push_leaf_left()
3022 btrfs_tree_unlock(path->nodes[0]); in __push_leaf_left()
3023 free_extent_buffer(path->nodes[0]); in __push_leaf_left()
3024 path->nodes[0] = left; in __push_leaf_left()
3025 path->slots[1] -= 1; in __push_leaf_left()
3029 path->slots[0] -= push_items; in __push_leaf_left()
3031 BUG_ON(path->slots[0] < 0); in __push_leaf_left()
3040 * push some data in the path leaf to the left, trying to free up at
3048 *root, struct btrfs_path *path, int min_data_size, in push_leaf_left() argument
3051 struct extent_buffer *right = path->nodes[0]; in push_leaf_left()
3058 slot = path->slots[1]; in push_leaf_left()
3061 if (!path->nodes[1]) in push_leaf_left()
3068 btrfs_assert_tree_locked(path->nodes[1]); in push_leaf_left()
3070 left = btrfs_read_node_slot(path->nodes[1], slot - 1); in push_leaf_left()
3088 path->nodes[1], slot - 1, &left, in push_leaf_left()
3107 return __push_leaf_left(path, min_data_size, in push_leaf_left()
3117 * split the path's leaf in two, making sure there is at least data_size
3118 * available for the resulting leaf level of the path.
3121 struct btrfs_path *path, in copy_for_split() argument
3159 insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1); in copy_for_split()
3163 BUG_ON(path->slots[0] != slot); in copy_for_split()
3166 btrfs_tree_unlock(path->nodes[0]); in copy_for_split()
3167 free_extent_buffer(path->nodes[0]); in copy_for_split()
3168 path->nodes[0] = right; in copy_for_split()
3169 path->slots[0] -= mid; in copy_for_split()
3170 path->slots[1] += 1; in copy_for_split()
3176 BUG_ON(path->slots[0] < 0); in copy_for_split()
3191 struct btrfs_path *path, in push_for_double_split() argument
3200 slot = path->slots[0]; in push_for_double_split()
3201 if (slot < btrfs_header_nritems(path->nodes[0])) in push_for_double_split()
3202 space_needed -= btrfs_leaf_free_space(path->nodes[0]); in push_for_double_split()
3208 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot); in push_for_double_split()
3215 nritems = btrfs_header_nritems(path->nodes[0]); in push_for_double_split()
3220 if (path->slots[0] == 0 || path->slots[0] == nritems) in push_for_double_split()
3223 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) in push_for_double_split()
3227 slot = path->slots[0]; in push_for_double_split()
3230 space_needed -= btrfs_leaf_free_space(path->nodes[0]); in push_for_double_split()
3231 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot); in push_for_double_split()
3244 * split the path's leaf in two, making sure there is at least data_size
3245 * available for the resulting leaf level of the path.
3252 struct btrfs_path *path, int data_size, in split_leaf() argument
3268 l = path->nodes[0]; in split_leaf()
3269 slot = path->slots[0]; in split_leaf()
3275 if (data_size && path->nodes[1]) { in split_leaf()
3281 wret = push_leaf_right(trans, root, path, space_needed, in split_leaf()
3289 wret = push_leaf_left(trans, root, path, space_needed, in split_leaf()
3294 l = path->nodes[0]; in split_leaf()
3301 if (!path->nodes[1]) { in split_leaf()
3302 ret = insert_new_root(trans, root, path, 1); in split_leaf()
3308 l = path->nodes[0]; in split_leaf()
3309 slot = path->slots[0]; in split_leaf()
3375 insert_ptr(trans, path, &disk_key, in split_leaf()
3376 right->start, path->slots[1] + 1, 1); in split_leaf()
3377 btrfs_tree_unlock(path->nodes[0]); in split_leaf()
3378 free_extent_buffer(path->nodes[0]); in split_leaf()
3379 path->nodes[0] = right; in split_leaf()
3380 path->slots[0] = 0; in split_leaf()
3381 path->slots[1] += 1; in split_leaf()
3384 insert_ptr(trans, path, &disk_key, in split_leaf()
3385 right->start, path->slots[1], 1); in split_leaf()
3386 btrfs_tree_unlock(path->nodes[0]); in split_leaf()
3387 free_extent_buffer(path->nodes[0]); in split_leaf()
3388 path->nodes[0] = right; in split_leaf()
3389 path->slots[0] = 0; in split_leaf()
3390 if (path->slots[1] == 0) in split_leaf()
3391 fixup_low_keys(path, &disk_key, 1); in split_leaf()
3401 copy_for_split(trans, path, l, right, slot, mid, nritems); in split_leaf()
3412 push_for_double_split(trans, root, path, data_size); in split_leaf()
3414 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) in split_leaf()
3421 struct btrfs_path *path, int ins_len) in setup_leaf_for_split() argument
3430 leaf = path->nodes[0]; in setup_leaf_for_split()
3431 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
3439 item_size = btrfs_item_size_nr(leaf, path->slots[0]); in setup_leaf_for_split()
3441 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3445 btrfs_release_path(path); in setup_leaf_for_split()
3447 path->keep_locks = 1; in setup_leaf_for_split()
3448 path->search_for_split = 1; in setup_leaf_for_split()
3449 ret = btrfs_search_slot(trans, root, &key, path, 0, 1); in setup_leaf_for_split()
3450 path->search_for_split = 0; in setup_leaf_for_split()
3457 leaf = path->nodes[0]; in setup_leaf_for_split()
3459 if (item_size != btrfs_item_size_nr(leaf, path->slots[0])) in setup_leaf_for_split()
3463 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len) in setup_leaf_for_split()
3467 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3473 ret = split_leaf(trans, root, &key, path, ins_len, 1); in setup_leaf_for_split()
3477 path->keep_locks = 0; in setup_leaf_for_split()
3478 btrfs_unlock_up_safe(path, 1); in setup_leaf_for_split()
3481 path->keep_locks = 0; in setup_leaf_for_split()
3485 static noinline int split_item(struct btrfs_path *path, in split_item() argument
3499 leaf = path->nodes[0]; in split_item()
3502 item = btrfs_item_nr(path->slots[0]); in split_item()
3511 path->slots[0]), item_size); in split_item()
3513 slot = path->slots[0] + 1; in split_item()
3538 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
3557 * The path may be released by this operation. After
3558 * the split, the path is pointing to the old item. The
3569 struct btrfs_path *path, in btrfs_split_item() argument
3574 ret = setup_leaf_for_split(trans, root, path, in btrfs_split_item()
3579 ret = split_item(path, new_key, split_offset); in btrfs_split_item()
3593 struct btrfs_path *path, in btrfs_duplicate_item() argument
3600 leaf = path->nodes[0]; in btrfs_duplicate_item()
3601 item_size = btrfs_item_size_nr(leaf, path->slots[0]); in btrfs_duplicate_item()
3602 ret = setup_leaf_for_split(trans, root, path, in btrfs_duplicate_item()
3607 path->slots[0]++; in btrfs_duplicate_item()
3608 setup_items_for_insert(root, path, new_key, &item_size, 1); in btrfs_duplicate_item()
3609 leaf = path->nodes[0]; in btrfs_duplicate_item()
3611 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
3612 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
3618 * make the item pointed to by the path smaller. new_size indicates
3623 void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end) in btrfs_truncate_item() argument
3636 leaf = path->nodes[0]; in btrfs_truncate_item()
3637 slot = path->slots[0]; in btrfs_truncate_item()
3703 fixup_low_keys(path, &disk_key, 1); in btrfs_truncate_item()
3717 * make the item pointed to by the path bigger, data_size is the added size.
3719 void btrfs_extend_item(struct btrfs_path *path, u32 data_size) in btrfs_extend_item() argument
3731 leaf = path->nodes[0]; in btrfs_extend_item()
3740 slot = path->slots[0]; in btrfs_extend_item()
3787 * @path: points to the leaf/slot where we are going to insert new items
3792 void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path, in setup_items_for_insert() argument
3812 if (path->slots[0] == 0) { in setup_items_for_insert()
3814 fixup_low_keys(path, &disk_key, 1); in setup_items_for_insert()
3816 btrfs_unlock_up_safe(path, 1); in setup_items_for_insert()
3818 leaf = path->nodes[0]; in setup_items_for_insert()
3819 slot = path->slots[0]; in setup_items_for_insert()
3887 * This does all the path init required, making room in the tree if needed.
3891 struct btrfs_path *path, in btrfs_insert_empty_items() argument
3905 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); in btrfs_insert_empty_items()
3911 slot = path->slots[0]; in btrfs_insert_empty_items()
3914 setup_items_for_insert(root, path, cpu_key, data_size, nr); in btrfs_insert_empty_items()
3920 * This does all the path init required, making room in the tree if needed.
3927 struct btrfs_path *path; in btrfs_insert_item() local
3931 path = btrfs_alloc_path(); in btrfs_insert_item()
3932 if (!path) in btrfs_insert_item()
3934 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); in btrfs_insert_item()
3936 leaf = path->nodes[0]; in btrfs_insert_item()
3937 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
3941 btrfs_free_path(path); in btrfs_insert_item()
3951 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path, in del_ptr() argument
3954 struct extent_buffer *parent = path->nodes[level]; in del_ptr()
3986 fixup_low_keys(path, &disk_key, level + 1); in del_ptr()
3992 * a helper function to delete the leaf pointed to by path->slots[1] and
3993 * path->nodes[1].
3995 * This deletes the pointer in path->nodes[1] and frees the leaf
3998 * The path must have already been setup for deleting the leaf, including
3999 * all the proper balancing. path->nodes[1] must be locked.
4003 struct btrfs_path *path, in btrfs_del_leaf() argument
4007 del_ptr(root, path, 1, path->slots[1]); in btrfs_del_leaf()
4013 btrfs_unlock_up_safe(path, 0); in btrfs_del_leaf()
4022 * delete the item at the leaf level in path. If that empties
4026 struct btrfs_path *path, int slot, int nr) in btrfs_del_items() argument
4038 leaf = path->nodes[0]; in btrfs_del_items()
4078 btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4086 fixup_low_keys(path, &disk_key, 1); in btrfs_del_items()
4091 /* push_leaf_left fixes the path. in btrfs_del_items()
4092 * make sure the path still points to our leaf in btrfs_del_items()
4095 slot = path->slots[1]; in btrfs_del_items()
4098 wret = push_leaf_left(trans, root, path, 1, 1, in btrfs_del_items()
4103 if (path->nodes[0] == leaf && in btrfs_del_items()
4105 wret = push_leaf_right(trans, root, path, 1, in btrfs_del_items()
4112 path->slots[1] = slot; in btrfs_del_items()
4113 btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4117 /* if we're still in the path, make sure in btrfs_del_items()
4122 if (path->nodes[0] == leaf) in btrfs_del_items()
4138 * This may release the path, and so you may lose any locks held at the
4141 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) in btrfs_prev_leaf() argument
4147 btrfs_item_key_to_cpu(path->nodes[0], &key, 0); in btrfs_prev_leaf()
4162 btrfs_release_path(path); in btrfs_prev_leaf()
4163 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); in btrfs_prev_leaf()
4166 btrfs_item_key(path->nodes[0], &found_key, 0); in btrfs_prev_leaf()
4170 * before we released our path. And after we released our path, that in btrfs_prev_leaf()
4190 * key and get a writable path.
4192 * This honors path->lowest_level to prevent descent past a given level
4203 struct btrfs_path *path, in btrfs_search_forward() argument
4213 int keep_locks = path->keep_locks; in btrfs_search_forward()
4215 path->keep_locks = 1; in btrfs_search_forward()
4219 WARN_ON(path->nodes[level]); in btrfs_search_forward()
4220 path->nodes[level] = cur; in btrfs_search_forward()
4221 path->locks[level] = BTRFS_READ_LOCK; in btrfs_search_forward()
4236 /* at the lowest level, we're done, setup the path and exit */ in btrfs_search_forward()
4237 if (level == path->lowest_level) { in btrfs_search_forward()
4241 path->slots[level] = slot; in btrfs_search_forward()
4267 path->slots[level] = slot; in btrfs_search_forward()
4268 sret = btrfs_find_next_key(root, path, min_key, level, in btrfs_search_forward()
4271 btrfs_release_path(path); in btrfs_search_forward()
4279 path->slots[level] = slot; in btrfs_search_forward()
4280 if (level == path->lowest_level) { in btrfs_search_forward()
4292 path->locks[level - 1] = BTRFS_READ_LOCK; in btrfs_search_forward()
4293 path->nodes[level - 1] = cur; in btrfs_search_forward()
4294 unlock_up(path, level, 1, 0, NULL); in btrfs_search_forward()
4297 path->keep_locks = keep_locks; in btrfs_search_forward()
4299 btrfs_unlock_up_safe(path, path->lowest_level + 1); in btrfs_search_forward()
4307 * and fixup the path. It looks for and returns the next key in the
4308 * tree based on the current path and the min_trans parameters.
4313 * path->keep_locks should be set to 1 on the search made before
4316 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, in btrfs_find_next_key() argument
4322 WARN_ON(!path->keep_locks && !path->skip_locking); in btrfs_find_next_key()
4324 if (!path->nodes[level]) in btrfs_find_next_key()
4327 slot = path->slots[level] + 1; in btrfs_find_next_key()
4328 c = path->nodes[level]; in btrfs_find_next_key()
4335 !path->nodes[level + 1]) in btrfs_find_next_key()
4338 if (path->locks[level + 1] || path->skip_locking) { in btrfs_find_next_key()
4349 orig_lowest = path->lowest_level; in btrfs_find_next_key()
4350 btrfs_release_path(path); in btrfs_find_next_key()
4351 path->lowest_level = level; in btrfs_find_next_key()
4352 ret = btrfs_search_slot(NULL, root, &cur_key, path, in btrfs_find_next_key()
4354 path->lowest_level = orig_lowest; in btrfs_find_next_key()
4358 c = path->nodes[level]; in btrfs_find_next_key()
4359 slot = path->slots[level]; in btrfs_find_next_key()
4381 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path, in btrfs_next_old_leaf() argument
4393 nritems = btrfs_header_nritems(path->nodes[0]); in btrfs_next_old_leaf()
4397 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); in btrfs_next_old_leaf()
4401 btrfs_release_path(path); in btrfs_next_old_leaf()
4403 path->keep_locks = 1; in btrfs_next_old_leaf()
4406 ret = btrfs_search_old_slot(root, &key, path, time_seq); in btrfs_next_old_leaf()
4408 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); in btrfs_next_old_leaf()
4409 path->keep_locks = 0; in btrfs_next_old_leaf()
4414 nritems = btrfs_header_nritems(path->nodes[0]); in btrfs_next_old_leaf()
4416 * by releasing the path above we dropped all our locks. A balance in btrfs_next_old_leaf()
4419 * advance the path if there are now more items available. in btrfs_next_old_leaf()
4421 if (nritems > 0 && path->slots[0] < nritems - 1) { in btrfs_next_old_leaf()
4423 path->slots[0]++; in btrfs_next_old_leaf()
4429 * - after releasing the path above, someone has removed the item that in btrfs_next_old_leaf()
4437 * with ret > 0, the key isn't found, the path points to the slot in btrfs_next_old_leaf()
4438 * where it should be inserted, so the path->slots[0] item must be the in btrfs_next_old_leaf()
4441 if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) { in btrfs_next_old_leaf()
4447 if (!path->nodes[level]) { in btrfs_next_old_leaf()
4452 slot = path->slots[level] + 1; in btrfs_next_old_leaf()
4453 c = path->nodes[level]; in btrfs_next_old_leaf()
4470 if (path->locks[level]) { in btrfs_next_old_leaf()
4471 btrfs_tree_read_unlock(path->nodes[i]); in btrfs_next_old_leaf()
4472 path->locks[i] = 0; in btrfs_next_old_leaf()
4474 free_extent_buffer(path->nodes[i]); in btrfs_next_old_leaf()
4475 path->nodes[i] = NULL; in btrfs_next_old_leaf()
4479 ret = read_block_for_search(root, path, &next, level, in btrfs_next_old_leaf()
4485 btrfs_release_path(path); in btrfs_next_old_leaf()
4489 if (!path->skip_locking) { in btrfs_next_old_leaf()
4500 btrfs_release_path(path); in btrfs_next_old_leaf()
4509 path->slots[level] = slot; in btrfs_next_old_leaf()
4512 path->nodes[level] = next; in btrfs_next_old_leaf()
4513 path->slots[level] = 0; in btrfs_next_old_leaf()
4514 if (!path->skip_locking) in btrfs_next_old_leaf()
4515 path->locks[level] = BTRFS_READ_LOCK; in btrfs_next_old_leaf()
4519 ret = read_block_for_search(root, path, &next, level, in btrfs_next_old_leaf()
4525 btrfs_release_path(path); in btrfs_next_old_leaf()
4529 if (!path->skip_locking) in btrfs_next_old_leaf()
4534 unlock_up(path, 0, 1, 0, NULL); in btrfs_next_old_leaf()
4546 struct btrfs_path *path, u64 min_objectid, in btrfs_previous_item() argument
4555 if (path->slots[0] == 0) { in btrfs_previous_item()
4556 ret = btrfs_prev_leaf(root, path); in btrfs_previous_item()
4560 path->slots[0]--; in btrfs_previous_item()
4562 leaf = path->nodes[0]; in btrfs_previous_item()
4566 if (path->slots[0] == nritems) in btrfs_previous_item()
4567 path->slots[0]--; in btrfs_previous_item()
4569 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
4588 struct btrfs_path *path, u64 min_objectid) in btrfs_previous_extent_item() argument
4596 if (path->slots[0] == 0) { in btrfs_previous_extent_item()
4597 ret = btrfs_prev_leaf(root, path); in btrfs_previous_extent_item()
4601 path->slots[0]--; in btrfs_previous_extent_item()
4603 leaf = path->nodes[0]; in btrfs_previous_extent_item()
4607 if (path->slots[0] == nritems) in btrfs_previous_extent_item()
4608 path->slots[0]--; in btrfs_previous_extent_item()
4610 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()