aboutsummaryrefslogtreecommitdiff
path: root/fs/btrfs/ctree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/ctree.c')
-rw-r--r--fs/btrfs/ctree.c290
1 files changed, 0 insertions, 290 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 98c08d353a7..5ffced91606 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -70,296 +70,6 @@ void btrfs_release_path(struct btrfs_path *p)
memset(p, 0, sizeof(*p));
}
-int __btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
-{
- if (a->objectid > b->objectid)
- return 1;
- if (a->objectid < b->objectid)
- return -1;
- if (a->type > b->type)
- return 1;
- if (a->type < b->type)
- return -1;
- if (a->offset > b->offset)
- return 1;
- if (a->offset < b->offset)
- return -1;
- return 0;
-}
-
-int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
-{
- if (a->objectid > b->objectid)
- return 1;
- if (a->objectid < b->objectid)
- return -1;
- if (a->type > b->type)
- return 1;
- if (a->type < b->type)
- return -1;
- return 0;
-}
-
-/*
- * search for key in the extent_buffer. The items start at offset p,
- * and they are item_size apart. There are 'max' items in p.
- *
- * the slot in the array is returned via slot, and it points to
- * the place where you would insert key if it is not found in
- * the array.
- *
- * slot may point to max if the key is bigger than all of the keys
- */
-static int __generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
- int max, int *slot)
-{
- int low = 0, high = max, mid, ret;
- struct btrfs_key *tmp;
-
- while (low < high) {
- mid = (low + high) / 2;
-
- tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
- ret = __btrfs_comp_keys(tmp, key);
-
- if (ret < 0) {
- low = mid + 1;
- } else if (ret > 0) {
- high = mid;
- } else {
- *slot = mid;
- return 0;
- }
- }
-
- *slot = low;
- return 1;
-}
-
-int __btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
- int *slot)
-{
- void *addr;
- unsigned long size;
-
- if (p->header.level) {
- addr = p->node.ptrs;
- size = sizeof(struct btrfs_key_ptr);
- } else {
- addr = p->leaf.items;
- size = sizeof(struct btrfs_item);
- }
-
- return __generic_bin_search(addr, size, key, p->header.nritems, slot);
-}
-
-static void clear_path(struct __btrfs_path *p)
-{
- int i;
-
- for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
- p->nodes[i] = NULL;
- p->slots[i] = 0;
- }
-}
-
-void __btrfs_free_path(struct __btrfs_path *p)
-{
- int i;
-
- for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
- if (p->nodes[i])
- free(p->nodes[i]);
- }
-
- clear_path(p);
-}
-
-static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
-{
- ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
- sizeof(struct btrfs_header));
- unsigned long size, offset = sizeof(*hdr);
- union btrfs_tree_node *res;
- u32 i;
-
- if (!btrfs_devread(physical, sizeof(*hdr), hdr))
- return -1;
-
- btrfs_header_to_cpu(hdr);
-
- if (hdr->level)
- size = sizeof(struct btrfs_node)
- + hdr->nritems * sizeof(struct btrfs_key_ptr);
- else
- size = btrfs_info.sb.nodesize;
-
- res = malloc_cache_aligned(size);
- if (!res) {
- debug("%s: malloc failed\n", __func__);
- return -1;
- }
-
- if (!btrfs_devread(physical + offset, size - offset,
- ((u8 *) res) + offset)) {
- free(res);
- return -1;
- }
-
- memcpy(&res->header, hdr, sizeof(*hdr));
- if (hdr->level)
- for (i = 0; i < hdr->nritems; ++i)
- btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
- else
- for (i = 0; i < hdr->nritems; ++i)
- btrfs_item_to_cpu(&res->leaf.items[i]);
-
- *buf = res;
-
- return 0;
-}
-
-int btrfs_search_tree(const struct __btrfs_root *root, struct btrfs_key *key,
- struct __btrfs_path *p)
-{
- u8 lvl, prev_lvl;
- int i, slot, ret;
- u64 logical, physical;
- union btrfs_tree_node *buf;
-
- clear_path(p);
-
- logical = root->bytenr;
-
- for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
- physical = btrfs_map_logical_to_physical(logical);
- if (physical == -1ULL)
- goto err;
-
- if (read_tree_node(physical, &buf))
- goto err;
-
- lvl = buf->header.level;
- if (i && prev_lvl != lvl + 1) {
- printf("%s: invalid level in header at %llu\n",
- __func__, logical);
- goto err;
- }
- prev_lvl = lvl;
-
- ret = __btrfs_bin_search(buf, key, &slot);
- if (ret < 0)
- goto err;
- if (ret && slot > 0 && lvl)
- slot -= 1;
-
- p->slots[lvl] = slot;
- p->nodes[lvl] = buf;
-
- if (lvl) {
- logical = buf->node.ptrs[slot].blockptr;
- } else {
- /*
- * The path might be invalid if:
- * cur leaf max < searched value < next leaf min
- *
- * Jump to the next valid element if it exists.
- */
- if (slot >= buf->header.nritems)
- if (btrfs_next_slot(p) < 0)
- goto err;
- break;
- }
- }
-
- return 0;
-err:
- __btrfs_free_path(p);
- return -1;
-}
-
-static int jump_leaf(struct __btrfs_path *path, int dir)
-{
- struct __btrfs_path p;
- u32 slot;
- int level = 1, from_level, i;
-
- dir = dir >= 0 ? 1 : -1;
-
- p = *path;
-
- while (level < BTRFS_MAX_LEVEL) {
- if (!p.nodes[level])
- return 1;
-
- slot = p.slots[level];
- if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
- || (dir < 0 && !slot))
- level++;
- else
- break;
- }
-
- if (level == BTRFS_MAX_LEVEL)
- return 1;
-
- p.slots[level] = slot + dir;
- level--;
- from_level = level;
-
- while (level >= 0) {
- u64 logical, physical;
-
- slot = p.slots[level + 1];
- logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
- physical = btrfs_map_logical_to_physical(logical);
- if (physical == -1ULL)
- goto err;
-
- if (read_tree_node(physical, &p.nodes[level]))
- goto err;
-
- if (dir > 0)
- p.slots[level] = 0;
- else
- p.slots[level] = p.nodes[level]->header.nritems - 1;
- level--;
- }
-
- /* Free rewritten nodes in path */
- for (i = 0; i <= from_level; ++i)
- free(path->nodes[i]);
-
- *path = p;
- return 0;
-
-err:
- /* Free rewritten nodes in p */
- for (i = level + 1; i <= from_level; ++i)
- free(p.nodes[i]);
- return -1;
-}
-
-int btrfs_prev_slot(struct __btrfs_path *p)
-{
- if (!p->slots[0])
- return jump_leaf(p, -1);
-
- p->slots[0]--;
- return 0;
-}
-
-int btrfs_next_slot(struct __btrfs_path *p)
-{
- struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
-
- if (p->slots[0] + 1 >= leaf->header.nritems)
- return jump_leaf(p, 1);
-
- p->slots[0]++;
- return 0;
-}
-
int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
{
if (k1->objectid > k2->objectid)
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-10 08:38:47 +0000