Home
last modified time | relevance | path

Searched refs:tree (Results 1 – 25 of 72) sorted by relevance

123

/fs/hfs/
Dbtree.c21 struct hfs_btree *tree; in hfs_btree_open() local
27 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
28 if (!tree) in hfs_btree_open()
31 mutex_init(&tree->tree_lock); in hfs_btree_open()
32 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
34 tree->sb = sb; in hfs_btree_open()
35 tree->cnid = id; in hfs_btree_open()
36 tree->keycmp = keycmp; in hfs_btree_open()
38 tree->inode = iget_locked(sb, id); in hfs_btree_open()
39 if (!tree->inode) in hfs_btree_open()
[all …]
Dbrec.c16 static int hfs_btree_inc_height(struct hfs_btree *tree);
24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
45 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
50 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
56 if (retval > node->tree->max_key_len + 1) { in hfs_brec_keylen()
[all …]
Dbnode.c31 if (pagenum >= node->tree->pages_per_bnode) in hfs_bnode_read()
63 struct hfs_btree *tree; in hfs_bnode_read_key() local
66 tree = node->tree; in hfs_bnode_read_key()
68 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
71 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
161 off = node->tree->node_size - 2; in hfs_bnode_dump()
168 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
171 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
188 struct hfs_btree *tree; in hfs_bnode_unlink() local
192 tree = node->tree; in hfs_bnode_unlink()
[all …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 fd->tree = tree; in hfs_find_init()
21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
27 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
28 switch (tree->cnid) { in hfs_find_init()
30 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); in hfs_find_init()
33 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); in hfs_find_init()
36 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); in hfs_find_init()
49 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
[all …]
Dinode.c77 struct hfs_btree *tree; in hfs_releasepage() local
84 tree = HFS_SB(sb)->ext_tree; in hfs_releasepage()
87 tree = HFS_SB(sb)->cat_tree; in hfs_releasepage()
94 if (!tree) in hfs_releasepage()
97 if (tree->node_size >= PAGE_SIZE) { in hfs_releasepage()
98 nidx = page->index >> (tree->node_size_shift - PAGE_SHIFT); in hfs_releasepage()
99 spin_lock(&tree->hash_lock); in hfs_releasepage()
100 node = hfs_bnode_findhash(tree, nidx); in hfs_releasepage()
109 spin_unlock(&tree->hash_lock); in hfs_releasepage()
111 nidx = page->index << (PAGE_SHIFT - tree->node_size_shift); in hfs_releasepage()
[all …]
/fs/hfsplus/
Dbtree.c135 struct hfs_btree *tree; in hfs_btree_open() local
142 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
143 if (!tree) in hfs_btree_open()
146 mutex_init(&tree->tree_lock); in hfs_btree_open()
147 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
148 tree->sb = sb; in hfs_btree_open()
149 tree->cnid = id; in hfs_btree_open()
153 tree->inode = inode; in hfs_btree_open()
155 if (!HFSPLUS_I(tree->inode)->first_blocks) { in hfs_btree_open()
160 mapping = tree->inode->i_mapping; in hfs_btree_open()
[all …]
Dbrec.c25 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
40 !(node->tree->attributes & HFS_TREE_VARIDXKEYS) && in hfs_brec_keylen()
41 (node->tree->cnid != HFSPLUS_ATTR_CNID)) { in hfs_brec_keylen()
42 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
45 node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (recoff > node->tree->node_size - 2) { in hfs_brec_keylen()
54 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
65 struct hfs_btree *tree; in hfs_brec_insert() local
72 tree = fd->tree; in hfs_brec_insert()
74 if (!tree->root) in hfs_brec_insert()
[all …]
Dbnode.c61 struct hfs_btree *tree; in hfs_bnode_read_key() local
64 tree = node->tree; in hfs_bnode_read_key()
66 tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_read_key()
67 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
70 key_len = tree->max_key_len + 2; in hfs_bnode_read_key()
310 off = node->tree->node_size - 2; in hfs_bnode_dump()
317 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
318 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
321 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
337 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 fd->tree = tree; in hfs_find_init()
21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
27 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
28 switch (tree->cnid) { in hfs_find_init()
30 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); in hfs_find_init()
33 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); in hfs_find_init()
36 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); in hfs_find_init()
49 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
[all …]
Dinode.c71 struct hfs_btree *tree; in hfsplus_releasepage() local
78 tree = HFSPLUS_SB(sb)->ext_tree; in hfsplus_releasepage()
81 tree = HFSPLUS_SB(sb)->cat_tree; in hfsplus_releasepage()
84 tree = HFSPLUS_SB(sb)->attr_tree; in hfsplus_releasepage()
90 if (!tree) in hfsplus_releasepage()
92 if (tree->node_size >= PAGE_SIZE) { in hfsplus_releasepage()
94 (tree->node_size_shift - PAGE_SHIFT); in hfsplus_releasepage()
95 spin_lock(&tree->hash_lock); in hfsplus_releasepage()
96 node = hfs_bnode_findhash(tree, nidx); in hfsplus_releasepage()
105 spin_unlock(&tree->hash_lock); in hfsplus_releasepage()
[all …]
Dhfsplus_fs.h104 struct hfs_btree *tree; member
290 struct hfs_btree *tree; member
388 void hfs_btree_close(struct hfs_btree *tree);
389 int hfs_btree_write(struct hfs_btree *tree);
390 int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes);
391 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree);
407 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid);
409 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num);
411 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num);
414 bool hfs_bnode_need_zeroout(struct hfs_btree *tree);
[all …]
Dextents.c104 res = hfs_bmap_reserve(fd->tree, fd->tree->depth + 1); in __hfsplus_ext_write_extent()
429 mutex_unlock(&fd.tree->tree_lock); in hfsplus_free_fork()
433 mutex_lock(&fd.tree->tree_lock); in hfsplus_free_fork()
590 mutex_unlock(&fd.tree->tree_lock); in hfsplus_file_truncate()
595 mutex_lock(&fd.tree->tree_lock); in hfsplus_file_truncate()
605 mutex_unlock(&fd.tree->tree_lock); in hfsplus_file_truncate()
609 mutex_lock(&fd.tree->tree_lock); in hfsplus_file_truncate()
/fs/btrfs/
Dextent-io-tree.h103 struct extent_io_tree *tree, unsigned int owner,
105 void extent_io_tree_release(struct extent_io_tree *tree);
107 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
110 static inline int lock_extent(struct extent_io_tree *tree, u64 start, u64 end) in lock_extent() argument
112 return lock_extent_bits(tree, start, end, NULL); in lock_extent()
115 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end);
120 u64 count_range_bits(struct extent_io_tree *tree,
125 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
127 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
129 int clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
[all …]
Dordered-data.c124 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree, in tree_search() argument
127 struct rb_root *root = &tree->tree; in tree_search()
132 if (tree->last) { in tree_search()
133 entry = rb_entry(tree->last, struct btrfs_ordered_extent, in tree_search()
136 return tree->last; in tree_search()
142 tree->last = ret; in tree_search()
159 struct btrfs_ordered_inode_tree *tree = &inode->ordered_tree; in __btrfs_add_ordered_extent() local
217 spin_lock_irq(&tree->lock); in __btrfs_add_ordered_extent()
218 node = tree_insert(&tree->tree, file_offset, in __btrfs_add_ordered_extent()
224 spin_unlock_irq(&tree->lock); in __btrfs_add_ordered_extent()
[all …]
Dextent_map.c36 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
38 tree->map = RB_ROOT_CACHED; in extent_map_tree_init()
39 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
40 rwlock_init(&tree->lock); in extent_map_tree_init()
235 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) in try_merge_map() argument
265 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
277 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
296 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, in unpin_extent_cache() argument
303 write_lock(&tree->lock); in unpin_extent_cache()
304 em = lookup_extent_mapping(tree, start, len); in unpin_extent_cache()
[all …]
Dextent_io.c108 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
109 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
111 struct extent_io_tree *tree, u64 start, u64 end) in __btrfs_debug_check_extent_io_range() argument
113 struct inode *inode = tree->private_data; in __btrfs_debug_check_extent_io_range()
172 struct extent_io_tree *tree = bio->bi_private; in submit_one_bio() local
178 if (is_data_inode(tree->private_data)) in submit_one_bio()
179 ret = btrfs_submit_data_bio(tree->private_data, bio, mirror_num, in submit_one_bio()
182 ret = btrfs_submit_metadata_bio(tree->private_data, bio, in submit_one_bio()
289 struct extent_io_tree *tree, unsigned int owner, in extent_io_tree_init() argument
292 tree->fs_info = fs_info; in extent_io_tree_init()
[all …]
DMakefile23 btrfs-y += super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.o \
25 transaction.o inode.o file.o tree-defrag.o \
28 export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
31 uuid-tree.o props.o free-space-tree.o tree-checker.o space-info.o \
33 subpage.o tree-mod-log.o
44 tests/free-space-tree-tests.o tests/extent-map-tests.o
Dextent_map.h77 void extent_map_tree_init(struct extent_map_tree *tree);
78 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
80 int add_extent_mapping(struct extent_map_tree *tree,
82 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em);
83 void replace_extent_mapping(struct extent_map_tree *tree,
92 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, u64 gen);
93 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em);
94 struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
/fs/unicode/
Dmkutf8data.c189 struct tree;
190 static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *,
192 static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *);
345 struct tree { struct
350 struct tree *next; argument
355 int *(*leaf_index)(struct tree *, void *); argument
380 static void *lookup(struct tree *tree, const char *key) in lookup() argument
385 node = tree->root; in lookup()
417 static void tree_walk(struct tree *tree) in tree_walk() argument
428 printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root); in tree_walk()
[all …]
/fs/ocfs2/
Duptodate.c157 unsigned int tree, to_purge, purged; in ocfs2_metadata_cache_purge() local
163 tree = !(ci->ci_flags & OCFS2_CACHE_FL_INLINE); in ocfs2_metadata_cache_purge()
168 to_purge, tree); in ocfs2_metadata_cache_purge()
173 if (tree) in ocfs2_metadata_cache_purge()
183 if (tree && purged != to_purge) in ocfs2_metadata_cache_purge()
350 struct ocfs2_meta_cache_item **tree) in ocfs2_expand_cache() argument
365 tree[i]->c_block = ci->ci_cache.ci_array[i]; in ocfs2_expand_cache()
373 __ocfs2_insert_cache_tree(ci, tree[i]); in ocfs2_expand_cache()
374 tree[i] = NULL; in ocfs2_expand_cache()
390 struct ocfs2_meta_cache_item *tree[OCFS2_CACHE_INFO_MAX_ARRAY] = in __ocfs2_set_buffer_uptodate() local
[all …]
Drefcounttree.c197 struct ocfs2_refcount_tree *tree = NULL; in ocfs2_find_refcount_tree() local
200 tree = rb_entry(n, struct ocfs2_refcount_tree, rf_node); in ocfs2_find_refcount_tree()
202 if (blkno < tree->rf_blkno) in ocfs2_find_refcount_tree()
204 else if (blkno > tree->rf_blkno) in ocfs2_find_refcount_tree()
207 return tree; in ocfs2_find_refcount_tree()
244 static void ocfs2_free_refcount_tree(struct ocfs2_refcount_tree *tree) in ocfs2_free_refcount_tree() argument
246 ocfs2_metadata_cache_exit(&tree->rf_ci); in ocfs2_free_refcount_tree()
247 ocfs2_simple_drop_lockres(OCFS2_SB(tree->rf_sb), &tree->rf_lockres); in ocfs2_free_refcount_tree()
248 ocfs2_lock_res_free(&tree->rf_lockres); in ocfs2_free_refcount_tree()
249 kfree(tree); in ocfs2_free_refcount_tree()
[all …]
/fs/ext4/
Dextents_status.c174 void ext4_es_init_tree(struct ext4_es_tree *tree) in ext4_es_init_tree() argument
176 tree->root = RB_ROOT; in ext4_es_init_tree()
177 tree->cache_es = NULL; in ext4_es_init_tree()
183 struct ext4_es_tree *tree; in ext4_es_print_tree() local
187 tree = &EXT4_I(inode)->i_es_tree; in ext4_es_print_tree()
188 node = rb_first(&tree->root); in ext4_es_print_tree()
264 struct ext4_es_tree *tree = NULL; in __es_find_extent_range() local
271 tree = &EXT4_I(inode)->i_es_tree; in __es_find_extent_range()
275 es1 = READ_ONCE(tree->cache_es); in __es_find_extent_range()
283 es1 = __es_tree_search(&tree->root, lblk); in __es_find_extent_range()
[all …]
/fs/btrfs/tests/
Dextent-io-tests.c435 struct extent_io_tree tree; in test_find_first_clear_extent_bit() local
441 extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL); in test_find_first_clear_extent_bit()
444 find_first_clear_extent_bit(&tree, 0, &start, &end, CHUNK_TRIMMED); in test_find_first_clear_extent_bit()
455 set_extent_bits(&tree, SZ_1M, SZ_4M - 1, in test_find_first_clear_extent_bit()
458 find_first_clear_extent_bit(&tree, SZ_512K, &start, &end, in test_find_first_clear_extent_bit()
468 set_extent_bits(&tree, SZ_32M, SZ_64M - 1, in test_find_first_clear_extent_bit()
474 find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end, in test_find_first_clear_extent_bit()
487 find_first_clear_extent_bit(&tree, SZ_2M, &start, &end, in test_find_first_clear_extent_bit()
500 set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED); in test_find_first_clear_extent_bit()
501 find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end, in test_find_first_clear_extent_bit()
[all …]
/fs/dlm/
Ddebug_fs.c423 struct rb_root *tree; in table_seq_start() local
452 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; in table_seq_start()
455 if (!RB_EMPTY_ROOT(tree)) { in table_seq_start()
456 for (node = rb_first(tree); node; node = rb_next(node)) { in table_seq_start()
484 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; in table_seq_start()
487 if (!RB_EMPTY_ROOT(tree)) { in table_seq_start()
488 node = rb_first(tree); in table_seq_start()
505 struct rb_root *tree; in table_seq_next() local
550 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; in table_seq_next()
553 if (!RB_EMPTY_ROOT(tree)) { in table_seq_next()
[all …]
/fs/fuse/
Ddax.c68 struct rb_root_cached tree; member
223 interval_tree_insert(&dmap->itn, &fi->dax->tree); in fuse_setup_one_mapping()
322 node = interval_tree_iter_first(&fi->dax->tree, start_idx, in inode_reclaim_dmap_range()
329 interval_tree_remove(&dmap->itn, &fi->dax->tree); in inode_reclaim_dmap_range()
477 node = interval_tree_iter_first(&fi->dax->tree, start_idx, start_idx); in fuse_setup_new_dax_mapping()
514 node = interval_tree_iter_first(&fi->dax->tree, idx, idx); in fuse_upgrade_dax_mapping()
589 node = interval_tree_iter_first(&fi->dax->tree, start_idx, start_idx); in fuse_iomap_begin()
909 interval_tree_remove(&dmap->itn, &fi->dax->tree); in reclaim_one_dmap_locked()
933 for (node = interval_tree_iter_first(&fi->dax->tree, 0, -1); node; in inode_lookup_first_dmap()
988 node = interval_tree_iter_first(&fi->dax->tree, start_idx, start_idx); in inode_inline_reclaim_one_dmap()
[all …]

123