Home
last modified time | relevance | path

Searched refs:btree (Results 1 – 25 of 38) sorted by relevance

12

/linux/fs/hpfs/
H A Danode.c15 struct bplus_header *btree, unsigned sec, in hpfs_bplus_lookup() argument
24 if (bp_internal(btree)) { in hpfs_bplus_lookup()
25 for (i = 0; i < btree->n_used_nodes; i++) in hpfs_bplus_lookup()
26 if (le32_to_cpu(btree->u.internal[i].file_secno) > sec) { in hpfs_bplus_lookup()
27 a = le32_to_cpu(btree->u.internal[i].down); in hpfs_bplus_lookup()
30 btree = GET_BTREE_PTR(&anode->btree); in hpfs_bplus_lookup()
37 for (i = 0; i < btree->n_used_nodes; i++) in hpfs_bplus_lookup()
38 if (le32_to_cpu(btree->u.external[i].file_secno) <= sec && in hpfs_bplus_lookup()
39 … le32_to_cpu(btree->u.external[i].file_secno) + le32_to_cpu(btree->u.external[i].length) > sec) { in hpfs_bplus_lookup()
40 …a = le32_to_cpu(btree->u.external[i].disk_secno) + sec - le32_to_cpu(btree->u.external[i].file_sec… in hpfs_bplus_lookup()
[all …]
H A Dmap.c180 if ((unsigned)fnode->btree.n_used_nodes + (unsigned)fnode->btree.n_free_nodes != in hpfs_map_fnode()
181 (bp_internal(GET_BTREE_PTR(&fnode->btree)) ? 12 : 8)) { in hpfs_map_fnode()
187 if (le16_to_cpu(fnode->btree.first_free) != in hpfs_map_fnode()
188 8 + fnode->btree.n_used_nodes * (bp_internal(GET_BTREE_PTR(&fnode->btree)) ? 8 : 12)) { in hpfs_map_fnode()
235 if ((unsigned)anode->btree.n_used_nodes + (unsigned)anode->btree.n_free_nodes != in hpfs_map_anode()
236 (bp_internal(GET_BTREE_PTR(&anode->btree)) ? 60 : 40)) { in hpfs_map_anode()
240 if (le16_to_cpu(anode->btree.first_free) != in hpfs_map_anode()
241 8 + anode->btree.n_used_nodes * (bp_internal(GET_BTREE_PTR(&anode->btree)) ? 8 : 12)) { in hpfs_map_anode()
H A Dalloc.c466 f->btree.n_free_nodes = 8; in hpfs_alloc_fnode()
467 f->btree.first_free = cpu_to_le16(8); in hpfs_alloc_fnode()
483 a->btree.n_free_nodes = 40; in hpfs_alloc_anode()
484 a->btree.n_used_nodes = 0; in hpfs_alloc_anode()
485 a->btree.first_free = cpu_to_le16(8); in hpfs_alloc_anode()
H A Dhpfs.h474 struct bplus_header_fixed btree; /* b+ tree, 8 extents or 12 subtrees */ member
516 struct bplus_header_fixed btree; /* b+tree, 40 extents or 60 subtrees */ member
H A Dnamei.c86 fnode->btree.n_free_nodes = 7; in hpfs_mkdir()
87 fnode->btree.n_used_nodes = 1; in hpfs_mkdir()
88 fnode->btree.first_free = cpu_to_le16(0x14); in hpfs_mkdir()
/linux/fs/nilfs2/
H A Dbtree.c17 #include "btree.h"
58 static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree, in nilfs_btree_get_new_block() argument
61 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode; in nilfs_btree_get_new_block()
112 static int nilfs_btree_node_size(const struct nilfs_bmap *btree) in nilfs_btree_node_size() argument
114 return i_blocksize(btree->b_inode); in nilfs_btree_node_size()
117 static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree) in nilfs_btree_nchildren_per_block() argument
119 return btree->b_nchildren_per_block; in nilfs_btree_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
411 nilfs_btree_get_root(const struct nilfs_bmap * btree) nilfs_btree_get_root() argument
428 nilfs_btree_height(const struct nilfs_bmap * btree) nilfs_btree_height() argument
434 nilfs_btree_get_node(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path,int level,int * ncmaxp) nilfs_btree_get_node() argument
450 nilfs_btree_bad_node(const struct nilfs_bmap * btree,struct nilfs_btree_node * node,int level) nilfs_btree_bad_node() argument
471 __nilfs_btree_get_block(const struct nilfs_bmap * btree,__u64 ptr,struct buffer_head ** bhp,const struct nilfs_btree_readahead_info * ra) __nilfs_btree_get_block() argument
541 nilfs_btree_get_block(const struct nilfs_bmap * btree,__u64 ptr,struct buffer_head ** bhp) nilfs_btree_get_block() argument
547 nilfs_btree_do_lookup(const struct nilfs_bmap * btree,struct nilfs_btree_path * path,__u64 key,__u64 * ptrp,int minlevel,int readahead) nilfs_btree_do_lookup() argument
609 nilfs_btree_do_lookup_last(const struct nilfs_bmap * btree,struct nilfs_btree_path * path,__u64 * keyp,__u64 * ptrp) nilfs_btree_do_lookup_last() argument
657 nilfs_btree_get_next_key(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path,int minlevel,__u64 * nextkey) nilfs_btree_get_next_key() argument
685 nilfs_btree_lookup(const struct nilfs_bmap * btree,__u64 key,int level,__u64 * ptrp) nilfs_btree_lookup() argument
702 nilfs_btree_lookup_contig(const struct nilfs_bmap * btree,__u64 key,__u64 * ptrp,unsigned int maxblocks) nilfs_btree_lookup_contig() argument
791 nilfs_btree_promote_key(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 key) nilfs_btree_promote_key() argument
813 nilfs_btree_do_insert(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_do_insert() argument
840 nilfs_btree_carry_left(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_carry_left() argument
886 nilfs_btree_carry_right(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_carry_right() argument
933 nilfs_btree_split(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_split() argument
983 nilfs_btree_grow(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_grow() argument
1012 nilfs_btree_find_near(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path) nilfs_btree_find_near() argument
1041 nilfs_btree_find_target_v(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path,__u64 key) nilfs_btree_find_target_v() 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) nilfs_btree_prepare_insert() argument
1210 nilfs_btree_commit_insert(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int maxlevel,__u64 key,__u64 ptr) nilfs_btree_commit_insert() argument
1234 nilfs_btree_insert(struct nilfs_bmap * btree,__u64 key,__u64 ptr) nilfs_btree_insert() argument
1263 nilfs_btree_do_delete(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_do_delete() argument
1288 nilfs_btree_borrow_left(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_borrow_left() argument
1320 nilfs_btree_borrow_right(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_borrow_right() argument
1353 nilfs_btree_concat_left(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_concat_left() argument
1379 nilfs_btree_concat_right(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_concat_right() argument
1404 nilfs_btree_shrink(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_shrink() argument
1428 nilfs_btree_nop(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp) nilfs_btree_nop() 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) nilfs_btree_prepare_delete() argument
1569 nilfs_btree_commit_delete(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int maxlevel,struct inode * dat) nilfs_btree_commit_delete() argument
1584 nilfs_btree_delete(struct nilfs_bmap * btree,__u64 key) nilfs_btree_delete() argument
1615 nilfs_btree_seek_key(const struct nilfs_bmap * btree,__u64 start,__u64 * keyp) nilfs_btree_seek_key() argument
1636 nilfs_btree_last_key(const struct nilfs_bmap * btree,__u64 * keyp) nilfs_btree_last_key() argument
1652 nilfs_btree_check_delete(struct nilfs_bmap * btree,__u64 key) nilfs_btree_check_delete() argument
1693 nilfs_btree_gather_data(struct nilfs_bmap * btree,__u64 * keys,__u64 * ptrs,int nitems) nilfs_btree_gather_data() argument
1742 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) nilfs_btree_prepare_convert_and_insert() argument
1799 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) nilfs_btree_commit_convert_and_insert() argument
1880 nilfs_btree_convert_and_insert(struct nilfs_bmap * btree,__u64 key,__u64 ptr,const __u64 * keys,const __u64 * ptrs,int n) nilfs_btree_convert_and_insert() argument
1912 nilfs_btree_propagate_p(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct buffer_head * bh) nilfs_btree_propagate_p() argument
1924 nilfs_btree_prepare_update_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct inode * dat) nilfs_btree_prepare_update_v() argument
1959 nilfs_btree_commit_update_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct inode * dat) nilfs_btree_commit_update_v() argument
1983 nilfs_btree_abort_update_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct inode * dat) nilfs_btree_abort_update_v() argument
1995 nilfs_btree_prepare_propagate_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int minlevel,int * maxlevelp,struct inode * dat) nilfs_btree_prepare_propagate_v() argument
2030 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) nilfs_btree_commit_propagate_v() argument
2045 nilfs_btree_propagate_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct buffer_head * bh) nilfs_btree_propagate_v() argument
2080 nilfs_btree_propagate(struct nilfs_bmap * btree,struct buffer_head * bh) nilfs_btree_propagate() argument
2125 nilfs_btree_propagate_gc(struct nilfs_bmap * btree,struct buffer_head * bh) nilfs_btree_propagate_gc() argument
2131 nilfs_btree_add_dirty_buffer(struct nilfs_bmap * btree,struct list_head * lists,struct buffer_head * bh) nilfs_btree_add_dirty_buffer() argument
2166 nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap * btree,struct list_head * listp) nilfs_btree_lookup_dirty_buffers() argument
2204 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) nilfs_btree_assign_p() argument
2246 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) nilfs_btree_assign_v() argument
2277 nilfs_btree_assign(struct nilfs_bmap * btree,struct buffer_head ** bh,sector_t blocknr,union nilfs_binfo * binfo) nilfs_btree_assign() argument
2316 nilfs_btree_assign_gc(struct nilfs_bmap * btree,struct buffer_head ** bh,sector_t blocknr,union nilfs_binfo * binfo) nilfs_btree_assign_gc() argument
2343 nilfs_btree_mark(struct nilfs_bmap * btree,__u64 key,int level) nilfs_btree_mark() argument
[all...]
H A DMakefile4 btnode.o bmap.o btree.o direct.o dat.o recovery.o \
/linux/drivers/md/bcache/
H A Dbtree.h117 struct btree { struct
127 struct btree *parent; argument
152 static inline bool btree_node_ ## flag(struct btree *b) \ argument
155 static inline void set_btree_node_ ## flag(struct btree *b) \
170 static inline struct btree_write *btree_current_write(struct btree *b) in btree_current_write()
175 static inline struct btree_write *btree_prev_write(struct btree *b) in btree_prev_write()
180 static inline struct bset *btree_bset_first(struct btree *b) in btree_bset_first()
185 static inline struct bset *btree_bset_last(struct btree *b) in btree_bset_last()
190 static inline unsigned int bset_block_offset(struct btree *b, struct bset *i) in bset_block_offset()
248 static inline void rw_lock(bool w, struct btree *b, int level) in rw_lock()
[all …]
H A Dbtree.c107 static inline struct bset *write_block(struct btree *b) in write_block()
112 static void bch_btree_init_next(struct btree *b) in bch_btree_init_next()
139 static uint64_t btree_csum_set(struct btree *b, struct bset *i) in btree_csum_set()
148 void bch_btree_node_read_done(struct btree *b) in bch_btree_node_read_done()
243 static void bch_btree_node_read(struct btree *b) in bch_btree_node_read()
281 static void btree_complete_write(struct btree *b, struct btree_write *w) in btree_complete_write()
298 closure_type(b, struct btree, io); in CLOSURE_CALLBACK()
305 closure_type(b, struct btree, io); in CLOSURE_CALLBACK()
320 closure_type(b, struct btree, io); in CLOSURE_CALLBACK()
329 struct btree *b = container_of(cl, struct btree, io); in btree_node_write_endio()
[all …]
H A Dextents.c128 struct btree *b = container_of(keys, struct btree, keys); in bch_bkey_dump()
168 struct btree *b = container_of(bk, struct btree, keys); in bch_btree_ptr_invalid()
173 static bool btree_ptr_bad_expensive(struct btree *b, const struct bkey *k) in btree_ptr_bad_expensive()
207 struct btree *b = container_of(bk, struct btree, keys); in bch_btree_ptr_bad()
232 struct btree *b = container_of(bk, struct btree, keys); in bch_btree_ptr_insert_fixup()
328 struct cache_set *c = container_of(b, struct btree, keys)->c; in bch_extent_insert_fixup()
502 struct btree *b = container_of(bk, struct btree, keys); in bch_extent_invalid()
507 static bool bch_extent_bad_expensive(struct btree *b, const struct bkey *k, in bch_extent_bad_expensive()
539 struct btree *b = container_of(bk, struct btree, keys); in bch_extent_bad()
585 struct btree *b = container_of(bk, struct btree, keys); in bch_extent_merge()
H A Ddebug.h11 void bch_btree_verify(struct btree *b);
20 static inline void bch_btree_verify(struct btree *b) {} in bch_btree_verify()
H A Dbcache.h223 struct btree;
280 int (*cache_miss)(struct btree *b, struct search *s,
671 struct btree *root;
674 struct btree *verify_data;
H A DMakefile5 bcache-y := alloc.o bset.o btree.o debug.o extents.o io.o\
H A Ddebug.c31 void bch_btree_verify(struct btree *b) in bch_btree_verify()
33 struct btree *v = b->c->verify_data; in bch_btree_verify()
H A DKconfig10 a btree for indexing and the layout is optimized for SSDs.
/linux/fs/xfs/libxfs/
H A Dxfs_da_btree.c154 to->btree = from3->__btree; in xfs_da3_node_hdr_from_disk()
162 to->btree = from->__btree; in xfs_da3_node_hdr_from_disk()
729 struct xfs_da_node_entry *btree; in xfs_da3_root_split() local
764 btree = icnodehdr.btree; in xfs_da3_root_split()
765 size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot); in xfs_da3_root_split()
803 btree = nodehdr.btree; in xfs_da3_root_split()
804 btree[0].hashval = cpu_to_be32(blk1->hashval); in xfs_da3_root_split()
805 btree[0].before = cpu_to_be32(blk1->blkno); in xfs_da3_root_split()
806 btree[1].hashval = cpu_to_be32(blk2->hashval); in xfs_da3_root_split()
807 btree[1].before = cpu_to_be32(blk2->blkno); in xfs_da3_root_split()
[all …]
H A Dxfs_da_btree.h159 struct xfs_da_node_entry *btree; member
/linux/Documentation/admin-guide/device-mapper/
H A Dpersistent-data.rst14 - Another btree-based caching target posted to dm-devel
72 dm-btree.[hc]
73 dm-btree-remove.c
74 dm-btree-spine.c
75 dm-btree-internal.h
77 Currently there is only one data structure, a hierarchical btree.
81 The btree is 'hierarchical' in that you can define it to be composed
83 thin-provisioning target uses a btree with two levels of nesting.
/linux/drivers/md/persistent-data/
H A DMakefile11 dm-btree.o \
12 dm-btree-remove.o \
13 dm-btree-spine.o
/linux/include/trace/events/
H A Dbcache.h64 TP_PROTO(struct btree *b),
258 TP_PROTO(struct btree *b),
263 TP_PROTO(struct btree *b),
283 TP_PROTO(struct btree *b),
293 TP_PROTO(struct btree *b),
333 TP_PROTO(struct btree *b, struct bkey *k, unsigned op, unsigned status),
366 TP_PROTO(struct btree *b, unsigned keys),
383 TP_PROTO(struct btree *b, unsigned keys),
388 TP_PROTO(struct btree *b, unsigned keys),
393 TP_PROTO(struct btree *b),
/linux/fs/befs/
H A DChangeLog27 * Did the string comparison really right this time (btree.c) [WD]
30 a pointer value. (btree.c) [WD]
38 keys within btree nodes, rather than the linear search we were using
39 before. (btree.c) [Sergey S. Kostyliov <rathamahata@php4.ru>]
56 (btree.c) [WD]
105 * Removed notion of btree handle from btree.c. It was unnecessary, as the
128 (btree.c) [WD]
133 seekleaf() in btree.c [WD]
148 (datastream.c, btree.c super.c inode.c) [WD]
253 * Fix bug with reading an empty directory. (btree.c and dir.c)
[all …]
H A DMakefile8 befs-objs := datastream.o btree.o super.o inode.o debug.o io.o linuxvfs.o
/linux/fs/xfs/scrub/
H A Ddabtree.c110 return hdr.btree + blk->index; in xchk_da_btree_node_entry()
337 struct xfs_da_node_entry *btree; in xchk_da_btree_block() local
441 btree = nodehdr.btree; in xchk_da_btree_block()
443 blk->hashval = be32_to_cpu(btree[*pmaxrecs - 1].hashval); in xchk_da_btree_block()
/linux/fs/xfs/
H A Dxfs_attr_inactive.c161 child_fsb = be32_to_cpu(ichdr.btree[0].before); in xfs_attr3_node_inactive()
238 child_fsb = be32_to_cpu(ichdr.btree[0].before); in xfs_attr3_node_inactive()
/linux/Documentation/filesystems/xfs/
H A Dxfs-self-describing-metadata.rst53 pointers in a btree end up with loops in them) are the key to understanding what
108 determine the scope of the corruption. For example, if we have a extent btree
118 freespace btree blocks are owned by an allocation group. Hence the size and
121 freespace btree block written to the wrong AG).
133 when the free space btree block that contains the block was last written
211 - short btree blocks have a 32 bit owner (ag number) and a 32 bit block

12