Searched refs:btree (Results 1 - 25 of 95) sorted by relevance

1234

/linux-master/fs/bcachefs/
H A Ddebug.h8 struct btree;
11 void __bch2_btree_verify(struct bch_fs *, struct btree *);
13 const struct btree *);
15 static inline void bch2_btree_verify(struct bch_fs *c, struct btree *b)
H A Dbbpos_types.h6 enum btree_id btree; member in struct:bbpos
10 static inline struct bbpos BBPOS(enum btree_id btree, struct bpos pos) argument
12 return (struct bbpos) { btree, pos };
H A Dbset.h32 * unless we're rewriting the btree node those stale keys still exist on disk.
41 * along with a header. A btree node is made up of a number of these, written at
49 * implement a btree iterator.
54 * to search entire btree nodes and iterate over them in sorted order.
56 * The btree iterator code serves both functions; it iterates through the keys
57 * in a btree node in sorted order, starting from either keys after a specific
58 * point (if you pass it a search key) or the start of the btree node.
68 * into the last (unwritten) set, most of the keys within a given btree node are
134 * We need one node per 128 bytes in the btree node, which means the auxiliary
135 * search trees take up 3% as much memory as the btree itsel
[all...]
H A Dbtree_cache.h15 void bch2_btree_node_hash_remove(struct btree_cache *, struct btree *);
16 int __bch2_btree_node_hash_insert(struct btree_cache *, struct btree *);
17 int bch2_btree_node_hash_insert(struct btree_cache *, struct btree *,
23 struct btree *__bch2_btree_node_mem_alloc(struct bch_fs *);
24 struct btree *bch2_btree_node_mem_alloc(struct btree_trans *, bool);
26 struct btree *bch2_btree_node_get(struct btree_trans *, struct btree_path *,
30 struct btree *bch2_btree_node_get_noiter(struct btree_trans *, const struct bkey_i *,
58 static inline struct btree *btree_node_mem_ptr(const struct bkey_i *k)
65 /* is btree node in hash table? */
66 static inline bool btree_node_hashed(struct btree *
[all...]
H A Dbbpos.h11 return cmp_int(l.btree, r.btree) ?: bpos_cmp(l.pos, r.pos);
21 if (pos.btree != BTREE_ID_NR) {
22 pos.btree++;
32 prt_str(out, bch2_btree_id_str(pos.btree));
H A Dbtree_update_interior.h13 int bch2_btree_node_check_topology(struct btree_trans *, struct btree *);
28 * Tracks an in progress split/rewrite of a btree node and the update to the
73 struct btree *b;
86 struct btree *b[BTREE_UPDATE_NODES_MAX];
101 struct btree *new_nodes[BTREE_UPDATE_NODES_MAX];
104 struct btree *old_nodes[BTREE_UPDATE_NODES_MAX];
118 * Enough room for btree_split's keys without realloc - btree node
125 struct btree *__bch2_btree_node_alloc_replacement(struct btree_update *,
127 struct btree *,
143 struct btree *
[all...]
H A Dbkey_sort.h6 struct btree *b;
15 static inline void sort_iter_init(struct sort_iter *iter, struct btree *b, unsigned size)
27 static inline void sort_iter_stack_init(struct sort_iter_stack *iter, struct btree *b)
47 bch2_sort_repack(struct bset *, struct btree *,
H A Dbtree_node_scan.h6 bool bch2_btree_node_is_stale(struct bch_fs *, struct btree *);
H A Dbtree_io.h14 struct btree;
18 static inline void set_btree_node_dirty_acct(struct bch_fs *c, struct btree *b)
24 static inline void clear_btree_node_dirty_acct(struct bch_fs *c, struct btree *b)
39 struct btree *b;
58 void bch2_btree_node_io_unlock(struct btree *);
59 void bch2_btree_node_io_lock(struct btree *);
60 void __bch2_btree_node_wait_on_read(struct btree *);
61 void __bch2_btree_node_wait_on_write(struct btree *);
62 void bch2_btree_node_wait_on_read(struct btree *);
63 void bch2_btree_node_wait_on_write(struct btree *);
[all...]
H A Dbtree_write_buffer_types.h17 enum btree_id btree:8; member in struct:wb_key_ref::__anon302::__anon303
19 enum btree_id btree:8;
39 enum btree_id btree:8; member in struct:btree_write_buffered_key
H A Dbtree_write_buffer.h38 enum btree_id btree, struct bkey_i *k)
43 return bch2_journal_key_to_wb_slowpath(c, dst, btree, k);
47 wb_k->btree = btree;
36 bch2_journal_key_to_wb(struct bch_fs *c, struct journal_keys_to_wb *dst, enum btree_id btree, struct bkey_i *k) argument
H A Dbtree_journal_iter.h14 * Iterate over keys in the btree, with keys from the journal overlaid on top:
19 struct btree *b;
51 struct btree_and_journal_iter *, struct btree *,
54 struct btree_and_journal_iter *, struct btree *);
H A Dbtree_types.h72 struct btree { struct
90 * Sets of sorted keys - the real btree node - plus a binary search tree
93 * to the memory we have allocated for this btree node. Additionally,
94 * set[0]->data points to the entire btree node as it exists on disk.
106 /* Key/pointer for this btree node */
129 * If a btree node isn't reachable yet, we don't want to kick off
145 * We never free a struct btree, except on shutdown - we just put it on
148 * dominated by buffers that hold the actual btree node data and those
154 * common to delete and allocate btree nodes in quick succession. It
170 * If we need to allocate memory for a new btree nod
706 btree_id_is_extents(enum btree_id btree) argument
[all...]
H A Dbset.c4 * btree node
22 struct btree *);
34 struct bset_tree *bch2_bkey_to_bset(struct btree *b, struct bkey_packed *k)
40 * There are never duplicate live keys in the btree - but including keys that
55 void bch2_dump_bset(struct bch_fs *c, struct btree *b,
104 void bch2_dump_btree_node(struct bch_fs *c, struct btree *b)
114 void bch2_dump_btree_node_iter(struct btree *b,
120 printk(KERN_ERR "btree node iter with %u/%u sets:\n",
137 struct btree_nr_keys bch2_btree_node_count_keys(struct btree *b)
152 void __bch2_verify_btree_nr_keys(struct btree *
[all...]
/linux-master/fs/hpfs/
H A Danode.c15 struct bplus_header *btree, unsigned sec,
24 if (bp_internal(btree)) {
25 for (i = 0; i < btree->n_used_nodes; i++)
26 if (le32_to_cpu(btree->u.internal[i].file_secno) > sec) {
27 a = le32_to_cpu(btree->u.internal[i].down);
30 btree = &anode->btree;
37 for (i = 0; i < btree->n_used_nodes; i++)
38 if (le32_to_cpu(btree->u.external[i].file_secno) <= sec &&
39 le32_to_cpu(btree
14 hpfs_bplus_lookup(struct super_block *s, struct inode *inode, struct bplus_header *btree, unsigned sec, struct buffer_head *bh) argument
63 struct bplus_header *btree; local
274 hpfs_remove_btree(struct super_block *s, struct bplus_header *btree) argument
404 struct bplus_header *btree; local
[all...]
/linux-master/drivers/md/persistent-data/
H A DMakefile11 dm-btree.o \
12 dm-btree-remove.o \
13 dm-btree-spine.o
/linux-master/fs/nilfs2/
H A Dbtree.c17 #include "btree.h"
58 static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree, argument
61 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
112 static int nilfs_btree_node_size(const struct nilfs_bmap *btree) argument
114 return i_blocksize(btree->b_inode);
117 static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree) argument
119 return btree->b_nchildren_per_block;
331 * nilfs_btree_node_broken - verify consistency of btree node
332 * @node: btree node block to be examined
334 * @inode: host inode of btree
410 nilfs_btree_get_root(const struct nilfs_bmap *btree) argument
427 nilfs_btree_height(const struct nilfs_bmap *btree) argument
433 nilfs_btree_get_node(const struct nilfs_bmap *btree, const struct nilfs_btree_path *path, int level, int *ncmaxp) argument
449 nilfs_btree_bad_node(const struct nilfs_bmap *btree, struct nilfs_btree_node *node, int level) argument
470 __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr, struct buffer_head **bhp, const struct nilfs_btree_readahead_info *ra) argument
540 nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr, struct buffer_head **bhp) argument
546 nilfs_btree_do_lookup(const struct nilfs_bmap *btree, struct nilfs_btree_path *path, __u64 key, __u64 *ptrp, int minlevel, int readahead) argument
608 nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree, struct nilfs_btree_path *path, __u64 *keyp, __u64 *ptrp) argument
657 nilfs_btree_get_next_key(const struct nilfs_bmap *btree, const struct nilfs_btree_path *path, int minlevel, __u64 *nextkey) argument
685 nilfs_btree_lookup(const struct nilfs_bmap *btree, __u64 key, int level, __u64 *ptrp) argument
702 nilfs_btree_lookup_contig(const struct nilfs_bmap *btree, __u64 key, __u64 *ptrp, unsigned int maxblocks) argument
791 nilfs_btree_promote_key(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 key) argument
813 nilfs_btree_do_insert(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
840 nilfs_btree_carry_left(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
886 nilfs_btree_carry_right(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
933 nilfs_btree_split(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
983 nilfs_btree_grow(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1012 nilfs_btree_find_near(const struct nilfs_bmap *btree, const struct nilfs_btree_path *path) argument
1041 nilfs_btree_find_target_v(const struct nilfs_bmap *btree, const struct nilfs_btree_path *path, __u64 key) argument
1061 nilfs_btree_prepare_insert(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int *levelp, __u64 key, __u64 ptr, struct nilfs_bmap_stats *stats) argument
1210 nilfs_btree_commit_insert(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int maxlevel, __u64 key, __u64 ptr) argument
1234 nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr) argument
1263 nilfs_btree_do_delete(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1288 nilfs_btree_borrow_left(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1320 nilfs_btree_borrow_right(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1353 nilfs_btree_concat_left(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1379 nilfs_btree_concat_right(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1404 nilfs_btree_shrink(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1428 nilfs_btree_nop(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) argument
1434 nilfs_btree_prepare_delete(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int *levelp, struct nilfs_bmap_stats *stats, struct inode *dat) argument
1569 nilfs_btree_commit_delete(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int maxlevel, struct inode *dat) argument
1584 nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key) argument
1615 nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start, __u64 *keyp) argument
1636 nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp) argument
1652 nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key) argument
1690 nilfs_btree_gather_data(struct nilfs_bmap *btree, __u64 *keys, __u64 *ptrs, int nitems) argument
1739 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key, union nilfs_bmap_ptr_req *dreq, union nilfs_bmap_ptr_req *nreq, struct buffer_head **bhp, struct nilfs_bmap_stats *stats) argument
1796 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr, const __u64 *keys, const __u64 *ptrs, int n, union nilfs_bmap_ptr_req *dreq, union nilfs_bmap_ptr_req *nreq, struct buffer_head *bh) argument
1868 nilfs_btree_convert_and_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr, const __u64 *keys, const __u64 *ptrs, int n) argument
1900 nilfs_btree_propagate_p(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct buffer_head *bh) argument
1912 nilfs_btree_prepare_update_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct inode *dat) argument
1947 nilfs_btree_commit_update_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct inode *dat) argument
1971 nilfs_btree_abort_update_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct inode *dat) argument
1983 nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int minlevel, int *maxlevelp, struct inode *dat) argument
2018 nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int minlevel, int maxlevel, struct buffer_head *bh, struct inode *dat) argument
2033 nilfs_btree_propagate_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct buffer_head *bh) argument
2068 nilfs_btree_propagate(struct nilfs_bmap *btree, struct buffer_head *bh) argument
2111 nilfs_btree_propagate_gc(struct nilfs_bmap *btree, struct buffer_head *bh) argument
2117 nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree, struct list_head *lists, struct buffer_head *bh) argument
2152 nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree, struct list_head *listp) argument
2190 nilfs_btree_assign_p(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) argument
2232 nilfs_btree_assign_v(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) argument
2263 nilfs_btree_assign(struct nilfs_bmap *btree, struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) argument
2302 nilfs_btree_assign_gc(struct nilfs_bmap *btree, struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) argument
2329 nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) argument
[all...]
H A DMakefile4 btnode.o bmap.o btree.o direct.o dat.o recovery.o \
/linux-master/drivers/md/bcache/
H A Dbtree.h8 * At a high level, bcache's btree is relatively standard b+ tree. All keys and
12 * In the interior nodes, a struct bkey always points to a child btree node, and
15 * of the child node - this would allow us to have variable sized btree nodes
16 * (handy for keeping the depth of the btree 1 by expanding just the root).
21 * overlapping extents - when we read in a btree node from disk, the first thing
25 * struct btree_op is a central interface to the btree code. It's used for
31 * Btree nodes are cached in memory; traversing the btree might require reading
32 * in btree nodes which is handled mostly transparently.
34 * bch_btree_node_get() looks up a btree node in the cache and reads it in from
36 * btree() macr
117 struct btree { struct
[all...]
H A Ddebug.h11 void bch_btree_verify(struct btree *b);
20 static inline void bch_btree_verify(struct btree *b) {}
H A DMakefile5 bcache-y := alloc.o bset.o btree.o debug.o extents.o io.o\
/linux-master/fs/befs/
H A DMakefile8 befs-objs := datastream.o btree.o super.o inode.o debug.o io.o linuxvfs.o
/linux-master/fs/hfs/
H A DMakefile8 hfs-objs := bitmap.o bfind.o bnode.o brec.o btree.o \
/linux-master/fs/hfsplus/
H A DMakefile8 hfsplus-objs := super.o options.o inode.o ioctl.o extents.o catalog.o dir.o btree.o \
/linux-master/include/linux/
H A Dbtree.h29 * struct btree_head - btree head
41 /* btree geometry */
59 * btree_init_mempool - initialise a btree with given mempool
61 * @head: the btree head to initialise
70 * btree_init - initialise a btree
72 * @head: the btree head to initialise
75 * btree needs. Returns zero or a negative error code
84 * @head: the btree head to destroy
92 * btree_lookup - look up a key in the btree
94 * @head: the btree t
[all...]

Completed in 240 milliseconds

1234